Package com.jgalgo

Interface Graph

  • All Known Subinterfaces:
    IndexGraph
    public interface Graph
    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, \(u\), and a target \(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 both implement 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(int), removeInEdgesOf(int) and removeOutEdgesOf(int) are equivalent for the same vertex. To check if a graph is directed or not, use the getCapabilities() method.

    Each vertex and edge in the graph is identified by a unique non negative int ID. For example. vertices() returns an IntSet of all the int IDs of the vertices of the graph. This allow for a more efficient graph implementations, rather then creating objects for vertices and edges. Vertices and edges may be created by addVertex() and addEdge(int, int), in which case the graph implementation will choose the int ID and will return it to the user. Alternativaly, the methods addVertex(int) and addEdge(int, int, int) can be used to add new vertices and edges with user chosen identifiers.

    Weights may be assigned to the graph vertices and/or edges. A weight is some value such as double primitive, boolean flag or an arbitrary Object. Multiple different weights can be added to the vertices and/or edges, each is identified by some key. When a new weights type is added to a graph, its added to all 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 an vertex/edge weight, and can be passed to algorithms as WeightFunction for example. See addVerticesWeights(Object, Class) and addEdgesWeights(Object, 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. See IndexGraph for more information. The IndexGraph should not be used in scenarios where performance does not matter.

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

     
 // Create a directed graph with three vertices and edges between them
 Graph g = Graph.newBuilderDirected().build();
 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
 Weights.Double w = g.addEdgesWeights("weightsKey", double.class);
 w.set(e1, 1.2);
 w.set(e2, 3.1);
 w.set(e3, 15.1);

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

 // Print the shortest path from v1 to v3
 assert ssspRes.distance(v3) == 4.3;
 assert ssspRes.getPath(v3).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)) {
 	int u = g.edgeSource(e), v = g.edgeTarget(e);
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
    Author:
    Barak Ugav
    See Also:
    Graph.Builder, GraphCapabilities, IndexGraph

    • Method Detail

      • vertices

        it.unimi.dsi.fastutil.ints.IntSet vertices()
        Get the set of all vertices of the graph.

        Each vertex in the graph is identified by a unique non negative integer ID 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 IDs of the graph vertices

      • edges

        it.unimi.dsi.fastutil.ints.IntSet edges()
        Get the set of all edges of the graph.

        Each edge in the graph is identified by a unique non negative integer ID, 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 IDs of the graph edges

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

        Returns:
        the new vertex identifier

      • addVertex

        void addVertex​(int vertex)
        Add a new vertex to the graph with user chosen ID.

        In contrast to addVertex(), in which the implementation chooses ,the new vertex identifier, the user can specified what int ID the new vertex should be assigned. 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.

        Note that vertices IDs must be non negative.

        Parameters:
        vertex - a user chosen identifier for the new vertex
        Throws:
        IllegalArgumentException - if the provided identifier is already used as identifier of one of the graph vertices, or if its negative

      • removeVertex

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

      • outEdges

        EdgeSet 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:
        IndexOutOfBoundsException - if source is not a valid vertex identifier

      • inEdges

        EdgeSet 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:
        IndexOutOfBoundsException - if target is not a valid vertex identifier

      • getEdge

        default 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:
        IndexOutOfBoundsException - if source or target are not valid vertices identifiers

      • getEdges

        EdgeSet 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:
        IndexOutOfBoundsException - if source or target are not valid vertices identifiers

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

        Parameters:
        source - a source vertex
        target - a target vertex
        Returns:
        the new edge identifier
        Throws:
        IndexOutOfBoundsException - if source or target are not valid vertices identifiers

      • addEdge

        void addEdge​(int source,
             int target,
             int edge)
        Add a new edge to the graph with user chosen ID.

        In contrast to addEdge(int, int), in which the implementation chooses the new edge identifier, the user can specified what int ID the new edge should be assigned. The set of graph edges must not contain duplications, therefore the provided identifier must not be currently used as one of the graph edges IDs.

        Parameters:
        source - a source vertex
        target - a target vertex
        edge - a user chosen identifier for the new edge
        Throws:
        IllegalArgumentException - if the provided identifier is already used as identifier of one of the graph edges, or if its negative

      • removeEdge

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

      • removeEdgesOf

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

      • removeOutEdgesOf

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

      • removeInEdgesOf

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

      • reverseEdge

        void reverseEdge​(int 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:
        IndexOutOfBoundsException - if edge is not a valid edge identifier

      • 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:
        IndexOutOfBoundsException - 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:
        IndexOutOfBoundsException - if edge is not a valid edge identifier

      • edgeEndpoint

        default 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:
        IndexOutOfBoundsException - 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

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

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        V - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        key - some key of the weights, could be anything
        Returns:
        vertices weights of the key, or null if no container found with the specified key

      • addVerticesWeights

        default <V,​WeightsT extends Weights<V>> WeightsT addVerticesWeights​(Object key,
                                                                          Class<? super V> 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. 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). 

         
 Graph g = ...;
 int v1 = g.newVertex();
 int v2 = g.newVertex();

 Weights<String> names = g.addVerticesWeights("name", String.class);
 names.set(v1, "Alice");
 names.set(v2, "Bob");

 Weights.Int ages = g.addVerticesWeights("age", int.class);
 ages.set(v1, 42);
 ages.set(v2, 35);

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        V - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        key - some key of the weights, could be anything
        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

        <V,​WeightsT extends Weights<V>> WeightsT addVerticesWeights​(Object key,
                                                                  Class<? super V> type,
                                                                  V 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 g = ...;
 int v1 = g.newVertex();
 int v2 = g.newVertex();
 int v3 = g.newVertex();

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

 assert "Alice".equals(names.get(v1))
 assert "Bob".equals(names.get(v2))
 assert "Unknown".equals(names.get(v3))

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        V - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        key - some key of the weights, could be anything
        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​(Object 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<Object> 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

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

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        E - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        key - some key of the weights, could be anything
        Returns:
        edges weights of the key, or null if no container found with the specified key

      • addEdgesWeights

        default <E,​WeightsT extends Weights<E>> WeightsT addEdgesWeights​(Object key,
                                                                       Class<? super E> 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 g = ...;
 int v1 = g.addVertex();
 int v2 = g.addVertex();
 int v3 = g.addVertex();
 int e1 = g.addEdge(v1, v2);
 int e2 = g.addEdge(v2, v3);

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

 Weights.Double roadLengths = g.addEdgesWeights("roadLength", double.class);
 roadLengths.set(e1, 42);
 roadLengths.set(e2, 35);

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        E - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        key - some key of the weights, could be anything
        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

        <E,​WeightsT extends Weights<E>> WeightsT addEdgesWeights​(Object key,
                                                               Class<? super E> type,
                                                               E 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 g = ...;
 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);

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

 assert "Asphalt".equals(names.get(e1))
 assert "Gravel".equals(names.get(e2))
 assert "Unknown".equals(names.get(e3))

        See Weights for a complete documentation of the weights containers.

        Type Parameters:
        E - The weight data type
        WeightsT - the weights container, used to avoid casts of containers of primitive types
        Parameters:
        key - some key of the weights, could be anything
        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​(Object 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<Object> 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

      • 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 and visa versa.

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

        Returns:
        an IndexGraph view of this graph

      • indexGraphVerticesMap

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

        Graph copy()
        Create a copy of this graph.

        An identical copy of this graph will be created, with the same vertices, edges, weights and capabilities.

        Returns:
        an identical copy of this graph

      • unmodifiableView

        default Graph unmodifiableView()
        Get an unmodifiable 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 unmodifiable, namely all operations that modify the graph will throw UnsupportedOperationException.

        Returns:
        an unmodifiable view of this graph

      • reverseView

        default Graph 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 visa 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

      • newBuilderUndirected

        static Graph.Builder newBuilderUndirected()
        Create an undirected graph builder.

        This is the recommended way to instantiate a new undirected graph.

        Returns:
        a new builder that can build undirected graphs

      • newBuilderDirected

        static Graph.Builder newBuilderDirected()
        Create a directed graph builder.

        This is the recommended way to instantiate a new directed graph.

        Returns:
        a new builder that can build directed graphs