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

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

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"}

.

See Also

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

See Also

Graph<TNodeData, TLinkData>