Table of Contents
- Introduction
- Basic Usage
- Advanced Usage
- Conclusion
- 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. :
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:
Node newNode = m_fdgGraph.CreateNode("some node label");
You can also add new node with NodeData by modifying node's label and/or mass:
NodeData data = new NodeData();
data.label = "some node label";
data.mass = 3.0f;
Node newNode = m_fdgGraph.CreateNode(data);
To add a node to the graph by manually creating node and node data
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:
List<string> nodeNames= new List<string>();
...
m_fdgGraph.CreateNodes(nodeNames);
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:
Node node = m_fdgGraph.GetNode("some node label");
How do I remove/detach a node?
To remove a node from the graph:
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):
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:
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:
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
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:
List<Pair<string,string>> edges= new List<Pair<string,string>>();
...
m_fdgGraph.CreateEdges(edges);
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:
Edge edge = m_fdgGraph.GetEdge("node1-node2");
You can also get the list of edges connected to a node as below:
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:
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:
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:
float stiffness = 81.76f;
float repulsion = 40000.0f;
float damping = 0.5f;
ForceDirected2D m_fdgPhysics = new ForceDirected2D(m_fdgGraph
stiffness,
repulsion,
damping
);
ForceDirected3D m_fdgPhysics = new ForceDirected3D(m_fdgGraph
stiffness,
repulsion,
damping
);
How do I change the variables for physics calculation for force-directed graph?
To change the stiffness of the spring (edge):
m_fdgPhysics.Stiffness = 90.55f;
To change the repulsion rate of the node:
m_fdgPhysics.Repulsion = 50000.0f;
To change the damping:
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):
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:
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
class Renderer: AbstractRenderer
{
public Renderer(IForceDirected iForceDirected): base(iForceDirected)
{
}
public override void Clear()
{
}
protected override void drawEdge(Edge iEdge, AbstractVector iPosition1, AbstractVector iPosition2)
{
}
protected override void drawNode(Node iNode, AbstractVector iPosition)
{
}
};
Then create an instance of your Renderer with ForceDirected2D/3D instance as a parameter:
Renderer m_fdgRenderer = new Renderer(m_fdgPhysics);
Finally to draw your Graph with the renderer you created above, you simply call Draw:
float timeStep = 0.05f;
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:
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:
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:
IGraphEventListener listener = new MyGraphEventListner();
m_fdgGraph.AddGraphListener(listner);
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
