
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.NodeOrders
public class NodeOrders
This class provides algorithms that order the nodes of a graph using specific criteria.
(u,v)
, node u
lies before v
in the ordering.
depth first search
.
(v_1,v_2,....,v_n)
of a biconnected graph is a node ordering which guarantees
that:
s
and sink node t
are connected by an edge.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 arraybased 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 arraybased 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 

public static boolean topological(Graph graph, int[] order)
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.
false
leaving the contents of the
result array order
unspecified.order.length == graph.N()
O(graph.N() + graph.E())
graph
 the input graphorder
 an array of Integer
s that will be filled during the execution and returns for each Node
v
, its zerobased index
within the calculated ordering, i.e., order[v.index()] == 5
means that v
is the
6
th node within the ordering
true
if the graph is acyclic, false
otherwisetopological(Graph)
public static NodeList topological(Graph graph)
acyclic
.O(graph.N() + graph.E())
graph
 the input graph
NodeList
containing the nodes of the graph in the order they appear in the topological
ordering
java.lang.IllegalArgumentException
 if the graph is cyclictopological(Graph, int[])
public static void dfsCompletion(Graph graph, int[] order)
This ordering is a reversed topological ordering in case the input graph is acyclic.
O(graph.N() + graph.E())
graph
 the input graphorder
 an array of Integer
s that returns for each Node
v
, its zerobased index
within the calculated ordering, i.e., order[v.index()] == 5
means that v
is the
6
th node within the orderingtopological(Graph,int[])
,
dfsCompletion(Graph)
public static NodeList dfsCompletion(Graph graph)
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.
O(graph.N() + graph.E())
graph
 the input graph
NodeList
containing the nodes of the graph in the order identical to the order of node completion
events in a depth first searchtopological(Graph,int[])
,
dfsCompletion(Graph,int[])
public static void st(Graph graph, int[] stOrder)
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:
s
and sink node t
are connected by an edge.v_i
in the ordering other than s
or t
, there are
neighbors v_j
and v_k
with j < i
and k > i
.
stOrder.length == graph.N()
biconnected
.O(graph.N() + graph.E())
graph
 the input graphstOrder
 an array of Integer
s that will be filled during the execution and returns for each Node
v
, its zerobased index within the calculated ordering, i.e.,
stOrder[v.index()] == 5
means that v
is the 6
th node
within the orderingst(Graph)
,
st(Graph, int[], Edge)
public static void st(Graph graph, int[] stOrder, Edge stEdge)
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:
s
and sink node t
are connected by an edge.v_i
in the ordering other than s
or t
, there are
neighbors v_j
and v_k
with j < i
and k > i
.
stOrder.length == graph.N()
biconnected
.O(graph.N() + graph.E())
graph
 the input graphstOrder
 an array of Integer
s that will be filled during the execution and returns for each
Node
v
, its zerobased index within the calculated ordering, i.e.,
stOrder[v.index()] == 5
means that v
is the 6
th node
within the orderingstEdge
 an Edge
that connects source node s
and sink node t
st(Graph)
,
st(Graph, int[])
public static NodeList st(Graph graph)
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:
s
and sink node t
are connected by an edge.v_i
in the ordering other than s
or t
, there are
neighbors v_j
and v_k
with j < i
and k > i
.
biconnected
.O(graph.N() + graph.E())
graph
 the input graph
NodeList
containing the nodes of the graph in the order defined by the st
orderingst(Graph, int[])
,
st(Graph, int[], Edge)
public static NodeList toNodeList(Graph graph, int[] order)
NodeList
that contains all nodes
in the order provided by the given array.
graph
 the input graphorder
 an array of Integer
s that will be filled during the execution and returns for each Node
v
, its zerobased index within the calculated ordering, i.e.,
order[v.index()] == 5
means that v
is the 6
th node within
the ordering
NodeList
containing the nodes of the graph in the order provided by the given arraypublic static void toNodeMap(Graph graph, int[] order, NodeMap result)
NodeMap
that will provide values of basic type int
.
graph
 the input graphorder
 an array of Integer
s that returns for each Node
v
, its zerobased index
within the calculated ordering, i.e., order[v.index()] == 5
means that v
is the
6
th node within the orderingresult
 the NodeMap
that will be filled during the execution with the
zerobased index of each node within the calculated orderingpublic static void toNodeMap(NodeList order, NodeMap result)
NodeList
based result returned by a method of this class
to a NodeMap
that will provide values of basic type int
.
order
 a NodeList
containing the nodes of the graph in the appropriate orderresult
 the NodeMap
that will be filled during the execution with the
zerobased index of each node within the calculated ordering

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 