Package com.jgalgo.alg.common

Interface IPath

    • Method Detail

      • 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

      • 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