|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
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 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.
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 maximize the score given by the tensor. |
protected static int[][] |
computeMaxKDAG(SymmetricTensor score)
Computes the maximal k-DAG, i.e. the k-DAG that maximize 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 and 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)
|
protected static String |
toGraphvizFormat(int[][] structure,
String arrow)
This method return a String representation of the structure that can be used in Graphviz to create an image. |
static String |
toUndirectedGraphvizFormat(int[][] structure)
|
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)
score
- the tensor for the edge weights
getStructureFromPath(int[], Tensor)
public static int[][] computeMaximalKDAG(Tensor score)
score
- the tensor of the score values
protected static int[][] computeMaxKDAG(SymmetricTensor score)
score
- the tensor of the score values
public static int[] enumerateHP(Tensor score)
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 structure length and tensor length does not matchpublic static double getScoreForPath(Tensor score, int l, byte k, int[] path)
path
and 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
- the pathscore
- the tensor of scores
public static String toDirectedGraphvizFormat(int[][] structure)
structure
- the structure of the graph
public static String toUndirectedGraphvizFormat(int[][] structure)
structure
- the structure of the graph
public static String toWeightedGraphvizFormat(int[][] structure, String arrow, Tensor t)
structure
- the structurearrow
- the kind of arrow that is used between the nodes, e.g. "--" and "->"t
- the weights
protected static String toGraphvizFormat(int[][] structure, String arrow)
structure
- the structurearrow
- the kind of arrow that is used between the nodes, e.g. "--" and "->"
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |