Nevron .NET Vision Documentation
Graphs

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:

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)
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 built-in support for the following types of graph traversal methods:

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 
See Also

 

 


©2017. Nevron Software LLC.

Send Feedback