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

    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 Details

    • 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