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

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

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