Package com.jgalgo.graph

Interface Graph<V,​E>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 // Print the shortest path from Berlin to Leipzig
 System.out.println("Distance from Berlin to Leipzig is: " + ssspRes.distance("Leipzig"));
 System.out.println("The shortest path from Berlin to Leipzig is:");
 for (Integer e : ssspRes.getPath("Leipzig").edges()) {
 	String u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
    Author:
    Barak Ugav
    See Also:
    GraphFactory, GraphBuilder, IndexGraph

    • Method Detail

      • vertices

        Set<V> vertices()
        Get the set of all vertices of the graph.

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

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

        Returns:
        a set containing all vertices of the graph

      • edges

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

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

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

        Returns:
        a set containing all edges of the graph

      • addVertex

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

        A vertex can be any non null hashable object, namely it must implement Object.hashCode() and Object.equals(Object) methods. The set of graph vertices must not contain duplications, therefore the provided identifier must not be currently used as one of the graph vertices IDs.

        Parameters:
        vertex - new vertex

      • removeVertex

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

      • outEdges

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

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

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

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

      • inEdges

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

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

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

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

      • getEdge

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

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

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

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

      • getEdges

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

      • addEdge

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

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

        The edge identifier must be unique and non null.

        Parameters:
        source - a source vertex
        target - a target vertex
        edge - a new edge identifier

      • removeEdge

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

      • removeEdgesOf

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

      • removeOutEdgesOf

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

      • removeInEdgesOf

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

      • reverseEdge

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

        If the graph is undirected, this method does nothing.

        Parameters:
        edge - an existing edge in the graph
        Throws:
        NoSuchEdgeException - if edge is not a valid edge identifier

      • edgeSource

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

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

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

      • edgeTarget

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

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

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

      • edgeEndpoint

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

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

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

      • clear

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

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

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

      • clearEdges

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

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

      • getVerticesWeights

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

        See Weights for a complete documentation of the weights containers.

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

      • addVerticesWeights

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

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

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

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

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

        See Weights for a complete documentation of the weights containers.

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

      • addVerticesWeights

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

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

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

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

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

        See Weights for a complete documentation of the weights containers.

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

      • removeVerticesWeights

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

        See Weights for a complete documentation of the weights containers.

        Parameters:
        key - the key of the weights

      • getVerticesWeightsKeys

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

        See Weights for a complete documentation of the weights containers.

        Returns:
        the keys of all the associated vertices weights

      • getEdgesWeights

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

        See Weights for a complete documentation of the weights containers.

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

      • addEdgesWeights

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

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

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

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

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

        See Weights for a complete documentation of the weights containers.

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

      • addEdgesWeights

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

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

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

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

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

        See Weights for a complete documentation of the weights containers.

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

      • removeEdgesWeights

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

        See Weights for a complete documentation of the weights containers.

        Parameters:
        key - the key of the weights

      • getEdgesWeightsKeys

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

        See Weights for a complete documentation of the weights containers.

        Returns:
        the keys of all the associated edges weights

      • isDirected

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

      • isAllowSelfEdges

        boolean isAllowSelfEdges()
        Checks whether self edges are supported.

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

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

      • isAllowParallelEdges

        boolean isAllowParallelEdges()
        Checks whether parallel edges are supported.

        Parallel edges are multiple edges with identical source and target.

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

      • indexGraph

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

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

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

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

        Returns:
        an IndexGraph view of this graph

      • indexGraphVerticesMap

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

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

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

        Returns:
        a mapping that map vertices IDs to vertices indices

      • indexGraphEdgesMap

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

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

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

        Returns:
        a mapping that map edges IDs to edges indices

      • copy

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

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

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

      • copy

        default Graph<V,​E> copy​(boolean copyWeights)
        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.

        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 Graph<V,​E> immutableCopy()
        Create an immutable copy of this graph, with the same vertices and edges, without copying weights.

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

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

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

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

      • immutableCopy

        default Graph<V,​E> immutableCopy​(boolean copyWeights)
        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.

        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 Graph<V,​E> immutableView()
        Get an immutable view of this graph.

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

        Returns:
        an immutable view of this graph

      • reverseView

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

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

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

        Returns:
        a reversed view of this graph

      • undirectedView

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

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

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

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

        Returns:
        an undirected view of this graph

      • subGraphCopy

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

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

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

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

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

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

      • newUndirected

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

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

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

      • newDirected

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

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

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