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.

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:

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

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 bi-map of (object - to/from - graph part), which means that you can easily get the graph part, which represents a shape and vice versa:

// 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);

' 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)

The common graph navigation routines are exposed by the methods and properties of the NGraphVertex and NGraphEdge classes. For example:

// 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;

' 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

The NGraph class has built-in 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.