y.algo
Class NodeOrders

java.lang.Object
  y.algo.NodeOrders

public class NodeOrders
extends Object

Provides graph algorithms that order the nodes of a graph by a specific criterion.

Constructor Summary

NodeOrders()

Method Summary

static NodeList	dfsCompletion(Graph graph) Like dfsCompletion(Graph,int[]) but the result is returned as a NodeList.
static void	dfsCompletion(Graph graph, int[] order) This method calculates a node order that is identical with the order of node completion events in a depth first search.
static NodeList	st(Graph graph) Like st(Graph, int[]) but the result is returned as a NodeList.
static void	st(Graph graph, int[] stOrder) Assigns an ST-order to the nodes of a biconnected graph.
static void	st(Graph graph, int[] stOrder, Edge stEdge) Similar to st(Graph, int[]).
static NodeList	toNodeList(Graph graph, int[] order) Converts an array-based result yield by a method of this class to a NodeList that contains all nodes of the order in the correct sequence.
static void	toNodeMap(Graph graph, int[] order, NodeMap result) Copies an array-based result yield 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 list-based result yield by a method of this class to a NodeMap.
static NodeList	topological(Graph graph) Returns a topological node order of an acyclic graph.
static boolean	topological(Graph graph, int[] order) Assigns a topological order to the nodes of an acyclic graph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NodeOrders

public NodeOrders()

Method Detail

topological

public static boolean topological(Graph graph,
                                  int[] order)

Assigns a topological order to the nodes of an acyclic graph.

If the given graph is not acyclic then this method returns false leaving the contents of result topOrder unspecified.

A topological node order of an acyclic graph has the property that for each node v all of its successors have a higher rank in the order than v itself.

Parameters:

graph - the graph being acted upon

order - result value that holds for each node v the zero-based index within the calculated order, i.e topOrder[v.index()] == 5 means that v is the 6-th node within the order.

Complexity:

O(graph.N()+graph.E())

Precondition:

order.length == graph.N()

topological

public static NodeList topological(Graph graph)

Returns a topological node order of an acyclic graph.

Complexity:

O(graph.N()+graph.E())

Precondition:

GraphChecker.isAcyclic(graph)

dfsCompletion

public static void dfsCompletion(Graph graph,
                                 int[] order)

This method calculates a node order that is identical with the order of node completion events in a depth first search. This order is a reversed topological order in case the input graph is acyclic.

See Also:

topological(Graph,int[])

Complexity:

O(graph.N()+graph.E())

dfsCompletion

public static NodeList dfsCompletion(Graph graph)

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

st

public static void st(Graph graph,
                      int[] stOrder)

Assigns an ST-order to the nodes of a biconnected graph. An ST order (v_1,v_2,....,v_n) for a biconnected graph is a node order which guarantees that

1. the first node S and the last node T are connected by an edge.
2. For each node v_i in the order that are not S or T there are neighbors v_j and v_k with j < i and k > i.

Parameters:

graph - the graph being acted upon

stOrder - result value that holds for each node v the zero-based index within the calculated order, i.e stOrder[v.index()] == 5 means that v is the 6-th node within the order.

Complexity:

O(graph.N()+graph.E())

Preconditions:

tOrder.length == graph.N()

GraphChecker.isBiconnected(graph)

st

public static void st(Graph graph,
                      int[] stOrder,
                      Edge stEdge)

Similar to st(Graph, int[]). Additionally, the edge between the first node S and the last node T of the returned ordering can be specified.

Parameters:

stEdge - an edge that connects the first node of the ordering with the last node of the ordering.

st

public static NodeList st(Graph graph)

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

toNodeList

public static NodeList toNodeList(Graph graph,
                                  int[] order)

Converts an array-based result yield by a method of this class to a NodeList that contains all nodes of the order in the correct sequence.

toNodeMap

public static void toNodeMap(Graph graph,
                             int[] order,
                             NodeMap result)

Copies an array-based result yield by a method of this class to a NodeMap that will provide values of basic type int.

toNodeMap

public static void toNodeMap(NodeList order,
                             NodeMap result)

Copies a list-based result yield by a method of this class to a NodeMap. The resulting NodeMap will provide for each node the index of the node within the given order. The index is of basic type int.