Search this API

y.algo
Class NodeOrders

java.lang.Object
  extended by 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

 

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:

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:

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:

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

© Copyright 2000-2022,
yWorks GmbH.
All rights reserved.