|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES All Classes | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectde.jstacs.algorithms.graphs.Chu_Liu_Edmonds
public class Chu_Liu_Edmonds
This class implements the algorithm of Chu_Liu_Edmonds to determine an optimal branching (optimal directed graph of order 1).
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 |
---|
public static final byte MAXIMALBRANCHING
public static final byte MINIMALBRANCHING
Method Detail |
---|
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 wrongly
Exception
- if something went wrong
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES All Classes | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |