public class Chu_Liu_Edmonds extends Object
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.
|
Modifier and Type | Method and Description |
---|---|
static byte[][] |
getOptimalBranching(double[][] graph,
double[][] rootWeights,
byte type)
Returns an optimal branching.
|
public static final byte MAXIMALBRANCHING
public static final byte MINIMALBRANCHING
public static byte[][] getOptimalBranching(double[][] graph, double[][] rootWeights, byte type) throws IllegalArgumentException, Exception
graph
- [number_of_nodes][number_of_nodes]
;
[1][2]
contains the weight of edge
(1,2), if node 2 is parent of node 1
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
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.IllegalArgumentException
- if the type was chosen wronglyException
- if something went wrong