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 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. the k-DAG that maximizes the score given by a `Tensor`.
`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`.
`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

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