Class AllDirectedPaths<V,​E>

  • Type Parameters:
    V - the graph vertex type
    E - the graph edge type

    public class AllDirectedPaths<V,​E>
    extends java.lang.Object
    A Dijkstra-like algorithm to find all paths between two sets of nodes in a directed graph, with options to search only simple paths and to limit the path length.
    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private java.util.Map<E,​java.lang.Integer> edgeMinDistancesBackwards​(java.util.Set<V> targetVertices, java.lang.Integer maxPathLength)
      Compute the minimum number of edges in a path to the targets through each edge, so long as it is not greater than a bound.
      private java.util.List<GraphPath<V,​E>> generatePaths​(java.util.Set<V> sourceVertices, java.util.Set<V> targetVertices, boolean simplePathsOnly, java.lang.Integer maxPathLength, java.util.Map<E,​java.lang.Integer> edgeMinDistancesFromTargets)
      Generate all paths from the sources to the targets, using pre-computed minimum distances.
      java.util.List<GraphPath<V,​E>> getAllPaths​(java.util.Set<V> sourceVertices, java.util.Set<V> targetVertices, boolean simplePathsOnly, java.lang.Integer maxPathLength)
      Calculate (and return) all paths from the source vertices to the target vertices.
      java.util.List<GraphPath<V,​E>> getAllPaths​(V sourceVertex, V targetVertex, boolean simplePathsOnly, java.lang.Integer maxPathLength)
      Calculate (and return) all paths from the source vertex to the target vertex.
      private GraphPath<V,​E> makePath​(java.util.List<E> edges)
      Transform an ordered list of edges into a GraphPath.
      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Field Detail

      • graph

        private final Graph<V,​E> graph
      • pathValidator

        private final PathValidator<V,​E> pathValidator
        Provides validation for the paths which will be computed. If the validator is null, this means that all paths are valid.
    • Constructor Detail

      • AllDirectedPaths

        public AllDirectedPaths​(Graph<V,​E> graph)
        Create a new instance.
        Parameters:
        graph - the input graph
        Throws:
        java.lang.IllegalArgumentException - if the graph is not directed
      • AllDirectedPaths

        public AllDirectedPaths​(Graph<V,​E> graph,
                                PathValidator<V,​E> pathValidator)
        Create a new instance with given pathValidator. If non-null, the pathValidator will be used while searching for paths, validating the addition of any edge to a partial path. Zero-length paths will therefore not be subject to pathValidator; length-1 paths will.
        Parameters:
        graph - the input graph
        pathValidator - validator for computed paths; may be null
        Throws:
        java.lang.IllegalArgumentException - if the graph is not directed
    • Method Detail

      • getAllPaths

        public java.util.List<GraphPath<V,​E>> getAllPaths​(V sourceVertex,
                                                                V targetVertex,
                                                                boolean simplePathsOnly,
                                                                java.lang.Integer maxPathLength)
        Calculate (and return) all paths from the source vertex to the target vertex.
        Parameters:
        sourceVertex - the source vertex
        targetVertex - the target vertex
        simplePathsOnly - if true, only search simple (non-self-intersecting) paths
        maxPathLength - maximum number of edges to allow in a path (if null, all paths are considered, which may be very slow due to potentially huge output)
        Returns:
        all paths from the source vertex to the target vertex
      • getAllPaths

        public java.util.List<GraphPath<V,​E>> getAllPaths​(java.util.Set<V> sourceVertices,
                                                                java.util.Set<V> targetVertices,
                                                                boolean simplePathsOnly,
                                                                java.lang.Integer maxPathLength)
        Calculate (and return) all paths from the source vertices to the target vertices.
        Parameters:
        sourceVertices - the source vertices
        targetVertices - the target vertices
        simplePathsOnly - if true, only search simple (non-self-intersecting) paths
        maxPathLength - maximum number of edges to allow in a path (if null, all paths are considered, which may be very slow due to potentially huge output)
        Returns:
        list of all paths from the sources to the targets containing no more than maxPathLength edges
      • edgeMinDistancesBackwards

        private java.util.Map<E,​java.lang.Integer> edgeMinDistancesBackwards​(java.util.Set<V> targetVertices,
                                                                                   java.lang.Integer maxPathLength)
        Compute the minimum number of edges in a path to the targets through each edge, so long as it is not greater than a bound.
        Parameters:
        targetVertices - the target vertices
        maxPathLength - maximum number of edges to allow in a path (if null, all edges will be considered, which may be expensive)
        Returns:
        the minimum number of edges in a path from each edge to the targets, encoded in a Map
      • generatePaths

        private java.util.List<GraphPath<V,​E>> generatePaths​(java.util.Set<V> sourceVertices,
                                                                   java.util.Set<V> targetVertices,
                                                                   boolean simplePathsOnly,
                                                                   java.lang.Integer maxPathLength,
                                                                   java.util.Map<E,​java.lang.Integer> edgeMinDistancesFromTargets)
        Generate all paths from the sources to the targets, using pre-computed minimum distances.
        Parameters:
        sourceVertices - the source vertices
        targetVertices - the target vertices
        maxPathLength - maximum number of edges to allow in a path
        simplePathsOnly - if true, only search simple (non-self-intersecting) paths (if null, all edges will be considered, which may be expensive)
        edgeMinDistancesFromTargets - the minimum number of edges in a path to a target through each edge, as computed by edgeMinDistancesBackwards.
        Returns:
        a List of all GraphPaths from the sources to the targets satisfying the given constraints
      • makePath

        private GraphPath<V,​E> makePath​(java.util.List<E> edges)
        Transform an ordered list of edges into a GraphPath. The weight of the generated GraphPath is set to the sum of the weights of the edges.
        Parameters:
        edges - the edges
        Returns:
        the corresponding GraphPath