de.jstacs.algorithms.graphs

Class 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

Constructors
Constructor and Description
`DAG()`
• Method Summary

All Methods
Modifier and Type Method and Description
`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

• 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
`Tensor`
• 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)
`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)
• 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
`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