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 NodeOrders.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 NodeOrders.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 NodeList	toNodeList(Graph graph, int[] order) Converts an array-based result yielded by a method of this class to a NodeList that contains all nodes of the order in the correct sequence.
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.

Precondition:

order.length == graph.N()

Complexity:

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

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.

topological

public static NodeList topological(Graph graph)

Returns a topological node order of an acyclic graph.

Precondition:

GraphChecker.isAcyclic(graph)

Complexity:

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

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.

Complexity:

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

See Also:

NodeOrders.topological(Graph,int[])

dfsCompletion

public static NodeList dfsCompletion(Graph graph)

Like NodeOrders.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.

   Preconditions:

   tOrder.length == graph.N()

   GraphChecker.isBiconnected(graph)

   Complexity:

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

   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.

st

public static NodeList st(Graph graph)

Like NodeOrders.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 yielded by a method of this class to a NodeList that contains all nodes of the order in the correct sequence.