Package com.jgalgo

Interface Path

  • All Superinterfaces:
    Collection<Integer>, Comparable<List<? extends Integer>>, IntCollection, IntIterable, IntList, Iterable<Integer>, List<Integer>
    public interface Path
extends IntList
    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.

    The Path object can be treated as a IntList of edges.

    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 g = ...;
 int sourceVertex = ...;
 int targetVertex = ...;
 Path p = Path.findPath(g, sourceVertex, targetVertex);

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

    • Method Detail

      • source

        int 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

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

      • edgeIter

        EdgeIter edgeIter()
        Get an EdgeIter that iterate over the edges of the path.
        Returns:
        an EdgeIter that iterate over the edges 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

      • toVerticesList

        default IntList toVerticesList()
        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 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. If this path form a cycle, the vertices list size is the same as the edge list, otherwise it is greater by one.

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

      • weight

        default double weight​(WeightFunction w)
        Get the weight of the path with respect to some weight function.

        The weight of a path is defined as the sum of its edges weights.

        Parameters:
        w - an edge weight function
        Returns:
        the sum of this path edges weights

      • findPath

        static Path findPath​(Graph 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