DynamicDAG (WebGraph 3.6.10)

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()`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- 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 class java.lang.Object
  - main
```
public static void main(java.lang.String[] args)
```