Package com.jgalgo.graph

Interface Graph<V,E>

Type Parameters:
V - the vertices type
E - the edges type
All Known Subinterfaces:
IndexGraph, IntGraph
All Known Implementing Classes:
AbstractGraph, GuavaNetworkWrapper, JGraphTWrapper
public interface Graph<V,E>
A discrete graph with vertices and edges.

A graph consist of a finite set of vertices \(V\) and edges \(E\). Vertices are some abstract entities, and edges are connections between the vertices, for example vertices can be cities and edges could be the roads between them, or vertices can be people the edges are the relation of "friends". Edges could be directed or undirected. Weights may be assigned to vertices or edges, for example the length of a road might be a weight of an edge. Than, questions such as "what is the shortest path between two cities?" might be answered using graph algorithms.

Each edge \(e=(u, v)\) in the graph has a source vertex, \(u\), and a target vertex, \(v\). In undirected graphs the 'source' and 'target' can be switched, as the edge is not directed, and we treat the source and target as interchangeable end points. If an edge \((u,v)\) exist in the graph, we say the vertices \(u\) and \(v\) and neighbors, or adjacent. The edges are usually stored in some list for each vertex, allowing efficient iteration of its edges. The degree of a vertex is the number of its edges. In directed graph, we have both in-degree and out-degree, which are the number of edges going in and out the vertex, respectively.

Vertices can be added or removed. When a vertex \(v\) is removed, all the edges with \(v\) as one of their end points are removed as well. Edges can be added as connection to existing vertices, or removed.

A directed graph and an undirected graph are both implemented by this interface. In a directed graph, the edges are directed, namely an edge \(e=(u, v)\) will be contained in outEdges(u) and in inEdges(v) and will not be contained in outEdges(v) and inEdges(u). In an undirected graph, the edges are undirected, namely an edge \(e=\{u, v\}\) will be contained in outEdges(u), inEdges(v), outEdges(v) and in inEdges(u). Also removeEdgesOf(Object), removeInEdgesOf(Object) and removeOutEdgesOf(Object) are equivalent for the same vertex in an undirected graph. To check if a graph is directed or not, use the isDirected() method.

Each vertex and edge in the graph is identified by a unique non null hashable object. The existing vertices and edges of the graph can be retrieved using vertices() and edges(). Vertices and edges may be added by addVertex(Object) and addEdge(Object, Object, Object).

Weights may be assigned to the graph vertices and/or edges. A weight is some value such as any primitive (for example double, int or boolean flag) or an Object. Multiple different weights can be added to the vertices and/or edges, each is identified by some string key. When a new weights type is added to a graph, it is added to all the vertices/edges, with either user provided default weight value, or null (0 in case the weight type is primitive). The weights are accessed via the Weights container, which can be used to get or set a vertex/edge weight, and can be passed to algorithms as a WeightFunction for example. See addVerticesWeights(String, Class) and addEdgesWeights(String, Class), or Weights for the full weights documentation.

Each graph expose an Index view on itself via the indexGraph() method. The returned IndexGraph is a graph in which the identifiers of the vertices are always (0,1,2, ...,verticesNum-1), and the identifiers of the edges are always (0,1,2, ...,edgesNum-1). To maintain this, the index graph implementation may rename existing vertices or edges along the graph lifetime. This rename behavior is less user friendly, but allow for high performance boost as no hash tables are needed, a simple array or bitmap can be used to map each vertex/edge to a value/weight/flag. The index graph returned by indexGraph() should not be modified directly by adding/removing vertices/edges/weights, use the enclosing graph instead. See IndexGraph for more information. The IndexGraph should not be used in scenarios where performance does not matter.

The number of vertices and edges can be read via g.vertices().size() and g.edges().size(). The out or in degree of a vertex is exposed by g.outEdges(vertex).size() and g.inEdges(vertex).size().

The number of vertices, \(|V|\), is usually denoted as \(n\) in algorithms time and space complexities, and similarly, the number of edges, \(|E|\), is usually denoted as \(m\).

To create a new empty graph, use newUndirected() or newDirected(). The returned graph will use the default implementation. For more control over the graph details, see GraphFactory. To construct an immutable graph, use GraphBuilder. 

 
 // Create an undirected graph with three vertices and edges between them
 Graph<String, Integer> g = Graph.newUndirected();
 g.addVertex("Berlin");
 g.addVertex("Leipzig");
 g.addVertex("Dresden");
 g.addEdge("Berlin", "Leipzig", 9);
 g.addEdge("Berlin", "Dresden", 13);
 g.addEdge("Dresden", "Leipzig", 14);

 // Assign some weights to the edges
 WeightsDouble<Integer> w = g.addEdgesWeights("distance-km", double.class);
 w.set(9, 191.1);
 w.set(13, 193.3);
 w.set(14, 121.3);

 // Calculate the shortest paths from Berlin to all other cities
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newInstance();
 ShortestPathSingleSource.Result<String, Integer> ssspRes = ssspAlgo.computeShortestPaths(g, w, "Berlin");

 // Print the shortest path from Berlin to Leipzig
 System.out.println("Distance from Berlin to Leipzig is: " + ssspRes.distance("Leipzig"));
 System.out.println("The shortest path from Berlin to Leipzig is:");
 for (Integer e : ssspRes.getPath("Leipzig").edges()) {
 	String u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
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 graph, using the edge builder.
    void
    addEdge(V source, V target, E edge)
    Add a new edge to the graph.
    void
    addEdges(EdgeSet<? extends V,? extends E> edges)
    Add multiple edges to the 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 this 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 this graph with default value.
    default V
    addVertex()
    Add a new vertex to the graph, using the vertex builder.
    void
    addVertex(V vertex)
    Add a new vertex to the graph.
    void
    addVertices(Collection<? extends V> vertices)
    Add multiple vertices to the 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 this 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 this graph with default value.
    void
    clear()
    Clear the graph completely by removing all vertices and edges.
    void
    clearEdges()
    Remove all the edges from the graph.
    default boolean
    containsEdge(V source, V target)
    Check whether the graph contains an edge with the given source and target.
    default Graph<V,E>
    copy()
    Create a copy of this graph, with the same vertices and edges, without copying weights.
    default Graph<V,E>
    copy(boolean copyVerticesWeights, boolean copyEdgesWeights)
    Create a copy of this graph, with the same vertices and edges, with/without copying weights.
    IdBuilder<E>
    edgeBuilder()
    Get the edge builder of this graph.
    V
    edgeEndpoint(E edge, V endpoint)
    Get the other end-point of an edge.
    Set<E>
    edges()
    Get the set of all edges of the graph.
    V
    edgeSource(E edge)
    Get the source vertex of an edge.
    <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.
    V
    edgeTarget(E edge)
    Get the target vertex of an edge.
    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.
    E
    getEdge(V source, V target)
    Get the edge whose source is source and target is target.
    EdgeSet<V,E>
    getEdges(V source, V target)
    Get the edges whose source is source and target is target.
    default Graph<V,E>
    immutableCopy()
    Create an immutable copy of this graph, with the same vertices and edges, without copying weights.
    default Graph<V,E>
    immutableCopy(boolean copyVerticesWeights, boolean copyEdgesWeights)
    Create an immutable copy of this graph, with the same vertices and edges, with/without copying weights.
    default Graph<V,E>
    immutableView()
    Get an immutable view of this graph.
    IndexGraph
    indexGraph()
    Get an Index graph view of this graph.
    IndexIdMap<E>
    indexGraphEdgesMap()
    Get the index-id edges mapping of this graph.
    IndexIdMap<V>
    indexGraphVerticesMap()
    Get the index-id vertices mapping of this graph.
    EdgeSet<V,E>
    inEdges(V target)
    Get the edges whose target is target.
    boolean
    isAllowParallelEdges()
    Checks whether parallel edges are supported.
    boolean
    isAllowSelfEdges()
    Checks whether self edges are supported.
    boolean
    isDirected()
    Checks whether the graph is directed.
    void
    moveEdge(E edge, V newSource, V newTarget)
    Move an existing edge to new source and target vertices.
    static <V, E> Graph<V,E>
    newDirected()
    Create a new directed empty graph.
    static <V, E> Graph<V,E>
    newUndirected()
    Create a new undirected empty graph.
    EdgeSet<V,E>
    outEdges(V source)
    Get the edges whose source is source.
    void
    removeEdge(E edge)
    Remove an edge from the graph.
    void
    removeEdges(Collection<? extends E> edges)
    Remove multiple edges from the graph.
    void
    removeEdgesOf(V vertex)
    Remove all the edges of a vertex.
    void
    removeEdgesWeights(String key)
    Remove a weight type associated with the edges of the graph.
    void
    removeInEdgesOf(V target)
    Remove all edges whose target is target.
    void
    removeOutEdgesOf(V source)
    Remove all edges whose source is source.
    void
    removeVertex(V vertex)
    Remove a vertex and all its edges from the graph.
    void
    removeVertices(Collection<? extends V> vertices)
    Remove multiple vertices and all their edges from the graph.
    void
    removeVerticesWeights(String key)
    Remove a weight type associated with the vertices of the graph.
    void
    renameEdge(E edge, E newId)
    Set a new identifier for an existing edge.
    void
    renameVertex(V vertex, V newId)
    Set a new identifier for an existing vertex.
    default void
    reverseEdge(E edge)
    Reverse an edge by switching its source and target.
    default Graph<V,E>
    reverseView()
    Get a reversed view of this graph.
    default Graph<V,E>
    subGraphCopy(Collection<V> vertices, Collection<E> edges)
    Create a new graph that is a subgraph of this graph.
    default Graph<V,E>
    undirectedView()
    Get an undirected view of this (directed) graph.
    IdBuilder<V>
    vertexBuilder()
    Get the vertex builder of this graph.
    Set<V>
    vertices()
    Get the set of all vertices of 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 all vertices of the graph.

      Each vertex in the graph is identified by a unique non null hashable object and the returned set is a set of all these identifiers.

      The Graph object does not expose an explicit method to get the number of vertices, but it can accessed using this method by g.vertices().size().

      Returns:
      a set containing all vertices of the graph

    • edges

      Set<E> edges()
      Get the set of all edges of the graph.

      Each edge in the graph is identified by a unique non null hashable object, and the returned set is a set of all these identifiers.

      The Graph object does not expose an explicit method to get the number of edges, but it can accessed using this method by g.edges().size().

      Returns:
      a set containing all edges of the graph

    • addVertex

      void addVertex(V vertex)
      Add a new vertex to the 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 the graph have 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 graph
      NullPointerException - if vertex is null

    • addVertex

      default V addVertex()
      Add a new vertex to the 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 graph does not have a vertex builder, namely if vertexBuilder() returns null

    • addVertices

      void addVertices(Collection<? extends V> vertices)
      Add multiple vertices to the 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 graph
      NullPointerException - if vertices is null or if any of the vertices is null

    • removeVertex

      void removeVertex(V vertex)
      Remove a vertex and all its edges from the graph.
      Parameters:
      vertex - the vertex identifier to remove
      Throws:
      NoSuchVertexException - if vertex is not a valid vertex identifier

    • removeVertices

      void removeVertices(Collection<? extends V> vertices)
      Remove multiple vertices and all their edges from the graph.
      Parameters:
      vertices - the vertices to remove
      Throws:
      NoSuchVertexException - if any of the vertices is not a valid vertex identifier
      NullPointerException - if vertices is null or if any of the vertices is null
      IllegalArgumentException - if vertices contains duplications

    • renameVertex

      void renameVertex(V vertex, V newId)
      Set a new identifier for an existing vertex.

      This method changes the identifier of an existing vertex, while keeping the edges connecting to it, along with the weights associated with it.

      Parameters:
      vertex - an existing vertex in the graph
      newId - the new vertex identifier
      Throws:
      NoSuchVertexException - if vertex is not a valid vertex identifier
      IllegalArgumentException - if newId is already in the graph
      NullPointerException - if newId is null

    • outEdges

      EdgeSet<V,E> outEdges(V source)
      Get the edges whose source is source.

      In case the graph is undirected, the set will contain all edges whose source is one of their end points.

      The graph object does not expose an explicit method to get the (out) degree of a vertex, but it can accessed using this method by g.outEdges(vertex).size().

      Parameters:
      source - a source vertex
      Returns:
      all the edges whose source is source
      Throws:
      NoSuchVertexException - if source is not a valid vertex identifier

    • inEdges

      EdgeSet<V,E> inEdges(V target)
      Get the edges whose target is target.

      In case the graph is undirected, the set will contain all edges whose target is one of their end points.

      The graph object does not expose an explicit method to get the (in) degree of a vertex, but it can accessed using this method by g.inEdges(vertex).size().

      Parameters:
      target - a target vertex
      Returns:
      all the edges whose target is target
      Throws:
      NoSuchVertexException - if target is not a valid vertex identifier

    • containsEdge

      default boolean containsEdge(V source, V target)
      Check whether the graph contains an edge with the given source and target.

      If the graph is undirected, the method will return true if there is an edge whose end-points are source and target, regardless of which is the source and which is the target.

      Parameters:
      source - the source vertex
      target - the target vertex
      Returns:
      true if the graph contains an edge with the given source and target, false otherwise
      Throws:
      NoSuchVertexException - if source or target are not valid vertices identifiers

    • getEdge

      E getEdge(V source, V target)
      Get the edge whose source is source and target is target.

      If the graph is not directed, the return edge is an edge that its end-points are source and target.

      In case there are multiple (parallel) edges between source and target, a single arbitrary one is returned.

      Parameters:
      source - a source vertex
      target - a target vertex
      Returns:
      id of the edge or null if no such edge exists
      Throws:
      NoSuchVertexException - if source or target are not valid vertices identifiers

    • getEdges

      EdgeSet<V,E> getEdges(V source, V target)
      Get the edges whose source is source and target is target.
      Parameters:
      source - a source vertex
      target - a target vertex
      Returns:
      all the edges whose source is source and target is target
      Throws:
      NoSuchVertexException - if source or target are not valid vertices identifiers

    • addEdge

      void addEdge(V source, V target, E edge)
      Add a new edge to the graph.

      If the graph does not support parallel edges, and an edge between source and target already exists, an exception will be raised. If the graph does not support self edges, and source and target are the same vertex, an exception will be raised.

      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 the graph have 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 graph or if the graph does not support parallel edges and an edge between source and target already exists or if the graph does not support self edges and source and target are the same vertex
      NullPointerException - if edge is null
      NoSuchVertexException - if source or target are not valid vertices identifiers

    • addEdge

      default E addEdge(V source, V target)
      Add a new edge to the 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 graph does not support parallel edges, and an edge between source and target already exists, an exception will be raised. If the graph does not support self edges, and source and target are the same vertex, an exception will be raised.

      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 graph does not have an edge builder, namely if edgeBuilder() returns null
      IllegalArgumentException - if the graph does not support parallel edges and an edge between source and target already exists or if the graph does not support self edges and source and target are the same vertex
      NoSuchVertexException - if source or target are not valid vertices identifiers

    • addEdges

      void addEdges(EdgeSet<? extends V,? extends E> edges)
      Add multiple edges to the 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 another Graph, or using EdgeSet.of(Set, Graph).

      If the graph does not support self edges and one of the added edges have the same vertex as source and target, an exception will be thrown. If the graph does not support parallel edges, and one of the added edges have the same source and target as one of the existing edges in the graph, or if two of the added edges have the same source and target, an exception will be thrown.

      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();

 Graph<V,E> matchingGraph = Graph.newUndirected();
 matchingGraph.addVertices(g.vertices());
 matchingGraph.addEdges(EdgeSet.of(matching, g));
      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, or if the graph does not support self edges and one the added edges has the same source and target vertices, or if the graph does not support parallel edges and by adding all the given edges there will be two or more edges with the same source and target vertices
      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

    • removeEdge

      void removeEdge(E edge)
      Remove an edge from the graph.
      Parameters:
      edge - the edge to remove
      Throws:
      NoSuchEdgeException - if edge is not a valid edge identifier

    • removeEdges

      void removeEdges(Collection<? extends E> edges)
      Remove multiple edges from the graph.
      Parameters:
      edges - the edges to remove
      Throws:
      NoSuchEdgeException - if any of the edges is not a valid edge identifier
      NullPointerException - if edges is null or if any of the edges is null
      IllegalArgumentException - if edges contains duplications

    • removeEdgesOf

      void removeEdgesOf(V vertex)
      Remove all the edges of a vertex.
      Parameters:
      vertex - a vertex in the graph
      Throws:
      NoSuchVertexException - if vertex is not a valid vertex identifier

    • removeOutEdgesOf

      void removeOutEdgesOf(V source)
      Remove all edges whose source is source.
      Parameters:
      source - a vertex in the graph
      Throws:
      NoSuchVertexException - if source is not a valid vertex identifier

    • removeInEdgesOf

      void removeInEdgesOf(V target)
      Remove all edges whose target is target.
      Parameters:
      target - a vertex in the graph
      Throws:
      NoSuchVertexException - if target is not a valid vertex identifier

    • renameEdge

      void renameEdge(E edge, E newId)
      Set a new identifier for an existing edge.

      This method changes the identifier of an existing edge, while keeping the source and target of the edge, along with the weights associated with it.

      Parameters:
      edge - an existing edge in the graph
      newId - the new edge identifier
      Throws:
      NoSuchEdgeException - if edge is not a valid edge identifier
      IllegalArgumentException - if newId is already in the graph
      NullPointerException - if newId is null

    • moveEdge

      void moveEdge(E edge, V newSource, V newTarget)
      Move an existing edge to new source and target vertices.

      This method changes the source and target of an existing edge, while keeping the identifier of the edge and the weights associated with it.

      Parameters:
      edge - an existing edge in the graph
      newSource - the new source vertex
      newTarget - the new target vertex
      Throws:
      NoSuchEdgeException - if edge is not a valid edge identifier
      NoSuchVertexException - if newSource or newTarget are not valid vertices identifiers
      IllegalArgumentException - if newSource and newTarget are the same vertex and the graph does not support self edges, or if the graph does not support parallel edges and an edge between newSource and newTarget already exists

    • reverseEdge

      default void reverseEdge(E edge)
      Reverse an edge by switching its source and target.
      Parameters:
      edge - an existing edge in the graph
      Throws:
      NoSuchEdgeException - if edge is not a valid edge identifier
      IllegalArgumentException - if the graph does not support parallel edges and another edge which is the reverse of edge already exists in the graph

    • edgeSource

      V edgeSource(E edge)
      Get the source vertex of an edge.

      If the graph is undirected, this function return an arbitrary end-point of the edge, but always other end-point than edgeTarget(Object) returns.

      Parameters:
      edge - the edge identifier
      Returns:
      the edge source vertex
      Throws:
      NoSuchEdgeException - if edge is not a valid edge identifier

    • edgeTarget

      V edgeTarget(E edge)
      Get the target vertex of an edge.

      If the graph is undirected, this function return an arbitrary end-point of the edge, but always the other end-point than edgeSource(Object) returns.

      Parameters:
      edge - the edge identifier
      Returns:
      the edge target vertex
      Throws:
      NoSuchEdgeException - if edge is not a valid edge identifier

    • edgeEndpoint

      V edgeEndpoint(E edge, V endpoint)
      Get the other end-point of an edge.

      Given an edge \((u,v)\) and a vertex \(w\), assuming \(w\) is an endpoint of the edge, namely that \(w\) is either \(u\) or \(v\), the method will return the other endpoint which is not \(w\). If \(w=u\) the method will return \(v\), if \(w=v\) the method will return \(u\).

      Parameters:
      edge - an edge identifier
      endpoint - one of the edge end-point
      Returns:
      the other end-point of the edge
      Throws:
      NoSuchEdgeException - if edge is not a valid edge identifier
      NoSuchVertexException - if endpoint is not a valid vertex identifier
      IllegalArgumentException - if endpoint is not an endpoint of the edge

    • clear

      void clear()
      Clear the graph completely by removing all vertices and edges.

      This function might be used to reuse an already allocated graph object.

      Note that this function also clears any weights associated with the vertices or edges.

    • clearEdges

      void clearEdges()
      Remove all the edges from the graph.

      Note that this function also clears any weights associated with the edges.

    • vertexBuilder

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

      The vertex builder is used to create new vertices in the graph during the execution of addVertex(), in which the vertex identifier is not provided by the user. Not all graphs have a vertex builder, and may return a null value. In that case, addVertex() cannot be used, only addVertex(Object).

      Returns:
      the vertex builder of this graph, or null if the graph does not have a vertex builder

    • edgeBuilder

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

      The edge builder is used to create new edges in the graph during the execution of addEdge(Object, Object), in which the edge identifier is not provided by the user. Not all graphs have an edge builder, and may return a null value. In that case, addEdge(Object, Object) cannot be used, only addEdge(Object, Object, Object).

      Returns:
      the edge builder of this graph, or null if the graph does not have an edge builder

    • 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 this graph.

      The created weights will be bounded to this graph, and will be updated when the graph is updated (when vertices are added or removed). To create an external weights container, for example in cases the graph is a user input and we are not allowed to modify it, use Weights.createExternalVerticesWeights(Graph, Class). 

       
 Graph<String, Int> g = ...;
 g.newVertex("Alice");
 g.newVertex("Bob");

 Weights<String> names = g.addVerticesWeights("surname", String.class);
 names.set("Alice", "Miller");
 names.set("Bob", "Jones");

 WeightsInt ages = g.addVerticesWeights("age", int.class);
 ages.set("Alice", 42);
 ages.set("Bob", 35);

      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 this graph with default value.

      The created weights will be bounded to this graph, and will be updated when the graph is updated. To create an external weights container, for example in cases the graph is a user input we are not allowed to modify it, use Weights.createExternalVerticesWeights(Graph, Class, Object). 

       
 Graph<String, Int> g = ...;
 g.newVertex("Alice");
 g.newVertex("Bob");
 g.newVertex("Charlie");

 Weights<String> names = g.addVerticesWeights("name", String.class, "Unknown");
 names.set("Alice", "Miller");
 names.set("Bob", "Jones");

 assert "Miller".equals(names.get("Alice"))
 assert "Jones".equals(names.get("Bob"))
 assert "Unknown".equals(names.get("Charlie"))

      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

    • removeVerticesWeights

      void removeVerticesWeights(String key)
      Remove a weight type associated with the vertices of the graph.

      See Weights for a complete documentation of the weights containers.

      Parameters:
      key - the key of the weights
      Throws:
      IllegalArgumentException - if there are no vertices weights with the specified key

    • verticesWeightsKeys

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

      See Weights 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 this graph.

      The created weights will be bounded to this graph, and will be updated when the graph is updated. To create an external weights container, for example in cases the graph is a user input you are not allowed to modify it, use Weights.createExternalEdgesWeights(Graph, Class). 

       
 Graph<String, Integer> g = ...;
 g.addVertex("Berlin");
 g.addVertex("Leipzig");
 g.addVertex("Dresden");
 g.addEdge("Berlin", "Leipzig", 9);
 g.addEdge("Berlin", "Dresden", 13);

 Weights<String> roadTypes = g.addEdgesWeights("roadType", String.class);
 roadTypes.set(9, "Asphalt");
 roadTypes.set(13, "Gravel");

 WeightsDouble roadLengths = g.addEdgesWeights("roadLength", double.class);
 roadLengths.set(9, 42);
 roadLengths.set(13, 35);

      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 this graph with default value.

      The created weights will be bounded to this graph, and will be updated when the graph is updated. To create an external weights container, for example in cases the graph is a user input we are not allowed to modify it, use Weights.createExternalEdgesWeights(Graph, Class, Object). 

       
 Graph<String, Integer> g = ...;
 g.addVertex("Berlin");
 g.addVertex("Leipzig");
 g.addVertex("Dresden");
 g.addEdge("Berlin", "Leipzig", 9);
 g.addEdge("Berlin", "Dresden", 13);
 g.addEdge("Dresden", "Leipzig", 14);

 Weights<String> roadTypes = g.addEdgesWeights("roadType", String.class, "Unknown");
 roadTypes.set(9, "Asphalt");
 roadTypes.set(13, "Gravel");

 assert "Asphalt".equals(names.get(9))
 assert "Gravel".equals(names.get(13))
 assert "Unknown".equals(names.get(14))

      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

    • removeEdgesWeights

      void removeEdgesWeights(String key)
      Remove a weight type associated with the edges of the graph.

      See Weights for a complete documentation of the weights containers.

      Parameters:
      key - the key of the weights
      Throws:
      IllegalArgumentException - if there are no edges weights with the specified key

    • edgesWeightsKeys

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

      See Weights for a complete documentation of the weights containers.

      Returns:
      the keys of all the associated edges weights

    • isDirected

      boolean isDirected()
      Checks whether the graph is directed.
      Returns:
      true if the graph is directed, else false.

    • isAllowSelfEdges

      boolean isAllowSelfEdges()
      Checks whether self edges are supported.

      Self edges are edges with the same source and target, namely a vertex with an edge to itself.

      Returns:
      true if the graph support self edges, else false.

    • isAllowParallelEdges

      boolean isAllowParallelEdges()
      Checks whether parallel edges are supported.

      Parallel edges are multiple edges with identical source and target.

      Returns:
      true if the graph support parallel edges, else false.

    • indexGraph

      IndexGraph indexGraph()
      Get an Index graph view of this graph.

      The returned IndexGraph is a graph in which the identifiers of the vertices are always (0,1,2, ...,verticesNum-1), and the identifiers of the edges are always (0,1,2, ...,edgesNum-1). To maintain this, the index graph implementation may rename existing vertices or edges along the graph lifetime. This rename behavior is less user friendly, but allow for high performance boost as no hash tables are needed, a simple array or bitmap can be used to map each vertex/edge to a value/weight/flag. See IndexGraph for more information. The IndexGraph should not be used in scenarios where performance does not matter.

      The returned graph is a view, namely a graph that will contain the same vertices and edges (with different int identifiers), and the same associated weights, that is automatically updated when the original graph is updated, but not visa versa. The index graph returned should not be modified directly by adding/removing vertices/edges/weights, use the enclosing graph instead.

      The mapping of the vertices and edges indices to the original vertices and edges identifiers can be obtained by the indexGraphVerticesMap() and indexGraphEdgesMap() methods.

      If this graph is an Index graph, this method returns this graph.

      Returns:
      an IndexGraph view of this graph

    • indexGraphVerticesMap

      IndexIdMap<V> indexGraphVerticesMap()
      Get the index-id vertices mapping of this graph.

      A regular graph contains vertices and edges which are identified by a fixed int IDs. An IndexGraph view is provided by the indexGraph() method, which is a graph in which all methods are accessed with indices rather than fixed IDs. This method expose the mapping between the indices and the fixed IDs of the graph vertices.

      Note that the mapping may change during the graph lifetime, as vertices are added and removed from the graph, and a regular graph IDs are fixed, while a index graph indices are always (0,1,2, ...,verticesNum-1). The returned mapping object will be updated automatically in such cases.

      Returns:
      a mapping that map vertices IDs to vertices indices

    • indexGraphEdgesMap

      IndexIdMap<E> indexGraphEdgesMap()
      Get the index-id edges mapping of this graph.

      A regular graph contains vertices and edges which are identified by a fixed int IDs. An IndexGraph view is provided by the indexGraph() method, which is a graph in which all methods are accessed with indices rather than fixed IDs. This method expose the mapping between the indices and the fixed IDs of the graph edges.

      Note that the mapping may change during the graph lifetime, as edges are added and removed from the graph, and a regular graph IDs are fixed, while a index graph indices are always (0,1,2, ...,edgesNum-1). The returned mapping object will be updated automatically in such cases.

      Returns:
      a mapping that map edges IDs to edges indices

    • copy

      default Graph<V,E> copy()
      Create a copy of this graph, with the same vertices and edges, without copying weights.

      An identical copy of this graph will be created, with the same vertices, edges, capabilities (inclusive) such as self edges and parallel edges support, without copying the vertices/edges weights. The returned graph will always be mutable, with no side affects on the original graph.

      Returns:
      an identical copy of this graph, with the same vertices and edges, without this graph weights

    • copy

      default Graph<V,E> copy(boolean copyVerticesWeights, boolean copyEdgesWeights)
      Create a copy of this graph, with the same vertices and edges, with/without copying weights.

      An identical copy of this graph will be created, with the same vertices, edges, capabilities (inclusive) such as self edges and parallel edges support, with/without copying the vertices/edges weights. The returned graph will always be mutable, with no side affects on the original graph.

      Note that although g.equals(g.copy()) is always true if both copyVerticesWeights copyEdgesWeights are true, there is no guarantee that g.indexGraph().equals(g.copy().indexGraph()). Namely, when the graph is copied, new indices may be assigned to the vertices and edges.

      Parameters:
      copyVerticesWeights - if true, the weights of the vertices will be copied to the new graph
      copyEdgesWeights - if true, the weights of the edges will be copied to the new graph
      Returns:
      an identical copy of the given graph, with the same vertices and edges, with/without this graph weights

    • immutableCopy

      default Graph<V,E> immutableCopy()
      Create an immutable copy of this graph, with the same vertices and edges, without copying weights.

      An identical copy of this graph will be created, with the same vertices and edges, without copying the vertices/edges weights. The returned graph will be immutable, and no vertices/edges/weights can be added or removed from it.

      A more compact and efficient representation may be used for the graph, if its known that it will not be changed in the future. It may be more efficient to create an immutable copy of a graph and pass the copy to algorithms instead of using the original graph.

      Note that although g.equals(g.immutableCopy()) is always true, there is no guarantee that g.indexGraph().equals(g.immutableCopy().indexGraph()). Namely, when the graph is copied, new indices may be assigned to the vertices and edges.

      Returns:
      an immutable copy of this graph, with the same vertices and edges, without this graph weights

    • immutableCopy

      default Graph<V,E> immutableCopy(boolean copyVerticesWeights, boolean copyEdgesWeights)
      Create an immutable copy of this graph, with the same vertices and edges, with/without copying weights.

      An identical copy of this graph will be created, with the same vertices and edges, with/without copying the vertices/edges weights. The returned graph will be immutable, and no vertices/edges/weights can be added or removed from it.

      A more compact and efficient representation may be used for the graph, if its known that it will not be changed in the future. It may be more efficient to create an immutable copy of a graph and pass the copy to algorithms instead of using the original graph.

      Note that although g.equals(g.immutableCopy()) is always true if both copyVerticesWeights and copyEdgesWeights are true, there is no guarantee that g.indexGraph().equals(g.immutableCopy().indexGraph()). Namely, when the graph is copied, new indices may be assigned to the vertices and edges.

      Parameters:
      copyVerticesWeights - if true, the weights of the vertices will be copied to the new graph
      copyEdgesWeights - if true, the weights of the edges will be copied to the new graph
      Returns:
      an immutable copy of this graph, with the same vertices and edges, with/without this graph weights

    • immutableView

      default Graph<V,E> immutableView()
      Get an immutable view of this graph.

      This method return a view of this graph, namely a Graph that contains the same vertices, edges and weights, that is automatically updated when the original graph is updated. The view is immutable, namely all operations that modify the graph will throw UnsupportedOperationException.

      Returns:
      an immutable view of this graph

    • reverseView

      default Graph<V,E> reverseView()
      Get a reversed view of this graph.

      This method return a view of this graph, namely a Graph that contains the same vertices, edges and weights, that is automatically updated when the original graph is updated and vice versa. The view is reversed, namely each source and target vertices of each edge are swapped.

      Note that modifying the returned view will change the original graph.

      Returns:
      a reversed view of this graph

    • undirectedView

      default Graph<V,E> undirectedView()
      Get an undirected view of this (directed) graph.

      This method return a view of this graph, namely a Graph that contains the same vertices, edges and weights, that is automatically updated when the original graph is updated and vice versa. The view is undirected, namely each directed edge \((u,v)\) will exist in all the sets g.outEdges(u), g.inEdges(u), g.outEdges(v) and g.inEdges(u). The view will contain the same number of edges as this graph.

      The returned view will return true for isAllowParallelEdges() even if the original graph does not support parallel edges. This is because the original graph could have both \((u,v)\) in \((v,u)\) without violating the parallel edges constraint, but the view will treat them as parallel edges as the direction is 'forgotten'.

      If this graph is undirected, this function return the graph itself.

      Returns:
      an undirected view of this graph

    • subGraphCopy

      default Graph<V,E> subGraphCopy(Collection<V> vertices, Collection<E> edges)
      Create a new graph that is a subgraph of this graph.

      If edges is null, then the created graph will be an induced subgraph of this graph, namely an induced subgraph of a graph \(G=(V,E)\) is a graph \(G'=(V',E')\) where \(V' \subseteq V\) and \(E' = \{\{u,v\} \mid u,v \in V', \{u,v\} \in E\}\). vertices must not be null in this case.

      If vertices is null, then edges must not be null, and the sub graph will contain all the vertices which are either a source or a target of an edge in edges.

      The created graph will have the same type (directed/undirected) as this graph. The vertices and edges of the created graph will be a subset of the vertices and edges of this graph.

      The weights of both vertices and edges will not be copied to the new sub graph. For more flexible sub graph creation, see Graphs.subGraph(Graph, Collection, Collection, boolean, boolean).

      Parameters:
      vertices - the vertices of the sub graph, if null then edges must not be null and the vertices of the sub graph will be all the vertices which are either a source or a target of an edge in edges
      edges - the edges of the sub graph, if null then vertices must not be null and the sub graph will be an induced subgraph of this graph
      Returns:
      a new graph that is a subgraph of this graph
      Throws:
      NullPointerException - if both vertices and edges are null

    • newUndirected

      static <V, E> Graph<V,E> newUndirected()
      Create a new undirected empty graph.

      The returned graph will be implemented using the default implementation. For more control over the graph details, see GraphFactory.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Returns:
      a new undirected empty graph

    • newDirected

      static <V, E> Graph<V,E> newDirected()
      Create a new directed empty graph.

      The returned graph will be implemented using the default implementation. For more control over the graph details, see GraphFactory.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Returns:
      a new directed empty graph