Class GraphExtensions

The static graph-analysis related extensions.

Inheritance
System.Object
GraphExtensions
Inherited Members
System.Object.ToString()
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 static class GraphExtensions

Methods

AssignLevel<TLinkData>(Graph<TreeLayoutData, TLinkData>, Node<TreeLayoutData, TLinkData>, Dictionary<Node<TreeLayoutData, TLinkData>, Boolean>, Int32)

Assigns tree-levels to the nodes.

Declaration
public static void AssignLevel<TLinkData>(this Graph<TreeLayoutData, TLinkData> graph, Node<TreeLayoutData, TLinkData> startNode, Dictionary<Node<TreeLayoutData, TLinkData>, bool> visited = null, int offset = 0)
    where TLinkData : new()
Parameters
Graph<TreeLayoutData, TLinkData> graph

The graph.
Node<TreeLayoutData, TLinkData> startNode

The start node.
System.Collections.Generic.Dictionary<Node<TreeLayoutData, TLinkData>, System.Boolean> visited

The nodes which have already been visited.
System.Int32 offset

The offset.
Type Parameters
TLinkData

The type of the link data.

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

Performs a BFT of the given graph starting at the given node and stops when the first node matching the condition is found.

Declaration
public static TNode BreadthFirstSearch<TNode, TLink>(this GraphBase<TNode, TLink> graph, Func<TNode, bool> condition, TNode startNode)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph to traverse.
System.Func<TNode, System.Boolean> condition

The condition a node has to satisfy to be return and thus halt the traversal.
TNode startNode

The start node.
Returns
TNode

Type Parameters
TNode

The type of the node.
TLink

The type of the link.
Remarks

See http://en.wikipedia.org/wiki/Breadth-first_search.

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

Performs a breadth-first traversal of the graph starting at the given node.

Declaration
public static void BreadthFirstTraversal<TNode, TLink>(this GraphBase<TNode, TLink> graph, Action<TNode> action, TNode startNode)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph to traverse.
System.Action<TNode> action

The action acting a the visited node.
TNode startNode

The start node.
Type Parameters
TNode

The type of the node.
TLink

The type of the link.
Remarks

See http://en.wikipedia.org/wiki/Breadth-first_search.

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

Performs a breadth-first traversal of the graph starting at the given node.

Declaration
public static void BreadthFirstTraversal<TNode, TLink>(this GraphBase<TNode, TLink> graph, IVisitor<TNode> visitor, TNode startNode)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph to traverse.
IVisitor<TNode> visitor

The visitor traversing the graph.
TNode startNode

The start node.
Type Parameters
TNode

The type of the node.
TLink

The type of the link.
Remarks

See http://en.wikipedia.org/wiki/Breadth-first_search.

Clone<TNodeData, TLinkData>(IEnumerable<Edge<TNodeData, TLinkData>>)

Returns a shallow clone from the given collection.

Declaration
public static IList<Edge<TNodeData, TLinkData>> Clone<TNodeData, TLinkData>(this IEnumerable<Edge<TNodeData, TLinkData>> list)
    where TNodeData : new()
    where TLinkData : new()
Parameters
System.Collections.Generic.IEnumerable<Edge<TNodeData, TLinkData>> list

The collection to clone.
Returns
System.Collections.Generic.IList<Edge<TNodeData, TLinkData>>

Type Parameters
TNodeData

The node data type.
TLinkData

The link data type.

CreateArray(Int32, Int32)

Returns an array of the specified size.

Declaration
public static int[] CreateArray(int size, int value)
Parameters
System.Int32 size

The size.
System.Int32 value

The Graph value of the elements in the array.
Returns
System.Int32[]

CreateArray(Int32, Int32, Int32)

Returns an array of the specified size.

Declaration
public static int[, ] CreateArray(int dim1, int dim2, int value)
Parameters
System.Int32 dim1

The first dimension.
System.Int32 dim2

The second dimension.
System.Int32 value

The Graph value of the elements.
Returns
System.Int32[,]

CreateBalancedForest(Int32, Int32, Int32)

Creates a forest of balanced trees.

Declaration
public static GraphBase<Node<object, object>, Edge<object, object>> CreateBalancedForest(int levels = 4, int siblingsCount = 2, int treeCount = 5)
Parameters
System.Int32 levels

The levels.
System.Int32 siblingsCount

The siblings count.
System.Int32 treeCount

The tree count.
Returns
GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>>

CreateBalancedTree(Int32, Int32)

Creates a balanced tree.

Declaration
public static GraphBase<Node<object, object>, Edge<object, object>> CreateBalancedTree(int levels = 3, int siblingsCount = 3)
Parameters
System.Int32 levels

The levels.
System.Int32 siblingsCount

The siblings count.
Returns
GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>>

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

Creates a bi-directional dictionary with keys equal to the (supposedly unique) identifiers and value equal to the provided initial value.

Declaration
public static Dictionary<Tuple<TNode, TNode>, int> CreateBiDictionary<TNode, TLink>(this GraphBase<TNode, TLink> graph, int value)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph.
System.Int32 value

The value.
Returns
System.Collections.Generic.Dictionary<System.Tuple<TNode, TNode>, System.Int32>

Type Parameters
TNode

The type of the node.
TLink

The type of the link.

CreateComponents(Int32)

Creates a random graph with a specified amounts of components.

Declaration
public static GraphBase<Node<object, object>, Edge<object, object>> CreateComponents(int numberOfComponent)
Parameters
System.Int32 numberOfComponent

The number of component.
Returns
GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>>

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

Creates a dictionary with keys equal to the (supposedly unique) identifiers and value equal to the provided initial value.

Declaration
public static Dictionary<int, int> CreateDictionary<TNode, TLink>(this GraphBase<TNode, TLink> graph, int value)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph.
System.Int32 value

The value.
Returns
System.Collections.Generic.Dictionary<System.Int32, System.Int32>

Type Parameters
TNode

The type of the node.
TLink

The type of the link.

CreateRandomConnectedGraph(Int32, Int32, Boolean)

Creates a random connected graph.

Declaration
public static GraphBase<Node<object, object>, Edge<object, object>> CreateRandomConnectedGraph(int nodesCount, int maxIncidence = 4, bool tree = false)
Parameters
System.Int32 nodesCount

The nodes count.
System.Int32 maxIncidence

The max incidence.
System.Boolean tree

If set to true the random graph will be effectively a tree.
Returns
GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>>

CreateRandomGraph(Int32, Int32, Boolean)

Creates a random graph.

Declaration
public static GraphBase<Node<object, object>, Edge<object, object>> CreateRandomGraph(int nodesCount = 150, int maxIncidence = 4, bool tree = false)
Parameters
System.Int32 nodesCount

The count.
System.Int32 maxIncidence

The maximum incidence of each node.
System.Boolean tree

If set to true the generated graph will be a tree.
Returns
GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>>

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

Performs a depth-first traversal of the graph starting at the given node.

Declaration
public static void DepthFirstTraversal<TNode, TLink>(this GraphBase<TNode, TLink> graph, Action<TNode, int> action, TNode startNode)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph.
System.Action<TNode, System.Int32> action

The action.
TNode startNode

The start node.
Type Parameters
TNode

The type of the node.
TLink

The type of the link.

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

Performs a depth-first traversal of the graph starting at the given node.

Declaration
public static void DepthFirstTraversal<TNode, TLink>(this GraphBase<TNode, TLink> graph, Action<TNode> action, TNode startNode)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph.
System.Action<TNode> action

The action.
TNode startNode

The start node.
Type Parameters
TNode

The type of the node.
TLink

The type of the link.

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

Performs a depth-first traversal of the graph starting at the given node.

Declaration
public static void DepthFirstTraversal<TNode, TLink>(this GraphBase<TNode, TLink> graph, IDepthVisitor<TNode> visitor, TNode startNode)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph.
IDepthVisitor<TNode> visitor

The visitor.
TNode startNode

The start node.
Type Parameters
TNode

The type of the node.
TLink

The type of the link.

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

Performs a depth-first traversal of the graph starting at the given node.

Declaration
public static void DepthFirstTraversal<TNode, TLink>(this GraphBase<TNode, TLink> graph, IVisitor<TNode> visitor, TNode startNode)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph to traverse.
IVisitor<TNode> visitor

The visitor.
TNode startNode

The start node.
Type Parameters
TNode

The type of the node.
TLink

The type of the link.
Remarks

See http://en.wikipedia.org/wiki/Depth-first_search.

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

Finds cycles in a graph using Tarjan strongly connected components algorithm.

Declaration
public static IList<TNode[]> FindCycles<TNode, TLink>(this GraphBase<TNode, TLink> graph, bool excludeSingleItems = true)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph.
System.Boolean excludeSingleItems

If set to true nodes with no edges are excluded.
Returns
System.Collections.Generic.IList<TNode[]>

A list of of vertex arrays (paths) that form cycles in the graph.
Type Parameters
TNode

The type of the node.
TLink

The type of the link.

HasIdenticalStructureWith(GraphBase<Node<Object, Object>, Edge<Object, Object>>, GraphBase<Node<Object, Object>, Edge<Object, Object>>)

Compares the two graph and assert they are identical.

Declaration
public static bool HasIdenticalStructureWith(this GraphBase<Node<object, object>, Edge<object, object>> graph1, GraphBase<Node<object, object>, Edge<object, object>> graph2)
Parameters
GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>> graph1

GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>> graph2

Returns
System.Boolean

KruskalsSpanningTree<TNode, TLink>(GraphBase<TNode, TLink>)

Kruskal algorithm.

Declaration
public static GraphBase<TNode, TLink> KruskalsSpanningTree<TNode, TLink>(GraphBase<TNode, TLink> graph)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
Parameters
GraphBase<TNode, TLink> graph

The graph.
Returns
GraphBase<TNode, TLink>

Type Parameters
TNode

The type of the node.
TLink

The type of the link.
Remarks

    .

    See Also

    Merge(GraphBase<Node<Object, Object>, Edge<Object, Object>>, GraphBase<Node<Object, Object>, Edge<Object, Object>>)

    Merges the given graph into the current graph.

    Declaration
    public static GraphBase<Node<object, object>, Edge<object, object>> Merge(this GraphBase<Node<object, object>, Edge<object, object>> graph, GraphBase<Node<object, object>, Edge<object, object>> otherGraph)
    Parameters
    GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>> graph

    The graph.
    GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>> otherGraph

    The graph to merge into the current one.
    Returns
    GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>>

    MoveGraph<TNodeData, TLinkData>(GraphBase<Node<TNodeData, TLinkData>, Edge<TNodeData, TLinkData>>, Double, Double)

    Offsets the specified graph.

    Declaration
    public static void MoveGraph<TNodeData, TLinkData>(this GraphBase<Node<TNodeData, TLinkData>, Edge<TNodeData, TLinkData>> layoutGraph, double offsetX, double offsetY)
    where TNodeData : new()
    where TLinkData : new()
    Parameters
    GraphBase<Node<TNodeData, TLinkData>, Edge<TNodeData, TLinkData>> layoutGraph

    The layout Graph.
    System.Double offsetX

    The horizontal offset.
    System.Double offsetY

    The vertical offset.
    Type Parameters
    TNodeData

    The node data type.
    TLinkData

    The link data type.

    MoveLink<TNodeData, TLinkData>(Edge<TNodeData, TLinkData>, Point)

    Moves link.

    Declaration
    public static void MoveLink<TNodeData, TLinkData>(this Edge<TNodeData, TLinkData> edge, Point point)
    where TNodeData : new()
    where TLinkData : new()
    Parameters
    Edge<TNodeData, TLinkData> edge

    The layout link.
    System.Windows.Point point

    The delta to move.
    Type Parameters
    TNodeData

    The node data type.
    TLinkData

    The link data type.

    Offset(Rect, Double, Double)

    Offsets the given rectangle.

    Declaration
    public static Rect Offset(this Rect rect, double x, double y)
    Parameters
    System.Windows.Rect rect

    The rectangle.
    System.Double x

    The horizontal offset.
    System.Double y

    The vertical offset.
    Returns
    System.Windows.Rect

    Parse(IEnumerable<String>)

    Parses the specified list representing the incidence structure of a graph.

    Declaration
    public static GraphBase<Node<object, object>, Edge<object, object>> Parse(IEnumerable<string> list)
    Parameters
    System.Collections.Generic.IEnumerable<System.String> list

    The list of link couples.
    Returns
    GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>>

    The graph corresponding to the incidence structure given.

    Position(Rect)

    Returns the position of the given rectangle.

    Declaration
    public static Point Position(this Rect rect)
    Parameters
    System.Windows.Rect rect

    The rectangle.
    Returns
    System.Windows.Point

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

    Prim's algorithm finds a minimum-cost spanning tree of an edge-weighted, connected, undirected graph.

    Declaration
    public static GraphBase<TNode, TLink> PrimsSpanningTree<TNode, TLink>(this GraphBase<TNode, TLink> graph, TNode fromNode, bool reverseWrongEdges = false)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
    Parameters
    GraphBase<TNode, TLink> graph

    The graph structure.
    TNode fromNode

    The node to start from.
    System.Boolean reverseWrongEdges

    If set to true and the graph is not directed then the edges which do not point in the correct tree flow direction will be reversed.
    Returns
    GraphBase<TNode, TLink>

    Type Parameters
    TNode

    The type of the node.
    TLink

    The type of the link.
    Remarks

    See http://en.wikipedia.org/wiki/Prim%27s_algorithm .

    Split<TNodeData, TLinkData>(Graph<TNodeData, TLinkData>)

    Splits the given, not necessarily connected, graph into its connected components.

    Declaration
    public static IEnumerable<Graph<TNodeData, TLinkData>> Split<TNodeData, TLinkData>(this Graph<TNodeData, TLinkData> graph)
    where TNodeData : new()
    where TLinkData : new()
    Parameters
    Graph<TNodeData, TLinkData> graph

    The graph to be split.
    Returns
    System.Collections.Generic.IEnumerable<Graph<TNodeData, TLinkData>>

    Type Parameters
    TNodeData

    The node data type.
    TLinkData

    The link data type.

    TakeRandomNode(GraphBase<Node<Object, Object>, Edge<Object, Object>>, Node<Object, Object>, Int32)

    Takes a random node with incidence less than specified.

    Declaration
    public static Node<object, object> TakeRandomNode(this GraphBase<Node<object, object>, Edge<object, object>> graph, Node<object, object> node = null, int incidenceLessThan = 4)
    Parameters
    GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>> graph

    The graph.
    Node<System.Object, System.Object> node

    The node which should not be returned; i.e. the random node should be in the complement of the given node.
    System.Int32 incidenceLessThan

    The incidence less than.
    Returns
    Node<System.Object, System.Object>

    TakeTwoRandomNodes(GraphBase<Node<Object, Object>, Edge<Object, Object>>)

    Takes two random nodes from the given graph.

    Declaration
    public static Tuple<Node<object, object>, Node<object, object>> TakeTwoRandomNodes(this GraphBase<Node<object, object>, Edge<object, object>> graph)
    Parameters
    GraphBase<Node<System.Object, System.Object>, Edge<System.Object, System.Object>> graph

    The graph.
    Returns
    System.Tuple<Node<System.Object, System.Object>, Node<System.Object, System.Object>>

    TarjansStronglyConnectedComponentsAlgorithm<TNode, TLink>(Boolean, TNode, IDictionary<TNode, Int32>, IDictionary<TNode, Int32>, ICollection<TNode[]>, Stack<TNode>, Int32)

    Executes Tarjan algorithm on the graph.

    Declaration
    public static void TarjansStronglyConnectedComponentsAlgorithm<TNode, TLink>(bool excludeSingleItems, TNode node, IDictionary<TNode, int> indices, IDictionary<TNode, int> lowLinks, ICollection<TNode[]> connected, Stack<TNode> stack, int index)
    where TNode : class, INode<TNode, TLink>, new()
    where TLink : class, IEdge<TNode, TLink>, new()
    Parameters
    System.Boolean excludeSingleItems

    If set to true single items (singletons) will not be taken into account.
    TNode node

    The node to start with.
    System.Collections.Generic.IDictionary<TNode, System.Int32> indices

    The current indices.
    System.Collections.Generic.IDictionary<TNode, System.Int32> lowLinks

    The current low links.
    System.Collections.Generic.ICollection<TNode[]> connected

    The connected components.
    System.Collections.Generic.Stack<TNode> stack

    The stack.
    System.Int32 index

    The current index.
    Type Parameters
    TNode

    The node data type.
    TLink

    The link data type.
    Remarks

    See http://en.wikipedia.org/wiki/Pseudoforest .

    UnionEmptyRects(Rect, Rect)

    If the first supplied rectangle has width or height zero the second rectangle will be returned. Otherwise the standard union of two rectangles will be used.

    Declaration
    public static Rect UnionEmptyRects(Rect rect1, Rect rect2)
    Parameters
    System.Windows.Rect rect1

    A rectangle.
    System.Windows.Rect rect2

    Another rectangle.
    Returns
    System.Windows.Rect

    UnionRects(Rect, Rect)

    Returns the smallest possible rectangle containing both of the specified rectangles.

    Declaration
    [Obsolete("Do not use this method. Use Utils.Union instead", false)]
public static Rect UnionRects(Rect rect1, Rect rect2)
    Parameters
    System.Windows.Rect rect1

    The first rectangle.
    System.Windows.Rect rect2

    The second rectangle.
    Returns
    System.Windows.Rect

    The union of the rectangles.