Package com.jgalgo.graph

Interface IndexGraph

  • All Superinterfaces:
    Graph<Integer,​Integer>, IntGraph
    All Known Implementing Classes:
    GraphBaseWithEdgeEndpointsContainer
    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:
    IndexIdMap

    • Method Detail

      • 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

      • addVertex

        int addVertex()
        Add a new vertex to the graph.

        The graph implementation will choose a new int identifier which is not currently used as one of the graph edges, and will return it as the new vertex ID.

        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
        Returns:
        the new vertex identifier

      • addVertex

        @Deprecated
default void addVertex​(int vertex)
        Deprecated.
        Unsupported operation.

        Index graphs vertices IDs are always (0,1,2, ...,verticesNum-1) and do not support user chosen IDs.

        Specified by:
        addVertex in interface IntGraph
        Parameters:
        vertex - a user chosen identifier for the new vertex
        Throws:
        UnsupportedOperationException - always

      • 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

      • addEdge

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

        The graph implementation will choose a new int identifier which is not currently used as one of the graph edges, and will return it as the new edge ID.

        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 identifier

      • addEdge

        @Deprecated
default void addEdge​(int source,
                     int target,
                     int edge)
        Deprecated.
        Unsupported operation.

        Index graphs edges IDs are always (0,1,2, ...,edgesNum-1) and do not support user chosen IDs.

        Specified by:
        addEdge in interface IntGraph
        Parameters:
        source - a source vertex
        target - a target vertex
        edge - a user chosen identifier for the new edge
        Throws:
        UnsupportedOperationException - always

      • 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

        default 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

        default 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

        default 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

      • reverseEdge

        void reverseEdge​(int edge)
        Reverse an edge by switching its source and target.

        If the graph is undirected, this method does nothing.

        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:
        reverseEdge in interface IntGraph
        Parameters:
        edge - an existing edge in the graph

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

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

      • 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

      • 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 modifiable, 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 copyWeights)
        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 modifiable, with no side affects on the original graph.

        Note that although g.equals(g.copy()) is always true if copyWeights is 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:
        copyWeights - if true, the weights of the vertices and 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 copyWeights)
        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 copyWeights is 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:
        copyWeights - if true, the weights of the vertices and 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