it.unimi.dsi.webgraph
Class ArrayListMutableGraph

java.lang.Object
  extended by it.unimi.dsi.webgraph.ArrayListMutableGraph

public class ArrayListMutableGraph
extends Object

A very simple mutable graph class based on IntArrayLists.

When creating examples for test cases or everyday usage, this class offers practical constructors. For instance, a 3-cycle is easily built as

     new ArrayListMutableGraph( 3, new int[][] { { 0, 1 }, { 1, 2 }, { 2, 0 } } )
 

Moreover, methods like addNodes(int) and addArc(int, int) allow to change the graph structure after construction, and several static factory methods provides ready-made common graphs (see, e.g., newCompleteBinaryIntree(int)).

A mutable graph is not an ImmutableGraph. However, it is possible to obtain an immutable view of a mutable graph. The view is valid until the exposed mutable graph is modified. A modification counter is used to cause a fail-fast behaviour in case the immutable view is used after modifications.

Warning: obtaining a NodeIterator and using it while modifying the graph will lead to unpredictable results.


Field Summary
protected  it.unimi.dsi.webgraph.ArrayListMutableGraph.ImmutableView immutableView
          A cached copy of the immutable view, if it has ever been requested.
protected  int lastModificationCount
          The modification count at the last call to immutableView().
protected  long m
          Current number of arcs.
protected  int modificationCount
          The current modification count.
protected  int n
          Current number of nodes.
protected  IntArrayList[] successors
          Current list of successor lists.
 
Constructor Summary
ArrayListMutableGraph()
          Creates a new empty mutable graph.
ArrayListMutableGraph(ImmutableGraph g)
          Creates a new mutable graph copying a given immutable graph.
ArrayListMutableGraph(int numNodes)
          Creates a new disconnected mutable graph with specified number of nodes.
ArrayListMutableGraph(int numNodes, int[][] arc)
          Creates a new mutable graph using a given number of nodes and a given list of arcs.
ArrayListMutableGraph(int numNodes, Transform.ArcFilter arcFilter)
          Creates a new mutable graph using a given number of nodes and a given arc filter.
 
Method Summary
 void addArc(int x, int y)
          Adds the given arc.
 void addNodes(int numNewNodes)
          Adds the given number of nodes, numbering them from numNodes() onwards.
protected  void ensureNode(int x)
          Guarantees that a node index is valid.
 boolean equals(Object o)
          Compare this mutable graph to another object.
 int hashCode()
          Returns a hash code for this mutable graph.
 ImmutableGraph immutableView()
          Returns an immutable view of this mutable graph.
static ArrayListMutableGraph newBidirectionalCycle(int numNodes)
          Returns a new mutable graph containing a bidirectional cycle.
static ArrayListMutableGraph newCompleteBinaryIntree(int height)
          Returns a new mutable graph containing a complete binary in-tree of given height.
static ArrayListMutableGraph newCompleteBinaryOuttree(int height)
          Returns a new mutable graph containing a complete binary out-tree of given height.
static ArrayListMutableGraph newCompleteGraph(int numNodes, boolean loops)
          Returns a new mutable graph containing a complete graph.
static ArrayListMutableGraph newDirectedCycle(int numNodes)
          Returns a new mutable graph containing a directed cycle.
 long numArcs()
           
 int numNodes()
           
 int outdegree(int x)
           
 void removeArc(int x, int y)
          Removes the given arc.
 void removeNode(int x)
          Removes the given node.
 int[] successorArray(int x)
           
 IntIterator successors(int x)
           
 String toString()
           
 
Methods inherited from class java.lang.Object
clone, finalize, getClass, notify, notifyAll, wait, wait, wait
 

Field Detail

n

protected int n
Current number of nodes.


m

protected long m
Current number of arcs.


successors

protected IntArrayList[] successors
Current list of successor lists. The backing array might be longer than n.


immutableView

protected it.unimi.dsi.webgraph.ArrayListMutableGraph.ImmutableView immutableView
A cached copy of the immutable view, if it has ever been requested.


modificationCount

protected int modificationCount
The current modification count.


lastModificationCount

protected int lastModificationCount
The modification count at the last call to immutableView().

Constructor Detail

ArrayListMutableGraph

public ArrayListMutableGraph()
Creates a new empty mutable graph.


ArrayListMutableGraph

public ArrayListMutableGraph(int numNodes)
Creates a new disconnected mutable graph with specified number of nodes.

Parameters:
numNodes - the number of nodes in the graph.

ArrayListMutableGraph

public ArrayListMutableGraph(int numNodes,
                             int[][] arc)
Creates a new mutable graph using a given number of nodes and a given list of arcs.

Parameters:
numNodes - the number of nodes in the graph.
arc - an array of arrays of length 2, specifying the arcs; no sanity checks are performed..

ArrayListMutableGraph

public ArrayListMutableGraph(ImmutableGraph g)
Creates a new mutable graph copying a given immutable graph.

This method will not invoke ImmutableGraph.numNodes(), but rather just create a NodeIterator and exhaust it.

Parameters:
g - an immutable graph.

ArrayListMutableGraph

public ArrayListMutableGraph(int numNodes,
                             Transform.ArcFilter arcFilter)
Creates a new mutable graph using a given number of nodes and a given arc filter.

Parameters:
numNodes - the number of nodes in the graph.
arcFilter - an arc filter which will specify which arcs go into the graph.
Method Detail

ensureNode

protected void ensureNode(int x)
Guarantees that a node index is valid.

Parameters:
x - a node index.

newDirectedCycle

public static ArrayListMutableGraph newDirectedCycle(int numNodes)
Returns a new mutable graph containing a directed cycle.

Parameters:
numNodes - the number of nodes in the cycle.

newBidirectionalCycle

public static ArrayListMutableGraph newBidirectionalCycle(int numNodes)
Returns a new mutable graph containing a bidirectional cycle.

Parameters:
numNodes - the number of nodes in the cycle.

newCompleteGraph

public static ArrayListMutableGraph newCompleteGraph(int numNodes,
                                                     boolean loops)
Returns a new mutable graph containing a complete graph.

Parameters:
numNodes - the number of nodes in the graph.
loops - true if you want loops, too.

newCompleteBinaryIntree

public static ArrayListMutableGraph newCompleteBinaryIntree(int height)
Returns a new mutable graph containing a complete binary in-tree of given height. Warning: starting from version 1.7, the spurious loop at the root has been removed.

Parameters:
height - the height of the tree (0 for the root only).

newCompleteBinaryOuttree

public static ArrayListMutableGraph newCompleteBinaryOuttree(int height)
Returns a new mutable graph containing a complete binary out-tree of given height. Warning: starting from version 1.7, the spurious loop at the root has been removed.

Parameters:
height - the height of the tree (0 for the root only).

immutableView

public ImmutableGraph immutableView()
Returns an immutable view of this mutable graph.

The view can be used until this mutable graph is modified. Attempt to use the view after modifying this mutable graph will cause a ConcurrentModificationException. After modification, a new call to this method will return a new immutable view.

Returns:
an immutable view of this mutable graph.

numNodes

public int numNodes()

outdegree

public int outdegree(int x)

numArcs

public long numArcs()

successorArray

public int[] successorArray(int x)

successors

public IntIterator successors(int x)

addNodes

public void addNodes(int numNewNodes)
Adds the given number of nodes, numbering them from numNodes() onwards. The new nodes have no successors.

Parameters:
numNewNodes - the number of new nodes.

removeNode

public void removeNode(int x)
Removes the given node. All arcs incident on the node are removed, too.

Parameters:
x - the node to be removed.

addArc

public void addArc(int x,
                   int y)
Adds the given arc.

Parameters:
x - the start of the arc.
y - the end of the arc.

removeArc

public void removeArc(int x,
                      int y)
Removes the given arc.

Parameters:
x - the start of the arc.
y - the end of the arc.

equals

public boolean equals(Object o)
Compare this mutable graph to another object.

Overrides:
equals in class Object
Returns:
true iff the given object is a mutable graph the same size, and the successor list of every node of this graph is equal to the successor list of the corresponding node of o.

hashCode

public int hashCode()
Returns a hash code for this mutable graph.

Overrides:
hashCode in class Object
Returns:
a hash code for this mutable graph.

toString

public String toString()
Overrides:
toString in class Object