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

Constructor Summary

TopSort()

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

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.