Class GraphBase<TNode, TLink>
Base graph class for the various incarnations in the graph analysis.
Inheritance
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()
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
|
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
|
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
|
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 |
Returns
|
System.Boolean
|
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 |
Returns
|
System.Boolean
|
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 |
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 |
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 |
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
ToLinksList()
Returns the links structure of this graph as a list of identifier tuples.
Declaration
public IList<string> ToLinksList()Returns
|
System.Collections.Generic.IList<System.String>
|
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 |
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. |