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