Class IncrementalImmutableSequentialGraph

  • All Implemented Interfaces:
    it.unimi.dsi.lang.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 Detail

      • END_OF_GRAPH

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

      • IncrementalImmutableSequentialGraph

        public IncrementalImmutableSequentialGraph()
    • Method Detail

      • 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.
      • add

        public void add​(int[] successor,
                        int offset,
                        int length)
                 throws java.lang.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:
        java.lang.InterruptedException
      • add

        public void add​(int[] successor)
                 throws java.lang.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:
        java.lang.InterruptedException