public class TopSort extends Object
Constructor and Description |
---|
TopSort() |
Modifier and Type | Method and Description |
---|---|
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.
|
public static int[][] getTopologicalOrder(int[][] parents2)
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
parents2
- the array of parentspublic static byte[] getTopologicalOrder2(byte[][] aM)
aM
- a two-dimensional array describing the graph: aM.length
is equal no number of nodes in the
graphaM[i]
contains information (parents) of node
i
aM[i]={3,2,i}
means, that node i
has parents 3 and 2aM[i]={i}
means, that node i
has
no parentsi
at the end of each aM[i]
is mandatorybyte
-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 !!!