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)
Method to compute 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 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 order
getTopologicalOrder2
public static byte[] getTopologicalOrder2(byte[][] aM)
- Method to compute a topological ordering for a given graph.
- Parameters:
aM
- two-dim array describing the graph
1. aM.length is equal no number of nodes in the graph
2. aM[i] contains information (parents) of node i
3. aM[i]={3,2,i} means, that node i has parents 3 and 2
4. aM[i]={i} means, that node i has no parents
5. the i at the end of each aM[i] is mandatory
- Returns:
- byte-array of length numberOfNodesInGraph that contains at pos 0 the nodeID of the first node
in the ordering, at pos 1 the nodeID of the second node in the order and so on
!!!if the graph contained a cyclus or other problems occured the returned array is of length zero