Package com.jgalgo.graph

Interface IntGraph

  • All Superinterfaces:
    Graph<Integer,​Integer>
    All Known Subinterfaces:
    IndexGraph
    public interface IntGraph
extends Graph<Integer,​Integer>
    A discrete graph with int vertices and edges.

    This interface is a specification of Graph for graphs with int vertices and edges, similarly how Int2IntMap is a specification of Map for maps with int keys and values. Methods that accept a primitive int as an identifier are provided, and the original ones that accept a Integer are deprecated. Specific IEdgeSet and IEdgeIter are returned for edges queries, avoiding boxing of integers. Similarly, the IWeights interface is used for weights containers, which accept primitive int as identifiers.

    Each vertex and edge in the graph is identified by a unique non negative int identifier. Vertices and edges may be created by addVertexInt() and addEdge(int, int), in which case the graph implementation will choose the int identifier and will return it to the user. Alternatively, the methods addVertex(int) and addEdge(int, int, int) (similar the regular Graph methods) can be used to add new vertices and edges with user chosen identifiers.

    Implementations of this interface are more efficient than the generic Graph interface, and should be used for better performance if its needed. For even better performance, consider using IndexGraph, which does violate the Graph interface as its vertices and edges may change during the lifetime of the graph and therefore less user friendly, but is even more efficient.

    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 IntGraphFactory. To construct an immutable graph, use IntGraphBuilder. 

     
 // Create a directed graph with three vertices and edges between them
 IntGraph g = IntGraph.newDirected();
 int v1 = g.addVertex();
 int v2 = g.addVertex();
 int v3 = g.addVertex();
 int e1 = g.addEdge(v1, v2);
 int e2 = g.addEdge(v2, v3);
 int e3 = g.addEdge(v1, v3);

 // Assign some weights to the edges
 IWeightsDouble weights = g.addEdgesWeights("weightsKey", double.class);
 weights.set(e1, 1.2);
 weights.set(e2, 3.1);
 weights.set(e3, 15.1);
 IWeightFunction weightFunc = weights;

 // Calculate the shortest paths from v1 to all other vertices
 ShortestPathSingleSource ssspAlgo = ShortestPathSingleSource.newInstance();
 ShortestPathSingleSource.Result ssspRes = ssspAlgo.computeShortestPaths(g, weightFunc, v1);

 // Print the shortest path from v1 to v3
 assert ssspRes.distance(v3) == 4.3;
 assert ssspRes.getPath(v3).edges().equals(IntList.of(e1, e2));
 System.out.println("Distance from v1 to v3 is: " + ssspRes.distance(v3));
 System.out.println("The shortest path from v1 to v3 is:");
 for (int e : ssspRes.getPath(v3).edges()) {
 	int u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
    Author:
    Barak Ugav
    See Also:
    IntGraphFactory, IntGraphBuilder, IndexGraph

    • Method Detail

      • vertices

        IntSet vertices()
        Description copied from interface: Graph
        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().

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

      • edges

        IntSet edges()
        Description copied from interface: Graph
        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().

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

      • addVertex

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

        Vertices must be non negative integers.

        If the graph have a vertex builder, namely if vertexBuilder() does not return null, the method addVertexInt() 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 the provided identifier is already used as identifier of one of the graph vertices, or if its negative

      • addVertexInt

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

        Unlike addVertex(int) 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: 

         
 int 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

      • addVertex

        @Deprecated
default Integer addVertex()
        Deprecated.
        Please use addVertexInt() instead to avoid un/boxing.
        Add a new vertex to the graph, using the vertex builder.

        Unlike Graph.addVertex(Object) in which the vertex is provided by the user, this method uses the vertex builder obtained by Graph.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;
        Specified by:
        addVertex in interface Graph<Integer,​Integer>
        Returns:
        the new vertex

      • removeVertex

        void removeVertex​(int 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

      • renameVertex

        void renameVertex​(int vertex,
                  int 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 or if newId is null

      • renameVertex

        @Deprecated
default void renameVertex​(Integer vertex,
                          Integer newId)
        Deprecated.
        Please use renameVertex(int, int) instead to avoid un/boxing.
        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.

        Specified by:
        renameVertex in interface Graph<Integer,​Integer>
        Parameters:
        vertex - an existing vertex in the graph
        newId - the new vertex identifier

      • outEdges

        IEdgeSet outEdges​(int 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

      • outEdges

        @Deprecated
default IEdgeSet outEdges​(Integer source)
        Deprecated.
        Please use outEdges(int) instead to avoid un/boxing.
        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().

        Specified by:
        outEdges in interface Graph<Integer,​Integer>
        Parameters:
        source - a source vertex
        Returns:
        all the edges whose source is source

      • inEdges

        IEdgeSet inEdges​(int 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

      • inEdges

        @Deprecated
default IEdgeSet inEdges​(Integer target)
        Deprecated.
        Please use inEdges(int) instead to avoid un/boxing.
        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().

        Specified by:
        inEdges in interface Graph<Integer,​Integer>
        Parameters:
        target - a target vertex
        Returns:
        all the edges whose target is target

      • containsEdge

        default boolean containsEdge​(int source,
                             int 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

      • containsEdge

        @Deprecated
default boolean containsEdge​(Integer source,
                             Integer target)
        Deprecated.
        Description copied from interface: Graph
        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.

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

      • getEdge

        int getEdge​(int source,
            int 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 -1 if no such edge exists
        Throws:
        NoSuchVertexException - if source or target are not valid vertices identifiers

      • getEdge

        @Deprecated
default Integer getEdge​(Integer source,
                        Integer target)
        Deprecated.
        Please use getEdge(int, int) instead to avoid un/boxing.
        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.

        Specified by:
        getEdge in interface Graph<Integer,​Integer>
        Parameters:
        source - a source vertex
        target - a target vertex
        Returns:
        id of the edge or null if no such edge exists

      • getEdges

        IEdgeSet getEdges​(int source,
                  int 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

      • getEdges

        @Deprecated
default IEdgeSet getEdges​(Integer source,
                          Integer target)
        Deprecated.
        Please use getEdges(int, int) instead to avoid un/boxing.
        Get the edges whose source is source and target is target.
        Specified by:
        getEdges in interface Graph<Integer,​Integer>
        Parameters:
        source - a source vertex
        target - a target vertex
        Returns:
        all the edges whose source is source and target is target

      • addEdge

        void addEdge​(int source,
             int target,
             int 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.

        Edges must be non negative integers.

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

        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

        @Deprecated
default void addEdge​(Integer source,
                     Integer target,
                     Integer edge)
        Deprecated.
        Please use addEdge(int, int, int) instead to avoid un/boxing.
        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 Graph.edgeBuilder() does not return null, the method Graph.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.

        Specified by:
        addEdge in interface Graph<Integer,​Integer>
        Parameters:
        source - a source vertex
        target - a target vertex
        edge - a new edge identifier

      • addEdge

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

        Unlike addEdge(int, int, int) 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: 

         
 int 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

      • addEdge

        @Deprecated
default Integer addEdge​(Integer source,
                        Integer target)
        Deprecated.
        Please use addEdge(int, int) instead to avoid un/boxing.
        Add a new edge to the graph, using the edge builder.

        Unlike Graph.addEdge(Object, Object, Object) in which the edge (identifier) is provided by the user, this method uses the edge builder obtained by Graph.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;
        Specified by:
        addEdge in interface Graph<Integer,​Integer>
        Parameters:
        source - a source vertex
        target - a target vertex
        Returns:
        the new edge

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

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

      • removeEdge

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

      • removeEdgesOf

        void removeEdgesOf​(int 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​(int 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​(int 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​(int edge,
                int 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 or if newId is negative

      • renameEdge

        @Deprecated
default void renameEdge​(Integer edge,
                        Integer newId)
        Deprecated.
        Please use renameEdge(int, int) instead to avoid un/boxing.
        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.

        Specified by:
        renameEdge in interface Graph<Integer,​Integer>
        Parameters:
        edge - an existing edge in the graph
        newId - the new edge identifier

      • moveEdge

        void moveEdge​(int edge,
              int newSource,
              int 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

      • moveEdge

        @Deprecated
default void moveEdge​(Integer edge,
                      Integer newSource,
                      Integer newTarget)
        Deprecated.
        Please use moveEdge(int, int, int) instead to avoid un/boxing.
        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.

        Specified by:
        moveEdge in interface Graph<Integer,​Integer>
        Parameters:
        edge - an existing edge in the graph
        newSource - the new source vertex
        newTarget - the new target vertex

      • reverseEdge

        default void reverseEdge​(int 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

        int edgeSource​(int 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(int) returns.

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

      • edgeTarget

        int edgeTarget​(int 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(int) returns.

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

      • edgeEndpoint

        int edgeEndpoint​(int edge,
                 int 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

      • edgeEndpoint

        @Deprecated
default Integer edgeEndpoint​(Integer edge,
                             Integer endpoint)
        Deprecated.
        Please use edgeEndpoint(int, int) instead to avoid un/boxing.
        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\).

        Specified by:
        edgeEndpoint in interface Graph<Integer,​Integer>
        Parameters:
        edge - an edge identifier
        endpoint - one of the edge end-point
        Returns:
        the other end-point of the edge

      • vertexBuilder

        IdBuilderInt vertexBuilder()
        Description copied from interface: Graph
        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).

        Specified by:
        vertexBuilder in interface Graph<Integer,​Integer>
        Returns:
        the vertex builder of this graph, or null if the graph does not have a vertex builder

      • verticesWeights

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

        See Weights for a complete documentation of the weights containers.

        The return object is always some sub class of IWeights, such as IWeightsInt or IWeightsDouble.

        Specified by:
        verticesWeights 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
        Returns:
        vertices weights of the key, or null if no container found with the specified key

      • edgesWeights

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

        See Weights for a complete documentation of the weights containers.

        The return object is always some sub class of IWeights, such as IWeightsInt or IWeightsDouble.

        Specified by:
        edgesWeights 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
        Returns:
        edges weights of the key, or null if no container found with the specified key

      • indexGraphVerticesMap

        IndexIntIdMap indexGraphVerticesMap()
        Description copied from interface: Graph
        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 Graph.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.

        Specified by:
        indexGraphVerticesMap in interface Graph<Integer,​Integer>
        Returns:
        a mapping that map vertices IDs to vertices indices

      • indexGraphEdgesMap

        IndexIntIdMap indexGraphEdgesMap()
        Description copied from interface: Graph
        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 Graph.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.

        Specified by:
        indexGraphEdgesMap in interface Graph<Integer,​Integer>
        Returns:
        a mapping that map edges IDs to edges indices

      • copy

        default IntGraph 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>
        Returns:
        an identical copy of this graph, with the same vertices and edges, without this graph weights

      • copy

        default IntGraph 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>
        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 IntGraph 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>
        Returns:
        an immutable copy of this graph, with the same vertices and edges, without this graph weights

      • immutableCopy

        default IntGraph 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>
        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 IntGraph 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>
        Returns:
        an immutable view of this graph

      • reverseView

        default IntGraph 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>
        Returns:
        a reversed view of this graph

      • undirectedView

        default IntGraph 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>
        Returns:
        an undirected view of this graph

      • subGraphCopy

        default IntGraph subGraphCopy​(Collection<Integer> vertices,
                              Collection<Integer> 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).

        Prefer to pass a IntCollection instead of Collection<Integer> as collections of vertices and edges.

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

      • newUndirected

        static IntGraph newUndirected()
        Create a new undirected empty int graph.

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

        Returns:
        a new undirected empty graph

      • newDirected

        static IntGraph newDirected()
        Create a new directed empty int graph.

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

        Returns:
        a new directed empty graph