Package com.jgalgo.graph

Interface IndexGraphBuilder

All Superinterfaces:
GraphBuilder<Integer,Integer>, IntGraphBuilder
public interface IndexGraphBuilder extends IntGraphBuilder
A builder for Index graphs.

The builder is used to construct non-empty index graphs. Differing from IndexGraphFactory which create new empty graphs, the builder is used to add vertices and edges before actually creating the graph. This capability is required to create immutable graphs, but can also be used to build mutable graph and may give a performance boost compared to creating an empty graph and adding the same vertices and edges.

To create a new builder, use one of the static methods undirected(), directed() or newInstance(boolean). For more options, create a new IndexGraphFactory and use IndexGraphFactory.newBuilder(), or use IndexGraphFactory.newBuilderCopyOf(Graph) to create a builder initialized with an existing graph vertices and edges.

This interface is a specification of IntGraphBuilder for IndexGraph.

Author:
Barak Ugav
See Also:

  • Method Details

    • addVertexInt

      int addVertexInt()
      Add a new vertex to the built graph, using the vertex builder.

      Unlike IntGraphBuilder.addVertex(int) in which the vertex is provided by the user, this method uses the vertex builder obtained by IntGraphBuilder.vertexBuilder() to create the new vertex and adds it to the graph.

      This method is equivalent to: 

       
 int vertex = vertexBuilder().build(vertices());
 addVertex(vertex);
 return vertex;

      The vertex created by this method will be assigned the next available index, verticesNum. For example, if the graph currently contains the vertices 0,1,2, the next vertex added will be 3.

      Specified by:
      addVertexInt in interface IntGraphBuilder
      Returns:
      the new vertex

    • addVertex

      @Deprecated default void addVertex(int vertex)
      Deprecated.
      use addVertexInt() instead
      Add a new vertex to the built graph.

      Vertices must be non negative integers.

      If there is a vertex builder, namely if IntGraphBuilder.vertexBuilder() does not return null, the method IntGraphBuilder.addVertexInt() can be used, which uses the vertex builder to create the new vertex object instead of requiring the user to provide it.

      Index graphs vertices IDs are always (0,1,2, ...,verticesNum-1) therefore the only vertex ID that can be added is verticesNum. For any other vertex passed to this method, an exception will be thrown. If verticesNum is passed, this method is equivalent to addVertexInt().

      Specified by:
      addVertex in interface IntGraphBuilder
      Parameters:
      vertex - new vertex
      Throws:
      IllegalArgumentException - if vertex is not verticesNum

    • addVertices

      void addVertices(Collection<? extends Integer> vertices)
      Add multiple vertices to the built graph.

      A vertex can be any non null hashable object, namely it must implement the Object.hashCode() and Object.equals(Object) methods. Duplicate vertices are not allowed.

      Prefer to pass IntCollection instead of Collection<Integer> as collection of vertices.

      Index graphs vertices IDs are always (0,1,2, ...,verticesNum-1) therefore the only vertices that can be added are (verticesNum,verticesNum+1,verticesNum+2, ...). For any other vertices passed to this method, an exception will be thrown.

      Specified by:
      addVertices in interface GraphBuilder<Integer,Integer>
      Specified by:
      addVertices in interface IntGraphBuilder
      Parameters:
      vertices - new vertices

    • addEdge

      int addEdge(int source, int target)
      Add a new edge to the built graph, using the edge builder.

      Unlike IntGraphBuilder.addEdge(int, int, int) in which the edge (identifier) is provided by the user, this method uses the edge builder obtained by IntGraphBuilder.edgeBuilder() to create the new edge object and adds it to the graph.

      If the graph does not support self or parallel edges and the added edge is such edge, an exception will not be thrown. The edges are validated only when the graph is built, and an exception will be thrown only then.

      This method is equivalent to: 

       
 int edge = edgeBuilder().build(edges());
 addEdge(source, target, edge);
 return edge;

      The edge created by this method will be assigned the next available index, edgesNum. For example, if the graph currently contains the edges 0,1,2, the next edge added will be 3.

      Specified by:
      addEdge in interface IntGraphBuilder
      Parameters:
      source - a source vertex
      target - a target vertex
      Returns:
      the new edge

    • addEdge

      @Deprecated default void addEdge(int source, int target, int edge)
      Deprecated.
      use addEdge(int, int) instead
      Add a new edge to the built graph.

      If the built graph does not support self or parallel edges and the added edge is such edge, an exception will not be thrown. The edges are validated only when the graph is built, and an exception will be thrown only then.

      Edges must be non negative integers.

      If there is an edge builder, namely if IntGraphBuilder.edgeBuilder() does not return null, the method IntGraphBuilder.addEdge(int, int) can be used, which uses the edge builder to create the new edge object instead of requiring the user to provide it.

      Index graphs edges IDs are always (0,1,2, ...,edgesNum-1) therefore the only edge ID that can be added is edgesNum. For any other edge passed to this method, an exception will be thrown. If edgesNum is passed, this method is equivalent to addEdge(int, int).

      Specified by:
      addEdge in interface IntGraphBuilder
      Parameters:
      source - a source vertex
      target - a target vertex
      edge - a new edge identifier
      Throws:
      IllegalArgumentException - if edge is not edgesNum

    • addEdges

      void addEdges(EdgeSet<? extends Integer,? extends Integer> edges)
      Add multiple edges to the built graph.

      The EdgeSet passed to this method contains both the edges themselves (the identifiers) and their endpoints (sources and targets), see EdgeSet.iterator(), EdgeIter.source(), EdgeIter.target(). An EdgeSet can be obtained from one of the methods of a Graph, or using EdgeSet.of(Set, Graph).

      An edge can be any non null hashable object, namely it must implement the Object.hashCode() and Object.equals(Object) methods. Duplicate edges are not allowed.

      In the following snippet, a maximum cardinality matching is computed on a graph, and a new graph containing only the matching edges is created: 

       
 Graph<V, E> g = ...;
 Set<E> matching = MatchingAlgo.newInstance().computeMaximumMatching(g, null).edges();

 GraphBuilder<V,E> matchingGraphBuilder = GraphBuilder.undirected();
 matchingGraphBuilder.addVertices(g.vertices());
 matchingGraphBuilder.addEdges(EdgeSet.of(matching, g));
 Graph<V,E> matchingGraph = matchingGraphBuilder.build()

      Prefer to pass IEdgeSet instead of EdgeSet<Integer, Integer> as set of edges. See IEdgeSet.of(IntSet, IntGraph).

      Index graphs edges IDs are always (0,1,2, ...,edgesNum-1) therefore the only edges that can be added are (edgesNum,edgesNum+1,edgesNum+2, ...). For any other edges passed to this method, an exception will be thrown. If there is no need to keep the identifiers of the edges, consider using addEdgesReassignIds(IEdgeSet).

      Specified by:
      addEdges in interface GraphBuilder<Integer,Integer>
      Specified by:
      addEdges in interface IntGraphBuilder
      Parameters:
      edges - the set of new edges, from which the edges identifiers as well as the endpoints (source and target) of each edge are accessible (see EdgeSet.iterator(), EdgeIter.source(), EdgeIter.target()).

    • addEdgesReassignIds

      IntSet addEdgesReassignIds(IEdgeSet edges)
      Add multiple edges to the built graph and re-assign ids for them.

      The IEdgeSet passed to this method contains the endpoints (sources and targets) of the edges, see EdgeSet.iterator(), EdgeIter.source(), EdgeIter.target(). The identifiers of the edges, which are also accessible via IEdgeSet are ignored, and new identifiers (indices) are assigned to the added edges. An IEdgeSet can be obtained from one of the methods of an IntGraph, or using IEdgeSet.of(IntSet, IntGraph).

      The identifiers assigned to the newly added edges are (edgesNum,edgesNum+1,edgesNum+2, ...) matching the iteration order of the provided set. This method different than addEdges(EdgeSet) in a similar way that addEdge(int, int) is different than addEdge(int, int, int).

      In the following snippet, a maximum cardinality matching is computed on a graph, and a new graph containing only the matching edges is created. It would be wrong to use addEdges(EdgeSet) in this example, as there is no guarantee that the added edges ids are (0, 1, 2, ...), which is a requirement to build an IndexGraph. 

       
 IndexGraph g = ...;
 IntSet matching = (IntSet) MatchingAlgo.newInstance().computeMaximumMatching(g, null).edges();

 IndexGraphBuilder matchingGraphBuilder = IndexGraphBuilder.undirected();
 matchingGraphBuilder.addVertices(g.vertices());
 matchingGraphBuilder.addEdgesReassignIds(IEdgeSet.of(matching, g));
 IndexGraph matchingGraph = matchingGraphBuilder.build();
      Parameters:
      edges - the set of edges to add. Only the endpoints of the edges is considered, while the edges identifiers are ignored.
      Returns:
      the set of newly edge identifiers added to the graph, (edgesNum,edgesNum+1,edgesNum+2, ...). The edges are assigned the indices in the order they are iterated in the given set

    • vertexBuilder

      default IdBuilderInt vertexBuilder()
      Get the vertex builder of this builder.

      The vertex builder is used to create new vertices during the execution of GraphBuilder.addVertex(), in which the vertex identifier is not provided by the user. No vertex builder necessarily exists, and this method may return a null value. In that case, GraphBuilder.addVertex() cannot be used, only GraphBuilder.addVertex(Object).

      The vertex builder returned by this method always assign the next available index, verticesNum, given the current set of vertices (0,1,2, ...,verticesNum-1). For example, if the graph currently contains the vertices 0,1,2, the next vertex added will be 3. The builder simply returns the current vertices set size, without validating that the set is actually (0,1,2, ...,verticesNum-1).

      Specified by:
      vertexBuilder in interface GraphBuilder<Integer,Integer>
      Specified by:
      vertexBuilder in interface IntGraphBuilder
      Returns:
      the vertex builder, or null if the there is no vertex builder

    • edgeBuilder

      default IdBuilderInt edgeBuilder()
      Get the edge builder of this builder.

      The edge builder is used to create new edges during the execution of GraphBuilder.addEdge(Object, Object), in which the edge identifier is not provided by the user. No edge builder necessarily exists, and this method may return a null value. In that case, GraphBuilder.addEdge(Object, Object) cannot be used, only GraphBuilder.addEdge(Object, Object, Object).

      The edge builder returned by this method always assign the next available index, edgesNum, given the current set of edges (0,1,2, ...,edgesNum-1). For example, if the graph currently contains the edges 0,1,2, the next edge added will be 3. The builder simply returns the current edges set size, without validating that the set is actually (0,1,2, ...,edgesNum-1).

      Specified by:
      edgeBuilder in interface GraphBuilder<Integer,Integer>
      Specified by:
      edgeBuilder in interface IntGraphBuilder
      Returns:
      the edge builder, or null if the there is no edge builder

    • build

      IndexGraph build()
      Description copied from interface: GraphBuilder
      Build a new immutable graph with the builder vertices and edges.

      Before the graph is built, the edges are validated. If the graph does not support self or parallel edges and such edges were added to the builder, an exception will be thrown.

      Specified by:
      build in interface GraphBuilder<Integer,Integer>
      Specified by:
      build in interface IntGraphBuilder
      Returns:
      a new immutable graph with the vertices and edges that were added to the builder.

    • buildMutable

      IndexGraph buildMutable()
      Description copied from interface: GraphBuilder
      Build a new mutable graph with the builder vertices and edges.

      Before the graph is built, the edges are validated. If the graph does not support self or parallel edges and such edges were added to the builder, an exception will be thrown.

      Specified by:
      buildMutable in interface GraphBuilder<Integer,Integer>
      Specified by:
      buildMutable in interface IntGraphBuilder
      Returns:
      a new mutable graph with the vertices and edges that were added to the builder.

    • reIndexAndBuild

      IndexGraphBuilder.ReIndexedGraph reIndexAndBuild(boolean reIndexVertices, boolean reIndexEdges)
      Re-Index the vertices/edges and build a new immutable graph with the new indexing.

      Re-indexing is the operation of assigning new indices to the vertices/edges. By re-indexing the vertices/edges, the performance of accessing/iterating over the graph vertices/edges may increase, for example if a more cache friendly indexing exists.

      Note that this method is not required to re-index the vertices (edges) if reIndexVertices (reIndexEdges) is true, it is simply allowed to. Whether or not a re-indexing was performed can be checked via the IndexGraphBuilder.ReIndexedGraph return value.

      Before the graph is built, the edges are validated. If the graph does not support self or parallel edges and such edges were added to the builder, an exception will be thrown.

      Parameters:
      reIndexVertices - if true, the implementation is allowed (but not required) to re-index the vertices of the graph. If false, the original vertices identifiers are used. Whether or not re-indexing was performed can be checked via IndexGraphBuilder.ReIndexedGraph.verticesReIndexing.
      reIndexEdges - if true, the implementation is allowed (but not required) to re-index the edges of the graph. If false, the original edges identifiers are used. Whether or not re-indexing was performed can be checked via IndexGraphBuilder.ReIndexedGraph.edgesReIndexing.
      Returns:
      the re-indexed immutable graph, along with the re-indexing mapping to the original indices

    • reIndexAndBuildMutable

      IndexGraphBuilder.ReIndexedGraph reIndexAndBuildMutable(boolean reIndexVertices, boolean reIndexEdges)
      Re-Index the vertices/edges and build a new mutable graph with the new indexing.

      Re-indexing is the operation of assigning new indices to the vertices/edges. By re-indexing the vertices/edges, the performance of accessing/iterating over the graph vertices/edges may increase, for example if a more cache friendly indexing exists.

      Note that this method is not required to re-index the vertices (edges) if reIndexVertices (reIndexEdges) is true, it is simply allowed to. Whether or not a re-indexing was performed can be checked via the IndexGraphBuilder.ReIndexedGraph return value.

      Before the graph is built, the edges are validated. If the graph does not support self or parallel edges and such edges were added to the builder, an exception will be thrown.

      Parameters:
      reIndexVertices - if true, the implementation is allowed (but not required) to re-index the vertices of the graph. If false, the original vertices identifiers are used. Whether or not re-indexing was performed can be checked via IndexGraphBuilder.ReIndexedGraph.verticesReIndexing.
      reIndexEdges - if true, the implementation is allowed (but not required) to re-index the edges of the graph. If false, the original edges identifiers are used. Whether or not re-indexing was performed can be checked via IndexGraphBuilder.ReIndexedGraph.edgesReIndexing.
      Returns:
      the re-indexed mutable graph, along with the re-indexing mapping to the original indices

    • undirected

      static IndexGraphBuilder undirected()
      Create a new builder that builds undirected graphs.

      The graphs built by this builder will have the same default capabilities as IndexGraphFactory, namely they will not support self edges and will support parallel edges. See the factory documentation for more information.

      For more options to instantiate a builder, create a new IndexGraphFactory and use one of its newBuilder methods.

      Returns:
      a new empty builder for undirected graphs

    • directed

      static IndexGraphBuilder directed()
      Create a new builder that builds directed graphs.

      The graphs built by this builder will have the same default capabilities as IndexGraphFactory, namely they will not support self edges and will support parallel edges. See the factory documentation for more information.

      For more options to instantiate a builder, create a new IndexGraphFactory and use one of its newBuilder methods.

      Returns:
      a new empty builder for directed graphs

    • newInstance

      static IndexGraphBuilder newInstance(boolean directed)
      Create a new builder that builds un/directed graphs.

      The graphs built by this builder will have the same default capabilities as IndexGraphFactory, namely they will not support self edges and will support parallel edges. See the factory documentation for more information.

      For more options to instantiate a builder, create a new IndexGraphFactory and use one of its newBuilder methods.

      Parameters:
      directed - if true, the new builder will build directed graphs, otherwise it will build undirected graphs
      Returns:
      a new empty builder for un/directed graphs

    • newCopyOf

      static IndexGraphBuilder newCopyOf(IndexGraph g)
      Create a new builder initialized with an existing graph vertices and edges, without copying the weights.

      If the given graph is directed, the new builder will build directed graphs, and similarly for undirected graphs.

      For more options to instantiate a builder, create a new IndexGraphFactory and use one of its newBuilder methods.

      Parameters:
      g - a graph
      Returns:
      a builder initialized with the given graph vertices and edges, without the original graph vertices/edges weights.

    • newCopyOf

      static IndexGraphBuilder newCopyOf(IndexGraph g, boolean copyVerticesWeights, boolean copyEdgesWeights)
      Create a new builder initialized with an existing graph vertices and edges, with/without copying the weights.

      If the given graph is directed, the new builder will build directed graphs, and similarly for undirected graphs.

      For more options to instantiate a builder, create a new IndexGraphFactory and use one of its newBuilder methods.

      Parameters:
      g - a graph
      copyVerticesWeights - if true, the weights of the vertices will be copied from the graph to the builder
      copyEdgesWeights - if true, the weights of the edges will be copied from the graph to the builder
      Returns:
      a builder initialized with the given graph vertices and edges, with/without the original graph vertices/edges weights.