de.jstacs.algorithms.graphs
Class TopSort
java.lang.Object
de.jstacs.algorithms.graphs.TopSort
public class TopSort
- extends Object
Class for a topological sort.
- Author:
- Jan Grau
Method Summary |
static int[][] |
getTopologicalOrder(int[][] parents2)
Returns the topological order of indexes according to
parents2 . |
static byte[] |
getTopologicalOrder2(byte[][] aM)
Computes a topological ordering for a given graph. |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
TopSort
public TopSort()
getTopologicalOrder
public static int[][] getTopologicalOrder(int[][] parents2)
- Returns the topological order of indexes according to
parents2
. The array parents2
at each position
i
contains the parents, i.e. incoming edges, for this
position at indexes 0
to parents2[i].length -
2 and i
itself at position
parents2[i].length - 1
. The returned array of the
topological order is organized as follows:
-
parents[i][0]
contains the index in
parents2
with number i
in the topological order
-
parents[j][1]
contains the number of index
j
in the topological order
- Parameters:
parents2
- the array of parents
- Returns:
- the topological order
getTopologicalOrder2
public static byte[] getTopologicalOrder2(byte[][] aM)
- Computes a topological ordering for a given graph.
- Parameters:
aM
- a two-dimensional array describing the graph:
aM.length
is equal no number of nodes in the
graph
aM[i]
contains information (parents) of node
i
aM[i]={3,2,i}
means, that node i
has parents 3 and 2
aM[i]={i}
means, that node i
has
no parents
- the
i
at the end of each aM[i]
is mandatory
- Returns:
byte
-array of length
"numberOfNodesInGraph" that contains at pos 0 the id of
the first node in the ordering, at pos 1 the id of the second
node in the order and so on !!!
If the graph contained a cyclus or other problems occurred the
returned array is of length zero.