Click here to Skip to main content
15,867,308 members
Articles / General Programming / Algorithms

EpForceDirectedGraph.cs- A 2D/3D force directed graph algorithm in C#

Rate me:
Please Sign up or sign in to vote.
5.00/5 (9 votes)
26 Oct 2014MIT5 min read 37.4K   1.6K   19   2
A 2D/3D force directed graph algorithm in C#

Image 1

Table of Contents

  1. Introduction 
  2. Basic Usage
  3. Advanced Usage
  4. Conclusion
  5. Reference

Introduction 

I was working on my game UI in C#, and I wanted an innovative algorithm for my game UI. While I was searching for a good algorithm (since I was not satisfied with regular button-based UI), I've found a great Javascript implementation of force directed graph by Denniss Hotson. And I came up with an idea, "Why not for C#?" So here it is! EpForceDirectedGraph.cs!

EpForceDirectedGraph.cs works very similar to Springy.

(If you are interested in more detail of the force directed graph algorithm and the original JavaScript implementation, please see Force-directed graph drawing from Wikipedia and Dennis Hotson 's implementation.)

Basic Usage  

Graph

The usage and the demo have been made very similar to Springy Online Demo for ease of usage.

You first need a Graph instance. :

C#
Graph m_fdgGraph = new Graph();   

This Graph instance will be used to operate your force-directed graph structure such as adding/removing new node, adding/removing edges, etc.

Node Operation

How do I add a node/nodes?

Simply to add new node with a name in the graph:

C#
Node newNode = m_fdgGraph.CreateNode("some node label");

You can also add new node with NodeData by modifying node's label and/or mass:

C#
NodeData data = new NodeData();
data.label = "some node label";
data.mass = 3.0f; // Optional
Node newNode = m_fdgGraph.CreateNode(data);

To add a node to the graph by manually creating node and node data

C#
NodeData data=new NodeData();
data.mass = 3.0f;
data.label = "some node label" 
Node newNode = new Node("Unique ID", data);
Node createdNode = m_fdgGraph.AddNode(newNode);

You may also bulk-add new nodes with list of string or NodeData:

C#
List<string> nodeNames= new List<string>();
...
m_fdgGraph.CreateNodes(nodeNames);
 
// OR

List<NodeData> nodeDatas =new List<NodeData>();
...
m_fdgGraph.CreateNodes(nodeDatas); 

After adding the nodes to the graph, you can easily get the node instance, you added, by its label:

C#
Node node = m_fdgGraph.GetNode("some node label");
How do I remove/detach a node?

To remove a node from the graph:

C#
Node node = m_fdgGraph.GetNode("some node label");
if(node != null)
   m_fdgGraph.RemoveNode(node);

To detach all the edges from a node (Note: The node will still exist in the graph):

C#
Node node = m_fdgGraph.GetNode("some node label");
if(node != null)
   m_fdgGraph.DetachNode(node);

Edge Operation

How do I add an edge/egdes?

After adding the nodes first, you can connect the two nodes by creating an edge:

C#
Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");

EdgeData data= new EdgeData();
data.label = "node1"+"-"+"node2";
data.length = 60.0f;
Edge newEdge = m_fdgGraph.CreateEdge(node1, node2, data);

You can also create new Edge by giving node's ID (which is unique id given on node creation) directly instead of node instances:

C#
Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");

EdgeData data= new EdgeData();
data.label = "node1"+"-"+"node2";
data.length = 60.0f;

Edge newEdge = m_fdgGraph.CreateEdge(node1.ID, node2.ID, data);

To add an edge to the graph by manually creating edge and edge data

C#
Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");

EdgeData data=new EdgeData();
data.label = "node1"+"-"+"node2";
data.length = 60.0f; 
Edge newEdge = new Edge("Unique ID", node1, node2, data);
Edge createdEdge = m_fdgGraph.AddEdge(newEdge);

You may also bulk-add new edges with the list of the pair of first node's Unique ID string, second node's Unique Id string, or the list of the first node's Unique ID string, second node's Unique Id string and EdgeData for the edge:

C#
// First string is first node's Unique ID and second string is second node's Unique ID
List<Pair<string,string>> edges= new List<Pair<string,string>>();
...
m_fdgGraph.CreateEdges(edges);
 
// OR

List<Triple<string,string,EdgeData>> edges =new List<Triple<string,string,EdgeData>>();
...
m_fdgGraph.CreateEdges(edges); 

After adding the edges to the graph, you can easily get the edge instance, you added, by its label:

C#
Edge edge = m_fdgGraph.GetEdge("node1-node2");

You can also get the list of edges connected to a node as below:

C#
Node node1 = m_fdgGraph.GetNode("node1");
List<Edge> edgesConnected = m_fdgGraph.GetEdges(node1);

Finally, you can get the list of edges connected between two nodes by:

C#
Node node1 = m_fdgGraph.GetNode("node1");
Node node2 = m_fdgGraph.GetNode("node2");
List<Edge> edgesConnected = m_fdgGraph.GetEdges(node1, node2);
How do I remove an edge?

To remove an edge from the graph:

C#
Edge edge = m_fdgGraph.GetEdge("node1-node2");
if(edge != null)
   m_fdgGraph.RemoveEdge(edge);

ForceDirected2D/ForceDirected3D

ForceDirected2D or ForceDirected3D is the calculation class of physics for force-directed graph. The instance of ForceDirected2D/3D will take in Graph (which is logical structure of force-directed graph), and will be inserted to the instance of the Renderer.

To create ForceDirected2D/3D to calculate the physics for your force-directed graph:

C#
float stiffness = 81.76f;
float repulsion = 40000.0f;
float damping   = 0.5f;

// 2D Force Directed
ForceDirected2D m_fdgPhysics = new ForceDirected2D(m_fdgGraph // instance of Graph
                                                   stiffness, // stiffness of the spring
                                                   repulsion, // node repulsion rate 
                                                   damping    // damping rate  
                                                   );
// OR

// 3D Force Directed
ForceDirected3D m_fdgPhysics = new ForceDirected3D(m_fdgGraph // instance of Graph
                                                   stiffness, // stiffness of the spring
                                                   repulsion, // node repulsion rate
                                                   damping    // damping rate 
                                                   );   
How do I change the variables for physics calculation for force-directed graph?

To change the stiffness of the spring (edge):

C#
m_fdgPhysics.Stiffness = 90.55f;

To change the repulsion rate of the node:

C#
m_fdgPhysics.Repulsion = 50000.0f;

To change the damping:

C#
m_fdgPhysics.Damping = 0.7f;

Finally you can also set the Threadshold to stop the physics iteration at certain point (depends on how you set the threadshold, it will affect the performance of the graph calculation):

C#
m_fdgPhysics.Threadshold = 0.1f;

This ForceDirected2D/3D does the most of the job on the background like figuring the positions of nodes and the edges , and this will be inserted to Renderer to calculate the graph to render.

Renderer

First you need to define your own Renderer which inherits AbstractRenderer:

C#
class Renderer: AbstractRenderer
{
   ...
};

You need to implement three methods to make your force-directed graph to render correctly.

  • Contructor [ base(IForceDirected) ]
    • You must pass the IForceDirected instance, created above, to AbstractRenderer constructor when you create your Renderer.
  • Clear [ void Clear() ]
    • Clear any previous drawing to draw new scene
    • This will be called within AbstractRenderer::Draw method.
  • drawEdge [ void drawEdge(Edge iEdge, AbstractVector iPosition1, AbstractVector iPosition2) ]
    • Draw the given edge according to the given positions
    • AbstractVector will be FDGVector2 if ForceDirected2D, and FDGVector3 if ForceDirected3D
  • drawNode [ void drawNode(Node iNode, AbstractVector iPosition) ]
    • Draw the given node according to the given position
    • AbstractVector will be FDGVector2 if ForceDirected2D, and FDGVector3 if ForceDirected3D
C#
class Renderer: AbstractRenderer
{
   public Renderer(IForceDirected iForceDirected): base(iForceDirected)
   {
      // Your initialization to draw
   }

   public override void Clear()
   {
      // Clear previous drawing if needed
      // will be called when AbstractRenderer:Draw is called
   }
   
   protected override void drawEdge(Edge iEdge, AbstractVector iPosition1, AbstractVector iPosition2)
   {
      // Draw the given edge according to given positions
   }

   protected override void drawNode(Node iNode, AbstractVector iPosition)
   {
      // Draw the given node according to given position
   }
};

Then create an instance of your Renderer with ForceDirected2D/3D instance as a parameter:

C#
Renderer m_fdgRenderer = new Renderer(m_fdgPhysics);   

Finally to draw your Graph with the renderer you created above, you simply call Draw:

C#
float timeStep = 0.05f; // The time passed from previous Draw call in second
m_fdgRenderer.Draw(timeStep);

Advanced Usage  

Extendibility

Expand NodeData

You can create your own class which inherits NodeData and expand it to hold more variables to use it later like on Draw and create the node with your version of NodeData:

C#
public class MyNodeData: NodeData
{
   public string subType{
      get;set; 
   }
   public MyNodeData(string iSubType):base()
   {
      subType= iSubType;
   }
}

...
MyNodeData data= new MyNodeData("Button");
data.label = "Play";
Node newNode = m_fdgGraph.CreateNode(data);

Expand EdgeData

Similar to the NodeData, you can also expand EdgeData by creating your own class which inherits EdgeData:

C#
public class MyEdgeData: EdgeData
{
   public string subType{
      get;set; 
   }
   public MyEdgeData(string iSubType):base()
   {
      subType= iSubType;
   }
}

...
MyEdgeData data= new MyEdgeData("Button");
data.label= "Play";
Edge newEdge = m_fdgGraph.CreateEdge(data);

Notify on graph structure change

You can register a listener class to get notified when the graph structure changed. The listener class must implements the IGraphEventListener interface's GraphChanged method. You can add the listener as below:

C#
IGraphEventListener listener = new MyGraphEventListner();
m_fdgGraph.AddGraphListener(listner); // After this point when graph structure changed, 
                                      //   listener.GraphChanged() method will be called

Conclusion  

Most of functionality and work of EpForceDirectedGraph.cs project was originally from Dennis Hotson's Springy, so all the hard work and contribution should go to Dennis Hotson. The reason I am presenting this is in a hope of being helpful to someone who might need this algorithm in C#.

Reference  

History

  • 10.27.2014: - Typo fixed
  • 10.26.2014: - Submitted the article 

License

This article, along with any associated source code and files, is licensed under The MIT License


Written By
Software Developer
United States United States
Woong Gyu La had been working as a software developer for over 8 years.
His personal interests are improving his personal projects,

EpLibrary (Visual C++ Utility Library)
https://github.com/juhgiyo/EpLibrary[^]

EpOraLibrary (Oracle OCI Wrapper Library for Visual C++)
https://github.com/juhgiyo/EpOraLibrary[^]

EpServerEngine (Visual C++ WinSock Server/Client Engine)
https://github.com/juhgiyo/EpServerEngine[^]

And other projects can be found at
https://github.com/juhgiyo?tab=repositories[^]

Finally, my other articles can be found at
http://www.codeproject.com/Articles/juhgiyo#articles[^]

You can contact me at juhgiyo@gmail.com[^]

Comments and Discussions

 
Questionplease how show label on node? Pin
Member 137054642-Jan-21 10:01
Member 137054642-Jan-21 10:01 
please .....how show label on node???
and on eadge?
please answer me...
GeneralMy vote of 5 Pin
Franc Morales19-Dec-16 15:51
Franc Morales19-Dec-16 15:51 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.