Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

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

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD