com.yworks.yfiles.algorithms

Class NodeOrders

java.lang.Object

com.yworks.yfiles.algorithms.NodeOrders

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

Method Summary

Modifier and Type	Method and Description
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 given the edge between source node s and sink node t.
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, INodeMap result) Copies an array-based result returned by a method of this class to a INodeMap that will provide values of basic type int.
static void	toNodeMap(NodeList order, INodeMap result) Copies a NodeList-based result returned by a method of this class to a INodeMap 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

dfsCompletion

public static final 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[])

dfsCompletion

public static final 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)

st

public static final NodeList st(Graph graph)

Assigns an st-ordering to the nodes of a biconnected graph.

Like st(Graph, int[], Edge) 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[], Edge)

st

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

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

See Also:

st(Graph), st(Graph, int[], Edge)

st

public static final 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[], Edge)

toNodeList

public static final 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 final void toNodeMap(Graph graph,
                                   int[] order,
                                   INodeMap result)

Copies an array-based result returned by a method of this class to a INodeMap 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 INodeMap that will be filled during the execution with the zero-based index of each node within the calculated ordering

toNodeMap

public static final void toNodeMap(NodeList order,
                                   INodeMap result)

Copies a NodeList-based result returned by a method of this class to a INodeMap that will provide values of basic type int.

Parameters:

order - a NodeList containing the nodes of the graph in the appropriate order

result - the INodeMap that will be filled during the execution with the zero-based index of each node within the calculated ordering

topological

public static final NodeList topological(Graph graph)

Returns a topological ordering of the nodes of a directed acyclic graph.

Throws:

IllegalArgumentException - if the graph is cyclic

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

See Also:

topological(Graph, int[])

topological

public static final 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)