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.
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 -
Field Summary
FieldsModifier and TypeFieldDescriptionThe underlying topological order of nodes. -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionboolean
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).Adds a new node.static void
toString()
-
Field Details
-
dynamicOrderedList
The underlying topological order of nodes.
-
-
Constructor Details
-
DynamicDAG
public DynamicDAG(double overflowThreshold) Creates an empty DAG.- Parameters:
overflowThreshold
- the threshold to be used to when building the dynamic ordered list.
-
-
Method Details
-
addNode
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
-
main
-