graph theory reminder

Graph Theory Reminder

This is intended to refresh these notions for those who have not played with them recently. It is also intended to specify the standards names used in the project and the library itself. As much as possible, QuickGraph naming convention follows the standard of graph theory naming.

Directed Graph, Vertex, Edges

Let us start by redefining the basic concepts of directed graphs, vertices and edges. All these definitions are illustrated in the figure above.

• A directed graph G=(VxE) consists of a finite set V=V(G) of vertices and a finite multi-set E contained in VxV = {(u,v)| u,v in V} of edges that are ordered pair of vertices where u is called the source vertex and v the target vertex.

Tip:

• TVertex and TEdge are generic parameters in QuickGraph. The TEdge parameter has an additional constraint that it has to implement IEdge<TVertex>

public interface IEdge<TVertex>
{
    TVertex Source {get;}
    TVertex Target { get;}
}

public interface ISomeGraphAlgorithm<TVertex,TEdge>
    where Edge : IEdge<TVertex>
{…}

• If e=(u,v), then e is an out-edge of u and an in-edge of v. in-degree(v) denotes the number of incoming edges of v and out-degree(u), the number of outgoing edges of u. The degree of u is the sum of its in-degree and out-degree.
• If a graph allows multiple edges from the same u,v vertex pair, it is called a multi-graph. Such edges are called parallel edges.
• A path from u to v is a sequence of edges e1,e2,...,en such that e1 source is u, en target is v and each edge in the sequence is an out-edge of it’s predecessor.
• A cycle is a path where the beginning vertex is equal to the end vertex.
• A directed acyclic graph (DAG) is a directed graph with no cycle.
• A weighted directed graph G:(VxExW) is a directed graph with an additional relation that associate each edge to a weight: e -> w(e) (for example, the distance).
• An adjacency graph is a data structure to represent a directed graph where the out-edges of any vertex can be accessed in amortized constant time.
• A bidirectional graph is a data structure to represent directed graph where both the out-edges and the in-edges of any vertex can be accessed in amortized constant time.
• QuickGraph also provides data structures for UndirectedGraph.

tip:

The adjacency graph is implemented as a dictionary of Vertex to a collection of out-edges. When using a bidirectional graph, two dictionaries (one for in-edges, one for out-edges) have to be used, which doubles the required memory. Such data structures are most efficient for sparse graphs.