Class GraphBase<TNode, TLink>

Base graph class for the various incarnations in the graph analysis.

Inheritance

System.Object

GraphBase<TNode, TLink>

Graph<TNodeData, TLinkData>

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

Namespace: Telerik.Windows.Diagrams.Core

Assembly: Telerik.Windows.Diagrams.Core.dll

Syntax

public class GraphBase<TNode, TLink>
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()

Type Parameters

TNode

The data type of the node which should be an implementation of the INode<TNode, TLink> interface and have a parameterless constructor.

TLink

The data type of the edge which should be an implementation of the IEdge<TNode, TLink> interface and have a parameterless constructor.

Remarks

The graph is directed by default (
```
IsDirected =
true
```
)
The adjacency structure is not centralized but resides in the Outgoing and Incoming collection attached to the Nodes.

Constructors

GraphBase()

Initializes a new instance of the GraphBase<TNode, TLink> class.

Declaration

public GraphBase()

GraphBase(GraphBase<TNode, TLink>)

Initializes a new instance of the GraphBase<TNode, TLink> class.

Declaration

public GraphBase(GraphBase<TNode, TLink> graph)

Parameters

GraphBase<TNode, TLink> graph

The graph content to start with. Note that references will be added, not clones.

Properties

IsAcyclic

Gets whether the graph is acyclic.

Declaration

public bool IsAcyclic { get; }

Property Value

System.Boolean

true if this instance is acyclic; otherwise, false.

Remarks

If there are no cycles in a graph it's acyclic. A cycle means a closed path or loop.
See also the article; http://en.wikipedia.org/wiki/Directed_acyclic_graph .

IsConnected

Gets whether this graph is connected. See also this article; http://en.wikipedia.org/wiki/Connected_graph.

Declaration

public bool IsConnected { get; }

Property Value

System.Boolean

true if this instance is connected; otherwise, false.

Remarks

A graph is connected if every two vertices are connected by a path. A connected graph has only one component.

IsDirected

Gets whether this graph is directed.

Declaration

public bool IsDirected { get; set; }

Property Value

System.Boolean

IsHamiltonian

Gets whether the graph is hamiltonian.

Declaration

public bool IsHamiltonian { get; }

Property Value

System.Boolean

true if this instance is acyclic; otherwise, false.

Remarks

An Hamiltonian cycle is a cycle which contains all nodes of the graph. If there is at least one such cycle the graph is called Hamiltonian.
See also the article http://en.wikipedia.org/wiki/Hamiltonian_graph .

Links

Gets or sets the links of this graph.

Declaration

public IList<TLink> Links { get; protected set; }

Property Value

System.Collections.Generic.IList<TLink>

The links collection.

Nodes

Gets or sets the nodes of this graph.

Declaration

public IList<TNode> Nodes { get; protected set; }

Property Value

System.Collections.Generic.IList<TNode>

The nodes collection.

Methods

AddLink(TNode, TNode)

Adds a link to this graph.

Declaration

public TLink AddLink(TNode source, TNode sink)

Parameters

TNode source

The source of the link.

TNode sink

The sink of the link.

Returns

TLink

The added link.

AddLink(TLink)

Adds the given link to the graph. It will add the sink and source nodes to the Nodes collection if they are not yet part of it.

Declaration

public TLink AddLink(TLink link)

Parameters

TLink link

The link to add.

Returns

TLink

The added link.

AddNode(TNode)

Adds the given node to the graph.

Declaration

public void AddNode(TNode node)

Parameters

TNode node

The node to add.

AddNodes(TNode[])

Adds a series of nodes to the graph.

Declaration

public void AddNodes(params TNode[] nodes)

Parameters

TNode[] nodes

The nodes.

AreConnected(TNode, TNode, Boolean)

Returns whether the given nodes are connected in one direction or the other.

Declaration

public bool AreConnected(TNode node1, TNode node2, bool strict = false)

Parameters

TNode node1

A node.

TNode node2

Another node.

System.Boolean strict

If set to true the first node has to be the source of the link and the second the sink..

Returns

System.Boolean

true If there is a link connecting the given nodes with the first one as source and the second as sink, false if both options have to be considered.

Remarks

Because the structure allows multigraphs the connectedness means there is at least one link between the given nodes.

AreConnected(Int32, Int32, Boolean)

Returns whether the given nodes are connected in one direction or the other.

Declaration

public bool AreConnected(int nodeId1, int nodeId2, bool strict = false)

Parameters

System.Int32 nodeId1

The id of the first node.

System.Int32 nodeId2

The id of the second node.

System.Boolean strict

If set to true the first node has to be the source of the link and the second the sink..

Returns

System.Boolean

true If there is a link connecting the given nodes with the first one as source and the second as sink, false if both options have to be considered.

Remarks

Because the structure allows multigraphs the connectedness means there is at least one link between the given nodes.

AreInSameComponent(Int32, Int32)

Returns whether the two nodes with specified ide's are the in same component.

Declaration

public bool AreInSameComponent(int id1, int id2)

Parameters

System.Int32 id1

The id1.

System.Int32 id2

The id2.

Returns

System.Boolean

AssignIdentifiers()

Assigns to each link and node an identifier based on their collection listIndex.

Declaration

public void AssignIdentifiers()

Clone()

Clones this instance.

Declaration

public GraphBase<TNode, TLink> Clone()

Returns

GraphBase<TNode, TLink>

DijkstraShortestPath(Int32, Int32)

Returns the shortest path between two nodes using the Dijkstra algorithm.

Declaration

public GraphPath<TNode, TLink> DijkstraShortestPath(int sourceId, int targetId)

Parameters

System.Int32 sourceId

From id.

System.Int32 targetId

To id.

Returns

GraphPath<TNode, TLink>

EnsureUniqueIdentifiers()

Ensures that the graph nodes all have a unique identifier assigned.

Declaration

public void EnsureUniqueIdentifiers()

Remarks

If the nodes do have unique identifiers nothing will be altered.

FindEdge(Int32, Int32, Boolean)

Finds the edge with the specified identifiers.

Declaration

public TLink FindEdge(int nodeId1, int nodeId2, bool strict)

Parameters

System.Int32 nodeId1

The id of the source.

System.Int32 nodeId2

The id of the sink.

System.Boolean strict

If set to true the found link has to go from nodeId1 to nodeId2.

Returns

TLink

FindLongestPath()

Finds the longest path in this (directed acyclic) graph.

Declaration

public GraphPath<TNode, TLink> FindLongestPath()

Returns

GraphPath<TNode, TLink>

A list of identifiers corresponding to the path, or null if the graph has cycles.

FindNode(Int32)

Finds the node with the specified identifier.

Declaration

public TNode FindNode(int id)

Parameters

System.Int32 id

The id to look for.

Returns

TNode

FindTreeRoot()

Attempts to find a tree root by looking at the longest paths in the graph.

Declaration

public TNode FindTreeRoot()

Returns

TNode

A tree root or null is none was found.

Remarks

The algorithms looks for all shortest paths between all vertices, which means it will also function for disconnected graphs but will return the root of the tree with longest path.

GetBoundingRectangle<TNodeData, TLinkData>(Boolean)

Returns the bounding rectangle of this layout graph.

Declaration

public Rect GetBoundingRectangle<TNodeData, TLinkData>(bool includeLinks = false)
    where TNodeData : new()
    where TLinkData : new()

Parameters

System.Boolean includeLinks

The include Links.

Returns

System.Windows.Rect

Type Parameters

TNodeData

TLinkData

GetConnectedComponents()

Returns the connected components of this graph.

Declaration

public IEnumerable<GraphBase<TNode, TLink>> GetConnectedComponents()

Returns

System.Collections.Generic.IEnumerable<GraphBase<TNode, TLink>>

The list of connected components.

GetNextIdInNodes(Int32)

Gets the next identifier of the nodes sequence.

Declaration

public int GetNextIdInNodes(int id)

Parameters

System.Int32 id

The id.

Returns

System.Int32

HaveUniqueIdentifiers()

Ensures the unique identifiers.

Declaration

public bool HaveUniqueIdentifiers()

Returns

System.Boolean

NumberOfComponents()

Returns the number of (connected) components.

Declaration

public int NumberOfComponents()

Returns

System.Int32

Examples

The following example create two components;

var g = new GraphBase<Node, Edge>();
for (var i = 0; i < 4; i++) g.AddNode(new Node(1, true));
g.AddLink(g.Nodes[0], g.Nodes[1]);
g.AddLink(g.Nodes[2], g.Nodes[3]);
var count = g.NumberOfComponents();

NumberOfComponents(out Dictionary<Int32, Int32>)

Returns the number of connected components.

Declaration

public int NumberOfComponents(out Dictionary<int, int> componentMap)

Parameters

System.Collections.Generic.Dictionary<System.Int32, System.Int32> componentMap

The component map as a dictionary where the key is the node identifier and the value is the number of the connected component to which the node belongs.

Returns

System.Int32

RemoveAllLinksFrom(TNode)

Detaches all links from from the given node and removes them from the graph structure.

Declaration

public void RemoveAllLinksFrom(TNode node)

Parameters

TNode node

The node.

RemoveLink(TLink)

Removes the link from the graph.

Declaration

public void RemoveLink(TLink link)

Parameters

TLink link

The link.

RemoveNode(TNode)

Removes the given node from this graph.

Declaration

public void RemoveNode(TNode node)

Parameters

TNode node

The node to remove.

RenumberNodes(Int32)

Assigns a new identifier to the nodes.

Declaration

public void RenumberNodes(int startId = 0)

Parameters

System.Int32 startId

The number to start the numbering from.

ShortestPaths()

Gets the shortest path lengths between each two vertices.

Declaration

public Dictionary<Tuple<TNode, TNode>, int> ShortestPaths()

Returns

System.Collections.Generic.Dictionary<System.Tuple<TNode, TNode>, System.Int32>

A dictionary keyed with the node id's and value equal to the path lengths.

ToLinkListString()

Returns a string representation of the incidence structure of this graph.

Declaration

public string ToLinkListString()

Returns

System.String

Examples

A diagram with links between identifier 1 and 2, 2 and 3, 3 and 4 will result in a string

{"1,2", "2,3",
"3,4"}

Declaration

public IList<string> ToLinksList()

Returns

System.Collections.Generic.IList<System.String>

TopologicalSort(Boolean)

Is a linear ordering of its vertices.

Declaration

public IList<int> TopologicalSort(bool forceNewIdentifier = false)

Parameters

System.Boolean forceNewIdentifier

Returns

System.Collections.Generic.IList<System.Int32>

The topologically sorted sequence of node identifiers or null is the graph has cycles.

Remarks

The sorting is not unique.
The graph has to be acyclic in order to have a topological sort.
The sorting works on disconnected graphs.

ToString()

Returns a System.String that represents this instance.

Declaration

public override string ToString()

Returns

System.String

A System.String that represents this instance.

Overrides

System.Object.ToString()

Extension Methods

CollectionExtensions.ToEnumerable<T>(T)

GraphExtensions.BreadthFirstTraversal<TNode, TLink>(GraphBase<TNode, TLink>, IVisitor<TNode>, TNode)

GraphExtensions.BreadthFirstTraversal<TNode, TLink>(GraphBase<TNode, TLink>, Action<TNode>, TNode)

GraphExtensions.BreadthFirstSearch<TNode, TLink>(GraphBase<TNode, TLink>, Func<TNode, Boolean>, TNode)

GraphExtensions.CreateBiDictionary<TNode, TLink>(GraphBase<TNode, TLink>, Int32)

GraphExtensions.CreateDictionary<TNode, TLink>(GraphBase<TNode, TLink>, Int32)

GraphExtensions.DepthFirstTraversal<TNode, TLink>(GraphBase<TNode, TLink>, IVisitor<TNode>, TNode)

GraphExtensions.DepthFirstTraversal<TNode, TLink>(GraphBase<TNode, TLink>, IDepthVisitor<TNode>, TNode)

GraphExtensions.DepthFirstTraversal<TNode, TLink>(GraphBase<TNode, TLink>, Action<TNode>, TNode)

GraphExtensions.DepthFirstTraversal<TNode, TLink>(GraphBase<TNode, TLink>, Action<TNode, Int32>, TNode)

GraphExtensions.FindCycles<TNode, TLink>(GraphBase<TNode, TLink>, Boolean)

GraphExtensions.PrimsSpanningTree<TNode, TLink>(GraphBase<TNode, TLink>, TNode, Boolean)

EnumerableExtensions.ToEnumerable<T>(T)