QuickGraph.NET Cheatsheet

QuickGraph.NET Cheatsheet.md

Using QuickGraph

Setting up your project

• Add a reference to QuickGraph.dll to your project. QuickGraph provides a version backward compatible with .Net 2.0 or a .Net 3.5 version. The only difference lies in the support for extension methods.
• Most data structures are defined under the QuickGraph namespace, algorithms are under the QuickGraph.Algorithms namespace.

Identify the vertex and edge types

The vertex type can be any type as all QuickGraph data structure are generic. The edge type must implement the IEdge<TVertex> interface:

class FooVertex {} // custom vertex type
class FooEdge : Edge<FooVertex> []() // custom edge type
class FooGraph : AdjacencyGraph<FooVertex, FooEdge> {} // custom graph type

---

Creating Graphs

Easy creation with extension methods

QuickGraph provides several extension methods in QuickGraph.GraphExtensions to create graph from list of edge or vertices. For example, from an ``IEnumerable<Edge>```:

using QuickGraph; // enables extension methods

var edges = new SEdge<int>[]() { new SEdge<int>(1,2), new SEdge<int>(0,1) };
var graph = edges.ToAdjacencyGraph<int, SEdge<int>>(edges);

Create a graph instance

Let us assume we need integer vertices and edges tagged with string. Int is the vertex type and we can use the TaggedEdge generic type for the edge type:

• TVertex type: int
• TEdge type using TaggedEdge<Vertex,Marker>: TaggedEdge<int, string>

var g = new AdjacencyGraph<int, TaggedEdge<int, string>>();

Wrapping a dictionary into a graph

You may have already a dictionary on hand that represents a graph, where the keys are the vertices and the value is a collection of out-edges (or adjacent edges). You can wrap this dictionary with QuickGraph without re-allocating new memory:

Dictionary<int, int[]()> dic = ...; // vertex -> target edges
var graph = dic.ToVertexAndEdgeListGraph(
    kv => Array.ConvertAll(kv.Value, v => new SEquitableEdge<int>(kv.Key, v))
    );

// without extension methods
var graph = GraphExtensions.ToVertexAndEdgeListGraph(
    dic,
    kv => Array.ConvertAll(kv.Value, v => new SEquitableEdge<int>(kv.Key, v))
    );

Adding vertices

This snippet creates two vertices and adds them to the graph.

int v1 = 1;
int v2 = 2;

g.AddVertex(v1);
g.AddVertex(v2);

Adding edges

The edges (v1,v2) and (v2,v1) are created and added to the graph.

var e1 = new TaggedEdge<int,string>(v1,v2,”hello”);

g.AddEdge(e1); 

Adding edges (and vertices)

You can also add an edge and implicitly add the vertices if they are missing

// v3, v4 are not added to the graph yet
var e2 = new TaggedEdge<int,string>(v3,v4,”hello”);

g.AddVerticesAndEdge(e2);

---

Walking Graphs

Iterate vertices

Use the Vertices property to get an enumerable collection of vertices:

foreach(var v in g.Vertices)
    Console.WriteLine(v);

Iterate edges

Use the Edges property get an enumerable collection of edges:

foreach(var e in g.Edges)
    Console.WriteLine(e);

Iterate out edges

The OutEdges method returns an enumerable collection of out-edges:

foreach(var v in g.Vertices)
    foreach(var e in g.OutEdges(v))
        Console.WriteLine(e);

Similarly, InEdges returns an enumerable collection of in-edges.

---

Mutating Graphs

Most data structures are mutable and support batched addition/removal of vertices/edges.

Removing vertices with a predicate

var g = new AjacencyGraph<string, Edge<string>>();
...
// remove any vertex starting with foo
int removed = g.RemoveVertexIf(v => v.StartsWith("foo"));
Console.WriteLine("{0} vertices removed", removed);

---

Edges

While a vertex could be any type with QuickGraph, the edge type must implement IEdge<TVertex> (and comply to it's contract). QuickGraph comes with various default implementations:

• classes
  • Edge<TVertex>, an vanilla implementation,
  • EquatableEdge<TVertex>, implements IEquatable<EquatableEdge<TVertex>>,
  • TaggedEdge<TVertex,TTag>, holds a tag,
  • TaggedEquatableEdge<TVertex,TTag>, equitable and holds a tag,
• structures
  • SEdge<TVertex>, an immutable edge,
  • SEquatableEdge<TVertex>, a struct that implements IEquatable<SEquatableEdge<TVertex>>,
  • STaggedEdge<TVertex, TTag>, holds a tag
  • STaggedEquatableEdge<TVertex,TTag>, equitable and holds a tag,

The struct based edge will provide better performance and should be used when you do not plan to use custom edges. Of course, you can always implement your own version IEdge<TVertex>. Tagged edges also implement ITagged<TTag>.

Undirected edges

In undirected graphs, the order of the source or target vertices should not matter. In order to improve efficiency, edges that implement the IUndirectedEdge<TVertex> interface must sort the vertices so that Source <= Target (with respect to the default Comparer). This provides some performance gains in various data structures and algorithms.

• classes
  • UndirectedEdge<TVertex>, an vanilla implementation,
  • TaggedUndirectedEdge<TVertex,TTag>, holds a tag,
• structures
  • SUndirectedEdge<TVertex>, an immutable edge,
  • SUndirectedTaggedEdge<TVertex, TTag>, holds a tag

---

Copied from https://github.com/YaccConstructor/QuickGraph/wiki