y.algo
Class NodeOrders

java.lang.Object
  y.algo.NodeOrders

public class NodeOrders
extends 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 Integers 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

See Also:

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

See Also:

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

See Also:

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

See Also:

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

See Also:

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

See Also:

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

See Also:

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