Package it.unimi.dsi.webgraph.scratch
Class DynamicDAG<K>
- java.lang.Object
-
- it.unimi.dsi.webgraph.scratch.DynamicDAG<K>
-
- Type Parameters:
K
- the type of nodes.
public class DynamicDAG<K> extends java.lang.Object
This class represents a dynamic DAG (nodes and arcs can be added but not deleted), keeping at the same time a topological order of its nodes, as described in: Haeupler, Bernhard, et al. "Incremental cycle detection, topological ordering, and strong component maintenance." ACM Transactions on Algorithms (TALG) 8.1 (2012): 3. Only Limited-Search (Fig. 1) is implemented.
-
-
Nested Class Summary
Nested Classes Modifier and Type Class Description static class
DynamicDAG.DAGNode<K>
The type of a DAG node.
-
Field Summary
Fields Modifier and Type Field Description DynamicOrderedList<DynamicDAG.DAGNode<K>>
dynamicOrderedList
The underlying topological order of nodes.
-
Constructor Summary
Constructors Constructor Description DynamicDAG(double overflowThreshold)
Creates an empty DAG.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
addArc(DynamicOrderedList.DOLNode<DynamicDAG.DAGNode<K>> source, DynamicOrderedList.DOLNode<DynamicDAG.DAGNode<K>> target)
Adds an arc, if needed (does nothing if the arc is already present).DynamicOrderedList.DOLNode<DynamicDAG.DAGNode<K>>
addNode(K content)
Adds a new node.static void
main(java.lang.String[] args)
java.lang.String
toString()
-
-
-
Field Detail
-
dynamicOrderedList
public DynamicOrderedList<DynamicDAG.DAGNode<K>> dynamicOrderedList
The underlying topological order of nodes.
-
-
Constructor Detail
-
DynamicDAG
public DynamicDAG(double overflowThreshold)
Creates an empty DAG.- Parameters:
overflowThreshold
- the threshold to be used to when building the dynamic ordered list.
-
-
Method Detail
-
addNode
public DynamicOrderedList.DOLNode<DynamicDAG.DAGNode<K>> addNode(K content)
Adds a new node.- Parameters:
content
- the node content.- Returns:
- the newly created node (as part of the topological order).
-
addArc
public boolean addArc(DynamicOrderedList.DOLNode<DynamicDAG.DAGNode<K>> source, DynamicOrderedList.DOLNode<DynamicDAG.DAGNode<K>> target)
Adds an arc, if needed (does nothing if the arc is already present).- Parameters:
source
- arc source.target
- arc target.- Returns:
true
if the arc was added (or there was no need to add it). False if adding the arc would create cycles.
-
toString
public java.lang.String toString()
- Overrides:
toString
in classjava.lang.Object
-
main
public static void main(java.lang.String[] args)
-
-