Remarks
These methods are specifically designed for graphs of type LayoutGraph. For algorithms applicable to the type IGraph, please refer to individual classes that allow to run a specific algorithm on an IGraph instance, for example, class ShortestPath or TreeAnalysis. These classes have more convenient configuration options and are typically named directly after the algorithm.
These algorithms encompass a wide range of functionalities including cycle detection, pathfinding, centrality computations, clustering, and more. The methods in this class are optimized for performance and designed to handle various types of graphs such as directed, undirected, weighted, and unweighted graphs.
The LayoutGraphAlgorithms class is intended for use with LayoutGraph objects, which represent the underlying structure of a graph in a layout environment. The algorithms provided here assist in determining graph properties, finding specific structures within a graph, and performing operations necessary for layout computations.
Many of the methods in this class offer optional parameters allowing for flexible configurations. For instance, several algorithms support both directed and undirected graphs, and many accept custom edge weight mappings to accommodate various use cases.
See Also
Developer's Guide
Members
Static Methods
Creates transitive edges that connect the visible nodes in the specified graph.
visible nodes in the specified graph.The algorithm generates a transitive edge between two visible nodes if:
- There exists a path between the two nodes using only invisible nodes as intermediate nodes.
- There is no existing edge directly connecting the two visible nodes.
The resulting transitive edges are added to the graph to ensure that all reachable nodes are directly connected. This helps in simplifying the graph structure by reducing the number of intermediary nodes.
Parameters
- graph: LayoutGraph
- The original graph that contains both visible and invisible nodes.
- directed: boolean
- A boolean indicating whether the edges should be treated as directed. If
true, the edges will be directed; otherwise, they will be undirected. - visibleNodes: function(LayoutNode): boolean
- A predicate describing whether a node is
visibleor not.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> of the created transitive edges. These are the edges added to connect visible nodes based on the described conditions.
Computes the shortest paths between all pairs of nodes in a graph with arbitrary edge costs.
This method works with instances of LayoutGraph. To find the shortest paths between all pairs of nodes in an IGraph use AllPairsShortestPaths instead.
If the given graph contains a negative-cost cycle, the method cannot compute valid shortest paths, and it will return null.
directed is set to false, the graph is treated as undirected, meaning each edge can be traversed in both directions. Consequently, the shortest paths may include edges traversed in the reverse direction.Parameters
- graph: LayoutGraph
- The graph in which the shortest paths between all pairs of nodes are to be computed.
- directed: boolean
- A boolean value indicating whether the graph should be treated as directed (
true) or undirected (false). - edgeCosts: IMapper<LayoutEdge, number>
- An IMapper<TKey, TValue> that provides the cost of traversing each edge in the graph. The key is the edge, and the value is the cost of traversing that edge.
Return Value
- IMapper<LayoutNode, IMapper<LayoutNode, number>>
- An IMapper<TKey, TValue> mapping each pair of nodes
sandtto the shortest path distance between them. The distance from nodesto nodetcan be accessed viaresult[s][t]. If there is no path fromstot, the value will be Number.POSITIVE_INFINITY. If the graph contains a negative-cost cycle, the method returnsnull.
Complexity
O(graph.Nodes.Count² * log(graph.Nodes.Count))Computes all edges that belong to any directed path from a source node to a sink node.
source node to a sink node.Parameters
- graph: LayoutGraph
- The input graph where the paths will be computed.
- source: LayoutNode
- The node from which the paths originate.
- sink: LayoutNode
- The node where the paths should terminate.
Return Value
- IMapper<LayoutEdge, boolean>
- An IMapper<K, V> that contains for each edge in the graph either
true, if the edge is on any directed path from source to sink, orfalseotherwise.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Returns all simple directed or undirected paths between two given nodes as a special cursor that calculates the next path in the sequence, only when needed.
Note: This method works with instances of LayoutGraph. To find all paths between two nodes in an IGraph use Paths instead.
The number of different paths connecting two nodes can be exponential to the number of nodes and edges of a given graph. Thus, the runtime of the algorithm can be excessive even for small graphs. This should also be considered when converting the returned enumerable to e.g. a list or array.
Parameters
- graph: LayoutGraph
- The input graph where the paths will be computed.
- source: LayoutNode
- The node from which the paths originate.
- sink: LayoutNode
- The node where the paths should terminate.
- directed: boolean
trueif the graph should be treated as directed, meaning edges are traversable only in one direction;falseif the graph should be considered undirected.- pathFilter?: function(IList<LayoutEdge>): boolean
- An optional predicate that accepts or rejects a found path, deciding whether it is added to the result. If no predicate is specified, all paths are accepted.
Return Value
- IEnumerable<IList<LayoutEdge>>
- An IEnumerable<T> that calculates the next path in the sequence on demand.
Complexity
O(2^ (graph.Nodes.Count + graph.Edges.Count)).1.0. If the graph is undirected, the method will consider edges traversable in both directions, potentially leading to undirected paths in the result.maxLength will be ignored.Parameters
- graph: LayoutGraph
- The input graph where the shortest paths will be computed.
- source: LayoutNode
- The node from which the shortest paths originate.
- sinks: IEnumerable<LayoutNode>
- A collection of target nodes where the paths should terminate.
- directed: boolean
trueif the graph should be treated as directed, meaning edges are traversable only in one direction;falseif the graph should be considered undirected.- resultPathEdges: IEnumerable<LayoutEdge>
- An IEnumerable<T> of LayoutEdge instances that will be populated during the execution of the method. This collection will contain the edges that form the shortest paths from the
sourcenode to the nodes insinks, in the correct order. - resultPathNodes: IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNode instances that will be populated during the execution of the method. This collection will contain the nodes that are part of the shortest paths from the
sourcenode to the nodes insinks, in the correct order. - maxLength?: number
- The maximum number of edges allowed in the shortest paths. If omitted, the length of the shortest paths is considered unlimited.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Computes the transitive closure and adds necessary transitive edges to a directed acyclic graph.
This method is specifically designed to work with instances of LayoutGraph. To compute the transitive closure for an IGraph, use TransitiveClosure instead.
Given a directed acyclic graph G = (V, E), the transitive closure of G is a graph in which an edge (v, w) is included if and only if there is a path from node v to node w in G.
Note that this implementation computes only the transitive closure and does not include the reflexive closure. Therefore, self-loops (edges from a vertex to itself) are not added to the graph.
Parameters
- graph: LayoutGraph
- The graph to which transitive edges will be added, if necessary.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> with the edges that have been added to the graph.
Computes the transitive reduction for a directed acyclic graph.
This method is designed to work with instances of LayoutGraph. For computing the transitive reduction for an IGraph, use TransitiveReduction instead.
The transitive reduction of a graph G = (V, E) is a graph where an edge (v, w) is included only if there is no path of length 2 or more from node v to node w in G. In other words, transitive edges are removed from the graph.
graph.Nodes.Count x graph.Nodes.Count matrix to store reachability data.Parameters
- graph: LayoutGraph
- The graph from which transitive edges will be removed to compute the transitive reduction.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> with the transitive edges that were removed from the graph.
Complexity
O(graph.Nodes.Count^3)Executes a breadth-first search (BFS) on a directed or undirected graph, returning the nodes organized into layers.
This method performs a BFS on instances of LayoutGraph. If you need to perform a BFS on IGraph instances, use the Bfs class instead.
The search begins with a set of "starting" nodes provided in startingNodes. These nodes are considered the initial layer (layer 0) of the search. The algorithm proceeds by expanding from these starting nodes to explore other nodes, assigning them to subsequent layers based on their distance from the starting nodes.
Each node discovered during the BFS is assigned a layer index, which is stored in the provided IMapper<K, V> resultLayerIds. Starting nodes are assigned a layer index of 0. Nodes in the i-th layer are those that are directly connected to nodes in the (i-1)-th layer and have not been previously assigned to any layer.
When BOTH is used, the node layers for SUCCESSOR and for PREDECESSOR are calculated and for each node the closer layer is used. This may result in some layers staying empty in the combined layer assignment.
If maximumLayerCount is greater than 0, the BFS will stop after the specified number of layers, and the result will include only the nodes up to this maximum layer.
maximumLayerCount is specified and restricts the number of layers, the returned array may contain fewer nodes than the total number of nodes in the graph. Only nodes with a layer index less than maximumLayerCount will be included.Parameters
- graph: LayoutGraph
- The LayoutGraph instance on which the BFS is to be executed.
- startingNodes: IEnumerable<LayoutNode>
- A collection of LayoutNodes representing the starting nodes from which the BFS starts.
- resultLayerIds?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> to store the layer index of each node encountered during the BFS. If a node is not reachable, its layer index will be set to
-1. IfresultLayerIdsis omitted, the method will not record layer indices. - direction?: TraversalDirection
- Specifies the direction of traversal in the graph. Use one of the values defined in TraversalDirection. The default is UNDIRECTED, which means the search will not consider the direction of the edges.
- maximumLayerCount?: number
- The maximum number of layers to be returned. If set to
0, the search will continue until all reachable nodes have been processed, regardless of the number of layers.
Return Value
- IEnumerable<LayoutNode>
- An array of IEnumerable<T> collections, where each collection contains the LayoutNodes that belong to a particular layer. The array index corresponds to the layer index.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)biconnectedComponentClustering
(graph: LayoutGraph, resultClusterIds: IMapper<LayoutNode, number>): numberstaticPartitions the graph into clusters based on its biconnected components.
biconnectedComponentClustering
(graph: LayoutGraph, resultClusterIds: IMapper<LayoutNode, number>): numberThis method is specifically designed to work with instances of LayoutGraph. If you need to partition an IGraph into clusters based on its biconnected components, use the BiconnectedComponentClustering method instead.
The partitioning groups nodes into clusters such that all nodes within each cluster are biconnected. Nodes that are part of multiple biconnected components will be assigned to exactly one of those components.
Biconnected components are defined only for undirected graphs. Consequently, this method disregards self-loops. Isolated nodes with only self-loops or no edges will not be assigned to any cluster, resulting in a null value for their resultClusterIds mapping.
Parameters
- graph: LayoutGraph
- The input graph to be analyzed.
- resultClusterIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be populated with the cluster assignments during execution. It maps each node to a non-negative representing the ID of the cluster to which the node belongs. Isolated nodes with only self-loop edges or no edges at all will be assigned a
nullvalue.
Return Value
- number
- The total number of distinct biconnected component clusters found in the graph.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown when either
graphorresultClusterIdsisnull.
Complexity
O(graph.Edges.Count + graph.Nodes.Count)Calculates the biconnected components and articulation points of the specified undirected graph, and returns the biconnected components.
This method works with instances of LayoutGraph. To determine biconnected components and articulation points in an IGraph instance, use BiconnectedComponents instead.
Biconnected components are maximal subgraphs where any two vertices are connected to each other by two disjoint paths. Articulation points (or cut vertices) are nodes which, when removed, increase the number of connected components of the graph.
The articulation points are returned as an IMapper<K, V> where each node is mapped to a boolean value indicating whether it is an articulation point.
-1.Parameters
- graph: LayoutGraph
- The input graph for which biconnected components and articulation points will be computed.
- resultComponentIds?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that, if provided, will be populated with the zero-based index of the biconnected component to which each edge belongs. Self-loops will have an index of
-1, as they do not belong to any biconnected component. - resultArticulationPoints?: IMapper<LayoutNode, boolean>
- An optional IMapper<K, V> that, if provided, will be populated with boolean values indicating whether each node is an articulation point (
trueif it is,falseotherwise).
Return Value
- IEnumerable<LayoutEdge>
- An array of biconnected components, each represented as an IEnumerable<T> of LayoutEdges contained in that component.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)This method specifically operates on instances of LayoutGraph. To calculate the bipartition for a graph represented by IGraph, consider using the Bipartition method.
A bipartite graph is one in which the set of vertices can be divided into two disjoint subsets such that no two vertices within the same subset are adjacent. This method determines whether the provided graph is bipartite and, if so, populates the provided collections with the nodes corresponding to the two partitions.
Parameters
- graph: LayoutGraph
- The graph to analyze. The graph should be an instance of LayoutGraph.
- resultPartition1: ICollection<LayoutNode>
- A collection that will be populated with the nodes belonging to the first partition, if the graph is bipartite.
- resultPartition2: ICollection<LayoutNode>
- A collection that will be populated with the nodes belonging to the second partition, if the graph is bipartite.
Return Value
- boolean
trueif the graph is bipartite and the partitions were successfully calculated; otherwise,false.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Sample Graphs
Identifies and returns a collection of Substructure instances representing the chains within the specified graph that contain at least minimumSize nodes.
minimumSize nodes.A chain is a linear sequence of nodes connected by edges, where each node (except for the first and last) has exactly two incident edges. The identified chain must consist of nodes and edges that share the same nodeTypes and edgeDirectedness.
A substructure is only identified as a chain if all edges in the sequence are either undirected or consistently directed according to the specified directedness. If any edge does not conform, the substructure is not recognized as a chain.
The edgeDirectedness parameter is used to determine how the edges in the chain are considered:
- A value of
1indicates that the edge is directed from source to target. - A value of
-1indicates that the edge is directed from target to source. - A value of
0indicates that the edge is undirected (the default for edges mapped tonull).
edgeDirectedness is not specified, all edges are treated as undirected. Similarly, if nodeTypes is not specified, all nodes are considered to be of the same type.Parameters
- graph: LayoutGraph
- The graph from which chains are to be identified.
- minimumSize: number
- The minimum number of nodes required for a subgraph to be considered a chain. Subgraphs with fewer nodes are ignored. The smallest value allowed for this parameter is
3. - nodeTypes?: IMapper<LayoutNode, any>
- An optional IMapper<TKey, TValue> mapping each LayoutNode to its type. Nodes that map to the same object are considered to be of the same type. If this parameter is not provided, all nodes are considered to be of the same type.
- edgeDirectedness?: IMapper<LayoutEdge, number>
- An optional IMapper<TKey, TValue> mapping each LayoutEdge to a nullable representing its directedness. If this parameter is not provided, all edges are treated as undirected.
Return Value
- IEnumerable<Substructure>
- A list of Substructure instances representing the identified chains in the graph.
Identifies and returns a collection of Substructure instances representing the (undirected) cliques within the specified graph, where each clique contains at least minimumSize nodes.
minimumSize nodes.A clique is defined as a subset of nodes of the same type (as determined by nodeTypes) where every node is directly connected to every other node in the subset.
It is important to note that the problem of finding a maximum clique is NP-hard. As such, this method employs a heuristic approach that does not guarantee the discovery of all cliques or the largest clique. The heuristic identifies cliques by focusing on those with at least one node that has at most one non-clique neighbor. Additionally, each node is restricted to membership in a single clique, ensuring that the returned cliques are non-overlapping.
nodeTypes, meaning they are associated with identical objects. If nodeTypes is not provided, all nodes are treated as having the same type.minimumSize can accept is 3.Parameters
- graph: LayoutGraph
- The graph from which cliques are to be identified.
- minimumSize: number
- The minimum number of nodes required for a subset to be considered a clique. Subsets with fewer nodes than this value will be ignored. The minimum permissible value for
minimumSizeis3. - nodeTypes?: IMapper<LayoutNode, any>
- An optional mapping that associates each node with a type. Nodes that are mapped to the same object are considered to be of the same type. If this parameter is
nullor not provided, all nodes will be treated as being of the same type.
Return Value
- IEnumerable<Substructure>
- A collection of Substructure objects representing the identified cliques within the graph. If no cliques are found that meet the criteria, an empty list is returned.
Computes the closeness centrality for each node in the specified graph.
This method calculates closeness centrality for nodes in an instance of LayoutGraph. To calculate closeness centrality for nodes in an IGraph instance, use ClosenessCentrality instead.
Closeness centrality is defined as the reciprocal of the sum of the shortest path distances from a node to all other nodes in the graph. Therefore, a node with high closeness centrality has shorter average distances to all other nodes. If the sum of the shortest path distances is 0 (i.e., the node is isolated), the closeness centrality is set to Number.POSITIVE_INFINITY.
Centrality measures help quantify the relative importance of nodes in a network. A higher centrality value indicates that a node is more central to the network according to the algorithm.
Parameters
- graph: LayoutGraph
- The input graph for which closeness centrality will be computed.
- directed?: boolean
- A boolean value indicating whether the graph should be treated as directed. Pass
trueif the graph is directed; otherwise, passfalse. - edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides positive double values representing the cost of each edge. If
edgeCostsis not specified, all edges are assumed to have equal cost.
Return Value
- IMapper<LayoutNode, number>
- An IMapper<K, V> that contains the closeness centrality values for each node in the graph. The key is a LayoutNode, and the value is a representing the centrality of that node.
Complexity
O((graph.Nodes.Count * graph.Edges.Count) + graph.Nodes.Count^2)for unweighted graphs.O((graph.Nodes.Count * graph.Edges.Count) + graph.Nodes.Count^2 * log(graph.Nodes.Count))for weighted graphs.
This method is specifically designed to work with instances of LayoutGraph. To calculate clustering coefficients for an IGraph, use the ClusteringCoefficient method instead.
The clustering coefficient quantifies the degree to which nodes in a graph cluster together. For a given node n, the local clustering coefficient is calculated as the ratio of the number of edges between the node's neighbors to the number of possible edges that could exist among those neighbors. The coefficient is a value ranging from 0.0 (no clustering) to 1.0 (complete clustering). For more details, refer to https://en.wikipedia.org/wiki/Clustering_coefficient.
Parameters
- graph: LayoutGraph
- The graph instance for which the clustering coefficient is to be computed.
- resultCoefficients: IMapper<LayoutNode, number>
- A mapping that will contain the clustering coefficient for each node in the graph.
- directed: boolean
- Specifies whether the graph is directed. If
true, the algorithm accounts for the direction of edges; otherwise, it assumes the graph is undirected.
Return Value
- number
- The average local clustering coefficient of all nodes in the graph.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown when
graphorresultCoefficientsisnull.
connectedComponents
(graph: LayoutGraph, resultComponentIds?: IMapper<LayoutNode, number>): IEnumerable<LayoutNode>staticCalculates the connected components of the specified graph.
connectedComponents
(graph: LayoutGraph, resultComponentIds?: IMapper<LayoutNode, number>): IEnumerable<LayoutNode>This method calculates the connected components of a LayoutGraph. To determine the connected components in an IGraph instance, use ConnectedComponents instead.
A graph G is considered connected if there exists an undirected path of edges between every pair of nodes in the graph.
The connected components of a graph are the maximal connected subgraphs into which the graph can be decomposed. Each connected component is a subgraph in which any two nodes are connected to each other by paths, and which is connected to no additional nodes in the graph.
Parameters
- graph: LayoutGraph
- The input graph for which connected components will be computed.
- resultComponentIds?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> that will be populated during the execution. It maps each LayoutNode to a zero-based index representing the connected component to which the node belongs. If this parameter is omitted, component indices will not be computed.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> where each element is an IEnumerable<T> of LayoutNodes. Each inner IEnumerable<T> represents a connected component, containing the nodes that belong to that component.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Identifies and returns a collection of Substructure instances representing the cycles within the specified graph that contain at least minimumSize nodes.
minimumSize nodes.A cycle is defined as a simple closed path in which the first and last nodes are identical, forming a loop. The algorithm only considers cycles where at most one edge connects any cycle node to the rest of the graph, effectively isolating the cycle with a single connecting edge.
All nodes and edges within a cycle must share the same nodeTypes and edgeDirectedness. If a cycle is found where nodes or edges do not match these criteria, it is not included in the result.
The directedness of the edges, specified by the edgeDirectedness parameter, is considered when identifying cycles. A valid cycle is one where all edges are either undirected or consistently directed according to the specified directedness.
The edgeDirectedness parameter is interpreted as follows:
- A value of
1indicates that the edge is directed from source to target. - A value of
-1indicates that the edge is directed from target to source. - A value of
0indicates that the edge is undirected (the default for edges mapped tonull).
edgeDirectedness is not specified, all edges are treated as undirected. Similarly, if nodeTypes is not specified, all nodes are considered to be of the same type.Parameters
- graph: LayoutGraph
- The graph from which cycles are to be identified.
- minimumSize: number
- The minimum number of nodes required for a subgraph to be considered a cycle. Subgraphs with fewer nodes are ignored. The smallest value allowed for this parameter is
3. - nodeTypes?: IMapper<LayoutNode, any>
- An optional IMapper<TKey, TValue> mapping each LayoutNode to its type. Nodes that map to the same object are considered to be of the same type. If this parameter is not provided, all nodes are considered to be of the same type.
- edgeDirectedness?: IMapper<LayoutEdge, number>
- An optional IMapper<TKey, TValue> mapping each LayoutEdge to a nullable representing its directedness. If this parameter is not provided, all edges are treated as undirected.
Return Value
- IEnumerable<Substructure>
- A list of Substructure instances representing the identified cycles in the graph.
degreeCentrality
(considerInEdges?: booleanconsiderOutEdges?: boolean): IMapper<LayoutNode, number>staticComputes the degree centrality for the nodes in the specified graph.
degreeCentrality
(This method calculates the degree centrality for nodes in an instance of LayoutGraph. To compute degree centrality for edges in an IGraph instance, use DegreeCentrality instead.
Degree centrality measures the number of edges incident to a node. This includes both incoming and outgoing edges, depending on the specified parameters. A higher degree centrality value indicates a node with more connections, which is generally considered more central in the network.
Centrality quantifies the concept that some nodes are "more central" or "important" than others based on their degree. The higher the centrality value, the more central the node is considered by the algorithm.
Parameters
- graph: LayoutGraph
- The input graph for which degree centrality will be computed.
- considerInEdges?: boolean
- A boolean value indicating whether incoming edges should be included in the degree centrality calculation. Pass
trueto include incoming edges; otherwise, passfalse. - considerOutEdges?: boolean
- A boolean value indicating whether outgoing edges should be included in the degree centrality calculation. Pass
trueto include outgoing edges; otherwise, passfalse.
Return Value
- IMapper<LayoutNode, number>
- An IMapper<K, V> that contains the degree centrality values for each node in the graph. The key is a LayoutNode, and the value is a representing the centrality of that node.
Complexity
O(graph.Nodes.Count)Computes a Delaunay triangulation of the given points.
A Delaunay triangulation is a triangulation such that none of the given points is inside the circumcircle of any of the calculated triangles.
The calculated triangulation is represented by an embedded graph, i.e. to each edge there exists a reverse edge and the outedges around each node are in embedded order. The returned edge and the (optional) reverseEdgeMap can be used to construct all faces of the plane graph and to determine its outer face.
Parameters
- resultGraph: LayoutGraph
- A graph whose nodes represent the points that should be triangulated. The resulting graph will contain edges that correspond to edges in the triangulation of the represented points.
- nodeLocations: IMapper<LayoutNode, Point>
- A mapping from nodes to their corresponding point's location.
- resultReversedEdges: IMapper<LayoutEdge, LayoutEdge>
- An IMapper<K, V> that will be populated with the reverse edge for each edge in the triangulation. If this argument is
nullthen no reverse edge information will be available.
Return Value
- LayoutEdge
- An edge on the outer face of the result graph or
nullif there are fewer than two points designated asnodeLocations.
Computes the density of the specified graph, considering only a simple version of it (see isSimple).
This method works with instances of LayoutGraph. To determine the density of an IGraph use getDensity instead.
The density of a graph is the ratio of the number of edges to the maximum possible number of edges. For simple graphs, the maximum number of edges is determined as follows:
edges / (nodes * (nodes - 1))for directed simple graphs, where each edge is unique and has a direction.2 * edges / (nodes * (nodes - 1))for undirected simple graphs, where each edge is counted once but can connect nodes in either direction.
This method calculates density based on the number of edges and nodes in the graph, while ignoring self-loops and multi-edges.
Parameters
- graph: LayoutGraph
- The graph for which the density is to be computed.
- directed?: boolean
trueif the graph should be considered as directed; otherwise,false.
Return Value
- number
- The density of the specified graph as a value.
startingNode node is null, this method returns silently.Parameters
- graph: LayoutGraph
- The input graph on which the DFS will be performed.
- startingNode: LayoutNode
- The node from which the DFS will start.
- directed?: boolean
trueif the edges of the graph should be treated as directed;falseotherwise. The default value isfalse.- visitAllTrees?: boolean
trueif DFS should continue searching after all nodes reachable from the start node are visited;falseto stop after the first DFS tree is completed. The default value istrue.- nodeVisiting?: function(LayoutNode, number): void
- A callback that will be invoked before a node is visited for the first time during DFS. If omitted, no action will be taken.
- nodeVisited?: function(LayoutNode, number, number): void
- A callback that will be invoked after a node visit is completed during DFS. If omitted, no action will be taken.
- edgeTraversing?: function(LayoutEdge, LayoutNode, boolean): void
- A callback that will be invoked before an edge is traversed for the first time during DFS. If omitted, no action will be taken.
- edgeTraversed?: function(LayoutEdge, LayoutNode): void
- A callback that will be invoked after DFS has returned from a node during edge traversal. If omitted, no action will be taken.
- nextTreeVisiting?: function(LayoutNode): void
- A callback that will be invoked when DFS continues its search from a new root node. This will only occur if the
visitAllTreesparameter is set totrue. If omitted, no action will be taken.
Sample Graphs
See Also
Developer's Guide
Calculates an ordering of the nodes that corresponds to the order of node completion events in a depth-first search.
Parameters
- graph: LayoutGraph
- The input graph for which the node ordering will be calculated.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNodes representing the nodes of the graph, ordered according to the sequence of node completion events in a depth-first search.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)This method works with instances of LayoutGraph. To determine the diameter of an IGraph use getDiameter instead.
The diameter of a graph is defined as the maximum eccentricity of any vertex in the graph. In other words, it is the length of the longest shortest path between any two vertices in the graph.
Eccentricity of a vertex is the greatest distance from that vertex to any other vertex in the graph.
The diameter calculation considers all edges, including multi-edges if they exist in the graph.
Parameters
- graph: LayoutGraph
- The graph for which the diameter is to be computed.
- directed?: boolean
trueif the graph should be treated as directed; otherwise,false.- edgeCosts?: IMapper<LayoutEdge, number>
- An IMapper<K, V> that provides the costs of the edges. If omitted, all edges are assumed to have a uniform cost of
1.
Return Value
- number
- The diameter of the specified graph. This is the length of the longest shortest path between any two vertices.
Computes the betweenness centrality for each edge in the specified graph.
This method calculates betweenness centrality specifically for edges in an instance of LayoutGraph. For computing betweenness centrality for both nodes and edges in an IGraph instance, use BetweennessCentrality instead.
Betweenness centrality measures the extent to which an edge lies on the shortest paths between other pairs of nodes in the graph. Edges with high betweenness centrality have a significant impact on the flow of information or connectivity in the network. Removing a central edge will significantly alter many shortest paths in the graph.
Centrality quantifies the notion that some edges are "more central" to the network than others. A higher centrality value indicates a more central edge according to the algorithm.
Parameters
- graph: LayoutGraph
- The input graph for which edge betweenness centrality will be computed.
- directed?: boolean
- A boolean value indicating whether the graph should be treated as directed. Pass
trueif the graph is directed; otherwise, passfalse. - edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides positive double values representing the cost of each edge. If
edgeCostsis not specified, all edges are assumed to have equal cost. For invalid or missing values, the algorithm will assume a default cost of1.0.
Return Value
- IMapper<LayoutEdge, number>
- An IMapper<K, V> that contains the betweenness centrality values for each edge in the graph. The key is an LayoutEdge, and the value is a representing the centrality of that edge.
Complexity
O(graph.Nodes.Count * graph.Edges.Count)for unweighted graphs.O(graph.Nodes.Count * (graph.Edges.Count + graph.Nodes.Count) * log(graph.Nodes.Count))for weighted graphs.
This method performs clustering on an instance of LayoutGraph. To partition an IGraph into clusters using edge-betweenness clustering, refer to EdgeBetweennessClustering instead.
The algorithm iteratively removes the edge with the highest betweenness centrality from the graph. The process continues until there are no more edges to remove or until the maximum number of clusters has been reached. The clustering configuration with the highest quality achieved during the iterations will be returned.
The method requires specifying the maximum number of clusters to be returned. A smaller maximum value will generally result in faster computation time. The maximum number of clusters cannot exceed graph.Nodes.Count, the number of nodes in the graph. Additionally, the number of returned clusters will never be less than the number of connected components of the graph.
Parameters
- graph: LayoutGraph
- The input graph to be partitioned.
- resultClusterIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be populated with the cluster ID for each node. The key is a LayoutNode and the value is an integer representing the cluster ID.
- directed: boolean
- A indicating whether the graph should be considered directed (
true) or undirected (false). - minimumClusterCount: number
- The minimum number of clusters to be returned. This value should be at least as large as the number of connected components in the graph.
- maximumClusterCount: number
- The maximum number of clusters to be returned. Must be greater than zero and less than or equal to the number of nodes in the graph.
- edgeCosts: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that specifies positive costs for the edges, where the key is an LayoutEdge and the value is a representing the cost. If
null, all edges are considered to have equal cost.
Return Value
- number
- The number of clusters generated by the algorithm. This value will be between the minimum and maximum cluster count specified, inclusive.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown if any of the following conditions are met:
minimumClusterCount > maximumClusterCountminimumClusterCount > graph.Nodes.CountmaximumClusterCount <= 0
Complexity
O(graph.Edges.Count) * O(edgeBetweenness) The time complexity is O(graph.Edges.Count) * O(edgeBetweenness), where graph.Edges.Count represents the number of edges in the graph and edgeBetweenness denotes the time complexity of computing edge betweenness centrality. The actual runtime is often faster in practice because edge betweenness is computed only for subgraphs, and the algorithm stops once the maximum number of clusters has been reached.This method operates on instances of LayoutGraph. To perform edge-betweenness clustering on an IGraph instance, use EdgeBetweennessClustering instead.
In each iteration, the edge with the highest betweenness centrality is removed from the graph. The algorithm terminates when there are no more edges to remove or when the specified maximum number of clusters is reached. The clustering with the highest quality achieved during the process is returned.
The algorithm includes several heuristic speed-up techniques based on the quality/time ratio. For the highest quality setting, the algorithm runs with minimal modifications. For values around 0.5, it uses the fast betweenness approximation method of Brandes and Pich (Centrality Estimation in Large Networks), which offers a slight decrease in quality but a significant speed-up, and is the recommended setting. To achieve the lowest running time, a local betweenness calculation is used as described by Gregory in Local Betweenness for Finding Communities in Networks.
The method requires a maximum number of clusters to be returned. A smaller maximum value will generally result in faster computation times. The upper bound on the number of clusters is graph.Nodes.Count, and the number of clusters returned is always at least the number of connected components in the graph.
Parameters
- graph: LayoutGraph
- The input graph to be partitioned.
- resultClusterIds: IMapper<LayoutNode, number>
- The IMapper<K, V> that will be populated with cluster IDs. Each node in the graph will be assigned an integer cluster ID.
- qualityTimeRatio: number
- A value between
0.0(indicating lower quality but faster computation) and1.0(indicating higher quality but slower computation). The recommended value for a balance between quality and speed is0.5. - minimumClusterCount: number
- The minimum number of clusters to be returned. The resulting number of clusters will be at least this value.
- maximumClusterCount: number
- The maximum number of clusters to be returned. The number of clusters returned will not exceed this value.
- refine: boolean
- A boolean value indicating whether the algorithm should refine the current clustering solution. If
true, the algorithm will attempt to improve the existing clustering; iffalse, the current clustering will be discarded and a new clustering will be computed from scratch.
Return Value
- number
- The number of clusters produced by the algorithm. This value will be between
minimumClusterCountandmaximumClusterCountand will be at least the number of connected components in the graph.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown if any of the following conditions are met:
minimumClusterCount > maximumClusterCountminimumClusterCount > graph.Nodes.CountmaximumClusterCount <= 0
Complexity
O(graph.Edges.Count) * O(edgeBetweenness)
The time complexity is O(graph.Edges.Count) * O(edgeBetweenness), where graph.Edges.Count represents the number of edges in the graph and edgeBetweenness denotes the time complexity of computing edge betweenness centrality. In practice, the algorithm is faster due to the computation of edge betweenness for subgraphs and the fact that the algorithm terminates once maximumClusterCount clusters are determined.
Computes the eigenvector centrality for each node in the specified undirected graph.
This method calculates the eigenvector centrality for nodes in an instance of LayoutGraph. To compute eigenvector centrality for nodes in an IGraph instance, use EigenvectorCentrality instead.
Eigenvector centrality measures the influence of a node in a network by considering both the number and quality of its connections. Nodes with high eigenvector centrality are connected to other highly influential nodes. The centrality values are scaled so that the highest centrality value is 1.0.
Centrality quantifies the concept that some nodes in a network are "more central" than others. A higher centrality value indicates a more central node according to the algorithm.
null to indicate that a valid solution could not be found. For graphs where convergence is an issue, consider using the pageRank algorithm as an alternative.Parameters
- graph: LayoutGraph
- The undirected graph for which eigenvector centrality will be computed.
- precision?: number
- A double value specifying the precision used during the power iteration method for calculating eigenvector centrality. It represents the maximum allowable difference for considering two values as equal during the iteration process.
Return Value
- IMapper<LayoutNode, number>
- An IMapper<K, V> containing the eigenvector centrality values for each node, scaled within the interval
[0, 1]. Returnsnullif the power iteration method does not converge and no valid eigenvector could be computed.
Returns an IEnumerable<Edge> that contains all the edges that are part of at least one directed or undirected simple cycle in the given graph.
This method is designed to work with instances of LayoutGraph. To identify all cycle edges within an IGraph, consider using the CycleEdges method instead.
Self-loops in the graph are always considered to be cycle edges, regardless of whether the graph is directed or undirected.
Parameters
- graph: LayoutGraph
- The graph in which cycle edges are to be identified.
- directed: boolean
- A indicating whether the graph should be treated as directed. Pass
trueto consider the graph directed; otherwise, passfalseto treat it as undirected.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> that contains all the edges that are part of at least one directed or undirected simple cycle in the graph.
Returns the center node of the specified undirected tree.
The center node of a tree is the node that, when used as the root, minimizes the maximum depth of the tree. This node has the property of inducing the most balanced tree structure possible.
This method is designed to work with undirected trees. It assumes that the provided graph is a valid tree and that it is non-empty.
Parameters
- tree: LayoutGraph
- The graph representing the undirected tree from which to find the center node. This parameter must not be
null.
Return Value
- LayoutNode
- The LayoutNode that is the center of the given undirected tree.
Returns an IEnumerable<Edge> that contains the edges of a cycle found in the given graph.
This method is specifically designed to work with instances of LayoutGraph. To detect a cycle in an IGraph, consider using the CycleEdges method instead.
The edges are returned in the order in which they appear within the detected cycle. If the cycle is empty, it indicates that no cycle was found in the provided graph.
If the graph is acyclic (contains no cycles), the returned IEnumerable<Edge> will be empty.
Parameters
- graph: LayoutGraph
- The graph in which a cycle is to be identified.
- directed: boolean
- A indicating whether the graph should be treated as directed. Pass
trueto consider the graph directed; otherwise, passfalseto treat it as undirected.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> containing the edges that form a cycle in the graph. If no cycle is found, an empty IEnumerable<Edge> is returned.
Complexity
O(graph.Edges.Count + graph.Nodes.Count)This method operates on instances of LayoutGraph. To detect feedback edges within an IGraph, consider using the FeedbackEdgeSet method instead.
The minimization of the cost is performed using heuristic approaches due to the computational complexity of finding an optimal solution for this problem, which is well-known to be NP-hard. Two heuristic methods are provided: a faster heuristic that offers quicker results, and a slower, higher-quality heuristic that typically results in fewer edges being marked as part of a cycle.
The cost associated with reversing an edge is specified using an IMapper<K, V> that maps each edge to a non-negative value.
Parameters
- graph: LayoutGraph
- The graph in which cycle edges are to be identified.
- resultCycleEdges: IMapper<LayoutEdge, boolean>
- An IMapper<K, V> instance that will be populated with the results of the operation. For each edge, the mapper returns
trueif the edge is identified as part of a cycle, andfalseotherwise. - resultCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> instance that holds the non-negative reversal cost for each edge. This parameter can be
nullif no cost information is required. - highQualityMode?: boolean
- A indicating whether to use the slower, higher-quality heuristic. Set to
trueto prioritize accuracy over speed; set tofalseto favor faster execution with potentially more edges marked as cycle edges.
Complexity
highQualityMode:O(graph.Edges.Count * graph.Edges.Count)whenhighQualityModeistrue.O(graph.Nodes.Count + graph.Edges.Count * log(graph.Nodes.Count))whenhighQualityModeisfalse.
Identifies and marks the edges of a given graph whose removal or reversal would render the graph acyclic, utilizing a depth-first search (DFS) approach.
This method is designed to work with instances of LayoutGraph. To determine feedback edges in an IGraph, consider using the FeedbackEdgeSet method instead.
Compared to the findCycleEdges method, this DFS-based approach may result in a slightly higher number of edges being identified as part of a cycle. However, the primary advantage of this method lies in its stability. The set of marked cycle edges is more consistent when edges are added to or removed from the graph over time.
Parameters
- graph: LayoutGraph
- The graph in which cycle edges are to be identified.
- resultCycleEdges: IMapper<LayoutEdge, boolean>
- An IMapper<K, V> instance that will be populated during the execution of the method. For each edge, the mapper returns
trueif the edge is detected as part of a cycle, andfalseotherwise.
Complexity
O(graph.Edges.Count + graph.Nodes.Count)Finds intersections between graph items or a subset of graph items in the specified graph.
The method is designed for use with instances of LayoutGraph. For operations involving intersections in an IGraph, use the Intersections class.
This method identifies intersections where one or more items from the affectedItems list are involved. It excludes intersections that only involve items not specified in the list. If the affectedItems list is empty or if the items are excluded due to the intersectionItemType setting, the result will not include any intersections.
The intersectionItemType parameter determines which types of graph items to consider for intersection detection. It can include types such as LayoutNode, LayoutEdge, LayoutNodeLabel, and LayoutEdgeLabel.
Parameters
- graph: LayoutGraph
- The graph in which intersections are to be detected.
- intersectionItemType: IntersectionItemTypes
- Specifies the type(s) of graph items to consider when finding intersections.
- affectedItems?: IEnumerable<any>
- An optional collection of items that must be involved in each intersection. This can include instances of LayoutNode, LayoutEdge, LayoutNodeLabel, and LayoutEdgeLabel. If omitted, all items in the graph are considered for intersection detection.
Return Value
- IEnumerable<LayoutGraphIntersection>
- An IEnumerable<T> of LayoutGraphIntersection objects representing the detected intersections between graph items. The list may be empty if no intersections involving the
affectedItemsare found.
Returns all leaf nodes of the specified tree.
This method operates on instances of LayoutGraph. To retrieve leaf nodes from a directed tree represented by an IGraph, use the TreeAnalysis class.
A leaf node is defined as a node that has no children (outdegree == 0) if the tree is directed, or a node with exactly one connection (degree == 1) if the tree is undirected.
Parameters
- tree: LayoutGraph
- The graph representing the tree from which leaf nodes are to be retrieved.
- directed?: boolean
- A boolean value indicating whether the tree should be treated as directed. Set to
trueif the tree is directed, orfalseif the tree is undirected.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNode objects representing all leaf nodes in the specified tree.
Finds and returns the multi-edges in the specified graph or incident to a specific node.
Multi-edges are defined as edges that connect the same two nodes. In directed graphs, multi-edges must have the same source and target nodes to be considered multi-edges of each other.
If the node parameter is provided, the method returns only the multi-edges that are incident to the specified node. If node is null, the method returns all multi-edges in the entire graph.
Parameters
- graph: LayoutGraph
- The graph in which to search for multi-edges.
- directed: boolean
trueto consider edge direction when identifying multi-edges;falseto consider only the nodes connected by the edges, regardless of direction.- node?: LayoutNode
- The node to which the multi-edges must be incident. If this parameter is
null, the method returns all multi-edges in the graph. This parameter is optional.
Return Value
- IEnumerable<LayoutEdge>
- An array of IEnumerable<T> collections, where each collection contains a set of multi-edges. If no multi-edges are found, an empty array is returned.
Sample Graphs
Determines the set of nodes that are reachable from a specified starting node, considering edges that cannot be traversed.
This method operates on instances of LayoutGraph. To determine node reachability in an IGraph instance, use Reachability instead.
The reachability is determined using a depth-first search (DFS) approach. Nodes that can be reached from the starting node are those that are reachable through a path that does not include any of the forbidden edges.
Parameters
- graph: LayoutGraph
- The input graph in which reachability is to be determined.
- start: LayoutNode
- The node from which the search starts. This node must be part of the graph.
- isDirected: boolean
- A boolean value indicating whether the edges should be considered as directed. Pass
trueif the edges are directed and should be traversed from source to target; passfalseif the edges are undirected and can be traversed in both directions.
Return Value
- IMapper<LayoutNode, boolean>
- An IMapper<K, V> where the key is a LayoutNode and the value is a . The value is
trueif the node can be reached from the starting node during the DFS; otherwise, it isfalse.
Returns a possible root node for the specified (undirected) tree.
This method is intended for use with instances of LayoutGraph. To determine the root of a directed tree in an IGraph, consider using the TreeAnalysis class.
The method's behavior varies depending on the structure of the input graph:
- If the input is a directed rooted tree or a reversed directed rooted tree, the method returns the corresponding root node, which is the node from which all other nodes are reachable.
- If the input is an undirected tree, the method returns a node that serves as a maximum weight center node, as defined in findWeightedCenterNode. This node balances the tree by minimizing the maximum distance to all other nodes.
- If the input is not a valid tree, the method attempts to return a node with
indegree == 0oroutdegree == 0, indicating a node with no incoming or outgoing edges, respectively.
Parameters
- tree: LayoutGraph
- The graph representing the tree from which to determine a possible root node.
Return Value
- LayoutNode
- A LayoutNode that can serve as a root for the given tree.
Collects all nodes of the subtree rooted in the specified root node.
The method works with instances of LayoutGraph. If you need to retrieve a subtree from a directed tree in an IGraph, consider using the TreeAnalysis class instead.
This method populates the provided collection with all nodes that are part of the subtree rooted at the specified root node.
Parameters
- root: LayoutNode
- The LayoutNode that serves as the root of the subtree.
Return Value
- IEnumerable<LayoutNode>
- All nodes of the subtree rooted in the specified root node.
findTreeEdges
(graph: LayoutGraph, treeNodes?: IEnumerable<IEnumerable<LayoutNode>>): IEnumerable<LayoutEdge>staticRetrieves an array of IEnumerable<T> collections, where each collection contains the edges belonging to a maximal directed subtree of the specified graph.
findTreeEdges
(graph: LayoutGraph, treeNodes?: IEnumerable<IEnumerable<LayoutNode>>): IEnumerable<LayoutEdge>This method is intended for use with instances of LayoutGraph. If you need to analyze instances of IGraph, consider using TreeAnalysis instead.
Additionally, this method can be used with the output from findTreeNodes. When applied in this context, the subtrees are treated as undirected.
Parameters
- graph: LayoutGraph
- The graph to analyze.
- treeNodes?: IEnumerable<IEnumerable<LayoutNode>>
- Optional LayoutNode instances that were previously computed using findTreeNodes. If provided, the method will only consider edges connecting these nodes when identifying subtrees.
Return Value
- IEnumerable<LayoutEdge>
- An array of IEnumerable<Edge> collections, where each collection contains the edges belonging to a maximal subtree within the graph.
Calculates the nodes that belong to a maximal subtree of the specified graph, based on the directed parameter.
directed parameter.This method is intended for use with instances of LayoutGraph. To analyze instances of IGraph, consider using TreeAnalysis instead.
If directed is true, the method retrieves nodes belonging to maximal directed subtrees. In this case, for each collection of nodes returned, the first node in the collection is the root of the subtree, and all outgoing edges from this root node connect to other nodes within the same subtree. The root node will have an in-degree of at least two.
If directed is false, the method retrieves nodes belonging to maximal undirected subtrees. For each collection of nodes returned, the first node is the only node within the subtree that may be incident to edges not belonging to the subtree. This feature is useful for clearly defining the boundary of a subtree within the graph.
Parameters
- graph: LayoutGraph
- The graph to be analyzed.
- directed?: boolean
- A boolean value indicating whether to retrieve directed subtrees (
true) or undirected subtrees (false).
Return Value
- IEnumerable<LayoutNode>
- the nodes that belong to a maximal subtree of the specified graph, based on the
directedparameter.
Finds the node in the given (undirected) tree that is used by the greatest number of paths interconnecting all nodes.
This method identifies the node that lies on the maximum number of undirected paths connecting every pair of nodes in the tree. Such a node is considered a "weighted center" because it plays a central role in the tree's connectivity.
The number of paths traversing each node can optionally be stored in the provided IMapper<K, V> instance. If a mapper is supplied, it will be populated with the number of paths per node as calculated during the operation.
This method assumes that the input graph is a valid tree and is non-empty.
Parameters
- tree: LayoutGraph
- The graph representing the tree in which to find the weighted center node. This parameter must not be
null. - weights?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> instance for storing the number of paths passing through each node. If omitted, no path counts will be stored.
Return Value
- LayoutNode
- A LayoutNode that is used by the greatest number of undirected paths in the tree.
Computes the graph centrality for each node in the specified graph.
This method calculates graph centrality for nodes in an instance of LayoutGraph. To compute graph centrality for edges in an IGraph instance, use GraphCentrality instead.
Graph centrality is defined as the reciprocal of the maximum shortest path distance from a node to all other nodes in the graph. Nodes with higher graph centrality have shorter average distances to all other nodes, indicating greater connectivity within the network.
Centrality generally serves to quantify the concept that in most networks, some nodes are "more central" or influential than others. A higher centrality value suggests that a node is more central according to the algorithm.
Parameters
- graph: LayoutGraph
- The input graph for which graph centrality will be computed.
- directed?: boolean
- A boolean value indicating whether the graph should be treated as directed. Pass
trueif the graph is directed; otherwise, passfalse. - edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides positive double values representing the cost of each edge. If
edgeCostsis not specified, all edges are assumed to have equal cost.
Return Value
- IMapper<LayoutNode, number>
- An IMapper<K, V> that contains the graph centrality values for each node in the graph. The key is a LayoutNode, and the value is a representing the centrality of that node.
Complexity
O((graph.Nodes.Count * graph.Edges.Count) + graph.Nodes.Count^2)for unweighted graphs.O((graph.Nodes.Count * graph.Edges.Count) + graph.Nodes.Count^2 * log(graph.Nodes.Count))for weighted graphs.
Partitions the specified graph into clusters using hierarchical clustering.
This method is designed to work with instances of LayoutGraph. To perform hierarchical clustering on an IGraph, use the HierarchicalClustering method instead.
The hierarchical clustering algorithm employed here follows an agglomerative approach, which is a bottom-up strategy. Initially, each node is considered its own cluster. In each iteration, pairs of clusters are merged based on their dissimilarity, as determined by the specified linkage and distance metric, until all nodes are aggregated into a single cluster.
The result is returned as a HierarchicalClusteringDendrogram. This object represents the clustering result as a binary tree structure. To traverse the dendrogram, start at the root node and use getChildren to access subsequent levels.
distances callback returns a negative value for the distance between two nodes, a distance of zero will be used instead.Parameters
- graph: LayoutGraph
- The input graph to be clustered.
- distances: function(LayoutNode, LayoutNode): number
- A callback function used to compute the distance between any two nodes. The function should return a non-negative value representing the distance between the nodes.
- linkage: HierarchicalClusteringLinkage
- Specifies the linkage criterion to be used for merging clusters.
Return Value
- HierarchicalClusteringDendrogram
- A HierarchicalClusteringDendrogram representing the hierarchical clustering as a binary tree structure, or
nullif the provided graph is empty.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown if an unknown linkage value is provided.
Complexity
O(graph.Nodes.Count ^ 3)This method is designed to work with instances of LayoutGraph. To perform hierarchical clustering on an IGraph, use the HierarchicalClustering method instead.
The hierarchical clustering algorithm employed here follows an agglomerative approach, which is a bottom-up strategy. Initially, each node is considered its own cluster. In each iteration, pairs of clusters are merged based on their dissimilarity, as determined by the specified linkage and distance metric, until all nodes are aggregated into a single cluster.
The final result is based on the specified cut-off value, which determines where to cut the hierarchical tree. The cut-off value indicates the maximum dissimilarity allowed between nodes within the same cluster. Only clusters with a dissimilarity value less than or equal to the cut-off value will be formed.
distances callback returns a negative value for the distance between two nodes, a distance of zero will be used instead.Parameters
- graph: LayoutGraph
- The input graph to be clustered.
- resultClusterIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be populated with the cluster assignments during execution. It maps each node to a representing the ID of the cluster to which the node belongs.
- distances: function(LayoutNode, LayoutNode): number
- A callback function used to compute the distance between any two nodes. The function should return a non-negative value representing the distance between the nodes.
- linkage: HierarchicalClusteringLinkage
- Specifies the linkage criterion to be used for merging clusters.
- cutOff: number
- The cut-off value that determines where to cut the hierarchical tree into clusters.
Return Value
- number
- The number of clusters resulting from the hierarchical clustering operation.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown if an unknown linkage value is provided.
Complexity
O(graph.Nodes.Count ^ 3)This method is designed to work with instances of LayoutGraph. To perform hierarchical clustering on an IGraph, use the HierarchicalClustering method instead.
The hierarchical clustering algorithm employed here follows an agglomerative approach, which is a bottom-up strategy. Initially, each node is considered its own cluster. In each iteration, pairs of clusters are merged based on their dissimilarity, as determined by the specified linkage and distance metric, until all nodes are aggregated into a single cluster.
The final clusters are determined based on the specified maximum number of clusters. This value is used to cut the hierarchical tree at the appropriate level, resulting in the desired number of clusters.
distances callback returns a negative value for the distance between two nodes, a distance of zero will be used instead.Parameters
- graph: LayoutGraph
- The input graph to be clustered.
- maximumClusterCount: number
- The maximum number of clusters desired. This value determines where to cut the hierarchical tree to achieve the specified number of clusters. It must be greater than zero and less than the total number of nodes in the graph.
- resultClusterIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be populated with the cluster assignments during execution. It maps each node to a representing the ID of the cluster to which the node belongs.
- distances: function(LayoutNode, LayoutNode): number
- A callback function used to compute the distance between any two nodes. The function should return a non-negative value representing the distance between the nodes.
- linkage: HierarchicalClusteringLinkage
- Specifies the linkage criterion to be used for merging clusters.
Return Value
- number
- The number of clusters resulting from the hierarchical clustering operation. This number will be equal to or less than the specified
maximumClusterCountvalue.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown if an unknown linkage value is provided.
Complexity
O(graph.Nodes.Count ^ 3)Partitions the nodes of the specified graph into independent sets.
This method calculates independent sets for an instance of LayoutGraph. To partition an IGraph into independent sets, use IndependentSets instead.
An independent set is a set of nodes in which no two nodes are adjacent. The method partitions the graph into multiple independent sets such that every node in the graph belongs to exactly one set, and no two nodes in the same set are connected by an edge.
The method iteratively calls the maximalIndependentSet method to build the partition.
Parameters
- graph: LayoutGraph
- The input graph to be partitioned.
Return Value
- IEnumerable<LayoutNode>
- An array of independent sets. Each element of the array is an IEnumerable<T> of LayoutNodes, where each IEnumerable<T> represents a distinct independent set in the graph.
See Also
intersect
<TPlaneObject> (planeObjects: IEnumerable<TPlaneObject>, intersectionCallback: function(TPlaneObject, TPlaneObject): void)staticCalculates the intersections of plane objects and invokes a callback for each intersecting pair.
intersect
<TPlaneObject> (planeObjects: IEnumerable<TPlaneObject>, intersectionCallback: function(TPlaneObject, TPlaneObject): void)This method uses a sweep-line algorithm to determine the intersections between the given plane objects. The callback is invoked for each pair of objects that intersect, ensuring that client code can respond to these intersections accordingly.
Note that objects with negative dimensions are ignored and do not produce any intersections.
Parameters
- planeObjects: IEnumerable<TPlaneObject>
- An IEnumerable<T> of plane objects to be checked for intersections.
- intersectionCallback: function(TPlaneObject, TPlaneObject): void
- A callback action that is invoked for each pair of intersecting plane objects. The callback receives the two intersecting objects as parameters, allowing client code to handle the intersections as needed.
Complexity
O(n log n + s), where n is the number of plane objects, and s is the number of intersectionsDetermines whether the specified directed graph is acyclic.
This method works with instances of LayoutGraph. To determine whether an IGraph is acyclic use isAcyclic instead.
A graph is considered acyclic if it contains no directed cycles. A directed cycle is a path that starts and ends at the same node, with all edges following the direction of the graph.
IsAcyclic(graph) <=> !IsCyclic(graph).Parameters
- graph: LayoutGraph
- The graph to be checked for acyclicity.
Return Value
- boolean
trueif the graph is acyclic; otherwise,false.
Sample Graphs
Determines whether the specified undirected graph is biconnected.
This method checks if an instance of LayoutGraph is biconnected. To determine if an IGraph is biconnected, use isBiconnected instead.
A graph is considered biconnected if it is connected and does not contain any cut vertices (articulation points). In other words, removing any single vertex does not disconnect the graph.
Parameters
- graph: LayoutGraph
- The undirected graph to be checked.
Return Value
- boolean
trueif the graph is biconnected; otherwise,false.
Sample Graphs
Determines whether the specified graph is bipartite.
If you need to determine whether an instance of IGraph is bipartite, use the isBipartite method instead.
A graph is considered bipartite if its nodes can be divided into two disjoint sets such that every edge connects a node in one set to a node in the other set.
Parameters
- graph: LayoutGraph
- The graph to analyze.
Return Value
- boolean
trueif thegraphis bipartite; otherwise,false.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Sample Graphs
Determines whether the specified graph is connected.
This method checks if a graph, represented by an instance of LayoutGraph, is connected. For determining the connectivity of an IGraph instance, use isConnected instead.
A graph is considered connected if there is a path of edges between every pair of nodes in the graph. This means there are no isolated nodes or disjoint subgraphs; every node can be reached from every other node.
Parameters
- graph: LayoutGraph
- The graph to be checked for connectivity.
Return Value
- boolean
trueif the graph is connected; otherwise,false.
Sample Graphs
Determines whether the specified graph is a forest, which is defined as a graph whose connected components are either directed rooted trees or undirected trees.
This method is specifically designed for LayoutGraph instances. To determine whether an IGraph is a forest, use isForest instead.
A forest is a disjoint union of trees, meaning it consists of multiple connected components where each component must independently satisfy the properties of a tree.
If directed is true, the method checks if each connected component of the graph is a directed rooted tree. This means that within each component, there must be exactly one root node, and all other nodes must be reachable from this root through directed edges, with no cycles.
If directed is false, the method verifies that each component is an undirected tree, i.e., a connected acyclic subgraph with no directionality in the edges.
Parameters
- graph: LayoutGraph
- The graph to be analyzed.
- directed: boolean
- A boolean value indicating the type of trees to check for in the forest. Set to
trueto check for directed rooted trees; set tofalseto check for undirected trees.
Return Value
- boolean
trueif the graph is a forest as defined by thedirectedparameter; otherwise,false.
Sample Graphs
Determines whether the specified graph is a directed rooted tree where each node has at most maximumChildCount children.
maximumChildCount children.This method is specifically designed to work with instances of LayoutGraph. If you need to analyze an IGraph instance to check if it is an n-ary tree, consider using isNaryTree instead.
An n-ary tree is a rooted tree in which each node has no more than n children. This method verifies that the graph structure adheres to this property, ensuring it is both rooted and directed.
Parameters
- graph: LayoutGraph
- The graph to be checked.
- maximumChildCount: number
- The maximum number of children that any node in the tree is allowed to have.
Return Value
- boolean
trueif the graph is a directed rooted tree where each node has at mostmaximumChildCountchildren; otherwise,false.
Sample Graphs
3 childrenDetermines whether the specified graph is planar.
This method works with instances of LayoutGraph. To determine whether an IGraph is planar, use isPlanar instead.
A graph is considered planar if it can be drawn on a plane without any of its edges crossing.
Parameters
- graph: LayoutGraph
- The graph to be checked for planarity.
Return Value
- boolean
trueif the graph is planar; otherwise,false.
Sample Graphs
Determines whether the specified directed graph is simple.
This method works with instances of LayoutGraph. To determine whether an IGraph is simple, use isSimple instead.
A graph is considered simple if it does not contain any two distinct edges, e1 and e2, such that e1.Source == e2.Source && e1.Target == e2.Target. In other words, a simple graph does not have multiple edges between the same pair of nodes.
Parameters
- graph: LayoutGraph
- The directed graph to be checked for simplicity.
Return Value
- boolean
trueif the graph is simple; otherwise,false.
Sample Graphs
Determines whether the specified directed graph is strongly connected.
This method evaluates the strong connectivity of a graph represented by an instance of LayoutGraph. To check the strong connectivity of a graph represented by an IGraph instance, use isStronglyConnected instead.
A graph is considered strongly connected if there exists a directed path between every pair of nodes. In a strongly connected graph, it is possible to reach any node from any other node by following the directed edges.
Parameters
- graph: LayoutGraph
- The directed graph to be checked for strong connectivity.
Return Value
- boolean
trueif the graph is strongly connected; otherwise,false.
Sample Graphs
Determines whether the specified graph represents a tree, with an option to check for either a directed rooted tree or an undirected tree.
This method is applicable to instances of LayoutGraph. If analyzing instances of IGraph, consider using isTree for general tree checks.
A tree is defined as a connected, acyclic graph. The specific type of tree validated by this method depends on the value of the directed parameter:
- Directed Rooted Tree – If
directedistrue, the method checks whether the graph is a directed rooted tree. A directed rooted tree is a graph with exactly one root node, from which all other nodes are reachable through directed edges, and it contains no cycles. - Undirected Tree – If
directedisfalse, the method checks whether the graph is an undirected tree. An undirected tree is a connected, acyclic graph where edges have no direction.
Parameters
- graph: LayoutGraph
- The graph to be analyzed.
- directed?: boolean
- A boolean value indicating the type of tree to check for:
trueto check for a directed rooted tree, orfalseto check for an undirected tree.
Return Value
- boolean
trueif the graph is a tree that matches the specified criteria; otherwise,false.
Sample Graphs
Calculates the k-core for a given undirected input graph and specific k value.
k. This method computes and returns the nodes of the k-core corresponding to the given k value.Parameters
- graph: LayoutGraph
- The undirected input graph for which the k-core is to be calculated.
- k: number
- The minimum degree (k-core) required for a node to be included in the resulting subgraph components.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> containing the nodes that form the k-core. The list may be empty if no such k-core exists.
Complexity
O((graph.Nodes.Count + graph.Edges.Count) * log(graph.Nodes.Count)) and requires linear space.Calculates the k-cores of an undirected input graph and assigns the largest k-value to each node.
k. This method computes the k-core for varying values of k and stores the largest k for which a node is included in the k-core.k, the k-core of the graph consists of all nodes with a resultKValues greater than or equal to k.Parameters
- graph: LayoutGraph
- The undirected input graph for which the k-core is to be calculated.
- resultKValues: IMapper<LayoutNode, number>
- An IMapper<TKey, TValue> that will be populated with the largest k-value for which each node is included in the k-core.
Return Value
- number
- The largest
kfor which the k-core of the graph is not empty.
Complexity
O((graph.Nodes.Count + graph.Edges.Count) * log(graph.Nodes.Count)) and requires linear space.This method works with instances of LayoutGraph. To partition an IGraph using k-means clustering, use KMeansClustering instead.
The nodes of the graph will be partitioned into k clusters based on their positions, such that their distance from the cluster's centroid (mean) is minimized.
The distance between nodes and centroids can be defined using various metrics, including Euclidean distance, Euclidean squared distance, Manhattan distance, or Chebyshev distance.
The algorithm will iterate up to iterations times to achieve convergence. If the number of given centroids is less than k or if no centroids are provided, the algorithm will randomly initialize centroids for all clusters.
k exceeds the number of nodes in the graph, the number of clusters will be adjusted to 2.k or if no centroids are specified, the algorithm will initialize centroids randomly.Parameters
- graph: LayoutGraph
- The input graph to be partitioned.
- resultClusterIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be filled during the execution and will return an integer value representing the ID of the cluster to which each node belongs.
- nodePositions: IMapper<LayoutNode, Point>
- An IMapper<K, V> that provides a Point representing the current position of each node in the graph.
- distanceMetric: KMeansDistanceMetric
- The distance metric to use for clustering. It should be one of the predefined distance metrics, such as Euclidean, Euclidean squared, Manhattan, or Chebyshev distance.
- k: number
- The number of clusters to form. If
kis greater than the number of nodes in the graph, it will be adjusted to2. - iterations?: number
- The maximum number of iterations the algorithm will perform to achieve convergence. The default value is
100. - centroids?: Point[]
- An optional array of initial centroids for the clusters. If omitted or if fewer centroids are provided than the number of clusters, the algorithm will randomly initialize centroids for all clusters.
Return Value
- number
- The number of resulting (non-empty) clusters after the algorithm converges.
Complexity
O(graph.Nodes.Count * k * d * I), where k is the number of clusters, I is the maximum number of iterations, and d is the dimension of the points (typically 2 for 2D coordinates).Computes the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.
k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.This method computes the k shortest paths from the source node to the sink node in a directed graph. The paths are ranked by their total cost, with the first path being the shortest.
The graph must have non-negative edge costs, as provided by the edgeCosts mapper.
The results are returned as an IEnumerable<T> of IEnumerable<T>s of LayoutEdge objects, where each inner enumerable represents a path from source to sink.
simplePaths is set to true, the method will only return paths where no node is repeated. For directed acyclic graphs (DAGs), this has no impact on runtime. However, for cyclic graphs, ensuring paths are simple can significantly increase the runtime.k paths if there are not enough distinct paths between the source and sink nodes.Parameters
- graph: LayoutGraph
- The directed graph in which the shortest paths are to be computed.
- edgeCosts: IMapper<LayoutEdge, number>
- An IMapper<TKey, TValue> that returns the cost associated with traversing each edge in the graph.
- source: LayoutNode
- The node from which the paths should originate.
- sink: LayoutNode
- The target node to which the paths should lead.
- k: number
- A non-negative integer specifying the number of shortest paths to find. If
kis 0, the method returns an empty enumerable. - simplePaths?: boolean
- A boolean value indicating whether the returned paths should be simple, meaning no node is repeated within any path. Setting this to
truemay increase the runtime for graphs with cycles.
Return Value
- IEnumerable<IEnumerable<LayoutEdge>>
- An IEnumerable<T> of IList<T> objects, each representing one of the
kshortest paths fromsourcetosink. The paths are ordered by their total cost, from the shortest to the longest. If there are fewer thankpaths available, the enumerable contains only the available paths. If no path exists, an empty enumerable is returned.
Complexity
For directed acyclic graphs (DAGs) or non-simple paths: O(graph.Edges.Count + graph.Nodes.Count * log(graph.Nodes.Count) + k)
For simple paths in cyclic graphs: O(k * graph.Nodes.Count * ((graph.Edges.Count + graph.Nodes.Count) * log(graph.Nodes.Count)))
This method operates on instances of LayoutGraph. To partition an IGraph into clusters using label propagation, use LabelPropagationClustering instead.
The label propagation algorithm works by iteratively updating the label of each node. In each iteration, a node's label is set to the most frequent label among its neighbors. If there are multiple candidates with the same frequency, the algorithm randomly selects one. Nodes with the same label after convergence are considered to belong to the same community.
The weight of a neighbor's label is calculated as nodeWeight(neighbor) * edgeWeight((node, neighbor)). The overall weight of a label for a node is the sum of these weights for all neighbors that have the same label.
Initially, each node is associated with a label from the IMapper<K, V> initialLabels. Nodes with negative initial labels are ignored and may not have an initial label. Consequently, some nodes may end up without any label, in which case the method get of resultFinalLabels will return -1 for these nodes. If no initialLabels is provided, each node starts with a unique label.
If IMapper<K, V> edgeDirectedness is provided, the algorithm considers only a subset of neighbors when determining a node's label. Specifically, it includes only those neighbors connected by edges with the following properties:
- The edge's directedness is greater than
0.0and the edge is incoming (i.e., the node is the edge's target). - The edge's directedness is less than
0.0and the edge is outgoing (i.e., the node is the edge's source). - The edge's directedness is
0.0(i.e., the edge is considered undirected).
0.0.edgeDirectedness is not provided, the algorithm assumes all edges are undirected (i.e., have directedness 0.0).Parameters
- graph: LayoutGraph
- The undirected input graph on which the label propagation algorithm is applied.
- resultFinalLabels: IMapper<LayoutNode, number>
- The IMapper<K, V> that will return the integer labels of each node after the algorithm has been applied. Nodes without a label will have a value of
-1. - initialLabels?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> that specifies the initial integer labels for each node. Negative values indicate nodes without an initial label. If not provided, each node starts with a unique label.
- nodeWeights?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> that provides the weights for the nodes. If not specified, the algorithm assumes a default weight of
1.0for all nodes. - edgeWeights?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides the weights for the edges. If not specified, the algorithm assumes a default weight of
1.0for all edges. - edgeDirectedness?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that specifies the directedness of the edges. If not provided, the algorithm assumes that all edges are undirected (i.e., have directedness
0.0).
Return Value
- number
- The number of distinct communities detected in the graph.
Calculates an assignment of the graph nodes to layers, using the specified layering algorithm.
0 denotes the first layer.Parameters
- graph: LayoutGraph
- The graph whose nodes should be assigned to layers.
- layeringAlgorithm: ILayerAssigner
- The algorithm used to calculate the layer assignment.
- resultLayerIds: IMapper<LayoutNode, number>
- A mapping from nodes to their layer index that will be populated during the computation. The index
0denotes the first layer.
Return Value
- number
- The number of calculated layers by the specified layering algorithm
longestPath
(graph: LayoutGraph, edgeCosts?: IMapper<LayoutEdge, number>): IEnumerable<LayoutEdge>staticComputes the longest directed path in a given acyclic weighted graph.
longestPath
(graph: LayoutGraph, edgeCosts?: IMapper<LayoutEdge, number>): IEnumerable<LayoutEdge>This method works with instances of LayoutGraph. To find the longest path in an IGraph use LongestPath instead.
All edges of the graph have an integral cost associated with them. The longest path is defined as one of all directed paths within the graph for which the costs of all contained edges sum up to a maximum.
Parameters
- graph: LayoutGraph
- The directed acyclic input graph where the path will be computed.
- edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<TKey, TValue> instance that provides the cost for traversing each edge. The key is the edge, and the value is the cost of traversing that edge. If no mapper is provided, the method assumes all edges have a uniform cost.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> containing the edges of the longest directed path.
Calculates the longest path from a given node to all other nodes in a given directed acyclic graph.
Parameters
- graph: LayoutGraph
- The directed acyclic input graph where the longest path lengths will be calculated.
- source: LayoutNode
- The node for which the lengths are calculated
- edgeCosts: IMapper<LayoutEdge, number>
- An IMapper<K, V> that returns the costs of type double for each edge. The longest path is the path for which the sum of the costs is maximal.
Return Value
- IMapper<LayoutNode, number>
- An IMapper<K, V> that contains for each node in the graph the length of the longest directed path from the
sourceto that node.
Computes the edges of a heuristically long, undirected, simple path within the given graph.
The edges are returned in the order that they appear in the found path.
A heuristic is used for finding a path that is long. It is not guaranteed, however, that the returned path is actually the longest path within the given graph, since that is a well-known hard problem.
Parameters
- graph: LayoutGraph
- The input graph where the path will be computed.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> containing the edges of an undirected simple path.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)This method operates on instances of LayoutGraph. To partition an IGraph into clusters using the Louvain modularity method, use LouvainModularityClustering instead.
The Louvain modularity algorithm begins by assigning each node to its own community. It then iteratively moves nodes between communities to optimize the modularity locally. This process is repeated by merging smaller communities into single nodes and restarting the optimization until no further improvement in modularity is possible.
The community index for each node indicates the community to which the node belongs. Nodes that are not assigned to any community have an index of -1.
If no IMapper<K, V> for edge weights is provided, the algorithm assumes that all edges have a weight of 1.0 by default.
Parameters
- graph: LayoutGraph
- The input graph to analyze, represented as a LayoutGraph.
- resultCommunityIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be filled with the calculated community index for each node.
- edgeWeights?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that maps each edge to its weight. If this parameter is not provided, the algorithm defaults to a weight of
1.0for all edges.
Return Value
- number
- The number of communities detected in the graph.
Makes the given graph biconnected by inserting the minimum number of edges required.
This method transforms an undirected graph into a biconnected graph. A biconnected graph is one where removing any single vertex does not disconnect the graph. If the input graph is not already connected, this method will not work correctly.
The input graph is assumed to be undirected. If the graph is not connected, the method will not perform as expected, as it relies on the graph being connected.
Parameters
- graph: LayoutGraph
- The input undirected graph that needs to be made biconnected.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<T> of LayoutEdge objects representing the edges added to the graph to make it biconnected.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Modifies the specified graph by adding additional edges to make it fully connected.
The number of edges added will be equal to the number of disconnected components in the original graph minus 1. This ensures that all nodes are reachable from any other node in the graph.
A fully connected graph is one where there is a path between every pair of nodes. If the graph is already connected, no edges are added.
Parameters
- graph: LayoutGraph
- The input graph to be connected.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<T> containing the edges that were added to the graph to achieve connectivity. The edges are of type LayoutEdge.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Converts the specified undirected tree into a directed rooted tree with the given node as the root by reversing necessary edges.
This method transforms an undirected tree into a directed rooted tree where the specified root becomes the root node. It achieves this by reversing the direction of certain edges to ensure that all edges point away from the root. The method returns a list of all the edges that were reversed during the conversion.
If the root is not specified, the method selects a suitable root node automatically, typically one that would result in a balanced tree.
Parameters
- tree: LayoutGraph
- The graph representing the undirected tree to be converted. This parameter must not be
null. - root?: LayoutNode
- The LayoutNode to be used as the root of the resulting directed tree. If
null, a root node will be selected automatically.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<Edge> containing all edges that were reversed to achieve the directed rooted tree structure.
Calculates a maximal independent set for the specified graph.
This method calculates a maximal independent set for an instance of LayoutGraph. To partition an IGraph into independent sets, use IndependentSets instead.
An independent set is a set of nodes in which no two nodes are adjacent. This method uses a greedy heuristic to find a large independent set, but it may not necessarily find the largest possible independent set.
The provided graph should be simple, meaning it must not contain multi-edges or self-loops.
Parameters
- graph: LayoutGraph
- The input graph for which a maximal independent set will be computed.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNodes that represents a maximal independent set of nodes in the graph.
See Also
This method solves a maximum flow problem on a directed graph using the preflow-push algorithm. The graph is represented by an instance of LayoutGraph. If you need to solve a maximum flow problem on an instance of IGraph, use the MaximumFlow class instead.
The algorithm calculates the maximum possible flow from a source node to a sink node in the graph. The implementation is based on the method described in Mehlhorn, Näher: LEDA: A Platform for Combinatorial and Geometric Computing, Cambridge University Press, 2000, pp. 443-488.
Edges may have infinite capacity, represented by 0x7FFFFFFF.
Parameters
- graph: LayoutGraph
- The directed graph representing the network.
- source: LayoutNode
- The source node in the network.
- sink: LayoutNode
- The sink node in the network.
- edgeCapacities: IMapper<LayoutEdge, number>
- An IMapper<K, V> that provides the capacity for each edge.
0x7FFFFFFFdenotes infinite capacity. - resultFlows?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that will be filled with the computed flow for each edge during execution. If omitted, a new mapper will be created.
Return Value
- number
- The value of the maximum flow from the source to the sink.
Complexity
O(mdeg * n^2 * m^(1/2)), where n is graph.Nodes.Count, m is graph.Edges.Count, and mdeg is the maximum degree of any node.See Also
The graph is represented by an instance of LayoutGraph. If you need to solve this problem on an instance of IGraph, use the MaximumFlow class instead.
This method extends the maximumFlow method by also identifying the minimum cut set associated with the source node in the network.
Parameters
- graph: LayoutGraph
- The directed graph representing the network.
- source: LayoutNode
- The source node in the network.
- sink: LayoutNode
- The sink node in the network.
- edgeCapacities: IMapper<LayoutEdge, number>
- An IMapper<K, V> that provides the capacity for each edge.
0x7FFFFFFFdenotes infinite capacity. - resultFlows?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that will be filled with the computed flow for each edge during execution. If omitted, a new mapper will be created.
- resultSourceCuts?: IMapper<LayoutNode, boolean>
- An optional IMapper<K, V> that will be filled with a boolean value for each node, indicating whether the node belongs to the minimum cut set associated with the source node. If omitted, a new mapper will be created.
Return Value
- number
- The value of the maximum flow from the source to the sink.
See Also
API
- maximumFlow
This method solves a minimum-cost flow problem on a directed graph using the capacity scaling algorithm. The graph is represented by an instance of LayoutGraph. If you need to solve a minimum-cost flow problem on an instance of IGraph, use the MinimumCostFlow class instead.
The algorithm calculates the flow with the minimum total cost that satisfies the edge capacities and node balances. Each edge in the graph has a cost and a capacity, while each node has a supply or demand.
The implementation is based on the successive shortest path algorithm as described in Ahuja, Magnanti, Orlin: Network Flows, Prentice Hall, 1993, pp. 320-324.
Edges may have infinite capacity, represented by 0x7FFFFFFF. Costs can be positive or negative.
Parameters
- graph: LayoutGraph
- The directed graph representing the network.
- maximumCapacities: IMapper<LayoutEdge, number>
- An IMapper<K, V> that provides the upper capacity bound for each edge.
- edgeCosts: IMapper<LayoutEdge, number>
- An IMapper<K, V> that provides the cost associated with each edge.
- supplies: IMapper<LayoutNode, number>
- An IMapper<K, V> that provides the supply or demand at each node. A positive value denotes supply, while a negative value denotes demand.
- resultFlows?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that will be filled with the computed flow for each edge during the execution. If omitted, a new mapper will be created.
- resultDuals?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> that will be filled with the dual values (potentials) for each node. If omitted, no dual values will be computed.
- minimumCapacities?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides the lower capacity bound for each edge. If omitted, no lower bound will be applied.
Return Value
- number
- The total cost of the computed flow.
Complexity
O(m*log U*(m+n log n)), where n is graph.Nodes.Count, m is graph.Edges.Count, and U is the maximum edge capacity.minimumSpanningTree
(graph: LayoutGraph, edgeCosts?: IMapper<LayoutEdge, number>): IEnumerable<LayoutEdge>staticCalculates the minimum spanning tree (MST) for the given undirected connected graph.
minimumSpanningTree
(graph: LayoutGraph, edgeCosts?: IMapper<LayoutEdge, number>): IEnumerable<LayoutEdge>This method is specifically designed for use with instances of LayoutGraph. For finding a minimum spanning tree of an IGraph, use SpanningTree instead.
A spanning tree of an undirected connected graph is a subset of its edges that connects all nodes in the graph without any cycles. In other words, it forms a tree that includes every vertex of the graph.
A minimum spanning tree is a spanning tree where the total cost of its edges is minimized. The cost of an edge is determined by the edgeCosts mapper. If no costs are provided, the method assumes a uniform cost for all edges.
The method uses Kruskal's algorithm to compute the MST. This algorithm sorts all edges and adds them one by one to the growing spanning tree, ensuring no cycles are formed, until all nodes are connected.
Parameters
- graph: LayoutGraph
- The undirected connected graph for which the minimum spanning tree is to be computed.
- edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides the cost for each edge in the graph. If
nullor if no costs are provided, a uniform cost of1is assumed for all edges.
Return Value
- IEnumerable<LayoutEdge>
- An IEnumerable<T> of LayoutEdge objects that form the edges of the minimum spanning tree.
Complexity
graph.Edges.Count * log(graph.Nodes.Count)Modularity measures the strength of the division of a graph into communities. It quantifies the density of edges within communities compared to the edges between communities. The modularity value ranges from -0.5 to 1. A higher modularity value indicates that the graph has a better community structure, where nodes within the same community have dense connections, while nodes in different communities have sparser connections.
To compute the modularity, an IMapper<K, V> communityIds is required, which provides an integer community index for each node. Nodes with the same index are assigned to the same community.
If the edgeWeights parameter is not specified, the algorithm assumes that all edges have an equal weight of 1.0. If all edges have a weight of 0.0, the computed modularity will be 0.0.
Parameters
- graph: LayoutGraph
- The graph for which the modularity is to be computed.
- communityIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that provides a community index for each node. Nodes with the same index belong to the same community.
- edgeWeights?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that maps each edge to a double value representing its weight. If not provided, all edges are assumed to have a weight of
1.0.
Return Value
- number
- The modularity value of the graph based on the provided community partition.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown if
graphorcommunityIdsisnull. - Exception ({ name: 'ArgumentError' })
- Thrown if
communityIdsisnullor ifcommunityIdsis not valid for the nodes in the graph.
See Also
Finds the nearest common ancestor of a subset of nodes within a directed rooted tree.
The method works with instances of LayoutGraph. For determining the nearest common ancestor of nodes in a directed tree within an IGraph, use the TreeAnalysis class instead.
This method determines the nearest common ancestor (NCA) of a given subset of nodes within a directed rooted tree. The NCA is defined as the deepest node in the tree that is an ancestor of all nodes in the subset.
The returned NCA is not part of the given subset of nodes but is the highest node in the tree hierarchy that is an ancestor to all nodes in the subset.
Parameters
- tree: LayoutGraph
- The graph representing the directed rooted tree.
- root: LayoutNode
- The LayoutNode representing the root of the tree.
- rootedDownward: boolean
- A boolean value indicating whether the tree is directed from the root to the leaves (
true), or from the leaves to the root (false). - nodes: IEnumerable<LayoutNode>
- An IEnumerable<Node> representing the subset of nodes for which the nearest common ancestor is to be found.
Return Value
- LayoutNode
- The LayoutNode representing the nearest common ancestor of the given subset of nodes, or
nullif no common ancestor is found.
Complexity
O(tree.Nodes.Count)Determines the direct and indirect neighbors of a given set of nodes in the specified graph.
This method works with instances of LayoutGraph. To determine direct and indirect neighbors of nodes in an IGraph instance, use neighbors (for direct neighbors only) or Neighborhood instead.
- Direct neighbors of a node are nodes that are directly connected by an edge to that node.
- Indirect neighbors are nodes that are directly connected to any direct or indirect neighbor of the node in question.
The order of the returned nodes is determined by a breadth-first search. The start nodes themselves will not be included in the resulting set.
The maximumDistance parameter limits the distance between the start nodes and the returned nodes. Only nodes that are reachable from a start node within the specified distance will be included in the result.
Setting maximumDistance to 1 will yield only the direct neighbors of all start nodes. Setting it to graph.Nodes.Count or larger will return all reachable nodes from the start nodes.
Parameters
- graph: LayoutGraph
- The graph in which to determine the neighbors.
- startNodes: IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNodes representing the nodes from which the search starts.
- maximumDistance: number
- An integer value specifying the maximum distance between a start node and a returned node. Nodes reachable within this distance from any start node will be included in the result.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNodes containing all direct and indirect neighbors of the start nodes.
Computes the betweenness centrality for each node in the specified graph.
This method calculates betweenness centrality for nodes in an instance of LayoutGraph. To compute betweenness centrality for nodes and edges in an IGraph instance, use BetweennessCentrality instead.
Betweenness centrality measures the extent to which a node lies on the shortest paths between other nodes in the graph. Nodes with high betweenness centrality have more influence over the flow of information in the network, as they lie on many shortest paths.
Centrality quantifies the concept that some nodes or edges in a network are "more central" than others. A higher centrality value indicates a more central node according to the algorithm.
Parameters
- graph: LayoutGraph
- The input graph for which betweenness centrality will be computed.
- directed?: boolean
- A boolean value indicating whether the graph should be treated as directed. Pass
trueif the graph is directed; otherwise, passfalse. - edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides positive double values representing the cost of each edge. If
edgeCostsis not specified, all edges are considered to have equal cost. For invalid or missing values, the algorithm will assume a default cost of1.0.
Return Value
- IMapper<LayoutNode, number>
- An IMapper<K, V> that contains the betweenness centrality values for each node in the graph. The key is a LayoutNode, and the value is a representing the centrality of that node.
Complexity
O(graph.Nodes.Count * graph.Edges.Count)for unweighted graphs.O(graph.Nodes.Count * (graph.Edges.Count + graph.Nodes.Count) * log(graph.Nodes.Count))for weighted graphs.
Computes the betweenness centrality for each node and edge in the specified graph.
This method calculates betweenness centrality for both nodes and edges in an instance of LayoutGraph. To compute betweenness centrality for nodes and edges in an IGraph instance, use BetweennessCentrality instead.
Betweenness centrality measures how often a node or edge lies on the shortest paths between all pairs of nodes in the graph. Nodes and edges with high betweenness centrality are critical for maintaining the connectivity and flow of information within the network. Removing a central node or edge will significantly alter many shortest paths in the graph.
Centrality quantifies the concept that some nodes or edges are "more central" to the network than others. A higher centrality value indicates a more central node or edge according to the algorithm.
Parameters
- graph: LayoutGraph
- The input graph for which betweenness centrality will be computed.
- directed?: boolean
- A boolean value indicating whether the graph should be treated as directed. Pass
trueif the graph is directed; otherwise, passfalse. - edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides positive double values representing the cost of each edge. If
edgeCostsis not specified, all edges are assumed to have equal cost. For invalid or missing values, the algorithm will assume a default cost of1.0.
Return Value
- IMapper<LayoutGraphItem, number>
- An IMapper<K, V> that contains the betweenness centrality values for each node and each edge in the graph. The key is a LayoutGraphItem (which could be a node or an edge), and the value is a representing the centrality of that item.
Complexity
O(graph.Nodes.Count * graph.Edges.Count)for unweighted graphs.O(graph.Nodes.Count * (graph.Edges.Count + graph.Nodes.Count) * log(graph.Nodes.Count))for weighted graphs.
This method calculates PageRank for nodes in an instance of LayoutGraph. To compute PageRank for nodes in an IGraph instance, use PageRank instead.
The PageRank algorithm, originally proposed by Sergey Brin and Lawrence Page, assigns a rank to each node based on its importance. The rank is propagated through the graph's edges, considering edge weights, node weights, and the direction of edges if specified.
S. Brin and L. Page. The anatomy of a large-scale hypertextual Web search engine.
Computer Networks and ISDN Systems, 30(1-7):107-117
1998.
The algorithm initializes each node's rank (see IMapper<K, V> initialPageRanks if provided). It then iteratively propagates rank values to successor nodes. The base factor for propagation is 1, which is scaled by edge weights (provided by edgeWeights) and node weights (provided by nodeWeights, if specified).
After propagation, ranks are scaled so that their total sum equals 1. Nodes with no successors distribute their rank among all nodes based on their weights (see nodeWeights). A damping factor ensures that a portion of each node's rank is distributed to all nodes, not just its successors.
The algorithm terminates when the relative change in each node's PageRank (computed as (newRank - oldRank) / oldRank) is below the specified precision or the maximum number of iterations is reached.
The edgeDirectedness IMapper<K, V> specifies the direction of edges, affecting how ranks are propagated. Edges with a positive directedness value propagate rank from source to target (this is the default if edgeDirectedness is null). Edges with a directedness of 0 are treated as undirected, propagating rank in both directions. Edges with negative directedness propagate rank from target to source.
0 and 1. A value of 0 means all of a node's rank is distributed to all nodes based on their weight, while a value of 1 means all of the rank is only distributed among its successors.initialPageRanks is omitted, the algorithm assumes an initial PageRank of 1.0 for all nodes.edgeDirectedness is omitted, the algorithm assumes all edges are directed from source to target with a directedness of 1.0.Parameters
- graph: LayoutGraph
- The graph for which PageRank values will be computed.
- resultPageRanks: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be populated with the PageRank value for each node.
- initialPageRanks?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> specifying the initial PageRank for each node. If
null, the algorithm assumes an initial rank of1.0for all nodes. - nodeWeights?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> specifying the weight for each node. If
null, the algorithm assumes a weight of1.0for all nodes. - edgeWeights?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> specifying the weight for each edge. If
null, the algorithm assumes a weight of1.0for all edges. - edgeDirectedness?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> specifying the directedness of each edge. If
null, the algorithm assumes all edges are directed from source to target with a directedness of1.0. - dampingFactor?: number
- A value between
0and1that determines the fraction of a node's rank distributed to its successors. A common default value is0.85. - precision?: number
- The non-negative precision threshold for the convergence of PageRank values. A common default value is
0.001.
Return Value
- number
- The sum of all node ranks after convergence.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Determines the direct and indirect predecessors of a specified list of nodes in the given graph.
This method operates on instances of LayoutGraph. For determining direct and indirect predecessors of nodes in an IGraph instance, use predecessors (for direct predecessors only) or Neighborhood instead.
- Direct predecessors of a node are the nodes from which there is an incoming edge to the node.
- Indirect predecessors are the nodes that are direct predecessors of other predecessors of the node.
The order of the returned nodes is determined by a breadth-first search. The start nodes themselves will not be included in the result.
The maximumDistance parameter limits the distance between a start node and the returned nodes. Only nodes that have a path to a start node with a length equal to or smaller than maximumDistance will be included in the result.
Setting maximumDistance to 1 will return only the direct predecessors of the start nodes. Setting maximumDistance to graph.Nodes.Count or higher will return all predecessors within the specified distance.
Parameters
- graph: LayoutGraph
- The graph in which to determine the predecessors.
- startNodes: IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNode objects representing the nodes from which the search starts.
- maximumDistance: number
- An integer specifying the maximum distance between a start node and a returned node. Nodes are included in the result if they have a path to any start node with a length equal to or less than this distance.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNode objects that includes all direct and indirect predecessors of the start nodes.
Computes the shortest path from a single source node to a single sink node in a graph.
This method works with instances of LayoutGraph. To find the shortest paths between two nodes in an IGraph use ShortestPath instead.
Each edge in the graph is associated with a non-negative double value that represents the traversal cost of the edge.
If the method returns an empty path, it indicates that there is no valid path between the specified source and sink nodes.
It is important to note that the edge costs provided should always be non-negative to ensure correct behavior of the algorithm.
directed is set to false, the graph is treated as undirected, meaning each edge can be traversed in both directions. Consequently, the shortest path may include edges traversed in the reverse direction.Parameters
- graph: LayoutGraph
- The graph in which the shortest path should be computed.
- source: LayoutNode
- The node from which the path search should start.
- sink: LayoutNode
- The destination node where the path search should end.
- directed?: boolean
- A boolean value indicating whether the graph should be treated as directed (
true) or undirected (false). - edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<TKey, TValue> instance that provides the cost for traversing each edge. The key is the edge, and the value is the cost of traversing that edge. If no mapper is provided, the method assumes all edges have a uniform cost.
- heuristicCosts?: IMapper<LayoutNode, number>
- An optional array of heuristic cost estimates for each node, used to improve the efficiency of the pathfinding algorithm. The value at index
nrepresents the estimated cost to reach the sink node from noden. If no array is provided, the method assumes a heuristic cost of zero for all nodes.
Return Value
- IEnumerable<LayoutEdge>
- The shortest path as an IEnumerable<T> of LayoutEdge objects, representing the sequence of edges from the source node to the sink node. If no path is found, the returned collection is empty.
Definition of the Rank Assignment Problem
Given a directed acyclic graph G = (V, E), where length(e) denotes the minimum length and weight(e) denotes the weight of an edge e, the rank assignment problem is to find integer values rank(v) for each vertex v in V such that:
rank(v) - rank(w) ≥ length(v, w)for all edges(v, w)inE, and- The sum
∑(weight(v, w) * (rank(v) - rank(w)))over all edges(v, w)inEis minimized.
This method assigns a minimum rank to the nodes in an acyclic graph, aiming to minimize the weighted sum of rank differences while satisfying the length constraints.
Although the theoretical time complexity of this algorithm is not proven to be polynomial, it typically converges quickly in practice and runs efficiently with a limited number of iterations.
The algorithm is based on the technique described in:
- E.R. Gansner et al., A Technique for Drawing Directed Graphs, IEEE Transactions on Software Engineering, Vol. 19, No. 3, March 1993.
Ensure that minimum edge lengths and weights are non-negative for valid results.
This method works with instances of LayoutGraph. To solve the rank assignment problem for an IGraph use RankAssignment instead.
Parameters
- graph: LayoutGraph
- The directed acyclic graph (DAG) for which the rank assignment is to be computed.
- resultLayerIds: IMapper<LayoutNode, number>
- An IMapper<K, V> that will be populated with the zero-based ranking index for each node upon successful completion.
- weights: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides integer values representing the weight of each edge. If
null, default weights are assumed. - minimumLengths: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides integer values representing the minimum length of each edge. If
null, default lengths are assumed. - stopDuration?: TimeSpan
- An optional TimeSpan specifying a time limit for the algorithm's execution. If omitted, no time limit is imposed.
- treeEdges?: IMapper<LayoutEdge, boolean>
- An optional IMapper<K, V> that returns
trueif the edge is a tree edge, orfalseotherwise. If omitted, the algorithms calculates a spanning tree itself. - root?: LayoutNode
- An optional LayoutNode representing the root node of the tree solution. If
null, no specific root is assumed. - validRanking?: boolean
- A indicating whether the
resultLayerIdscontains a valid ranking upon completion.
Return Value
- number
- The number of layers in the resulting rank assignment. This value represents the depth of the layered ranking of the nodes.
This method works with instances of LayoutGraph. To find the shortest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths instead.
The graph can be treated as directed or undirected, depending on the value of the directed parameter.
Each edge is associated with a cost, represented by a non-negative double value. The method fills the provided mappers with the computed shortest distances and the corresponding predecessor edges.
directed is set to false, the graph is treated as undirected, meaning each edge can be traversed in both directions. Consequently, the shortest paths may include edges traversed in the reverse direction.Parameters
- graph: LayoutGraph
- The graph in which the shortest paths are to be computed.
- source: LayoutNode
- The node from which the shortest paths are calculated.
- directed?: boolean
- A boolean value indicating whether the graph should be treated as directed (
true) or undirected (false). - edgeCosts?: IMapper<LayoutEdge, number>
- An optional IMapper<TKey, TValue> that returns the cost of traversing each edge. If no mapper is provided, the method assumes all edges have a uniform cost.
- resultDistances?: IMapper<LayoutNode, number>
- An IMapper<TKey, TValue> that will be populated with the shortest distance from the
sourcenode to every other node. If a node is unreachable, the corresponding value will be Number.POSITIVE_INFINITY. - resultPredecessorEdges?: any
- An IMapper<TKey, TValue> that will be populated with the predecessor edge for each node on the shortest path from the
sourcenode. For thesourcenode itself or if no path exists, the value will benull.
Return Value
- boolean
trueif the graph does not contain any negative-cost cycles; otherwise,false.
Identifies and returns a collection of Substructure instances representing the star structures within the specified graph that contain at least minimumSize nodes.
minimumSize nodes.A star is defined as a subgraph where a central root node is connected to multiple other nodes, each with a degree of one.
Since a star only includes elements with the same edgeDirectedness and nodeTypes, it is possible for a root node to be associated with multiple stars. In such cases, the algorithm returns only the largest star associated with that root.
The directedness of the edges, specified by the edgeDirectedness parameter, is considered when identifying star substructures. A valid star is one where all edges are either undirected or consistently directed according to the specified directedness.
The edgeDirectedness parameter is interpreted as follows:
- A value of
1indicates that the edge is directed from source to target. - A value of
-1indicates that the edge is directed from target to source. - A value of
0indicates that the edge is undirected (the default for edges mapped tonull).
edgeDirectedness is not specified, all edges are treated as undirected. Similarly, if nodeTypes is not specified, all nodes are considered to be of the same type.Parameters
- graph: LayoutGraph
- The graph from which star structures are to be identified.
- minimumSize: number
- The minimum number of degree-one nodes required for a subgraph to be considered a star. Subgraphs with fewer nodes are ignored. The smallest value allowed for this parameter is
2. - nodeTypes?: IMapper<LayoutNode, any>
- An optional IMapper<TKey, TValue> mapping each LayoutNode to its type. Nodes that map to the same object are considered to be of the same type. If this parameter is not provided, all nodes are considered to be of the same type.
- edgeDirectedness?: IMapper<LayoutEdge, number>
- An optional IMapper<TKey, TValue> mapping each LayoutEdge to a nullable representing its directedness. If this parameter is not provided, all edges are treated as undirected.
Return Value
- IEnumerable<Substructure>
- A list of Substructure instances representing the identified star structures in the graph.
Assigns an st-ordering to the nodes of a biconnected graph, given an edge between the source node s and the sink node t.
st-ordering to the nodes of a biconnected graph, given an edge between the source node s and the sink node t.An st-ordering (v_1, v_2, ..., v_n) of a biconnected graph is a specific ordering of nodes that satisfies the following conditions:
- The source node
sand the sink nodetare connected by an edge. - For every node
v_iin the ordering, other thansort, there exist neighboring nodesv_jandv_ksuch thatj < iandk > i.
This ordering is useful in graph drawing algorithms and other applications where a specific traversal order of nodes is required.
Parameters
- graph: LayoutGraph
- The input graph, which must be a biconnected graph.
- stEdge?: LayoutEdge
- The LayoutEdge connecting the source node
sand the sink nodet. This edge defines the start and end points of thest-ordering. If no edge is defined, a random edge that is not a self-loop will be used.
Return Value
Complexity
O(graph.Nodes.Count + graph.Edges.Count)stronglyConnectedComponents
(graph: LayoutGraph, resultComponentIds?: IMapper<LayoutNode, number>): IEnumerable<LayoutNode>staticCalculates the strongly connected components of the specified graph and returns the total number of components.
stronglyConnectedComponents
(graph: LayoutGraph, resultComponentIds?: IMapper<LayoutNode, number>): IEnumerable<LayoutNode>This method identifies the strongly connected components within an instance of LayoutGraph. To determine strongly connected components in an instance of IGraph, use StronglyConnectedComponents instead.
A graph is considered strongly connected if there exists a directed path between every pair of nodes within the graph. The strongly connected components of a graph are its maximal subgraphs in which every pair of nodes is mutually reachable.
Parameters
- graph: LayoutGraph
- The input graph for which strongly connected components will be calculated.
- resultComponentIds?: IMapper<LayoutNode, number>
- An optional IMapper<K, V> that will be populated during the execution of the method. This mapper will return the zero-based index of the strongly connected component to which each node belongs.
Return Value
- IEnumerable<LayoutNode>
- An array of strongly connected components, where each component is represented as an IEnumerable<T> of LayoutNode objects contained within that component.
Complexity
O(graph.Nodes.Count + graph.Edges.Count)Calculates and returns the depths of each subtree within a rooted directed tree.
The method works with instances of LayoutGraph. For similar operations on directed trees in an IGraph, use the TreeAnalysis class.
This method computes the depth of the subtree rooted at each node in a directed tree. The depth of a subtree is defined as the number of edges in the longest path from the root of that subtree to any of its leaf nodes. The depths are returned as a mapping, where the key is the node, and the value is the depth of the subtree rooted at that node.
Parameters
- tree: LayoutGraph
- The graph representing the rooted directed tree.
Return Value
- IMapper<LayoutNode, number>
- A mapping from nodes to the depths of the subtrees rooted in that node.
Calculates and returns the size (number of nodes) of each subtree within a rooted directed tree.
The method is designed for use with instances of LayoutGraph. For similar operations on directed trees in an IGraph, use the TreeAnalysis class.
This method computes the size of the subtree rooted at each node in a directed tree. The size of a subtree is defined as the total number of nodes contained in that subtree, including the root node of the subtree itself. The sizes are returned as a mapping, where the key is the node, and the value is the size of the subtree rooted at that node.
Parameters
- tree: LayoutGraph
- The graph representing the rooted directed tree.
Return Value
- IMapper<LayoutNode, number>
- A mapping from nodes to the size of the subtrees rooted in that node.
Determines the direct and indirect successors of a specified list of nodes in the given graph.
This method operates on instances of LayoutGraph. To determine direct and indirect successors of nodes in an IGraph instance, you can use successors (for direct successors only) or Neighborhood instead.
- A direct successor of a node is any node that is the target of an outgoing edge from the start node.
- An indirect successor is a node that is reachable through one or more direct successors, i.e., it is a successor of a direct successor.
The nodes are returned in the order determined by a breadth-first search. The start nodes themselves will not be included in the resulting set.
The maximumDistance parameter controls the maximum distance between a start node and the returned nodes. Only nodes that are within this distance (or path length) from any start node will be included.
Setting maximumDistance to 1 will return only the direct successors of the start nodes. Setting it to a value equal to or greater than graph.Nodes.Count will include all reachable successors of the start nodes, effectively encompassing all nodes in the graph reachable within that distance.
Parameters
- graph: LayoutGraph
- The graph in which to determine the successors.
- startNodes: IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNodes that specifies the nodes from which the search begins.
- maximumDistance: number
- An integer that specifies the maximum allowed distance between a start node and the returned nodes. Nodes within this distance from any start node will be included in the result.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNodes containing all direct and indirect successors of the start nodes within the specified distance.
Returns a topological ordering of the nodes in a directed acyclic graph.
This method computes a topological order specifically for instances of LayoutGraph. To retrieve a topological order of nodes in an IGraph instance, use getTopologicalOrder instead.
A topological ordering of the nodes in a directed graph is a linear ordering such that for each directed edge (u,v), the source node u appears before the target node v in the ordering. This is only possible if the graph is acyclic.
Parameters
- graph: LayoutGraph
- The input graph for which a topological order of the nodes is to be computed.
Return Value
- IEnumerable<LayoutNode>
- An IEnumerable<T> of LayoutNode objects, representing the nodes of the graph in topological order.
Throws
- Exception ({ name: 'ArgumentError' })
- Thrown if the input graph is cyclic, as a topological ordering is only defined for acyclic graphs.
Complexity
O(graph.Nodes.Count + graph.Edges.Count).Identifies and returns a collection of Substructure instances representing the trees within the specified graph that contain at least minimumSize nodes.
minimumSize nodes.A tree is defined as a connected subgraph where the root is the only node that may have non-tree edges. All nodes within a tree must share the same type, as defined by the nodeTypes parameter.
The directedness of the edges, specified by the edgeDirectedness parameter, is considered when identifying subtrees. A valid subtree is one where all edges are either undirected or consistently directed according to the specified directedness.
The edgeDirectedness parameter is interpreted as follows:
- A value of
1indicates that the edge is directed from source to target. - A value of
-1indicates that the edge is directed from target to source. - A value of
0indicates that the edge is undirected (the default for edges mapped tonull).
edgeDirectedness is not specified, all edges are treated as undirected. Similarly, if nodeTypes is not specified, all nodes are considered to be of the same type.Parameters
- graph: LayoutGraph
- The graph from which trees are to be identified.
- minimumSize: number
- The minimum number of nodes required for a subgraph to be considered a tree. Subgraphs with fewer nodes are ignored. The smallest value allowed for this parameter is
3. - nodeTypes?: IMapper<LayoutNode, any>
- An optional IMapper<TKey, TValue> mapping each LayoutNode to its type. Nodes that map to the same object are considered to be of the same type. If this parameter is not provided, all nodes are considered to be of the same type.
- edgeDirectedness?: IMapper<LayoutEdge, number>
- An optional IMapper<TKey, TValue> mapping each LayoutEdge to a nullable representing its directedness. If this parameter is not provided, all edges are treated as undirected.
Return Value
- IEnumerable<Substructure>
- A list of Substructure instances representing the identified trees in the graph.
weightCentrality
(considerInEdges?: booleanconsiderOutEdges?: boolean): IMapper<LayoutNode, number>staticComputes the weight centrality for the nodes in the specified graph.
weightCentrality
(This method calculates weight centrality for nodes in an instance of LayoutGraph. To compute weight centrality for edges in an IGraph instance, use WeightCentrality instead.
Weight centrality measures the weight associated with the incoming, outgoing, or all edges connected to a node. This measure helps to identify nodes that are central in terms of the weights of their connections.
Centrality quantifies the idea that some nodes in a network are "more central" based on their edge weights. A higher centrality value indicates a node with more weight in its connections, making it more central according to the algorithm.
edgeWeights is null, the method will effectively calculate degree centrality instead.Parameters
- graph: LayoutGraph
- The input graph for which weight centrality will be computed.
- considerInEdges?: boolean
- A boolean value indicating whether incoming edges should be included in the centrality calculation. Pass
trueto include incoming edges; otherwise, passfalse. - considerOutEdges?: boolean
- A boolean value indicating whether outgoing edges should be included in the centrality calculation. Pass
trueto include outgoing edges; otherwise, passfalse. - edgeWeights?: IMapper<LayoutEdge, number>
- An optional IMapper<K, V> that provides positive double values representing the weight of each edge. If
edgeWeightsis not specified, all edges are assumed to have a uniform weight of1.0.
Return Value
- IMapper<LayoutNode, number>
- An IMapper<K, V> that contains the weight centrality values for each node in the graph. The key is a LayoutNode, and the value is a representing the centrality of that node.
Complexity
O(graph.Edges.Count)