LayoutGraphAlgorithms

Show usages

Provides a collection of algorithms for analyzing and manipulating a LayoutGraph within the context of layout processing.

Inheritance Hierarchy

LayoutGraphAlgorithms

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.

Type Details

yFiles module: algorithms

Static Methods

addTransitiveEdges

(graph: LayoutGraph, directed: boolean, visibleNodes: function(LayoutNode):boolean) : IEnumerable<LayoutEdge>

Creates transitive edges that connect the visible nodes in the specified graph.

Remarks

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

options - Object
A map of options to pass to the method.

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 visible or not.

Signature Details

function(obj: LayoutNode) : boolean

Represents the method that defines a set of criteria and determines whether the specified object meets those criteria.

Parameters

obj - LayoutNode: The object to compare against the criteria defined within the method represented by this delegate.

Returns

boolean: true if obj meets the criteria defined within the method represented by this delegate; otherwise, false.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<Edge> of the created transitive edges. These are the edges added to connect visible nodes based on the described conditions.

allPairsShortestPath

(graph: LayoutGraph, directed: boolean, edgeCosts: IMapper<LayoutEdge,number>) : IMapper<LayoutNode,IMapper<LayoutNode,number>>

Computes the shortest paths between all pairs of nodes in a graph with arbitrary edge costs.

Remarks

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.

Complexity

O(graph.Nodes.Count² * log(graph.Nodes.Count))

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪IMapper<LayoutNode,IMapper<LayoutNode,number>>?: An IMapper<TKey,TValue> mapping each pair of nodes s and t to the shortest path distance between them. The distance from node s to node t can be accessed via result[s][t]. If there is no path from s to t, the value will be Number.POSITIVE_INFINITY. If the graph contains a negative-cost cycle, the method returns null.

When 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.

allPathEdges

(graph: LayoutGraph, source: LayoutNode, sink: LayoutNode) : IMapper<LayoutEdge,boolean>

Computes all edges that belong to any directed path from a source node to a sink node.

Remarks

Note: This method works with instances of LayoutGraph. To find all paths between two nodes in an IGraph use Paths instead.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪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, or false otherwise.

allPaths

(graph: LayoutGraph, source: LayoutNode, sink: LayoutNode, directed: boolean, pathFilter?: function(IList<LayoutEdge>):boolean) : IEnumerable<IList<LayoutEdge>>

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.

Remarks

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.

Complexity

The complexity of enumerating the returned cursor is O(2^ (graph.Nodes.Count + graph.Edges.Count)).

Preconditions

Input graph, source node, and sink node must not be null.

Parameters

options - Object
A map of options to pass to the method.

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

true if the graph should be treated as directed, meaning edges are traversable only in one direction; false if 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.

Signature Details

function(obj: IList<LayoutEdge>) : boolean

Represents the method that defines a set of criteria and determines whether the specified object meets those criteria.

Parameters

obj - IList<LayoutEdge>: The object to compare against the criteria defined within the method represented by this delegate.

Returns

boolean: true if obj meets the criteria defined within the method represented by this delegate; otherwise, false.

Returns

↪IEnumerable<IList<LayoutEdge>>: An IEnumerable<T> that calculates the next path in the sequence on demand.

allUnweightedShortestPaths

(graph: LayoutGraph, source: LayoutNode, sinks: IEnumerable<LayoutNode>, directed: boolean, resultPathEdges: IEnumerable<LayoutEdge>, resultPathNodes: IEnumerable<LayoutNode>, maxLength?: number)

Computes all nodes and edges that belong to the shortest path from a specified source node to a set of sinks in the graph, ensuring the path does not exceed a given distance.

Remarks

This method assumes that each edge in the input graph has a uniform cost of 1.0. If the graph is undirected, the method will consider edges traversable in both directions, potentially leading to undirected paths in the result.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

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: true if the graph should be treated as directed, meaning edges are traversable only in one direction; false if 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 source node to the nodes in sinks, 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 source node to the nodes in sinks, 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.

In an undirected graph, edges can be traversed in both directions, which means that the computed shortest paths may also be undirected.

Shortest paths that exceed the specified maxLength will be ignored.

applyTransitiveClosure

(graph: LayoutGraph) : IEnumerable<LayoutEdge>

Computes the transitive closure and adds necessary transitive edges to a directed acyclic graph.

Remarks

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.

Preconditions

The graph must be acyclic, as verified by .

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to which transitive edges will be added, if necessary.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<Edge> with the edges that have been added to the graph.

applyTransitiveReduction

(graph: LayoutGraph) : IEnumerable<LayoutEdge>

Computes the transitive reduction for a directed acyclic graph.

Remarks

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.

Complexity

O(graph.Nodes.Count^3)

Preconditions

The graph must be acyclic, as verified by .

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph from which transitive edges will be removed to compute the transitive reduction.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<Edge> with the transitive edges that were removed from the graph.

This implementation is memory-intensive as it allocates an graph.Nodes.Count x graph.Nodes.Count matrix to store reachability data.

bfs

(graph: LayoutGraph, startingNodes: IEnumerable<LayoutNode>, resultLayerIds?: IMapper<LayoutNode,number>, direction?: TraversalDirection, maximumLayerCount?: number) : IEnumerable<LayoutNode>

Executes a breadth-first search (BFS) on a directed or undirected graph, returning the nodes organized into layers.

Remarks

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.

Example for a BFS run. The marked node is the core node from which BFS starts while node labels indicate the resulting layers.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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. If resultLayerIds is 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.

Returns

↪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.

If 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.

biconnectedComponentClustering

(graph: LayoutGraph, resultClusterIds: IMapper<LayoutNode,number>) : number

Partitions the graph into clusters based on its biconnected components.

Remarks

This 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.

Complexity

O(graph.Edges.Count + graph.Nodes.Count)

Parameters

options - Object
A map of options to pass to the method.

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 number 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 null value.

Returns

↪number: The total number of distinct biconnected component clusters found in the graph.

Throws

Exception({ name: 'ArgumentError' }): Thrown when either graph or resultClusterIds is null.

biconnectedComponents

(graph: LayoutGraph, resultComponentIds?: IMapper<LayoutEdge,number>, resultArticulationPoints?: IMapper<LayoutNode,boolean>) : IEnumerable<LayoutEdge>

Calculates the biconnected components and articulation points of the specified undirected graph, and returns the biconnected components.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Preconditions

The input graph must be .

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 (true if it is, false otherwise).

Returns

↪IEnumerable<LayoutEdge>[]: An array of biconnected components, each represented as an IEnumerable<T> of LayoutEdges contained in that component.

Self-loops do not belong to any biconnected component, and thus have a component index of -1.

bipartition

(graph: LayoutGraph, resultPartition1: ICollection<LayoutNode>, resultPartition2: ICollection<LayoutNode>) : boolean

Calculates a bipartition of the specified graph, if one exists.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪boolean: true if the graph is bipartite and the partitions were successfully calculated; otherwise, false.

Sample Graphs

chainSubstructures

(graph: LayoutGraph, minimumSize: number, nodeTypes?: IMapper<LayoutNode,any>, edgeDirectedness?: IMapper<LayoutEdge,number>) : IEnumerable<Substructure>

Identifies and returns a collection of Substructure instances representing the chains within the specified graph that contain at least minimumSize nodes.

Remarks

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 1 indicates that the edge is directed from source to target.
A value of -1 indicates that the edge is directed from target to source.
A value of 0 indicates that the edge is undirected (the default for edges mapped to null).

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 number representing its directedness. If this parameter is not provided, all edges are treated as undirected.

Returns

↪IEnumerable<Substructure>: A list of Substructure instances representing the identified chains in the graph.

If 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.

cliqueSubstructures

(graph: LayoutGraph, minimumSize: number, nodeTypes?: IMapper<LayoutNode,any>) : IEnumerable<Substructure>

Identifies and returns a collection of Substructure instances representing the (undirected) cliques within the specified graph, where each clique contains at least minimumSize nodes.

Remarks

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.

Parameters

options - Object
A map of options to pass to the method.

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 minimumSize is 3.
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 null or not provided, all nodes will be treated as being of the same type.

Returns

↪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.

Nodes within each clique are of the same nodeTypes, meaning they are associated with identical objects. If nodeTypes is not provided, all nodes are treated as having the same type.

The smallest value that minimumSize can accept is 3.

closenessCentrality

(graph: LayoutGraph, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>) : IMapper<LayoutNode,number>

Computes the closeness centrality for each node in the specified graph.

Remarks

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.

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.

Preconditions

The graph must be for meaningful centrality values.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true if the graph is directed; otherwise, pass false.
edgeCosts - IMapper<LayoutEdge,number>: An optional IMapper<K,V> that provides positive double values representing the cost of each edge. If edgeCosts is not specified, all edges are assumed to have equal cost.

Returns

↪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 number representing the centrality of that node.

For non-connected graphs, the centrality values of all nodes will be zero because the distance to some nodes is infinite.

clusteringCoefficient

(graph: LayoutGraph, resultCoefficients: IMapper<LayoutNode,number>, directed: boolean) : number

Computes the local clustering coefficient for each node in the specified graph and returns the average clustering coefficient across all nodes.

Remarks

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 number 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

options - Object
A map of options to pass to the method.

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.

Returns

↪number: The average local clustering coefficient of all nodes in the graph.

Throws

Exception({ name: 'ArgumentError' }): Thrown when graph or resultCoefficients is null.

The algorithm does not consider self-loops or multi-edges. Group nodes are treated as regular nodes in the calculation.

connectedComponents

(graph: LayoutGraph, resultComponentIds?: IMapper<LayoutNode,number>) : IEnumerable<LayoutNode>

Calculates the connected components of the specified graph.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪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.

cycleSubstructures

(graph: LayoutGraph, minimumSize: number, nodeTypes?: IMapper<LayoutNode,any>, edgeDirectedness?: IMapper<LayoutEdge,number>) : IEnumerable<Substructure>

Identifies and returns a collection of Substructure instances representing the cycles within the specified graph that contain at least minimumSize nodes.

Remarks

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 1 indicates that the edge is directed from source to target.
A value of -1 indicates that the edge is directed from target to source.
A value of 0 indicates that the edge is undirected (the default for edges mapped to null).

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 number representing its directedness. If this parameter is not provided, all edges are treated as undirected.

Returns

↪IEnumerable<Substructure>: A list of Substructure instances representing the identified cycles in the graph.

If 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.

degreeCentrality

(graph: LayoutGraph, considerInEdges?: boolean, considerOutEdges?: boolean) : IMapper<LayoutNode,number>

Computes the degree centrality for the nodes in the specified graph.

Remarks

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.

Complexity

O(graph.Nodes.Count)

Preconditions

At least one of the flags considerInEdges or considerOutEdges must be true.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true to include incoming edges; otherwise, pass false.
considerOutEdges - boolean: A boolean value indicating whether outgoing edges should be included in the degree centrality calculation. Pass true to include outgoing edges; otherwise, pass false.

Returns

↪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 number representing the centrality of that node.

delaunayTriangulation

(resultGraph: LayoutGraph, nodeLocations: IMapper<LayoutNode,Point>, resultReversedEdges: IMapper<LayoutEdge,LayoutEdge>) : LayoutEdge

Computes a Delaunay triangulation of the given points.

Remarks

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

options - Object
A map of options to pass to the method.

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 null then no reverse edge information will be available.

Returns

↪LayoutEdge?: An edge on the outer face of the result graph or null if there are fewer than two points designated as nodeLocations.

density

(graph: LayoutGraph, directed?: boolean) : number

Computes the density of the specified graph, considering only a simple version of it (see isSimple).

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph for which the density is to be computed.
directed - boolean: true if the graph should be considered as directed; otherwise, false.

Returns

↪number: The density of the specified graph as a number value.

This method ignores self-loops (edges connecting a node to itself) and multi-edges (multiple edges between the same pair of nodes).

dfs

(graph: LayoutGraph, startingNode: LayoutNode, directed?: boolean, visitAllTrees?: boolean, nodeVisiting?: function(LayoutNode, number):void, nodeVisited?: function(LayoutNode, number, number):void, edgeTraversing?: function(LayoutEdge, LayoutNode, boolean):void, edgeTraversed?: function(LayoutEdge, LayoutNode):void, nextTreeVisiting?: function(LayoutNode):void)

Executes a depth-first search (DFS) on the specified graph starting from the given node.

Remarks

This method simplifies the use of the DFS algorithm by allowing the caller to specify the graph, the starting node, and various callback functions that will be invoked at key points during the DFS traversal. The algorithm can be customized by providing implementations for one or more of the callback delegates.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

graph - LayoutGraph

The input graph on which the DFS will be performed.

startingNode - LayoutNode

The node from which the DFS will start.

directed - boolean

true if the edges of the graph should be treated as directed; false otherwise. The default value is false.

visitAllTrees - boolean

true if DFS should continue searching after all nodes reachable from the start node are visited; false to stop after the first DFS tree is completed. The default value is true.

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.

Signature Details

function(node: LayoutNode, visitOrder: number)

Delegate for handling the event before a node is visited for the first time during DFS.

Parameters

node - LayoutNode: The node being visited.
visitOrder - number: The order in which the node is visited during DFS.

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.

Signature Details

function(node: LayoutNode, visitOrder: number, completionOrder: number)

Delegate for handling the event after a node visit is completed during DFS.

Parameters

node - LayoutNode: The node whose visit is completed.
visitOrder - number: The order in which the node was visited during DFS.
completionOrder - number: The order in which the node is completed after visiting all its neighbors.

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.

Signature Details

function(edge: LayoutEdge, node: LayoutNode, treeEdge: boolean)

Delegate for handling the event before an edge is traversed for the first time during DFS.

Parameters

edge - LayoutEdge: The edge being traversed.
node - LayoutNode: The node to be visited next, if treeEdge is true.
treeEdge - boolean: true if the node will be visited as part of the DFS tree; false otherwise.

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.

Signature Details

function(edge: LayoutEdge, node: LayoutNode)

Delegate for handling the event after DFS has returned from a node during edge traversal.

Parameters

edge - LayoutEdge: The edge via which the node was reached.
node - LayoutNode: The node that was visited via the given edge.

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 visitAllTrees parameter is set to true. If omitted, no action will be taken.

Signature Details

function(root: LayoutNode)

Delegate for handling the event before DFS continues its search from a new root node.

Parameters

root - LayoutNode: The new root node from which DFS continues.

Sample Graphs

If the startingNode node is null, this method returns silently.

dfsCompletionNodeOrder

(graph: LayoutGraph) : IEnumerable<LayoutNode>

Calculates an ordering of the nodes that corresponds to the order of node completion events in a depth-first search.

Remarks

If the input graph is acyclic, this ordering will be a reversed topological ordering of the nodes.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input graph for which the node ordering will be calculated.

Returns

↪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.

diameter

(graph: LayoutGraph, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>) : number

Computes the diameter of the specified graph.

Remarks

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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph for which the diameter is to be computed.
directed - boolean: true if 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.

Returns

↪number: The diameter of the specified graph. This is the length of the longest shortest path between any two vertices.

Multi-edges (multiple edges between the same pair of nodes) are considered in the diameter calculation.

The algorithm used to compute the diameter solves the all-pairs shortest path problem. Depending on the structure of the graph and the provided edge costs, the method may use an algorithm with the theoretically best running time. However, practical performance can vary based on the specific characteristics of the graph.

edgeBetweenness

(graph: LayoutGraph, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>) : IMapper<LayoutEdge,number>

Computes the betweenness centrality for each edge in the specified graph.

Remarks

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.

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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true if the graph is directed; otherwise, pass false.
edgeCosts - IMapper<LayoutEdge,number>: An optional IMapper<K,V> that provides positive double values representing the cost of each edge. If edgeCosts is not specified, all edges are assumed to have equal cost. For invalid or missing values, the algorithm will assume a default cost of 1.0.

Returns

↪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 number representing the centrality of that edge.

edgeBetweennessClustering

(graph: LayoutGraph, resultClusterIds: IMapper<LayoutNode,number>, directed: boolean, minimumClusterCount: number, maximumClusterCount: number, edgeCosts: IMapper<LayoutEdge,number>) : number

Partitions the graph into clusters using edge betweenness centrality.

Remarks

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.

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.

Preconditions

- minimumClusterCount <= maximumClusterCount
- minimumClusterCount <= graph.Nodes.Count
- maximumClusterCount > 0

Parameters

options - Object
A map of options to pass to the method.

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 boolean 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 number representing the cost. If null, all edges are considered to have equal cost.

Returns

↪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 > maximumClusterCount
minimumClusterCount > graph.Nodes.Count
maximumClusterCount <= 0

edgeBetweennessClustering

(graph: LayoutGraph, resultClusterIds: IMapper<LayoutNode,number>, qualityTimeRatio: number, minimumClusterCount: number, maximumClusterCount: number, refine: boolean) : number

Partitions the graph into clusters using the edge betweenness clustering algorithm proposed by Girvan and Newman.

Remarks

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.

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.

Preconditions

- minimumClusterCount <= maximumClusterCount
- minimumClusterCount <= graph.Nodes.Count
- maximumClusterCount > 0

Parameters

options - Object
A map of options to pass to the method.

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) and 1.0 (indicating higher quality but slower computation). The recommended value for a balance between quality and speed is 0.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; if false, the current clustering will be discarded and a new clustering will be computed from scratch.

Returns

↪number: The number of clusters produced by the algorithm. This value will be between minimumClusterCount and maximumClusterCount and 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 > maximumClusterCount
minimumClusterCount > graph.Nodes.Count
maximumClusterCount <= 0

eigenvectorCentrality

(graph: LayoutGraph, precision?: number) : IMapper<LayoutNode,number>

Computes the eigenvector centrality for each node in the specified undirected graph.

Remarks

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.

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪IMapper<LayoutNode,number>?: An IMapper<K,V> containing the eigenvector centrality values for each node, scaled within the interval [0, 1]. Returns null if the power iteration method does not converge and no valid eigenvector could be computed.

The power iteration method used to compute the dominant eigenvector may not converge for some input graphs. In such cases, the method will return 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.

findAllCycleEdges

(graph: LayoutGraph, directed: boolean) : IEnumerable<LayoutEdge>

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.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph in which cycle edges are to be identified.
directed - boolean: A boolean indicating whether the graph should be treated as directed. Pass true to consider the graph directed; otherwise, pass false to treat it as undirected.

Returns

↪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.

Self-loops are always considered to be cycle edges.

findCenterRoot

(tree: LayoutGraph) : LayoutNode

Returns the center node of the specified undirected tree.

Remarks

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.

Preconditions

The tree must be .
The tree must be a valid .

Parameters

options - Object
A map of options to pass to the method.

tree - LayoutGraph: The graph representing the undirected tree from which to find the center node. This parameter must not be null.

Returns

↪LayoutNode: The LayoutNode that is the center of the given undirected tree.

findCycle

(graph: LayoutGraph, directed: boolean) : IEnumerable<LayoutEdge>

Returns an IEnumerable<Edge> that contains the edges of a cycle found in the given graph.

Remarks

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.

Complexity

O(graph.Edges.Count + graph.Nodes.Count)

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph in which a cycle is to be identified.
directed - boolean: A boolean indicating whether the graph should be treated as directed. Pass true to consider the graph directed; otherwise, pass false to treat it as undirected.

Returns

↪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.

findCycleEdges

(graph: LayoutGraph, resultCycleEdges: IMapper<LayoutEdge,boolean>, resultCosts?: IMapper<LayoutEdge,number>, highQualityMode?: boolean)

Identifies and marks the edges of a given graph whose removal or reversal would transform the graph into an acyclic structure, while attempting to minimize the associated costs of the marked edges.

Remarks

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 number value.

Complexity

The time complexity of the operation varies based on the value of highQualityMode:

O(graph.Edges.Count * graph.Edges.Count) when highQualityMode is true.
O(graph.Nodes.Count + graph.Edges.Count * log(graph.Nodes.Count)) when highQualityMode is false.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true if the edge is identified as part of a cycle, and false otherwise.
resultCosts - IMapper<LayoutEdge,number>: An optional IMapper<K,V> instance that holds the non-negative number reversal cost for each edge. This parameter can be null if no cost information is required.
highQualityMode - boolean: A boolean indicating whether to use the slower, higher-quality heuristic. Set to true to prioritize accuracy over speed; set to false to favor faster execution with potentially more edges marked as cycle edges.

findCycleEdgesDfs

(graph: LayoutGraph, resultCycleEdges: IMapper<LayoutEdge,boolean>)

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.

Remarks

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.

Complexity

O(graph.Edges.Count + graph.Nodes.Count)

Parameters

options - Object
A map of options to pass to the method.

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 true if the edge is detected as part of a cycle, and false otherwise.

findIntersections

(graph: LayoutGraph, intersectionItemType: IntersectionItemTypes, affectedItems?: IEnumerable<any>) : IEnumerable<LayoutGraphIntersection>

Finds intersections between graph items or a subset of graph items in the specified graph.

Remarks

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

options - Object
A map of options to pass to the method.

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.

Returns

↪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 affectedItems are found.

findLeafNodes

(tree: LayoutGraph, directed?: boolean) : IEnumerable<LayoutNode>

Returns all leaf nodes of the specified tree.

Remarks

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.

Preconditions

The given graph must be a .

Parameters

options - Object
A map of options to pass to the method.

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 true if the tree is directed, or false if the tree is undirected.

Returns

↪IEnumerable<LayoutNode>: An IEnumerable<T> of LayoutNode objects representing all leaf nodes in the specified tree.

findMultiEdges

(graph: LayoutGraph, directed: boolean, node?: LayoutNode) : IEnumerable<LayoutEdge>

Finds and returns the multi-edges in the specified graph or incident to a specific node.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph in which to search for multi-edges.
directed - boolean: true to consider edge direction when identifying multi-edges; false to 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.

Returns

↪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

findReachableNodes

(graph: LayoutGraph, start: LayoutNode, isDirected: boolean) : IMapper<LayoutNode,boolean>

Determines the set of nodes that are reachable from a specified starting node, considering edges that cannot be traversed.

Remarks

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

options - Object
A map of options to pass to the method.

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 true if the edges are directed and should be traversed from source to target; pass false if the edges are undirected and can be traversed in both directions.

Returns

↪IMapper<LayoutNode,boolean>: An IMapper<K,V> where the key is a LayoutNode and the value is a boolean. The value is true if the node can be reached from the starting node during the DFS; otherwise, it is false.

findRoot

(tree: LayoutGraph) : LayoutNode

Returns a possible root node for the specified (undirected) tree.

Remarks

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 == 0 or outdegree == 0, indicating a node with no incoming or outgoing edges, respectively.

Preconditions

The tree must be a valid , or there must be exactly one node with indegree == 0 or outdegree == 0.
The tree must be .

Parameters

options - Object
A map of options to pass to the method.

tree - LayoutGraph: The graph representing the tree from which to determine a possible root node.

Returns

↪LayoutNode: A LayoutNode that can serve as a root for the given tree.

findSubtreeNodes

(root: LayoutNode) : IEnumerable<LayoutNode>

Collects all nodes of the subtree rooted in the specified root node.

Remarks

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

options - Object
A map of options to pass to the method.

root - LayoutNode: The LayoutNode that serves as the root of the subtree.

Returns

↪IEnumerable<LayoutNode>: All nodes of the subtree rooted in the specified root node.

findTreeEdges

(graph: LayoutGraph, treeNodes?: IEnumerable<IEnumerable<LayoutNode>>) : IEnumerable<LayoutEdge>

Retrieves an array of IEnumerable<T> collections, where each collection contains the edges belonging to a maximal directed subtree of the specified graph.

Remarks

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

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutEdge>[]: An array of IEnumerable<Edge> collections, where each collection contains the edges belonging to a maximal subtree within the graph.

findTreeNodes

(graph: LayoutGraph, directed?: boolean) : IEnumerable<LayoutNode>

Calculates the nodes that belong to a maximal subtree of the specified graph, based on the directed parameter.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to be analyzed.
directed - boolean: A boolean value indicating whether to retrieve directed subtrees (true) or undirected subtrees (false).

Returns

↪IEnumerable<LayoutNode>[]: the nodes that belong to a maximal subtree of the specified graph, based on the directed parameter.

findWeightedCenterNode

(tree: LayoutGraph, weights?: IMapper<LayoutNode,number>) : LayoutNode

Finds the node in the given (undirected) tree that is used by the greatest number of paths interconnecting all nodes.

Remarks

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.

Preconditions

The tree must be a valid .
The tree must be .

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪LayoutNode: A LayoutNode that is used by the greatest number of undirected paths in the tree.

graphCentrality

(graph: LayoutGraph, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>) : IMapper<LayoutNode,number>

Computes the graph centrality for each node in the specified graph.

Remarks

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.

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.

Preconditions

An must be provided as input that returns zero for each to represent the initial closeness centrality.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true if the graph is directed; otherwise, pass false.
edgeCosts - IMapper<LayoutEdge,number>: An optional IMapper<K,V> that provides positive double values representing the cost of each edge. If edgeCosts is not specified, all edges are assumed to have equal cost.

Returns

↪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 number representing the centrality of that node.

For disconnected graphs, the centrality values of all nodes will be zero since the distance to some nodes is considered infinite.

hierarchicalClustering

(graph: LayoutGraph, distances: function(LayoutNode, LayoutNode):number, linkage: HierarchicalClusteringLinkage) : HierarchicalClusteringDendrogram

Partitions the specified graph into clusters using hierarchical clustering.

Remarks

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.

Complexity

O(graph.Nodes.Count ^ 3)

Parameters

options - Object
A map of options to pass to the method.

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.

Signature Details

function(arg1: LayoutNode, arg2: LayoutNode) : number

Encapsulates a method that has two parameters and returns a value of the type specified by the TResult parameter.

Parameters

arg1 - LayoutNode: The first parameter of the method that this delegate encapsulates.
arg2 - LayoutNode: The second parameter of the method that this delegate encapsulates.

Returns

number: The return value of the method that this delegate encapsulates.

linkage - HierarchicalClusteringLinkage

Specifies the linkage criterion to be used for merging clusters.

Returns

↪HierarchicalClusteringDendrogram?: A HierarchicalClusteringDendrogram representing the hierarchical clustering as a binary tree structure, or null if the provided graph is empty.

Throws

Exception({ name: 'ArgumentError' }): Thrown if an unknown linkage value is provided.

If the distances callback returns a negative value for the distance between two nodes, a distance of zero will be used instead.

hierarchicalClustering

(graph: LayoutGraph, resultClusterIds: IMapper<LayoutNode,number>, distances: function(LayoutNode, LayoutNode):number, linkage: HierarchicalClusteringLinkage, cutOff: number) : number

Partitions the specified graph into clusters using hierarchical clustering.

Remarks

This method is designed to work with instances of LayoutGraph. To perform hierarchical clustering on an IGraph, use the HierarchicalClustering method instead.

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.

Complexity

O(graph.Nodes.Count ^ 3)

Parameters

options - Object
A map of options to pass to the method.

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 number 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.

Signature Details

function(arg1: LayoutNode, arg2: LayoutNode) : number

Encapsulates a method that has two parameters and returns a value of the type specified by the TResult parameter.

Parameters

arg1 - LayoutNode: The first parameter of the method that this delegate encapsulates.
arg2 - LayoutNode: The second parameter of the method that this delegate encapsulates.

Returns

number: The return value of the method that this delegate encapsulates.

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.

Returns

↪number: The number of clusters resulting from the hierarchical clustering operation.

Throws

Exception({ name: 'ArgumentError' }): Thrown if an unknown linkage value is provided.

The cut-off value should be greater than zero. If a negative value is given, zero will be used instead.

If the distances callback returns a negative value for the distance between two nodes, a distance of zero will be used instead.

hierarchicalClustering

(graph: LayoutGraph, maximumClusterCount: number, resultClusterIds: IMapper<LayoutNode,number>, distances: function(LayoutNode, LayoutNode):number, linkage: HierarchicalClusteringLinkage) : number

Partitions the specified graph into clusters using hierarchical clustering.

Remarks

This method is designed to work with instances of LayoutGraph. To perform hierarchical clustering on an IGraph, use the HierarchicalClustering method instead.

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.

Complexity

O(graph.Nodes.Count ^ 3)

Parameters

options - Object
A map of options to pass to the method.

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 number 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.

Signature Details

function(arg1: LayoutNode, arg2: LayoutNode) : number

Encapsulates a method that has two parameters and returns a value of the type specified by the TResult parameter.

Parameters

arg1 - LayoutNode: The first parameter of the method that this delegate encapsulates.
arg2 - LayoutNode: The second parameter of the method that this delegate encapsulates.

Returns

number: The return value of the method that this delegate encapsulates.

linkage - HierarchicalClusteringLinkage

Specifies the linkage criterion to be used for merging clusters.

Returns

↪number: The number of clusters resulting from the hierarchical clustering operation. This number will be equal to or less than the specified maximumClusterCount value.

Throws

Exception({ name: 'ArgumentError' }): Thrown if an unknown linkage value is provided.

The cut-off value should be greater than zero. If a negative value is given, zero will be used instead.

If the distances callback returns a negative value for the distance between two nodes, a distance of zero will be used instead.

independentSets

(graph: LayoutGraph) : IEnumerable<LayoutNode>

Partitions the nodes of the specified graph into independent sets.

Remarks

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.

Preconditions

The input graph must be (i.e., it must not contain multi-edges or self-loops).

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input graph to be partitioned.

Returns

↪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.

intersect

<TPlaneObject>(planeObjects: IEnumerable<TPlaneObject>, intersectionCallback: function(TPlaneObject, TPlaneObject):void)

Calculates the intersections of plane objects and invokes a callback for each intersecting pair.

Remarks

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.

Complexity

O(n log n + s), where n is the number of plane objects, and s is the number of intersections

Type Parameters

TPlaneObject: The type of the plane objects, which must implement .

Parameters

options - Object
A map of options to pass to the method.

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.

Signature Details

function(arg1: TPlaneObject, arg2: TPlaneObject)

Encapsulates a method that has two parameters and does not return a value.

Parameters

arg1 - TPlaneObject: The first parameter of the method that this delegate encapsulates.
arg2 - TPlaneObject: The second parameter of the method that this delegate encapsulates.

isAcyclic

(graph: LayoutGraph) : boolean

Determines whether the specified directed graph is acyclic.

Remarks

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.

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to be checked for acyclicity.

Returns

↪boolean: true if the graph is acyclic; otherwise, false.

Sample Graphs

The relationship between acyclicity and cyclicity is given by: IsAcyclic(graph) <=> !IsCyclic(graph).

isBiconnected

(graph: LayoutGraph) : boolean

Determines whether the specified undirected graph is biconnected.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The undirected graph to be checked.

Returns

↪boolean: true if the graph is biconnected; otherwise, false.

Sample Graphs

isBipartite

(graph: LayoutGraph) : boolean

Determines whether the specified graph is bipartite.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to analyze.

Returns

↪boolean: true if the graph is bipartite; otherwise, false.

Sample Graphs

isConnected

(graph: LayoutGraph) : boolean

Determines whether the specified graph is connected.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to be checked for connectivity.

Returns

↪boolean: true if the graph is connected; otherwise, false.

Sample Graphs

isForest

(graph: LayoutGraph, directed: boolean) : boolean

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.

Remarks

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

options - Object
A map of options to pass to the method.

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 true to check for directed rooted trees; set to false to check for undirected trees.

Returns

↪boolean: true if the graph is a forest as defined by the directed parameter; otherwise, false.

Sample Graphs

isNaryTree

(graph: LayoutGraph, maximumChildCount: number) : boolean

Determines whether the specified graph is a directed rooted tree where each node has at most maximumChildCount children.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to be checked.
maximumChildCount - number: The maximum number of children that any node in the tree is allowed to have.

Returns

↪boolean: true if the graph is a directed rooted tree where each node has at most maximumChildCount children; otherwise, false.

Sample Graphs

isPlanar

(graph: LayoutGraph) : boolean

Determines whether the specified graph is planar.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to be checked for planarity.

Returns

↪boolean: true if the graph is planar; otherwise, false.

Sample Graphs

isSimple

(graph: LayoutGraph) : boolean

Determines whether the specified directed graph is simple.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The directed graph to be checked for simplicity.

Returns

↪boolean: true if the graph is simple; otherwise, false.

Sample Graphs

isStronglyConnected

(graph: LayoutGraph) : boolean

Determines whether the specified directed graph is strongly connected.

Remarks

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

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The directed graph to be checked for strong connectivity.

Returns

↪boolean: true if the graph is strongly connected; otherwise, false.

Sample Graphs

isTree

(graph: LayoutGraph, directed?: boolean) : boolean

Determines whether the specified graph represents a tree, with an option to check for either a directed rooted tree or an undirected tree.

Remarks

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 directed is true, 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 directed is false, the method checks whether the graph is an undirected tree. An undirected tree is a connected, acyclic graph where edges have no direction.

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The graph to be analyzed.
directed - boolean: A boolean value indicating the type of tree to check for: true to check for a directed rooted tree, or false to check for an undirected tree.

Returns

↪boolean: true if the graph is a tree that matches the specified criteria; otherwise, false.

Sample Graphs

kCore

(graph: LayoutGraph, k: number) : IEnumerable<LayoutNode>

Calculates the k-core for a given undirected input graph and specific k value.

Remarks

The k-core of an undirected graph is the maximal subgraph where each node has a degree of at least k. This method computes and returns the nodes of the k-core corresponding to the given k value.

Complexity

The algorithm has a runtime complexity of O((graph.Nodes.Count + graph.Edges.Count) * log(graph.Nodes.Count)) and requires linear space.

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutNode>: An IEnumerable<T> containing the nodes that form the k-core. The list may be empty if no such k-core exists.

This method does not modify the input graph but returns the nodes that form the k-core. The returned list may be empty.

Self-loops are ignored in this computation.

kCores

(graph: LayoutGraph, resultKValues: IMapper<LayoutNode,number>) : number

Calculates the k-cores of an undirected input graph and assigns the largest k-value to each node.

Remarks

The k-core of an undirected graph is the maximal subgraph in which each node has a degree of at least 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.

Complexity

The algorithm has a runtime complexity of O((graph.Nodes.Count + graph.Edges.Count) * log(graph.Nodes.Count)) and requires linear space.

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪number: The largest k for which the k-core of the graph is not empty.

For any given k, the k-core of the graph consists of all nodes with a resultKValues greater than or equal to k.

Self-loops are ignored in this computation.

kMeansClustering

(graph: LayoutGraph, resultClusterIds: IMapper<LayoutNode,number>, nodePositions: IMapper<LayoutNode,Point>, distanceMetric: KMeansDistanceMetric, k: number, iterations?: number, centroids?: Point[]) : number

Partitions the graph into clusters using the k-means clustering algorithm.

Remarks

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.

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).

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 k is greater than the number of nodes in the graph, it will be adjusted to 2.
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.

Returns

↪number: The number of resulting (non-empty) clusters after the algorithm converges.

If the number of clusters specified by k exceeds the number of nodes in the graph, the number of clusters will be adjusted to 2.

If fewer initial centroids are provided than k or if no centroids are specified, the algorithm will initialize centroids randomly.

kShortestPaths

(graph: LayoutGraph, edgeCosts: IMapper<LayoutEdge,number>, source: LayoutNode, sink: LayoutNode, k: number, simplePaths?: boolean) : IEnumerable<IEnumerable<LayoutEdge>>

Computes the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.

Remarks

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.

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)))

Parameters

options - Object
A map of options to pass to the method.

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 k is 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 true may increase the runtime for graphs with cycles.

Returns

↪IEnumerable<IEnumerable<LayoutEdge>>: An IEnumerable<T> of IList<T> objects, each representing one of the k shortest paths from source to sink. The paths are ordered by their total cost, from the shortest to the longest. If there are fewer than k paths available, the enumerable contains only the available paths. If no path exists, an empty enumerable is returned.

If 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.

The method may return fewer than k paths if there are not enough distinct paths between the source and sink nodes.

labelPropagation

(graph: LayoutGraph, resultFinalLabels: IMapper<LayoutNode,number>, initialLabels?: IMapper<LayoutNode,number>, nodeWeights?: IMapper<LayoutNode,number>, edgeWeights?: IMapper<LayoutEdge,number>, edgeDirectedness?: IMapper<LayoutEdge,number>) : number

Detects communities in the specified input graph using the label propagation algorithm.

Remarks

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.0 and the edge is incoming (i.e., the node is the edge's target).
The edge's directedness is less than 0.0 and 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).

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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.0 for 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.0 for 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).

Returns

↪number: The number of distinct communities detected in the graph.

A node with a self-loop is considered a neighbor of itself, and its own label is included when calculating the most frequent label among neighbors. To exclude self-loops, set their weight to 0.0.

If none of a node's neighbors have a label with positive weight, the node retains its current label.

If edgeDirectedness is not provided, the algorithm assumes all edges are undirected (i.e., have directedness 0.0).

layerAssignment

(graph: LayoutGraph, layeringAlgorithm: ILayerAssigner, resultLayerIds: IMapper<LayoutNode,number>) : number

Calculates an assignment of the graph nodes to layers, using the specified layering algorithm.

Remarks

The calculated assignment is given as a mapping from nodes to the index of their assigned layer. The index 0 denotes the first layer.

Parameters

options - Object
A map of options to pass to the method.

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 0 denotes the first layer.

Returns

↪number: The number of calculated layers by the specified layering algorithm

longestPath

(graph: LayoutGraph, edgeCosts?: IMapper<LayoutEdge,number>) : IEnumerable<LayoutEdge>

Computes the longest directed path in a given acyclic weighted graph.

Remarks

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.

Preconditions

The graph must be .
The graph must have non-negative edge costs.

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<Edge> containing the edges of the longest directed path.

longestPaths

(graph: LayoutGraph, source: LayoutNode, edgeCosts: IMapper<LayoutEdge,number>) : IMapper<LayoutNode,number>

Calculates the longest path from a given node to all other nodes in a given directed acyclic graph.

Remarks

This method works with instances of LayoutGraph. To find the longest paths from one node to all other nodes in an IGraph use SingleSourceShortestPaths with negative edge costs instead.

Preconditions

The graph must be .

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪IMapper<LayoutNode,number>: An IMapper<K,V> that contains for each node in the graph the length of the longest directed path from the source to that node.

longPath

(graph: LayoutGraph) : IEnumerable<LayoutEdge>

Computes the edges of a heuristically long, undirected, simple path within the given graph.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Preconditions

The graph must be .

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input graph where the path will be computed.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<Edge> containing the edges of an undirected simple path.

louvainModularity

(graph: LayoutGraph, resultCommunityIds: IMapper<LayoutNode,number>, edgeWeights?: IMapper<LayoutEdge,number>) : number

Finds communities in the specified input graph using the Louvain modularity method.

Remarks

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

options - Object
A map of options to pass to the method.

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.0 for all edges.

Returns

↪number: The number of communities detected in the graph.

makeBiconnected

(graph: LayoutGraph) : IEnumerable<LayoutEdge>

Makes the given graph biconnected by inserting the minimum number of edges required.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Preconditions

The graph must be for the method to function correctly. If the graph is not connected, may be required before calling this method.

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input undirected graph that needs to be made biconnected.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<T> of LayoutEdge objects representing the edges added to the graph to make it biconnected.

makeConnected

(graph: LayoutGraph) : IEnumerable<LayoutEdge>

Modifies the specified graph by adding additional edges to make it fully connected.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input graph to be connected.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<T> containing the edges that were added to the graph to achieve connectivity. The edges are of type LayoutEdge.

makeTreeDirected

(tree: LayoutGraph, root?: LayoutNode) : IEnumerable<LayoutEdge>

Converts the specified undirected tree into a directed rooted tree with the given node as the root by reversing necessary edges.

Remarks

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.

Preconditions

The tree must be a valid .
The root must be a node within the tree, if specified.

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<Edge> containing all edges that were reversed to achieve the directed rooted tree structure.

maximalIndependentSet

(graph: LayoutGraph) : IEnumerable<LayoutNode>

Calculates a maximal independent set for the specified graph.

Remarks

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.

Preconditions

The input graph must be , meaning it should not contain multi-edges or self-loops.

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input graph for which a maximal independent set will be computed.

Returns

↪IEnumerable<LayoutNode>: An IEnumerable<T> of LayoutNodes that represents a maximal independent set of nodes in the graph.

maximumFlow

(graph: LayoutGraph, source: LayoutNode, sink: LayoutNode, edgeCapacities: IMapper<LayoutEdge,number>, resultFlows?: IMapper<LayoutEdge,number>) : number

Solves a maximum flow problem using the preflow-push algorithm.

Remarks

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.

Complexity

The worst-case running time is 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.

Parameters

options - Object
A map of options to pass to the method.

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. 0x7FFFFFFF denotes 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.

Returns

↪number: The value of the maximum flow from the source to the sink.

maximumFlowMinimumCut

(graph: LayoutGraph, source: LayoutNode, sink: LayoutNode, edgeCapacities: IMapper<LayoutEdge,number>, resultFlows?: IMapper<LayoutEdge,number>, resultSourceCuts?: IMapper<LayoutNode,boolean>) : number

Solves a maximum flow problem using the preflow-push algorithm and identifies the minimum cut set.

Remarks

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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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. 0x7FFFFFFF denotes 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.

Returns

↪number: The value of the maximum flow from the source to the sink.

minimumCostFlow

(graph: LayoutGraph, maximumCapacities: IMapper<LayoutEdge,number>, edgeCosts: IMapper<LayoutEdge,number>, supplies: IMapper<LayoutNode,number>, resultFlows?: IMapper<LayoutEdge,number>, resultDuals?: IMapper<LayoutNode,number>, minimumCapacities?: IMapper<LayoutEdge,number>) : number

Solves a minimum cost flow problem using a capacity scaling algorithm.

Remarks

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.

Complexity

The algorithm has a pseudo-polynomial running time of 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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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.

Returns

↪number: The total cost of the computed flow.

minimumSpanningTree

(graph: LayoutGraph, edgeCosts?: IMapper<LayoutEdge,number>) : IEnumerable<LayoutEdge>

Calculates the minimum spanning tree (MST) for the given undirected connected graph.

Remarks

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.

Complexity

graph.Edges.Count * log(graph.Nodes.Count)

Preconditions

The graph must be .

Parameters

options - Object
A map of options to pass to the method.

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 null or if no costs are provided, a uniform cost of 1 is assumed for all edges.

Returns

↪IEnumerable<LayoutEdge>: An IEnumerable<T> of LayoutEdge objects that form the edges of the minimum spanning tree.

modularity

(graph: LayoutGraph, communityIds: IMapper<LayoutNode,number>, edgeWeights?: IMapper<LayoutEdge,number>) : number

Computes the modularity of a given graph based on the provided community partition.

Remarks

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

options - Object
A map of options to pass to the method.

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.

Returns

↪number: The modularity value of the graph based on the provided community partition.

Throws

Exception({ name: 'ArgumentError' }): Thrown if graph or communityIds is null.
Exception({ name: 'ArgumentError' }): Thrown if communityIds is null or if communityIds is not valid for the nodes in the graph.

nearestCommonAncestor

(tree: LayoutGraph, root: LayoutNode, rootedDownward: boolean, nodes: IEnumerable<LayoutNode>) : LayoutNode

Finds the nearest common ancestor of a subset of nodes within a directed rooted tree.

Remarks

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.

Complexity

O(tree.Nodes.Count)

Preconditions

The tree must be a valid .

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪LayoutNode?: The LayoutNode representing the nearest common ancestor of the given subset of nodes, or null if no common ancestor is found.

neighbors

(graph: LayoutGraph, startNodes: IEnumerable<LayoutNode>, maximumDistance: number) : IEnumerable<LayoutNode>

Determines the direct and indirect neighbors of a given set of nodes in the specified graph.

Remarks

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

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutNode>: An IEnumerable<T> of LayoutNodes containing all direct and indirect neighbors of the start nodes.

nodeBetweenness

(graph: LayoutGraph, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>) : IMapper<LayoutNode,number>

Computes the betweenness centrality for each node in the specified graph.

Remarks

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.

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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true if the graph is directed; otherwise, pass false.
edgeCosts - IMapper<LayoutEdge,number>: An optional IMapper<K,V> that provides positive double values representing the cost of each edge. If edgeCosts is not specified, all edges are considered to have equal cost. For invalid or missing values, the algorithm will assume a default cost of 1.0.

Returns

↪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 number representing the centrality of that node.

nodeEdgeBetweenness

(graph: LayoutGraph, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>) : IMapper<LayoutGraphItem,number>

Computes the betweenness centrality for each node and edge in the specified graph.

Remarks

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.

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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true if the graph is directed; otherwise, pass false.
edgeCosts - IMapper<LayoutEdge,number>: An optional IMapper<K,V> that provides positive double values representing the cost of each edge. If edgeCosts is not specified, all edges are assumed to have equal cost. For invalid or missing values, the algorithm will assume a default cost of 1.0.

Returns

↪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 number representing the centrality of that item.

pageRank

(graph: LayoutGraph, resultPageRanks: IMapper<LayoutNode,number>, initialPageRanks?: IMapper<LayoutNode,number>, nodeWeights?: IMapper<LayoutNode,number>, edgeWeights?: IMapper<LayoutEdge,number>, edgeDirectedness?: IMapper<LayoutEdge,number>, dampingFactor?: number, precision?: number) : number

Computes the PageRank values for all nodes in the specified graph based on their attached edges.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 of 1.0 for all nodes.
nodeWeights - IMapper<LayoutNode,number>: An optional IMapper<K,V> specifying the weight for each node. If null, the algorithm assumes a weight of 1.0 for all nodes.
edgeWeights - IMapper<LayoutEdge,number>: An optional IMapper<K,V> specifying the weight for each edge. If null, the algorithm assumes a weight of 1.0 for 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 of 1.0.
dampingFactor - number: A value between 0 and 1 that determines the fraction of a node's rank distributed to its successors. A common default value is 0.85.
precision - number: The non-negative precision threshold for the convergence of PageRank values. A common default value is 0.001.

Returns

↪number: The sum of all node ranks after convergence.

The damping factor should be between 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.

If IMapper<K,V> initialPageRanks is omitted, the algorithm assumes an initial PageRank of 1.0 for all nodes.

If IMapper<K,V> nodeWeights is omitted, the algorithm assumes a weight of 1.0 for all nodes.

If IMapper<K,V> edgeWeights is omitted, the algorithm assumes a weight of 1.0 for all edges.

If IMapper<K,V> edgeDirectedness is omitted, the algorithm assumes all edges are directed from source to target with a directedness of 1.0.

predecessors

(graph: LayoutGraph, startNodes: IEnumerable<LayoutNode>, maximumDistance: number) : IEnumerable<LayoutNode>

Determines the direct and indirect predecessors of a specified list of nodes in the given graph.

Remarks

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

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutNode>: An IEnumerable<T> of LayoutNode objects that includes all direct and indirect predecessors of the start nodes.

shortestPath

(graph: LayoutGraph, source: LayoutNode, sink: LayoutNode, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>, heuristicCosts?: IMapper<LayoutNode,number>) : IEnumerable<LayoutEdge>

Computes the shortest path from a single source node to a single sink node in a graph.

Remarks

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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 n represents the estimated cost to reach the sink node from node n. If no array is provided, the method assumes a heuristic cost of zero for all nodes.

Returns

↪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.

When 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.

simplexRankAssignment

(graph: LayoutGraph, resultLayerIds: IMapper<LayoutNode,number>, weights: IMapper<LayoutEdge,number>, minimumLengths: IMapper<LayoutEdge,number>, stopDuration?: TimeSpan, treeEdges?: IMapper<LayoutEdge,boolean>, root?: LayoutNode, validRanking?: boolean) : number

Solves the rank assignment problem for a directed acyclic graph (DAG) using the simplex method, with an optional time limit for the algorithm's execution.

Remarks

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) in E, and
The sum ∑(weight(v, w) * (rank(v) - rank(w))) over all edges (v, w) in E is 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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true if the edge is a tree edge, or false otherwise. 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 boolean indicating whether the resultLayerIds contains a valid ranking upon completion.

Returns

↪number: The number of layers in the resulting rank assignment. This value represents the depth of the layered ranking of the nodes.

If the algorithm exceeds the specified time limit, the result may not be optimal.

singleSourceShortestPath

(graph: LayoutGraph, source: LayoutNode, directed?: boolean, edgeCosts?: IMapper<LayoutEdge,number>, resultDistances?: IMapper<LayoutNode,number>, resultPredecessorEdges?: IMapper<LayoutNode,yfiles.layout.LayoutEdge|null>) : boolean

Computes the shortest path distances from a single source node to all other nodes in a graph.

Remarks

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.

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 source node to every other node. If a node is unreachable, the corresponding value will be Number.POSITIVE_INFINITY.
resultPredecessorEdges - IMapper<LayoutNode,yfiles.layout.LayoutEdge|null>: An IMapper<TKey,TValue> that will be populated with the predecessor edge for each node on the shortest path from the source node. For the source node itself or if no path exists, the value will be null.

Returns

↪boolean: true if the graph does not contain any negative-cost cycles; otherwise, false.

This method selects the algorithm with the theoretically optimal running time based on the graph structure and edge costs. However, theoretical performance may not always align with practical results.

starSubstructures

(graph: LayoutGraph, minimumSize: number, nodeTypes?: IMapper<LayoutNode,any>, edgeDirectedness?: IMapper<LayoutEdge,number>) : IEnumerable<Substructure>

Identifies and returns a collection of Substructure instances representing the star structures within the specified graph that contain at least minimumSize nodes.

Remarks

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 1 indicates that the edge is directed from source to target.
A value of -1 indicates that the edge is directed from target to source.
A value of 0 indicates that the edge is undirected (the default for edges mapped to null).

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 number representing its directedness. If this parameter is not provided, all edges are treated as undirected.

Returns

↪IEnumerable<Substructure>: A list of Substructure instances representing the identified star structures in the graph.

If 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.

stOrder

(graph: LayoutGraph, stEdge?: LayoutEdge) : IEnumerable<LayoutNode>

Assigns an st-ordering to the nodes of a biconnected graph, given an edge between the source node s and the sink node t.

Remarks

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 s and the sink node t are connected by an edge.
For every node v_i in the ordering, other than s or t, there exist neighboring nodes v_j and v_k such that j < i and k > i.

This ordering is useful in graph drawing algorithms and other applications where a specific traversal order of nodes is required.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Preconditions

The graph must be .

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input graph, which must be a biconnected graph.
stEdge - LayoutEdge: The LayoutEdge connecting the source node s and the sink node t. This edge defines the start and end points of the st-ordering. If no edge is defined, a random edge that is not a self-loop will be used.

Returns

↪IEnumerable<LayoutNode>: An IEnumerable<T> containing the LayoutNodes of the graph in the order defined by the st -ordering.

stronglyConnectedComponents

(graph: LayoutGraph, resultComponentIds?: IMapper<LayoutNode,number>) : IEnumerable<LayoutNode>

Calculates the strongly connected components of the specified graph and returns the total number of components.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count)

Parameters

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutNode>[]: An array of strongly connected components, where each component is represented as an IEnumerable<T> of LayoutNode objects contained within that component.

subTreeDepths

(tree: LayoutGraph) : IMapper<LayoutNode,number>

Calculates and returns the depths of each subtree within a rooted directed tree.

Remarks

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

options - Object
A map of options to pass to the method.

tree - LayoutGraph: The graph representing the rooted directed tree.

Returns

↪IMapper<LayoutNode,number>: A mapping from nodes to the depths of the subtrees rooted in that node.

subtreeSizes

(tree: LayoutGraph) : IMapper<LayoutNode,number>

Calculates and returns the size (number of nodes) of each subtree within a rooted directed tree.

Remarks

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

options - Object
A map of options to pass to the method.

tree - LayoutGraph: The graph representing the rooted directed tree.

Returns

↪IMapper<LayoutNode,number>: A mapping from nodes to the size of the subtrees rooted in that node.

successors

(graph: LayoutGraph, startNodes: IEnumerable<LayoutNode>, maximumDistance: number) : IEnumerable<LayoutNode>

Determines the direct and indirect successors of a specified list of nodes in the given graph.

Remarks

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

options - Object
A map of options to pass to the method.

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.

Returns

↪IEnumerable<LayoutNode>: An IEnumerable<T> of LayoutNodes containing all direct and indirect successors of the start nodes within the specified distance.

topologicalNodeOrder

(graph: LayoutGraph) : IEnumerable<LayoutNode>

Returns a topological ordering of the nodes in a directed acyclic graph.

Remarks

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.

Complexity

O(graph.Nodes.Count + graph.Edges.Count).

Preconditions

The graph must be acyclic. Use to verify this condition.

Parameters

options - Object
A map of options to pass to the method.

graph - LayoutGraph: The input graph for which a topological order of the nodes is to be computed.

Returns

↪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.

treeSubstructures

(graph: LayoutGraph, minimumSize: number, nodeTypes?: IMapper<LayoutNode,any>, edgeDirectedness?: IMapper<LayoutEdge,number>) : IEnumerable<Substructure>

Identifies and returns a collection of Substructure instances representing the trees within the specified graph that contain at least minimumSize nodes.

Remarks

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 1 indicates that the edge is directed from source to target.
A value of -1 indicates that the edge is directed from target to source.
A value of 0 indicates that the edge is undirected (the default for edges mapped to null).

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 number representing its directedness. If this parameter is not provided, all edges are treated as undirected.

Returns

↪IEnumerable<Substructure>: A list of Substructure instances representing the identified trees in the graph.

A structure such as a chain or star is also considered a valid tree.

If 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.

weightCentrality

(graph: LayoutGraph, considerInEdges?: boolean, considerOutEdges?: boolean, edgeWeights?: IMapper<LayoutEdge,number>) : IMapper<LayoutNode,number>

Computes the weight centrality for the nodes in the specified graph.

Remarks

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.

Complexity

O(graph.Edges.Count)

ParametersOptions Overload

options - Object
A map of options to pass to the method.

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 true to include incoming edges; otherwise, pass false.
considerOutEdges - boolean: A boolean value indicating whether outgoing edges should be included in the centrality calculation. Pass true to include outgoing edges; otherwise, pass false.
edgeWeights - IMapper<LayoutEdge,number>: An optional IMapper<K,V> that provides positive double values representing the weight of each edge. If edgeWeights is not specified, all edges are assumed to have a uniform weight of 1.0.

Returns

↪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 number representing the centrality of that node.

Weight centrality degenerates to degree centrality when all edges have uniform weight. Specifically, if edgeWeights is null, the method will effectively calculate degree centrality instead.