Diagram for .NET > User's Guide > Data Structures > 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.
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:
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 |
The NGraph class has built-in support for the following types of graph traversal methods: