Package com.jgalgo.graph

Interface IndexGraph

All Superinterfaces:
Graph<Integer,Integer>, IntGraph
public interface IndexGraph extends IntGraph
A graph whose vertices and edges identifiers are indices.

The Graph interface provide addition, removal and querying of vertices and edges, all using some hashable identifiers. These identifiers are fixed, and once a vertex or edge is assigned an ID, it will not change during the graph lifetime. On the other hand, an Index graph is a IntGraph object in which the vertices and edges identifiers of the graph are always (0,1,2, ...,verticesNum-1) and (0,1,2, ...,edgesNum-1).

The index graph invariants allow for a great performance boost, as a simple array or bitmap can be used to associate a value/weight/flag with each vertex/edge. But it does come with a cost: to maintain the invariants, implementations may need to rename existing vertices or edges during the graph lifetime. These renames can be subscribed-to using addVertexRemoveListener(IndexRemoveListener) and addEdgeRemoveListener(IndexRemoveListener).

An index graph may be obtained as a view from a regular Graph using Graph.indexGraph(), or it can be created on its own using IndexGraphFactory. In cases where no removal of vertices or edges is required, and there is no need to use pre-defined IDs, there is no drawback of using the IndexGraph as a regular IntGraph, as it will expose an identical functionality while providing better performance.

If an IndexGraph is obtained from a regular Graph (or IntGraph) using Graph.indexGraph(), the IndexGraph should not be modified directly. Vertices/edges/weights should be added/removed only via the original fixed identifiers graph.

All graph algorithms implementations should operation on Index graphs only, for best performance. If a regular Graph is provided to an algorithm, the Index graph should be retrieved using Graph.indexGraph(), the algorithm expensive logic should operate on the returned Index graph and finally the result should be transformed back to the regular graph IDs. The mapping from a regular graph IDs to indices and vice versa is provided by IndexIdMap, which can be accessed using Graph.indexGraphVerticesMap() and Graph.indexGraphEdgesMap().

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

Author:
Barak Ugav
See Also:

  • Method Details

    • vertices

      IntSet 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().

      In an Index graph, the set of vertices are always (0,1,2, ...,verticesNum-1).

      Specified by:
      vertices in interface Graph<Integer,Integer>
      Specified by:
      vertices in interface IntGraph
      Returns:
      a set containing all vertices of the graph

    • edges

      IntSet 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().

      In an Index graph, the set of edges are always (0,1,2, ...,edgesNum-1).

      Specified by:
      edges in interface Graph<Integer,Integer>
      Specified by:
      edges in interface IntGraph
      Returns:
      a set containing all edges of the graph

    • addVertexInt

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

      Unlike IntGraph.addVertex(int) in which the vertex is provided by the user, this method uses the vertex builder obtained by IntGraph.vertexBuilder() to create the new vertex object 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.

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

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

    • addVertex

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

      Vertices must be non negative integers.

      If the graph have a vertex builder, namely if IntGraph.vertexBuilder() does not return null, the method IntGraph.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().

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

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

    • addVertices

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

      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.

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addVertices in interface Graph<Integer,Integer>
      Specified by:
      addVertices in interface IntGraph
      Parameters:
      vertices - new vertices

    • removeVertex

      void removeVertex(int vertex)
      Remove a vertex and all its edges from the graph.

      After removing a vertex, the graph implementation may swap and rename vertices to maintain its invariants. Theses renames can be subscribed using addVertexRemoveListener(IndexRemoveListener).

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      removeVertex in interface IntGraph
      Parameters:
      vertex - the vertex identifier to remove

    • renameVertex

      @Deprecated default void renameVertex(int vertex, int newId)
      Deprecated.
      unsupported operation
      Unsupported operation.
      Specified by:
      renameVertex in interface IntGraph
      Parameters:
      vertex - an existing vertex in the graph
      newId - the new vertex identifier
      Throws:
      UnsupportedOperationException - always

    • addEdge

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

      Unlike IntGraph.addEdge(int, int, int) in which the edge (identifier) is provided by the user, this method uses the edge builder obtained by IntGraph.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: 

       
 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.

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addEdge in interface IntGraph
      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 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.

      Edges must be non negative integers.

      If the graph have an edge builder, namely if IntGraph.edgeBuilder() does not return null, the method IntGraph.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).

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addEdge in interface IntGraph
      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 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));

      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).

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addEdges in interface Graph<Integer,Integer>
      Specified by:
      addEdges in interface IntGraph
      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 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 another 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).

      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.

      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 maintain the index graph invariants. 

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

 IndexGraph matchingGraph = IndexGraph.newUndirected();
 matchingGraph.addVertices(g.vertices());
 matchingGraph.addEdgesReassignIds(IEdgeSet.of(matching, g));

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      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

    • removeEdge

      void removeEdge(int edge)
      Remove an edge from the graph.

      After removing an edge, the graph implementation may swap and rename edges to maintain its invariants. Theses renames can be subscribed using addEdgeRemoveListener(IndexRemoveListener).

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      removeEdge in interface IntGraph
      Parameters:
      edge - the edge identifier

    • removeEdgesOf

      void removeEdgesOf(int vertex)
      Remove all the edges of a vertex.

      After removing an edge, the graph implementation may swap and rename edges to maintain its invariants. Theses renames can be subscribed using addEdgeRemoveListener(IndexRemoveListener).

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      removeEdgesOf in interface IntGraph
      Parameters:
      vertex - a vertex in the graph

    • removeOutEdgesOf

      void removeOutEdgesOf(int source)
      Remove all edges whose source is source.

      After removing an edge, the graph implementation may swap and rename edges to maintain its invariants. Theses renames can be subscribed using addEdgeRemoveListener(IndexRemoveListener).

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      removeOutEdgesOf in interface IntGraph
      Parameters:
      source - a vertex in the graph

    • removeInEdgesOf

      void removeInEdgesOf(int target)
      Remove all edges whose target is target.

      After removing an edge, the graph implementation may swap and rename edges to maintain its invariants. Theses renames can be subscribed using addEdgeRemoveListener(IndexRemoveListener).

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      removeInEdgesOf in interface IntGraph
      Parameters:
      target - a vertex in the graph

    • renameEdge

      @Deprecated default void renameEdge(int edge, int newId)
      Deprecated.
      unsupported operation
      Unsupported operation.
      Specified by:
      renameEdge in interface IntGraph
      Parameters:
      edge - an existing edge in the graph
      newId - the new edge identifier
      Throws:
      UnsupportedOperationException - always

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

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      clear in interface Graph<Integer,Integer>

    • clearEdges

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

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

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      clearEdges in interface Graph<Integer,Integer>

    • vertexBuilder

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

      The vertex builder is used to create new vertices in the graph during the execution of Graph.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, Graph.addVertex() cannot be used, only Graph.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 Graph<Integer,Integer>
      Specified by:
      vertexBuilder in interface IntGraph
      Returns:
      the vertex builder of this graph, or null if the graph does not have a vertex builder

    • edgeBuilder

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

      The edge builder is used to create new edges in the graph during the execution of Graph.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, Graph.addEdge(Object, Object) cannot be used, only Graph.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 Graph<Integer,Integer>
      Specified by:
      edgeBuilder in interface IntGraph
      Returns:
      the edge builder of this graph, or null if the graph does not have an edge builder

    • addVerticesWeights

      default <T, WeightsT extends Weights<Integer, 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.

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addVerticesWeights in interface Graph<Integer,Integer>
      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

    • addVerticesWeights

      <T, WeightsT extends Weights<Integer, 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.

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addVerticesWeights in interface Graph<Integer,Integer>
      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

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

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      removeVerticesWeights in interface Graph<Integer,Integer>
      Parameters:
      key - the key of the weights

    • addEdgesWeights

      default <T, WeightsT extends Weights<Integer, 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.

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addEdgesWeights in interface Graph<Integer,Integer>
      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

    • addEdgesWeights

      <T, WeightsT extends Weights<Integer, 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.

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      addEdgesWeights in interface Graph<Integer,Integer>
      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

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

      If this index graph object was obtained from a regular Graph using Graph.indexGraph(), this method should not be called. Use the original graph instead.

      Specified by:
      removeEdgesWeights in interface Graph<Integer,Integer>
      Parameters:
      key - the key of the weights

    • addVertexRemoveListener

      void addVertexRemoveListener(IndexRemoveListener listener)
      Adds a listener that will be called each time a vertex remove or swap is performed.

      An IndexGraph may rename vertices during its lifetime to maintain the invariant that all vertices are identified by 0,1,2,...,verticesNum-1. This method can be used to track these changes, by registering a listener that will be invoked each time such a rename is performed.

      If a vertex is removed with the last index (verticesNum-1), the vertex can simply be removed. Otherwise, the vertex will be swapped with the last vertex and then removed. In both cases, the listener will be called.

      Parameters:
      listener - a remove listener that will be called each time a vertex remove or swap is performed

    • removeVertexRemoveListener

      void removeVertexRemoveListener(IndexRemoveListener listener)
      Removes a vertex remove listener.

      After a listener was added using addVertexRemoveListener(IndexRemoveListener), this method can remove it.

      Parameters:
      listener - a remove listener that should be removed

    • addEdgeRemoveListener

      void addEdgeRemoveListener(IndexRemoveListener listener)
      Adds a listener that will be called each time a edge swap is performed.

      An IndexGraph may rename edges during its lifetime to maintain the invariant that all edges are identified by 0,1,2,...,edgesNum-1. This method can be used to track these changes, by registering a listener that will be invoked each time such a rename is performed.

      If an edge is removed with the last index (edgesNum-1), the edge can simply be removed. Otherwise, the edge will be swapped with the last edge and then removed. In both cases, the listener will be called.

      Parameters:
      listener - a remove listener that will be called each time a edge remove or swap is performed

    • removeEdgeRemoveListener

      void removeEdgeRemoveListener(IndexRemoveListener listener)
      Removes an edge remove listener.

      After a listener was added using addEdgeRemoveListener(IndexRemoveListener), this method can remove it.

      Parameters:
      listener - a remove listener that should be removed

    • indexGraph

      @Deprecated default IndexGraph indexGraph()
      Deprecated.
      this function will always return the same graph, no reason to call it
      The index graph of an IndexGraph is itself.
      Specified by:
      indexGraph in interface Graph<Integer,Integer>
      Returns:
      this graph

    • indexGraphVerticesMap

      @Deprecated IndexIntIdMap indexGraphVerticesMap()
      Deprecated.
      this function will always return the identity mapping, no reason to call it
      The IDs and indices of an IndexGraph are the same.
      Specified by:
      indexGraphVerticesMap in interface Graph<Integer,Integer>
      Specified by:
      indexGraphVerticesMap in interface IntGraph
      Returns:
      a mapping that map vertices IDs to vertices indices

    • indexGraphEdgesMap

      @Deprecated IndexIntIdMap indexGraphEdgesMap()
      Deprecated.
      this function will always return the identity mapping, no reason to call it
      The IDs and indices of an IndexGraph are the same.
      Specified by:
      indexGraphEdgesMap in interface Graph<Integer,Integer>
      Specified by:
      indexGraphEdgesMap in interface IntGraph
      Returns:
      a mapping that map edges IDs to edges indices

    • copy

      default IndexGraph copy()
      Description copied from interface: Graph
      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.

      Specified by:
      copy in interface Graph<Integer,Integer>
      Specified by:
      copy in interface IntGraph
      Returns:
      an identical copy of this graph, with the same vertices and edges, without this graph weights

    • copy

      default IndexGraph copy(boolean copyVerticesWeights, boolean copyEdgesWeights)
      Description copied from interface: Graph
      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.

      Specified by:
      copy in interface Graph<Integer,Integer>
      Specified by:
      copy in interface IntGraph
      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 IndexGraph immutableCopy()
      Description copied from interface: Graph
      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.

      Specified by:
      immutableCopy in interface Graph<Integer,Integer>
      Specified by:
      immutableCopy in interface IntGraph
      Returns:
      an immutable copy of this graph, with the same vertices and edges, without this graph weights

    • immutableCopy

      default IndexGraph immutableCopy(boolean copyVerticesWeights, boolean copyEdgesWeights)
      Description copied from interface: Graph
      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.

      Specified by:
      immutableCopy in interface Graph<Integer,Integer>
      Specified by:
      immutableCopy in interface IntGraph
      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 IndexGraph immutableView()
      Description copied from interface: Graph
      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.

      Specified by:
      immutableView in interface Graph<Integer,Integer>
      Specified by:
      immutableView in interface IntGraph
      Returns:
      an immutable view of this graph

    • reverseView

      default IndexGraph reverseView()
      Description copied from interface: Graph
      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.

      Specified by:
      reverseView in interface Graph<Integer,Integer>
      Specified by:
      reverseView in interface IntGraph
      Returns:
      a reversed view of this graph

    • undirectedView

      default IndexGraph undirectedView()
      Description copied from interface: Graph
      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 Graph.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.

      Specified by:
      undirectedView in interface Graph<Integer,Integer>
      Specified by:
      undirectedView in interface IntGraph
      Returns:
      an undirected view of this graph

    • newUndirected

      static IndexGraph newUndirected()
      Create a new undirected empty index graph.

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

      Returns:
      a new undirected empty index graph

    • newDirected

      static IndexGraph newDirected()
      Create a new directed empty index graph.

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

      Returns:
      a new directed empty index graph