Package it.unimi.dsi.webgraph

Class ArrayListMutableGraph

java.lang.Object
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 Details

    • 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 Details

    • 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 Details

    • 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