This class provides algorithms that order the nodes of a graph using specific criteria.
Remarks
Note: Methods of this class work with instances of Graph. To retrieve a topological order of nodes in an IGraph use getTopologicalOrder instead.
Definitions
- A topological ordering of the nodes of a directed graph is a linear ordering of the nodes such that for each directed edge
(u,v), nodeulies beforevin the ordering. - A DFS completion ordering of the nodes of a graph is a node ordering identical to the order of node completion events in a depth first search.
- An st-ordering
(v_1,v_2,....,v_n)of a biconnected graph is a node ordering which guarantees that:- Source node
sand sink nodetare connected by an edge. - For each node
v_iin the ordering other thansort, there are neighborsv_jandv_kwithj < iandk > i.
- Source node
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.NodeOrders
Static Methods
Calculates an ordering of the nodes identical to the order of node completion events in a depth first search.
Remarks
Complexity
O(graph.N() + graph.E())
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- order - number[]
- an array of numbers that returns for each YNode
v, its zero-based index within the calculated ordering, i.e.,order[v.index()] == 5means thatvis the6-th node within the ordering
See Also
Calculates an ordering of the nodes identical to the order of node completion events in a depth first search.
Remarks
Like dfsCompletion but the result is returned as a YNodeList.
This ordering is a reversed topological ordering in case the input graph is acyclic.
Complexity
O(graph.N() + graph.E())
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
Returns
- ↪YNodeList
- a YNodeList containing the nodes of the graph in the order identical to the order of node completion events in a depth first search
See Also
Assigns an st-ordering to the nodes of a biconnected graph given the edge between source node s and sink node t.
Remarks
st-ordering (v_1,v_2,....,v_n) of a biconnected graph is a node ordering which guarantees that:- Source node
sand sink nodetare connected by an edge. - For each node
v_iin the ordering other thansort, there are neighborsv_jandv_kwithj < iandk > i.
Complexity
O(graph.N() + graph.E())
Preconditions
stOrder.length == graph.N()- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- stOrder - number[]
- an array of numbers that will be filled during the execution and returns for each YNode
v, its zero-based index within the calculated ordering, i.e.,stOrder[v.index()] == 5means thatvis the6-th node within the ordering - stEdge - Edge
See Also
Assigns an st-ordering to the nodes of a biconnected graph.
Remarks
Like st but the result is returned as a YNodeList.
An st-ordering (v_1,v_2,....,v_n) of a biconnected graph is a node ordering which guarantees that:
- Source node
sand sink nodetare connected by an edge. - For each node
v_iin the ordering other thansort, there are neighborsv_jandv_kwithj < iandk > i.
Complexity
O(graph.N() + graph.E())
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
Returns
See Also
Converts an array-based result returned by a method of this class to a YNodeList that contains all nodes in the order provided by the given array.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- order - number[]
- an array of numbers that will be filled during the execution and returns for each YNode
v, its zero-based index within the calculated ordering, i.e.,order[v.index()] == 5means thatvis the6-th node within the ordering
Returns
Copies an array-based result returned by a method of this class to a INodeMap that will provide values of basic type int.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- order - number[]
- an array of numbers that returns for each YNode
v, its zero-based index within the calculated ordering, i.e.,order[v.index()] == 5means thatvis the6-th node within the ordering - result - INodeMap
- the INodeMap that will be filled during the execution with the zero-based index of each node within the calculated ordering
Domain YNode Values number a zero-based index for each node within the calculated ordering
Copies a YNodeList-based result returned by a method of this class to a INodeMap that will provide values of basic type int.
Parameters
A map of options to pass to the method.
- order - YNodeList
- a YNodeList containing the nodes of the graph in the appropriate order
- result - INodeMap
- the INodeMap that will be filled during the execution with the zero-based index of each node within the calculated ordering
Domain YNode Values number a zero-based index for each node within the calculated ordering
Assigns a topological ordering to the nodes of a directed acyclic graph.
Remarks
Note: This method works with instances of Graph. To retrieve a topological order of nodes in an IGraph use getTopologicalOrder instead.
A topological ordering of the nodes of a directed graph is a linear ordering of the nodes such that for each directed edge (u,v), node u lies before v in the ordering.
Complexity
O(graph.N() + graph.E())
Preconditions
order.length == graph.N()
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- order - number[]
- an array of numbers that will be filled during the execution and returns for each YNode
v, its zero-based index within the calculated ordering, i.e.,order[v.index()] == 5means thatvis the6-th node within the ordering
Returns
- ↪boolean
trueif the graph is acyclic,falseotherwise
See Also
false leaving the contents of the result array order unspecified.Returns a topological ordering of the nodes of a directed acyclic graph.
Remarks
Complexity
O(graph.N() + graph.E())
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
Returns
- ↪YNodeList
- a YNodeList containing the nodes of the graph in the order they appear in the topological ordering
Throws
- Exception({ name: 'ArgumentError' })
- if the graph is cyclic