Package it.unimi.dsi.webgraph

Class ArrayListMutableGraph

  • public class ArrayListMutableGraph
extends java.lang.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 Detail

      • n

        protected int n
        Current number of nodes.

      • m

        protected long m
        Current number of arcs.

      • successors

        protected it.unimi.dsi.fastutil.ints.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 it.unimi.dsi.fastutil.ints.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​(java.lang.Object o)
        Compare this mutable graph to another object.
        Overrides:
        equals in class java.lang.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 java.lang.Object
        Returns:
        a hash code for this mutable graph.

      • toString

        public java.lang.String toString()
        Overrides:
        toString in class java.lang.Object