Documentation

Class GraphBase<TNode, TLink>

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

Inheritance

System.Object

GraphBase<TNode, TLink>

Graph<TNodeData, TLinkData>

Namespace: Telerik.Windows.Diagrams.Core

Assembly: Telerik.Windows.Diagrams.Core.dll

Syntax

public class GraphBase<TNode, TLink> : Object 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.

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)