15,843,727 members
Articles / General Programming / Algorithms

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

Rate me:
26 Oct 2014MIT5 min read 37.1K   1.6K   19   2
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#
`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)
{
}

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

Written By
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[^]