Package com.jgalgo.graph

Interface GraphBuilder<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Known Subinterfaces:
IndexGraphBuilder, IntGraphBuilder
public interface GraphBuilder<V,E>
A builder for graphs.

The builder is used to construct non-empty graphs. Differing from GraphFactory 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 gain 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 GraphFactory and use GraphFactory.newBuilder(), or use GraphFactory.newBuilderCopyOf(Graph) to create a builder initialized with an existing graph vertices and edges.

Author:
Barak Ugav
See Also:

  • Method Summary

    Modifier and Type
    Method
    Description
    default E
    addEdge(V source, V target)
    Add a new edge to the built graph, using the edge builder.
    void
    addEdge(V source, V target, E edge)
    Add a new edge to the built graph.
    void
    addEdges(EdgeSet<? extends V,? extends E> edges)
    Add multiple edges to the built graph.
    default <T, WeightsT extends Weights<E, T>>
    WeightsT
    addEdgesWeights(String key, Class<? super T> type)
    Add a new weights container associated with the edges of the built graph.
    <T, WeightsT extends Weights<E, T>>
    WeightsT
    addEdgesWeights(String key, Class<? super T> type, T defVal)
    Add a new weights container associated with the edges of the built graph with default value.
    default V
    addVertex()
    Add a new vertex to the built graph, using the vertex builder.
    void
    addVertex(V vertex)
    Add a new vertex to the built graph.
    void
    addVertices(Collection<? extends V> vertices)
    Add multiple vertices to the built graph.
    default <T, WeightsT extends Weights<V, T>>
    WeightsT
    addVerticesWeights(String key, Class<? super T> type)
    Add a new weights container associated with the vertices of the built graph.
    <T, WeightsT extends Weights<V, T>>
    WeightsT
    addVerticesWeights(String key, Class<? super T> type, T defVal)
    Add a new weights container associated with the vertices of built graph with default value.
    Graph<V,E>
    build()
    Build a new immutable graph with the builder vertices and edges.
    Graph<V,E>
    buildMutable()
    Build a new mutable graph with the builder vertices and edges.
    void
    clear()
    Clear the builder by removing all vertices and edges added to it.
    static <V, E> GraphBuilder<V,E>
    directed()
    Create a new builder that builds directed graphs.
    IdBuilder<E>
    edgeBuilder()
    Get the edge builder of this builder.
    Set<E>
    edges()
    Get the set of edges that were added to the graph.
    <T, WeightsT extends Weights<E, T>>
    WeightsT
    edgesWeights(String key)
    Get the edges weights of some key.
    Set<String>
    edgesWeightsKeys()
    Get the keys of all the associated edges weights.
    void
    ensureEdgeCapacity(int edgeCapacity)
    Hint the implementation to allocate space for at least edgeCapacity edges.
    void
    ensureVertexCapacity(int vertexCapacity)
    Hint the implementation to allocate space for at least vertexCapacity vertices.
    boolean
    isDirected()
    Check if the graph built by this builder is directed or undirected.
    static <V, E> GraphBuilder<V,E>
    newCopyOf(Graph<V,E> g)
    Create a new builder initialized with an existing graph vertices and edges, without copying the weights.
    static <V, E> GraphBuilder<V,E>
    newCopyOf(Graph<V,E> g, boolean copyVerticesWeights, boolean copyEdgesWeights)
    Create a new builder initialized with an existing graph vertices and edges, with/without copying the weights.
    static <V, E> GraphBuilder<V,E>
    newInstance(boolean directed)
    Create a new builder that builds un/directed graphs.
    static <V, E> GraphBuilder<V,E>
    undirected()
    Create a new builder that builds undirected graphs.
    IdBuilder<V>
    vertexBuilder()
    Get the vertex builder of this builder.
    Set<V>
    vertices()
    Get the set of vertices that were added to the graph.
    <T, WeightsT extends Weights<V, T>>
    WeightsT
    verticesWeights(String key)
    Get the vertices weights of some key.
    Set<String>
    verticesWeightsKeys()
    Get the keys of all the associated vertices weights.

  • Method Details

    • vertices

      Set<V> vertices()
      Get the set of vertices that were added to the graph.
      Returns:
      the graph vertices

    • edges

      Set<E> edges()
      Get the set of edges that were added to the graph.
      Returns:
      the graph edges

    • addVertex

      void addVertex(V vertex)
      Add a new vertex 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.

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

      Parameters:
      vertex - new vertex
      Throws:
      IllegalArgumentException - if vertex is already in the built graph
      NullPointerException - if vertex is null

    • addVertex

      default V addVertex()
      Add a new vertex to the built graph, using the vertex builder.

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

      This method is equivalent to: 

       
 V vertex = vertexBuilder().build(vertices());
 addVertex(vertex);
 return vertex;
      Returns:
      the new vertex
      Throws:
      UnsupportedOperationException - if the builder does not have a vertex builder, namely if vertexBuilder() returns null

    • addVertices

      void addVertices(Collection<? extends V> 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.

      Parameters:
      vertices - new vertices
      Throws:
      IllegalArgumentException - if vertices contains duplications or if any of the vertices is already in the built graph
      NullPointerException - if vertices is null or if any of the vertices is null

    • addEdge

      void addEdge(V source, V target, E edge)
      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.

      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.

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

      Parameters:
      source - a source vertex
      target - a target vertex
      edge - a new edge identifier
      Throws:
      IllegalArgumentException - if edge is already in the built graph
      NullPointerException - if edge is null, as null identifiers are not allowed
      NoSuchVertexException - if source or target are not vertices in the graph

    • addEdge

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

      Unlike addEdge(Object, Object, Object) in which the edge (identifier) is provided by the user, this method uses the edge builder obtained by edgeBuilder() to create the new edge object and adds it to the 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.

      This method is equivalent to: 

       
 E edge = edgeBuilder().build(edges());
 addEdge(source, target, edge);
 return edge;
      Parameters:
      source - a source vertex
      target - a target vertex
      Returns:
      the new edge
      Throws:
      UnsupportedOperationException - if the builder does not have an edge builder, namely if edgeBuilder() returns null
      NoSuchVertexException - if source or target are not valid vertices identifiers

    • addEdges

      void addEdges(EdgeSet<? extends V,? extends E> 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()
      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()).
      Throws:
      IllegalArgumentException - if edges contains duplications, or if any of the edges is already in the graph
      NullPointerException - if edges is null or if any of the edges is null
      NoSuchVertexException - if any of the edges endpoint is not a vertex in the graph

    • ensureVertexCapacity

      void ensureVertexCapacity(int vertexCapacity)
      Hint the implementation to allocate space for at least vertexCapacity vertices.

      The implementation may ignore any calls to this function.

      Parameters:
      vertexCapacity - the minimum number of vertices to allocate space for

    • ensureEdgeCapacity

      void ensureEdgeCapacity(int edgeCapacity)
      Hint the implementation to allocate space for at least edgeCapacity edges.

      The implementation may ignore any calls to this function.

      Parameters:
      edgeCapacity - the minimum number of edges to allocate space for

    • verticesWeights

      <T, WeightsT extends Weights<V, T>> WeightsT verticesWeights(String key)
      Get the vertices weights of some key.

      See Weights for a complete documentation of the weights containers.

      Type Parameters:
      T - The weight data type
      WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
      Parameters:
      key - key of the weights
      Returns:
      vertices weights of the key, or null if no container found with the specified key

    • addVerticesWeights

      default <T, WeightsT extends Weights<V, T>> WeightsT addVerticesWeights(String key, Class<? super T> type)
      Add a new weights container associated with the vertices of the built graph.

      See Weights for a complete documentation of the weights containers.

      Type Parameters:
      T - The weight data type
      WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
      Parameters:
      key - key of the weights, null is not allowed
      type - the type of the weights, used for primitive types weights
      Returns:
      a new weights container
      Throws:
      NullPointerException - if key is null
      IllegalArgumentException - if a vertices weights container with the same key already exists in the graph

    • addVerticesWeights

      <T, WeightsT extends Weights<V, T>> WeightsT addVerticesWeights(String key, Class<? super T> type, T defVal)
      Add a new weights container associated with the vertices of built graph with default value.

      See Weights for a complete documentation of the weights containers.

      Type Parameters:
      T - The weight data type
      WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
      Parameters:
      key - key of the weights, null is not allowed
      type - the type of the weights, used for primitive types weights
      defVal - default value use for the weights container
      Returns:
      a new weights container
      Throws:
      NullPointerException - if key is null
      IllegalArgumentException - if a vertices weights container with the same key already exists in the graph

    • verticesWeightsKeys

      Set<String> verticesWeightsKeys()
      Get the keys of all the associated vertices weights.

      See IWeights for a complete documentation of the weights containers.

      Returns:
      the keys of all the associated vertices weights

    • edgesWeights

      <T, WeightsT extends Weights<E, T>> WeightsT edgesWeights(String key)
      Get the edges weights of some key.

      See Weights for a complete documentation of the weights containers.

      Type Parameters:
      T - The weight data type
      WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
      Parameters:
      key - key of the weights
      Returns:
      edges weights of the key, or null if no container found with the specified key

    • addEdgesWeights

      default <T, WeightsT extends Weights<E, T>> WeightsT addEdgesWeights(String key, Class<? super T> type)
      Add a new weights container associated with the edges of the built graph.

      See Weights for a complete documentation of the weights containers.

      Type Parameters:
      T - The weight data type
      WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
      Parameters:
      key - key of the weights, null is not allowed
      type - the type of the weights, used for primitive types weights
      Returns:
      a new weights container
      Throws:
      NullPointerException - if key is null
      IllegalArgumentException - if a edges weights container with the same key already exists in the graph

    • addEdgesWeights

      <T, WeightsT extends Weights<E, T>> WeightsT addEdgesWeights(String key, Class<? super T> type, T defVal)
      Add a new weights container associated with the edges of the built graph with default value.

      See Weights for a complete documentation of the weights containers.

      Type Parameters:
      T - The weight data type
      WeightsT - the weights container, used to avoid casts of containers of primitive types such as WeightsInt, WeightsDouble ect.
      Parameters:
      key - key of the weights, null is not allowed
      type - the type of the weights, used for primitive types weights
      defVal - default value use for the weights container
      Returns:
      a new weights container
      Throws:
      NullPointerException - if key is null
      IllegalArgumentException - if a edges weights container with the same key already exists in the graph

    • edgesWeightsKeys

      Set<String> edgesWeightsKeys()
      Get the keys of all the associated edges weights.

      See IWeights for a complete documentation of the weights containers.

      Returns:
      the keys of all the associated edges weights

    • clear

      void clear()
      Clear the builder by removing all vertices and edges added to it.

    • vertexBuilder

      IdBuilder<V> vertexBuilder()
      Get the vertex builder of this builder.

      The vertex builder is used to create new vertices during the execution of 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, addVertex() cannot be used, only addVertex(Object).

      Returns:
      the vertex builder, or null if the there is no vertex builder

    • edgeBuilder

      IdBuilder<E> edgeBuilder()
      Get the edge builder of this builder.

      The edge builder is used to create new edges during the execution of 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, addEdge(Object, Object) cannot be used, only addEdge(Object, Object, Object).

      Returns:
      the edge builder, or null if the there is no edge builder

    • isDirected

      boolean isDirected()
      Check if the graph built by this builder is directed or undirected.
      Returns:
      true if the graph built by this builder is directed, false if it is undirected

    • build

      Graph<V,E> build()
      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.

      Returns:
      a new immutable graph with the vertices and edges that were added to the builder.
      Throws:
      IllegalArgumentException - if the built graph does not support self or parallel edges and such edges were added to the builder

    • buildMutable

      Graph<V,E> buildMutable()
      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.

      Returns:
      a new mutable graph with the vertices and edges that were added to the builder.
      Throws:
      IllegalArgumentException - if the built graph does not support self or parallel edges and such edges were added to the builder

    • undirected

      static <V, E> GraphBuilder<V,E> undirected()
      Create a new builder that builds undirected graphs.

      The graphs built by this builder will have the same default capabilities as GraphFactory, 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 GraphFactory and use one of its newBuilder methods.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Returns:
      a new empty builder for undirected graphs

    • directed

      static <V, E> GraphBuilder<V,E> directed()
      Create a new builder that builds directed graphs.

      The graphs built by this builder will have the same default capabilities as GraphFactory, 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 GraphFactory and use one of its newBuilder methods.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Returns:
      a new empty builder for directed graphs

    • newInstance

      static <V, E> GraphBuilder<V,E> 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 GraphFactory, 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 GraphFactory and use one of its newBuilder methods.

      Type Parameters:
      V - the vertices type
      E - the edges type
      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 <V, E> GraphBuilder<V,E> newCopyOf(Graph<V,E> 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 GraphFactory and use one of its newBuilder methods.

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

    • newCopyOf

      static <V, E> GraphBuilder<V,E> newCopyOf(Graph<V,E> 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 GraphFactory and use one of its newBuilder methods.

      Type Parameters:
      V - the vertices type
      E - the edges type
      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.