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 Chu_Liu_Edmonds

    java.lang.Object
      de.jstacs.algorithms.graphs.Chu_Liu_Edmonds

    public class Chu_Liu_Edmonds

extends Object

This class implements the algorithm of Chu_Liu_Edmonds to determine an optimal branching (optimal directed graph of order 1).

Author:
  Andre Gohr

Field Summary
`static byte` | `MAXIMALBRANCHING` Compute the branching yielding the maximum sum of weights.
`static byte` | `MINIMALBRANCHING` Compute the branching yielding the minimum sum of weights.

Method Summary
`static byte[][]` | `getOptimalBranching(double[][] graph, double[][] rootWeights, byte type)` Returns an optimal branching.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

### MAXIMALBRANCHING

    public static final byte MAXIMALBRANCHING

  Compute the branching yielding the maximum sum of weights.

  See Also:
    Constant Field Values

### MINIMALBRANCHING

    public static final byte MINIMALBRANCHING

  Compute the branching yielding the minimum sum of weights.

  See Also:
    Constant Field Values

Method Detail

### getOptimalBranching

    public static byte[][] getOptimalBranching(double[][] graph,
                                               double[][] rootWeights,
                                               byte type)
                                        throws IllegalArgumentException,
                                               Exception

  Returns an optimal branching.

  Parameters:
    `graph` -
    - of dimension `[number_of_nodes][number_of_nodes]`;
    - e.g. `[1][2]` contains the weight of edge (1,2), if node 2 is parent of node 1
    - the weight of non-existing edges should be `Double.POSITIVE_INFINITY`/ `Double.NEGATIVE_INFINITY` if a minimal/maximal branching is desired
    `rootWeights` - of dimension `[number_of_nodes][1]` and contains for each node the additional costs, if this node becomes a root of the optimal branching. Whether the returned optimal branching is a optimal directed spanning tree has to be checked by the client.
    `type` - either `Chu_Liu_Edmonds.MAXIMALBRANCHING` or `Chu_Liu_Edmonds.MINIMALBRANCHING`
  Returns:
    an optimal branching (probable a forest) decoded using a `byte[][]`. The first dimension is defined by the number of nodes N. If node i has parent `j -> byte[i]`={j,i}; if node i has no parent -> `byte[i]`={i}. The last position always contains the child node. The positions before contains the parent node if any.
  Throws:
    `IllegalArgumentException` - if the type was chosen wrongly
    `Exception` - if something went wrong

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