14,978,482 members
Articles / General Programming / Algorithms
Article
Posted 26 Oct 2014

30.3K views
18 bookmarked

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

Rate me:
A 2D/3D force directed graph algorithm in C#

## 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);

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);

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#

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)
{
}

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);

### 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#.

## History

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

## Share

 Software Developer 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[^]