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)`

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

  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-exsisting edges should be Double.POSITIVE_INFINITY/Double.NEGATIVE_INFINITY if a minimal/maximial 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 spaning 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 containes the child node. The positions before contains the parent node if any.
  Throws:
    `IllegalArgumentException`
    `Exception`

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