﻿ Graphs
Nevron .NET Vision
Diagram for .NET / User's Guide / Data Structures / Graphs

In This Topic
Graphs
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 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:

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

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 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.
All types of graph traversal methods use the visitor design-pattern, 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