|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES All Classes | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectde.jstacs.algorithms.graphs.DAG
public class DAG
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.
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 |
---|
public DAG()
Method Detail |
---|
public static int[] computeMaximalHP(Tensor score)
DAG
). Be aware of the memory
(O(2^L * L^k)) and time consumption.
score
- the Tensor
for the edge weights
Tensor
,
getStructureFromPath(int[], Tensor)
public static int[][] computeMaximalKDAG(Tensor score)
DAG
), i.e. the k-DAG that
maximizes the score given by a Tensor
.
score
- the Tensor
of the score values
Tensor
protected static int[][] computeMaxKDAG(SymmetricTensor score)
DAG
), i.e. the k-DAG that
maximizes the score given by a SymmetricTensor
.
score
- the SymmetricTensor
of the score values
SymmetricTensor
public static int[] enumerateHP(Tensor score)
DAG
). It tries to enumerate
all permutations and returns the best. This is only possible for a small
number of nodes (<=10).
score
- the Tensor
for the edge weights
getStructureFromPath(int[], Tensor)
public static double getScore(Tensor t, int[][] structure) throws IllegalArgumentException
t
- the Tensor
for the edge weightsstructure
- the graph (encoded as:
(structure[i][0],...,structure[i][structure[i].length-2])->structure[i][structure[i].length-1]
)
IllegalArgumentException
- if the structure length and the tensor length do not matchpublic static double getScoreForPath(Tensor score, int l, byte k, int[] path)
path
using the first
l
nodes and dependencies of order k
.
score
- the Tensor
of scoresl
- the number of used nodes (from perm
)k
- the orderpath
- the path
public static int[][] getStructureFromPath(int[] path, Tensor score)
path
and
score-"function".
path
- the pathscore
- the Tensor
of scores
public static String toDirectedGraphvizFormat(int[][] structure)
String
representation of the
structure that can be used in Graphviz to create an image.
structure
- the structure of the graph
String
representationtoGraphvizFormat(int[][], String)
public static String toUndirectedGraphvizFormat(int[][] structure)
String
representation of the
structure that can be used in Graphviz to create an image.
structure
- the structure of the graph
String
representationtoGraphvizFormat(int[][], String)
public static String toWeightedGraphvizFormat(int[][] structure, String arrow, Tensor t)
String
representation of the weighted
structure that can be used in Graphviz to create an image.
structure
- the structure of the grapharrow
- the kind of arrow that is used between the nodes, e.g.
"--" and "->"t
- the weights
String
representation of the weighted structureprotected static String toGraphvizFormat(int[][] structure, String arrow)
String
representation of the structure that
can be used in Graphviz to create an image.
structure
- the structure of the grapharrow
- the kind of arrow that is used between the nodes, e.g.
"--" and "->"
String
representation of the structure
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES All Classes | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |