Package it.unimi.dsi.webgraph

Class IncrementalImmutableSequentialGraph

java.lang.Object
it.unimi.dsi.webgraph.ImmutableGraph
it.unimi.dsi.webgraph.ImmutableSequentialGraph
it.unimi.dsi.webgraph.IncrementalImmutableSequentialGraph
All Implemented Interfaces:
FlyweightPrototype<ImmutableGraph>
public class IncrementalImmutableSequentialGraph
extends ImmutableSequentialGraph
An adapter exposing an ImmutableGraph that can be filled incrementally using a family of addition methods that make it possible to specify the list of successors of each node in increasing order. At the end of the process, the user must add the special marker list END_OF_GRAPH.

The class provides a single call to nodeIterator(): once the returned NodeIterator has been exhausted, numNodes() will return the number of nodes, which will be equal to the number of calls to addition methods.

The class works using a producer/consumer patten: in a typical usage, the thread invoking the addition method will be different from the thread performing the traversal, as in 

        final IncrementalImmutableSequentialGraph g = new IncrementalImmutableSequentialGraph();
        ExecutorService executor = Executors.newSingleThreadExecutor();
        final Future<Void> future = executor.submit(new Callable<Void>() {
                public Void call() throws IOException {
                        BVGraph.store(g, basename);
                        return null;
                }
        });

        // Do one add() for each node, to specify the successors

        g.add(IncrementalImmutableSequentialGraph.END_OF_GRAPH);
        future.get();
        executor.shutdown();

  • Field Details

    • END_OF_GRAPH

      public static int[] END_OF_GRAPH
      A marker for the end of the graph.

  • Constructor Details

    • IncrementalImmutableSequentialGraph

      public IncrementalImmutableSequentialGraph()

  • Method Details

    • numNodes

      public int numNodes()
      Description copied from class: ImmutableGraph
      Returns the number of nodes of this graph.

      Albeit this method is not optional, it is allowed that this method throws an UnsupportedOperationException if this graph has never been entirely traversed using a node iterator. This apparently bizarre behaviour is necessary to support implementations as ArcListASCIIGraph, which do not know the actual number of nodes until a traversal has been completed.

      Specified by:
      numNodes in class ImmutableGraph
      Returns:
      the number of nodes.

    • nodeIterator

      public NodeIterator nodeIterator()
      Description copied from class: ImmutableGraph
      Returns a node iterator for scanning the graph sequentially, starting from the first node.
      Overrides:
      nodeIterator in class ImmutableGraph
      Returns:
      a NodeIterator for accessing nodes and successors sequentially.

    • add

      public void add​(int[] successor, int offset, int length) throws InterruptedException
      Adds a new node having as successors contained in the specified array fragment.

      The array must be sorted in increasing order.

      Parameters:
      successor - an array.
      offset - the first valid entry in successor.
      length - the number of valid entries.
      Throws:
      InterruptedException

    • add

      public void add​(int[] successor) throws InterruptedException
      Adds a new node having as successors contained in the specified array.

      The array must be sorted in increasing order.

      Parameters:
      successor - an array.
      Throws:
      InterruptedException