de.jstacs.algorithms.graphs
Class DAG

java.lang.Object
  de.jstacs.algorithms.graphs.DAG

public class DAG
extends Object

This is the main class of the graph library. Most methods are written for maximization, but they can also be used for minimization if the score is inverted.

A DAG is a directed acyclic graph. A k-DAG is a DAG with k special nodes that have 0,1,...,k-1 parents and all the other nodes have k parents. A path is a sequence of nodes so that two neighboring nodes are connected by an edge. A HP (Hamiltonian Path) is a path that visits all nodes of an DAG exactly once and maximizes some score function. The HP(k) is the Hamiltonian Path using a score function that depends on the last k visited nodes.

Author:

Jens Keilwagen

Constructor Summary

DAG()

Method Summary

static int[]	computeMaximalHP(Tensor score) The method computes the HP(k) (see DAG).
static int[][]	computeMaximalKDAG(Tensor score) Computes the maximal k-DAG (see DAG), i.e.
protected static int[][]	computeMaxKDAG(SymmetricTensor score) Computes the maximal k-DAG (see DAG), i.e.
static int[]	enumerateHP(Tensor score) The method computes the HP(k) (see DAG).
static double	getScore(Tensor t, int[][] structure) Returns the score for any graph.
static double	getScoreForPath(Tensor score, int l, byte k, int[] path) Returns the score for a given path path using the first l nodes and dependencies of order k.
static int[][]	getStructureFromPath(int[] path, Tensor score) Extracts the structure from a given path path and score-"function".
static String	toDirectedGraphvizFormat(int[][] structure) This method returns a directed String representation of the structure that can be used in Graphviz to create an image.
protected static String	toGraphvizFormat(int[][] structure, String arrow) This method returns a String representation of the structure that can be used in Graphviz to create an image.
static String	toUndirectedGraphvizFormat(int[][] structure) This method returns an undirected String representation of the structure that can be used in Graphviz to create an image.
static String	toWeightedGraphvizFormat(int[][] structure, String arrow, Tensor t) This method returns a String representation of the weighted structure that can be used in Graphviz to create an image.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DAG

public DAG()

Method Detail

computeMaximalHP

public static int[] computeMaximalHP(Tensor score)

The method computes the HP(k) (see DAG). Be aware of the memory (O(2^L * L^k)) and time consumption.

Parameters:

score - the Tensor for the edge weights

Returns:

the HP(k) (the sequence of nodes)

See Also:

Tensor, getStructureFromPath(int[], Tensor)

computeMaximalKDAG

public static int[][] computeMaximalKDAG(Tensor score)

Computes the maximal k-DAG (see DAG), i.e. the k-DAG that maximizes the score given by a Tensor.

This implementation uses a DP (dynamic programming) algorithm.

Parameters:

score - the Tensor of the score values

Returns:

the maximal k-DAG

See Also:

Tensor

computeMaxKDAG

protected static int[][] computeMaxKDAG(SymmetricTensor score)

Computes the maximal k-DAG (see DAG), i.e. the k-DAG that maximizes the score given by a SymmetricTensor.

This implementation uses a DP (dynamic programming) algorithm.

Parameters:

score - the SymmetricTensor of the score values

Returns:

the maximal k-DAG

See Also:

SymmetricTensor

enumerateHP

public static int[] enumerateHP(Tensor score)

The method computes the HP(k) (see DAG). It tries to enumerate all permutations and returns the best. This is only possible for a small number of nodes (<=10).

Parameters:

score - the Tensor for the edge weights

Returns:

the HP(k) (the sequence of nodes)

See Also:

getStructureFromPath(int[], Tensor)

getScore

public static double getScore(Tensor t,
                              int[][] structure)
                       throws IllegalArgumentException

Returns the score for any graph.

Parameters:

t - the Tensor for the edge weights

structure - the graph (encoded as: (structure[i][0],...,structure[i][structure[i].length-2])->structure[i][structure[i].length-1] )

Returns:

the score for the graph

Throws:

IllegalArgumentException - if the structure length and the tensor length do not match

getScoreForPath

public static double getScoreForPath(Tensor score,
                                     int l,
                                     byte k,
                                     int[] path)

Returns the score for a given path path using the first l nodes and dependencies of order k.

Parameters:

score - the Tensor of scores

l - the number of used nodes (from perm)

k - the order

path - the path

Returns:

the score for the given path

getStructureFromPath

public static int[][] getStructureFromPath(int[] path,
                                           Tensor score)

Extracts the structure from a given path path and score-"function".

Parameters:

path - the path

score - the Tensor of scores

Returns:

the structure of the given path (the edges)

toDirectedGraphvizFormat

public static String toDirectedGraphvizFormat(int[][] structure)

This method returns a directed String representation of the structure that can be used in Graphviz to create an image.

Parameters:

structure - the structure of the graph

Returns:

a directed String representation

See Also:

toGraphvizFormat(int[][], String)

toUndirectedGraphvizFormat

public static String toUndirectedGraphvizFormat(int[][] structure)

This method returns an undirected String representation of the structure that can be used in Graphviz to create an image.

Parameters:

structure - the structure of the graph

Returns:

an undirected String representation

See Also:

toGraphvizFormat(int[][], String)

toWeightedGraphvizFormat

public static String toWeightedGraphvizFormat(int[][] structure,
                                              String arrow,
                                              Tensor t)

This method returns a String representation of the weighted structure that can be used in Graphviz to create an image.

Parameters:

structure - the structure of the graph

arrow - the kind of arrow that is used between the nodes, e.g. "--" and "->"

t - the weights

Returns:

a String representation of the weighted structure

toGraphvizFormat

protected static String toGraphvizFormat(int[][] structure,
                                         String arrow)

This method returns a String representation of the structure that can be used in Graphviz to create an image.

Parameters:

structure - the structure of the graph

arrow - the kind of arrow that is used between the nodes, e.g. "--" and "->"

Returns:

a String representation of the structure