Package com.jgalgo.alg.common

Interface Path<V,​E>

  • Type Parameters:
    V - the vertices type
    E - the edges type
    All Known Subinterfaces:
    IPath
    public interface Path<V,​E>
    A path of edges in a graph.

    A path is a list of edges \(e_1,e_2,\ldots\) where each target vertex of edge \(e_i\) is the source vertex of the next edge \(e_{i+1}\). If the graph is undirected the definition of a 'source' and 'target' are interchangeable, and each pair of consecutive edges simply share an endpoint.

    A Path object might be used to represent a cycle as well, if the source and target of the path are the same vertex.

    If the underlying graph was modified after the Path object was created, the Path object should not be used. 

     
 Graph<String, Integer> g = ...;
 String sourceVertex = ...;
 String targetVertex = ...;
 Path<String, Integer> p = Path.findPath(g, sourceVertex, targetVertex);

 System.out.println("The path between u and v consist of the following edges:");
 for (EdgeIter<String, Integer> it = p.edgeIter(); it.hasNext();) {
 	Integer e = it.next();
 	String u = it.source(), v = it.target();
 	System.out.println(" " + e + "(" + u + ", " + v + ")");
 }
    Author:
    Barak Ugav

    • Method Summary

      All Methods Static Methods Instance Methods Abstract Methods Default Methods 
      Modifier and Type Method Description
      EdgeIter<V,​E> edgeIter()
      Get an EdgeIter that iterate over the edges of the path.
      List<E> edges()
      Get the edges forming this path.
      boolean equals​(Object o)
      Check whether this path equals another object.
      static <V,​E>
      Path<V,​E>      		 findPath​(Graph<V,​E> g, V source, V target)
      Find a valid path from \(u\) to \(v\).
      Graph<V,​E> graph()
      Get the graph this path is defined on.
      default boolean isCycle()
      Check whether this path form a cycle.
      static <V,​E>
      boolean      		 isPath​(Graph<V,​E> g, V source, V target, List<E> edges)
      Check whether the given edge list is a valid path in the given graph.
      boolean isSimple()
      Check whether this path is simple.
      static <V,​E>
      Path<V,​E>      		 pathFromIndexPath​(Graph<V,​E> g, IPath indexPath)
      Create a path view from a path in the index graph of the given graph.
      static <V,​E>
      Set<V>      		 reachableVertices​(Graph<V,​E> g, Iterator<V> sources)
      Find all the vertices reachable from a given set of source vertices.
      static <V,​E>
      Set<V>      		 reachableVertices​(Graph<V,​E> g, V source)
      Find all the vertices reachable from a given source vertex.
      V source()
      Get the source vertex of the path.
      Path<V,​E> subPath​(int fromEdgeIndex, int toEdgeIndex)
      Create a sub path of this path that contains the edges between the specified fromEdgeIndex, inclusive, and toEdgeIndex, exclusive.
      V target()
      Get the target vertex of the path.
      static <V,​E>
      Path<V,​E>      		 valueOf​(Graph<V,​E> g, V source, V target, List<E> edges)
      Create a new path from an edge list, a source and a target vertices.
      List<V> vertices()
      Get the vertices forming this path.
      static <V,​E>
      Iterator<V>      		 verticesIter​(Graph<V,​E> g, V source, List<E> edges)
      Create an iterator that iterate over the vertices visited by an edge path.

    • Method Detail

      • source

        V source()
        Get the source vertex of the path.

        If the returned vertex is the same as target(), the represented path is actually a cycle.

        Returns:
        the source vertex of the path.

      • target

        V target()
        Get the target vertex of the path.

        If the returned vertex is the same as source(), the represented path is actually a cycle.

        Returns:
        the target vertex of the path.

      • isCycle

        default boolean isCycle()
        Check whether this path form a cycle.

        A cycle is a path which start and ends at the same vertex.

        Returns:
        true if this path form a cycle, else false

      • isSimple

        boolean isSimple()
        Check whether this path is simple.

        A path is simple if the path does not visit the same vertex twice. Specifically, a cycle is not simple.

        Returns:
        true if this path is simple, else false

      • edgeIter

        EdgeIter<V,​E> edgeIter()
        Get an EdgeIter that iterate over the edges of the path.
        Returns:
        an EdgeIter that iterate over the edges of the path.

      • edges

        List<E> edges()
        Get the edges forming this path.

        The path is defined as a list of edges \(e_1,e_2,\ldots\), where each target vertex of an edge \(e_i\) is the source vertex of the next edge \(e_{i+1}\).

        Returns:
        the edges forming this path, by the path order

      • vertices

        List<V> vertices()
        Get the vertices forming this path.

        The path is defined as a list of edges \(e_1,e_2,\ldots\), where each target vertex of an edge \(e_i\) is the source vertex of the next edge \(e_{i+1}\). The list of vertices of this path is the vertices visited by this path, ordered by their visit order. The first vertex is the source of the path and the last vertex is the target of the path. The size of the returned list is always the size of the edges list plus one.

        Note that if this path is a cycle, the first and last vertices in the returned list are the same vertex.

        Returns:
        the vertices visited by this path, by the path order

      • graph

        Graph<V,​E> graph()
        Get the graph this path is defined on.
        Returns:
        the graph this path is defined on.

      • subPath

        Path<V,​E> subPath​(int fromEdgeIndex,
                        int toEdgeIndex)
        Create a sub path of this path that contains the edges between the specified fromEdgeIndex, inclusive, and toEdgeIndex, exclusive.

        This method is equivalent to the following code: 

        
 List<E> edges = edges().subList(fromEdgeIndex, toEdgeIndex);
 V source = vertices().get(fromEdgeIndex);
 V target = vertices().get(toEdgeIndex);
 return Path.valueOf(graph(), source, target, edges);
        Parameters:
        fromEdgeIndex - low endpoint (inclusive) of the edges subList
        toEdgeIndex - high endpoint (exclusive) of the edges subList
        Returns:
        a sub path of the specified edges range within this path edges list
        Throws:
        IndexOutOfBoundsException - if fromEdgeIndex < 0 or toEdgeIndex > edgesNum or fromEdgeIndex > toEdgeIndex

      • equals

        boolean equals​(Object o)
        Check whether this path equals another object.

        If the given object is not a path, this function returns false. For two paths to be equal, they must be defined in the same graph, which is compared using the naive == operator, and they must represent the same path in the graph. If one path is a cycle and the other is not, they are not equal. If both are not cycles, they must have the same source and target vertices, and the same edges in the same order. If both are cycles, they must have the same edges in the same order, but an offset between the lists of edges is allowed. For example, the two paths \(e_1,e_2,e_3\) and \(e_2,e_3,e_1\) are equal (if they form a cycle!). Note that the sources and targets vertices are not equal in the example. For undirected graphs, all the above rules holds with the option to reverse one of the list of edges.

        Overrides:
        equals in class Object
        Parameters:
        o - the object to compare to
        Returns:
        true if this path equals the given object, else false

      • valueOf

        static <V,​E> Path<V,​E> valueOf​(Graph<V,​E> g,
                                           V source,
                                           V target,
                                           List<E> edges)
        Create a new path from an edge list, a source and a target vertices.

        The edges list passed to this function is used for the whole lifetime of the returned path. The list should not be modified after passed to this method, as it is not cloned.

        Note that this function does not check whether the given edge list is a valid path in the given graph. To check for validity, use isPath(Graph, Object, Object, List).

        If an IntGraph is passed as argument, the returned path will be an IPath object.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - the graph
        source - a source vertex
        target - a target vertex
        edges - a list of edges that form a path from the source to the target vertices in the
        Returns:
        a new path

      • pathFromIndexPath

        static <V,​E> Path<V,​E> pathFromIndexPath​(Graph<V,​E> g,
                                                     IPath indexPath)
        Create a path view from a path in the index graph of the given graph.
        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - the graph, must not be an index graph
        indexPath - the path in the index graph of the given graph
        Returns:
        a path view

      • isPath

        static <V,​E> boolean isPath​(Graph<V,​E> g,
                                  V source,
                                  V target,
                                  List<E> edges)
        Check whether the given edge list is a valid path in the given graph.

        A list of edges is a valid path in the graph if it is a list of edges \(e_1,e_2,\ldots\) where each target vertex of an edge \(e_i\) is the source vertex of the next edge \(e_{i+1}\). If the graph is undirected the definition of a 'source' and 'target' are interchangeable, and each pair of consecutive edges simply share an endpoint. In addition, the edge list must start with the source vertex and end with the target vertex.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        source - a source vertex
        target - a target vertex
        edges - a list of edges that form a path from the source to the target vertices in the graph.
        Returns:
        true if the given edge list is a valid path in the given graph, else false

      • verticesIter

        static <V,​E> Iterator<V> verticesIter​(Graph<V,​E> g,
                                            V source,
                                            List<E> edges)
        Create an iterator that iterate over the vertices visited by an edge path.

        The returned iterator will be identical to the iterator of vertices()}.

        This method assume the list of edges is a valid path in the graph starting from the given source vertex, no validation is performed to check that.

        If the passed graph is an instance of IntGraph, the returned iterator will be an instance of IntIterator.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        source - the source vertex of the path
        edges - a list of edges that from a path starting from source
        Returns:
        an iterator that iterate over the vertices visited by the path

      • findPath

        static <V,​E> Path<V,​E> findPath​(Graph<V,​E> g,
                                            V source,
                                            V target)
        Find a valid path from \(u\) to \(v\).

        This function uses BFS, which will result in the shortest path in the number of edges.

        If an IntGraph is passed as argument, the returned path will be an IPath object.

        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        source - source vertex
        target - target vertex
        Returns:
        a path from \(u\) to \(v\), or null if no such path was found

      • reachableVertices

        static <V,​E> Set<V> reachableVertices​(Graph<V,​E> g,
                                            V source)
        Find all the vertices reachable from a given source vertex.
        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        source - a source vertex
        Returns:
        a set of all the vertices reachable from the given source vertex

      • reachableVertices

        static <V,​E> Set<V> reachableVertices​(Graph<V,​E> g,
                                            Iterator<V> sources)
        Find all the vertices reachable from a given set of source vertices.
        Type Parameters:
        V - the vertices type
        E - the edges type
        Parameters:
        g - a graph
        sources - an iterator over a set of source vertices
        Returns:
        a set of all the vertices reachable from the given source vertices