Search this API

## y.algo Class NodeOrders

```java.lang.Object
y.algo.NodeOrders
```

`public class NodeOrdersextends java.lang.Object`

This class provides algorithms that order the nodes of a graph using specific criteria.

### 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)`, node `u` lies before `v` in 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 `s` and sink node `t` are connected by an edge.
• For each node `v_i` in the ordering other than `s` or `t`, there are neighbors `v_j` and `v_k` with `j < i` and `k > i`.

Method Summary
`static NodeList` `dfsCompletion(Graph graph)`
Calculates an ordering of the nodes identical to the order of node completion events in a depth first search.
`static void` ```dfsCompletion(Graph graph, int[] order)```
Calculates an ordering of the nodes identical to the order of node completion events in a depth first search.
`static NodeList` `st(Graph graph)`
Assigns an `st`-ordering to the nodes of a biconnected graph.
`static void` ```st(Graph graph, int[] stOrder)```
Assigns an `st`-ordering to the nodes of a biconnected graph.
`static void` ```st(Graph graph, int[] stOrder, Edge stEdge)```
Assigns an `st`-ordering to the nodes of a biconnected graph given the edge between source node `s` and sink node `t`.
`static NodeList` ```toNodeList(Graph graph, int[] order)```
Converts an array-based result returned by a method of this class to a `NodeList` that contains all nodes in the order provided by the given array.
`static void` ```toNodeMap(Graph graph, int[] order, NodeMap result)```
Copies an array-based result returned by a method of this class to a `NodeMap` that will provide values of basic type `int`.
`static void` ```toNodeMap(NodeList order, NodeMap result)```
Copies a `NodeList`-based result returned by a method of this class to a `NodeMap` that will provide values of basic type `int`.
`static NodeList` `topological(Graph graph)`
Returns a topological ordering of the nodes of a directed acyclic graph.
`static boolean` ```topological(Graph graph, int[] order)```
Assigns a topological ordering to the nodes of a directed acyclic graph.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Method Detail

### topological

```public static boolean topological(Graph graph,
int[] order)```
Assigns a topological ordering to the nodes of a directed acyclic graph.

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.

If the given graph is not acyclic, this method returns `false` leaving the contents of the result array `order` unspecified.
Precondition:
`order.length == graph.N()`
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`order` - an array of `Integer`s that will be filled during the execution and returns for each `Node` `v`, its zero-based index within the calculated ordering, i.e., `order[v.index()] == 5` means that `v` is the `6`-th node within the ordering
Returns:
`true` if the graph is acyclic, `false` otherwise
`topological(Graph)`

### topological

`public static NodeList topological(Graph graph)`
Returns a topological ordering of the nodes of a directed acyclic graph.

Precondition:
The graph must be `acyclic`.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
Returns:
a `NodeList` containing the nodes of the graph in the order they appear in the topological ordering
Throws:
`java.lang.IllegalArgumentException` - if the graph is cyclic
`topological(Graph, int[])`

### dfsCompletion

```public static void dfsCompletion(Graph graph,
int[] order)```
Calculates an ordering of the nodes identical to the order of node completion events in a depth first search.

This ordering is a reversed topological ordering in case the input graph is acyclic.

Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`order` - an array of `Integer`s that returns for each `Node` `v`, its zero-based index within the calculated ordering, i.e., `order[v.index()] == 5` means that `v` is the `6`-th node within the ordering
`topological(Graph,int[])`, `dfsCompletion(Graph)`

### dfsCompletion

`public static NodeList dfsCompletion(Graph graph)`
Calculates an ordering of the nodes identical to the order of node completion events in a depth first search.

Like `dfsCompletion(Graph,int[])` but the result is returned as a `NodeList`.

This ordering is a reversed topological ordering in case the input graph is acyclic.

Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
Returns:
a `NodeList` containing the nodes of the graph in the order identical to the order of node completion events in a depth first search
`topological(Graph,int[])`, `dfsCompletion(Graph,int[])`

### st

```public static void st(Graph graph,
int[] stOrder)```
Assigns an `st`-ordering to the nodes of a biconnected graph.

An `st`-ordering `(v_1,v_2,....,v_n)` of a biconnected graph is a node ordering which guarantees that:

• Source node `s` and sink node `t` are connected by an edge.
• For each node `v_i` in the ordering other than `s` or `t`, there are neighbors `v_j` and `v_k` with `j < i` and `k > i`.

Preconditions:
`stOrder.length == graph.N()`
The graph must be `biconnected`.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`stOrder` - an array of `Integer`s that will be filled during the execution and returns for each `Node` `v`, its zero-based index within the calculated ordering, i.e., `stOrder[v.index()] == 5` means that `v` is the `6`-th node within the ordering
`st(Graph)`, `st(Graph, int[], Edge)`

### st

```public static void st(Graph graph,
int[] stOrder,
Edge stEdge)```
Assigns an `st`-ordering to the nodes of a biconnected graph given the edge between source node `s` and sink node `t`.

An `st`-ordering `(v_1,v_2,....,v_n)` of a biconnected graph is a node ordering which guarantees that:

• Source node `s` and sink node `t` are connected by an edge.
• For each node `v_i` in the ordering other than `s` or `t`, there are neighbors `v_j` and `v_k` with `j < i` and `k > i`.

Preconditions:
`stOrder.length == graph.N()`
The graph must be `biconnected`.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
`stOrder` - an array of `Integer`s that will be filled during the execution and returns for each `Node` `v`, its zero-based index within the calculated ordering, i.e., `stOrder[v.index()] == 5` means that `v` is the `6`-th node within the ordering
`stEdge` - an `Edge` that connects source node `s` and sink node `t`
`st(Graph)`, `st(Graph, int[])`

### st

`public static NodeList st(Graph graph)`
Assigns an `st`-ordering to the nodes of a biconnected graph.

Like `st(Graph, int[])` but the result is returned as a `NodeList`.

An `st`-ordering `(v_1,v_2,....,v_n)` of a biconnected graph is a node ordering which guarantees that:

• Source node `s` and sink node `t` are connected by an edge.
• For each node `v_i` in the ordering other than `s` or `t`, there are neighbors `v_j` and `v_k` with `j < i` and `k > i`.

Precondition:
The graph must be `biconnected`.
Complexity:
`O(graph.N() + graph.E())`
Parameters:
`graph` - the input graph
Returns:
a `NodeList` containing the nodes of the graph in the order defined by the `st`-ordering
`st(Graph, int[])`, `st(Graph, int[], Edge)`

### toNodeList

```public static NodeList toNodeList(Graph graph,
int[] order)```
Converts an array-based result returned by a method of this class to a `NodeList` that contains all nodes in the order provided by the given array.

Parameters:
`graph` - the input graph
`order` - an array of `Integer`s that will be filled during the execution and returns for each `Node` `v`, its zero-based index within the calculated ordering, i.e., `order[v.index()] == 5` means that `v` is the `6`-th node within the ordering
Returns:
a `NodeList` containing the nodes of the graph in the order provided by the given array

### toNodeMap

```public static void toNodeMap(Graph graph,
int[] order,
NodeMap result)```
Copies an array-based result returned by a method of this class to a `NodeMap` that will provide values of basic type `int`.

Parameters:
`graph` - the input graph
`order` - an array of `Integer`s that returns for each `Node` `v`, its zero-based index within the calculated ordering, i.e., `order[v.index()] == 5` means that `v` is the `6`-th node within the ordering
`result` - the `NodeMap` that will be filled during the execution with the zero-based index of each node within the calculated ordering

### toNodeMap

```public static void toNodeMap(NodeList order,
NodeMap result)```
Copies a `NodeList`-based result returned by a method of this class to a `NodeMap` that will provide values of basic type `int`.

Parameters:
`order` - a `NodeList` containing the nodes of the graph in the appropriate order
`result` - the `NodeMap` that will be filled during the execution with the zero-based index of each node within the calculated ordering