Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD

## 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 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 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).
`static int[][]` | `computeMaximalKDAG(Tensor score)` Computes the maximal k-DAG, i.e. the k-DAG that maximizes the score given by the tensor.
`protected static int[][]` | `computeMaxKDAG(SymmetricTensor score)` Computes the maximal k-DAG, i.e. the k-DAG that maximizes the score given by the tensor.
`static int[]` | `enumerateHP(Tensor score)` The method computes the HP(k).
`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 and score-"function".
`static String` | `toDirectedGraphvizFormat(int[][] structure)` This method returns a `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 a `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). Be aware of the memory (O(2^L * L^k)) and time consumption.

  Parameters:
    `score` - the tensor for the edge weights
  Returns:
    the HP (the sequence of nodes)
  See Also:
    `getStructureFromPath(int[], Tensor)`

### computeMaximalKDAG

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

  Computes the maximal k-DAG, i.e. the k-DAG that maximizes the score given by the tensor.
  This implementation uses a DP algorithm.

  Parameters:
    `score` - the tensor of the score values
  Returns:
    the k-DAG

### computeMaxKDAG

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

  Computes the maximal k-DAG, i.e. the k-DAG that maximizes the score given by the tensor.
  This implementation uses a DP algorithm.

  Parameters:
    `score` - the tensor of the score values
  Returns:
    the k-DAG

### enumerateHP

    public static int[] enumerateHP(Tensor score)

  The method computes the HP(k). 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 (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
  Throws:
    `IllegalArgumentException` - if structure length and 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 path

### getStructureFromPath

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

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

  Parameters:
    `path` - the path
    `score` - the tensor of scores
  Returns:
    the structure (the edges)

### toDirectedGraphvizFormat

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

  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
  Returns:
    a directed `String` representation
  See Also:
    `toGraphvizFormat(int[][], String)`

### toUndirectedGraphvizFormat

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

  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
  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
    `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 that can be used in Graphviz to create an image

### 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
    `arrow` - the kind of arrow that is used between the nodes, e.g. "--" and "->"
  Returns:
    a `String` representation of the structure that can be used in Graphviz to create an image

Overview | Package | Class | Use | Tree | Deprecated | Index | Help
PREV CLASS NEXT CLASS | FRAMES NO FRAMES
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD