de.jstacs.algorithms.graphs

## Class TopSort

• ```public class TopSort
extends Object```
Class for a topological sort.
Author:
Jan Grau
• ### Constructor Summary

Constructors
Constructor and Description
`TopSort()`
• ### Method Summary

All Methods
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.
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Constructor Detail

• #### TopSort

`public TopSort()`
• ### Method Detail

• #### 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:
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 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.