In This Topic
Graph theory is based on two corner stone abstractions  graph vertex (or simply vertex) and graph edge (or simply edge). A generic graph G = (V, E) consists of a finite set V of vertices and a finite multiset E of edges, that is, unordered pairs (u, v) of vertices. A directed graph (or digraph) is defined similarly to a graph, except that the elements of E, called directed edges, are ordered pairs of vertices.
Graph Parts and Graph Types
It is in many cases required to create a graph representation of a connected set of shapes. This gives you the needed abstraction level to be able to work with shapes as if they were simple graph vertices and edges.
In a graph representation of a diagram, each shape is represented by a single graph part. Each graph part is an instance of the NGraphPart class. Shapes whose GraphPart property is set to false are ignored (not represented by a graph part).
A graph part can either be a vertex or an edge, which is determined by it's Type property. 1D Shapes are always represented by edge parts, while 2D shapes are always represented by vertex parts.
Based on the type of graph, different classes derived from NGraphPart can be used to expose the specific operations, which can be executed with vertices and edges. All types of graphs derive from the base NGraphPartContainer class.
Currently implemented are two types of graphs:

Generic Graph  a generic graph (or simply graph) is represented by an instance of the
NGraph class (derived from the
NGraphPartContainer class). The vertices of a graph are instances of the
NGraphVertex class. The edges of a graph are instances of the
NGraphEdge class.

Tree Graph  a tree graph (or simply tree) is a connected directed acyclic graph, in which each vertex has only one incoming edge except the root vertex, for which there is no incoming edge. A tree is represented by an instance of
NTree class (derived from
NGraphPartContainer class). The vertices of a tree are instances of the
NTreeVertex class. The edges of a tree are instances of the
NTreeEdge class.
Creating a Generic Graph
A generic graph representing the connected structure of shapes can be constructed with the help of the NGraphBuilder and NShapeGraphAdapter classes. The following example creates a graph, which represents the connected component in which a shape resides:
C# 
Copy Code

NGraphBuilder graphBuilder = new NGraphBuilder(new NShapeGraphAdapter(), new NGraphPartFactory());
NObjectGraphPartMap map;
NGraph graph = graphBuilder.BuildGraph(shape, out map);

Visual Basic 
Copy Code

Dim graphBuilder As New NGraphBuilder(New NShapeGraphAdapter(), New NGraphPartFactory())
Dim map As NObjectGraphPartMap
Dim graph As NGraph = graphBuilder.BuildGraph(shape, map)

The output NObjectGraphPartMap instance is a bimap of (object  to/from  graph part), which means that you can easily get the graph part, which represents a shape and vice versa:
C# 
Copy Code

// get the graph part which represents a shape
NGraphPart part = map.GetPartFromObject(shape);
// get the shape which the part represents
NShape shape = (NShape)map.GetObjectFromPart(part);

Visual Basic 
Copy Code

' get the graph part which represents a shape
Dim part NGraphPart = map.GetPartFromObject(shape)
' get the shape which the part represents
Dim shape NShape = map.GetObjectFromPart(part)

Graph Navigation
The common graph navigation routines are exposed by the methods and properties of the NGraphVertex and NGraphEdge classes. For example:
C# 
Copy Code

// obtain the From vertex of a graph edge
NGraphVertex fromVertex = edge.FromVertex;
// obtain the To vertex of a graph edge
NGraphVertex toVertex = edge.ToVertex;
// get all edges connected to this vertex
NGraphEdgeList edges = vertex.Edges;
// get all neighbour vertices
NGraphVertexList neighbours = vertex.NeighbourVertices;

Visual Basic 
Copy Code

' obtain the From vertex of a graph edge
Dim fromVertex As NGraphVertex = edge.FromVertex
' obtain the To vertex of a graph edge
Dim toVertex As NGraphVertex = edge.ToVertex
' get all edges connected to this vertex
Dim edges As NGraphEdgeList = vertex.Edges
' get all neighbour vertices
Dim neighbours As NGraphVertexList = vertex.NeighbourVertices

Graph Checks
The
NGraph class exposes several properties, which can help you retrieve useful information about it. Currently these are:
IsTree,
IsConnected,
IsStronglyConnected,
IsCyclic etc.
Graph traversal
The NGraph class has builtin support for the following types of graph traversal methods:
 Depth First Traversal  in this type of graph traversal the algorithm first visits the start vertex and then recursively visits its destination or neighbour vertices (depending on whether you want to treat the graph as directed or undirected). It is implemented by the DepthFirstTraversal method.
 Breadth First Traversal  in this type of graph traversal the algorithm first visits the starting vertex, then all the vertices which can be reached in one step, then in two steps and so on. In breath first traversal you can also treat the graph as directed or undirected. It is implemented by the BreadthFirstTraversal method.
 Topological Order Traversal  in this type of graph traversal the algorithm visits the vertices in their topological order (sort). A topological sort is a list of the vertices of a directed graph in which all the successors of any given vertex appear in the sequence after that vertex. Topological order traversal is only applicable for directed graphs. It is implemented by the TopologicalOrderTraversal method.
All types of graph traversal methods use the visitor designpattern, which means that they accept an instance of the
NGraphPartVisitor class. When a vertex or an edge has been visited the algorithm will call the
Visit method of the visitor, passing as argument the part which has been visited.
Spanning trees
Any of the above mentioned graph traversal methods can be used to generate a spanning tree of the visited sub graph. You can however also use the following
NGraph methods to do this:
CreateDepthFirstSpanningTree,
CreateBreadthFirstSpanningTree and
CreateTopoligicalOrderTree.
Related Examples
Windows Forms: Document Object Model  Data Structures folder
See Also