Package edu.kit.ipd.sdq.attacksurface.graph.patch

Class AllDirectedPaths<V,E>

java.lang.Object
edu.kit.ipd.sdq.attacksurface.graph.patch.AllDirectedPaths<V,E>
Type Parameters:
V - the graph vertex type
E - the graph edge type
public class AllDirectedPaths<V,E> extends 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.

  • Constructor Summary

    Constructors
    Constructor
    Description
    AllDirectedPaths(org.jgrapht.Graph<V,E> graph)
    Create a new instance.
    AllDirectedPaths(org.jgrapht.Graph<V,E> graph, org.jgrapht.alg.shortestpath.PathValidator<V,E> pathValidator)
    Create a new instance with given pathValidator.

  • Method Summary

    Modifier and Type
    Method
    Description
    List<org.jgrapht.GraphPath<V,E>>
    getAllPaths(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, Integer maxPathLength)
    Calculate (and return) all paths from the source vertices to the target vertices.
    List<org.jgrapht.GraphPath<V,E>>
    getAllPaths(V sourceVertex, V targetVertex, boolean simplePathsOnly, Integer maxPathLength)
    Calculate (and return) all paths from the source vertex to the target vertex.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • AllDirectedPaths

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

    • AllDirectedPaths

      public AllDirectedPaths(org.jgrapht.Graph<V,E> graph, org.jgrapht.alg.shortestpath.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:
      IllegalArgumentException - if the graph is not directed

  • Method Details

    • getAllPaths

      public List<org.jgrapht.GraphPath<V,E>> getAllPaths(V sourceVertex, V targetVertex, boolean simplePathsOnly, 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 List<org.jgrapht.GraphPath<V,E>> getAllPaths(Set<V> sourceVertices, Set<V> targetVertices, boolean simplePathsOnly, 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