a delicious .NET graph library
 All Classes Namespaces Files Functions Variables Enumerations Enumerator Properties Pages


Graphs can be accessed in a read-only way through the IGraph interface. The IBuildableGraph and IDestroyableGraph interfaces provide write access to a graph.

The structs Node and Arc represent the nodes and arcs of a graph. Node.Invalid and Arc.Invalid are null-like constants, denoting "no node" and "no arc", respectively.

Though all graphs use the same type for representing Node and Arc objects, they are generally not interchangeable between graphs. Each graph has its own Node and Arc set. If you pass a Node obtained from a graph to a method of another graph, you will likely get an error. (Adaptors are an exception from this general rule.)

Most of the algorithms can be divided into two categories:

Creating graphs

A graph can have at most int.MaxValue nodes and int.MaxValue arcs.

To create your first graph, enter the following code:

CustomGraph g = new CustomGraph();
Node a = g.AddNode();
Node b = g.AddNode();
Node c = g.AddNode();
Arc ab = g.AddArc(a, b, Directedness.Directed);
Arc bc = g.AddArc(b, c, Directedness.Undirected);

The above code creates a graph on three nodes, consisting of a directed arc and an edge. As you can see, the CustomGraph class can be used to build a graph.

You can also use some "graph constants". These are predefined graphs which usually consume very little memory, due to their special nature. They include CompleteBipartiteGraph and CompleteGraph. Using them is more efficient than e.g. building a complete graph using CustomGraph.

Graphs can also be loaded and saved. See the IO.SimpleGraphFormat, IO.LemonGraphFormat and IO.GraphML.GraphMLFormat classes.

Processing graphs


var g = new CompleteGraph(100); // create a complete graph on 100 nodes
var cost = new Dictionary<Node, double>(); // create a cost function on the nodes
int i = 0;
foreach (Node node in g.Nodes()) cost[node] = i++; // assign some integral costs to the nodes
Func<Arc, double> arcCost =
(arc => cost[g.U(arc)] + cost[g.V(arc)]); // a cost of an arc will be the sum of the costs of the two nodes
foreach (Arc arc in g.Arcs())
Console.WriteLine("Cost of "+g.ArcToString(arc)+" is "+arcCost(arc));

Using adaptors

By using adaptors, you can perform slight modifications on graphs without actually altering the graph object. Adaptors are analogous to camera filters as they allow you to see an underlying object in a different way.

Two basic adaptor examples are Subgraph and Supergraph.

Example for Subgraph:

var g = new CompleteGraph(10); // create a complete graph on 10 nodes
var sg = new Subgraph(g); // create a subgraph of the complete graph
sg.Enable(g.GetNode(0), false); // disable a single node
Console.WriteLine("The subgraph contains "+sg.NodeCount()+" nodes and "+sg.ArcCount()+" arcs.");

Example for Supergraph:

var g = new CompleteGraph(20); // create a complete graph on 20 nodes
var sg = new Supergraph(g); // create a supergraph of the complete graph
var s = sg.AddNode(); // add a node
sg.AddArc(s, g.GetNode(3), Directedness.Directed); // add a directed arc
Console.WriteLine("The extended graph contains "+sg.NodeCount()+" nodes and "+sg.ArcCount()+" arcs.");

Generally speaking, Node and Arc objects are interchangeable between the underlying graph and the adaptor, as long as it "makes sense". For clarification, you should always read the description of the adaptor class you want to use. For example:

Thus, the code below is correct and will not produce an error:

CustomGraph g;
Subgraph sg = new Subgraph(g);
foreach (var arc in sg.Arcs()) // we are enumerating the arcs of the *subgraph*!
// we are now querying arc properties using the *original graph*!
Console.WriteLine("This arc goes from "+g.U(arc)+" to "+g.V(arc)+
", and is "+(g.IsEdge(arc) ? "" : "not ")+"an edge.");
Console.WriteLine("As text: "+g.ArcToString(arc));

Other adaptor types:

Modifying the underlying graph while using an adaptor is often illegal, depending on the adaptor type. You should always read the description of the adaptor carefully.


The following algorithms are available: