Package com.jgalgo.alg.common

Interface IPath

All Superinterfaces:
Path<Integer,Integer>
public interface IPath extends Path<Integer,Integer>
A path of edges in an int graph.

This interface is a specification of Path for IntGraph. For the full documentation see Path.

Author:
Barak Ugav

  • Method Summary

    Modifier and Type
    Method
    Description
    IEdgeIter
    edgeIter()
    Get an EdgeIter that iterate over the edges of the path.
    IntList
    edges()
    Get the edges forming this path.
    static IPath
    findPath(IntGraph g, int source, int target)
    Find a valid path from \(u\) to \(v\).
    IntGraph
    graph()
    Get the graph this path is defined on.
    default boolean
    isCycle()
    Check whether this path form a cycle.
    static boolean
    isPath(IntGraph g, int source, int target, IntList edges)
    Check whether the given edge list is a valid path in the given graph.
    static IntSet
    reachableVertices(IntGraph g, int source)
    Find all the vertices reachable from a given source vertex.
    static IntSet
    reachableVertices(IntGraph g, IntIterator sources)
    Find all the vertices reachable from a set of given source vertices.
    default Integer
    source()
    Deprecated.
    Please use sourceInt() instead to avoid un/boxing.
    int
    sourceInt()
    Get the source vertex of the path.
    IPath
    subPath(int fromEdgeIndex, int toEdgeIndex)
    Create a sub path of this path that contains the edges between the specified fromEdgeIndex, inclusive, and toEdgeIndex, exclusive.
    default Integer
    target()
    Deprecated.
    Please use targetInt() instead to avoid un/boxing.
    int
    targetInt()
    Get the target vertex of the path.
    static IPath
    valueOf(IntGraph g, int source, int target, IntList edges)
    Create a new path from an edge list, a source and a target vertices.
    IntList
    vertices()
    Get the vertices forming this path.
    static IntIterator
    verticesIter(IntGraph g, int source, IntList edges)
    Create an iterator that iterate over the vertices visited by an edge path.

    Methods inherited from interface com.jgalgo.alg.common.Path

    equals, isSimple

  • Method Details

    • sourceInt

      int sourceInt()
      Get the source vertex of the path.

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

      Returns:
      the source vertex of the path.

    • source

      @Deprecated default Integer source()
      Deprecated.
      Please use sourceInt() instead to avoid un/boxing.
      Get the source vertex of the path.

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

      Specified by:
      source in interface Path<Integer,Integer>
      Returns:
      the source vertex of the path.

    • targetInt

      int targetInt()
      Get the target vertex of the path.

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

      Returns:
      the target vertex of the path.

    • target

      @Deprecated default Integer target()
      Deprecated.
      Please use targetInt() instead to avoid un/boxing.
      Get the target vertex of the path.

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

      Specified by:
      target in interface Path<Integer,Integer>
      Returns:
      the target vertex of the path.

    • isCycle

      default boolean isCycle()
      Description copied from interface: Path
      Check whether this path form a cycle.

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

      Specified by:
      isCycle in interface Path<Integer,Integer>
      Returns:
      true if this path form a cycle, else false

    • edgeIter

      IEdgeIter edgeIter()
      Description copied from interface: Path
      Get an EdgeIter that iterate over the edges of the path.
      Specified by:
      edgeIter in interface Path<Integer,Integer>
      Returns:
      an EdgeIter that iterate over the edges of the path.

    • edges

      IntList edges()
      Description copied from interface: Path
      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}\).

      Specified by:
      edges in interface Path<Integer,Integer>
      Returns:
      the edges forming this path, by the path order

    • vertices

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

      Specified by:
      vertices in interface Path<Integer,Integer>
      Returns:
      the vertices visited by this path, by the path order

    • graph

      IntGraph graph()
      Description copied from interface: Path
      Get the graph this path is defined on.
      Specified by:
      graph in interface Path<Integer,Integer>
      Returns:
      the graph this path is defined on.

    • subPath

      IPath subPath(int fromEdgeIndex, int toEdgeIndex)
      Description copied from interface: Path
      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);
      Specified by:
      subPath in interface Path<Integer,Integer>
      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

    • valueOf

      static IPath valueOf(IntGraph g, int source, int target, IntList 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(IntGraph, int, int, IntList).

      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

    • isPath

      static boolean isPath(IntGraph g, int source, int target, IntList 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.

      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

    • findPath

      static IPath findPath(IntGraph g, int source, int 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.

      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 IntSet reachableVertices(IntGraph g, int source)
      Find all the vertices reachable from a given source vertex.
      Parameters:
      g - a graph
      source - a source vertex
      Returns:
      a set of all the vertices reachable from the given source vertex

    • verticesIter

      static IntIterator verticesIter(IntGraph g, int source, IntList 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.

      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

    • reachableVertices

      static IntSet reachableVertices(IntGraph g, IntIterator sources)
      Find all the vertices reachable from a set of given source vertices.
      Parameters:
      g - a graph
      sources - a set of source vertices
      Returns:
      a set of all the vertices reachable from the given source vertices