de.jstacs.algorithms.graphs

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

Fields
Modifier and Type Field and Description
`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

All Methods
Modifier and Type Method and Description
`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.
Constant Field Values
• #### MINIMALBRANCHING

`public static final byte MINIMALBRANCHING`
Compute the branching yielding the minimum sum of weights.
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