001package org.dllearner.utilities.graph; 002 003import java.util.*; 004 005import org.jgrapht.Graph; 006import org.jgrapht.GraphPath; 007import org.jgrapht.graph.GraphWalk; 008 009/** 010 * An algorithm to find all paths between two sets of nodes in a directed graph, with 011 * options to search only simple paths and to limit the path length. 012 * 013 * @param <V> the graph vertex type 014 * @param <E> the graph edge type 015 */ 016public class AllPaths<V, E> { 017 private final Graph<V, E> graph; 018 019 public AllPaths(Graph<V, E> graph) { 020 this.graph = graph; 021 } 022 023 private List<GraphPath<V, E>> generatePaths( 024 Set<V> sourceVertices, boolean simplePathsOnly, 025 Integer maxPathLength) { 026 /* 027 * We walk forwards through the network from the source vertices, exploring all outgoing 028 * edges whose minimum distances is small enough. 029 */ 030 List<GraphPath<V, E>> completePaths = new ArrayList<>(); 031 Deque<List<E>> incompletePaths = new LinkedList<>(); 032 033 // Input sanity checking 034 if (maxPathLength != null && maxPathLength < 0) { 035 throw new IllegalArgumentException("maxPathLength must be non-negative if defined"); 036 } 037 038 // Bootstrap the search with the source vertices 039 for (V source : sourceVertices) { 040 completePaths.add(GraphWalk.singletonWalk(graph, source, 0d)); 041 042 if (maxPathLength != null && maxPathLength == 0) { 043 continue; 044 } 045 046 for (E edge : graph.outgoingEdgesOf(source)) { 047 assert graph.getEdgeSource(edge).equals(source); 048 049 completePaths.add(makePath(Collections.singletonList(edge))); 050 051 if ((maxPathLength == null || maxPathLength > 1)) { 052 List<E> path = Collections.singletonList(edge); 053 incompletePaths.add(path); 054 } 055 } 056 } 057 058 if (maxPathLength != null && maxPathLength == 0) { 059 return completePaths; 060 } 061 062 // Walk through the queue of incomplete paths 063 for (List<E> incompletePath; (incompletePath = incompletePaths.poll()) != null; ) { 064 Integer lengthSoFar = incompletePath.size(); 065 assert (maxPathLength == null) || (lengthSoFar < maxPathLength); 066 067 E leafEdge = incompletePath.get(lengthSoFar - 1); 068 V leafNode = graph.getEdgeTarget(leafEdge); 069 070 Set<V> pathVertices = new HashSet<>(); 071 for (E pathEdge : incompletePath) { 072 pathVertices.add(graph.getEdgeSource(pathEdge)); 073 pathVertices.add(graph.getEdgeTarget(pathEdge)); 074 } 075 076 for (E outEdge : graph.outgoingEdgesOf(leafNode)) { 077 // Proceed if the outgoing edge is marked and the mark 078 // is sufficiently small 079 if (maxPathLength == null || lengthSoFar <= maxPathLength) { 080 List<E> newPath = new ArrayList<>(incompletePath); 081 newPath.add(outEdge); 082 083 // If requested, make sure this path isn't self-intersecting 084 if (simplePathsOnly && pathVertices.contains(graph.getEdgeTarget(outEdge))) { 085 continue; 086 } 087 088 GraphPath<V, E> completePath = makePath(newPath); 089 assert sourceVertices.contains(completePath.getStartVertex()); 090 assert (maxPathLength == null) || (completePath.getLength() <= maxPathLength); 091 completePaths.add(completePath); 092 093 // If this path is short enough, consider further extensions of it 094 if ((maxPathLength == null) || (newPath.size() < maxPathLength)) { 095 incompletePaths.addFirst(newPath); 096 } 097 } 098 } 099 } 100 101 assert incompletePaths.isEmpty(); 102 return completePaths; 103 } 104 105 /** 106 * Transform an ordered list of edges into a GraphPath. 107 * <p> 108 * The weight of the generated GraphPath is set to the sum of the weights of the edges. 109 * 110 * @param edges the edges 111 * @return the corresponding GraphPath 112 */ 113 private GraphPath<V, E> makePath(List<E> edges) { 114 V source = graph.getEdgeSource(edges.get(0)); 115 V target = graph.getEdgeTarget(edges.get(edges.size() - 1)); 116 double weight = edges.stream().mapToDouble(graph::getEdgeWeight).sum(); 117 return new GraphWalk<>(graph, source, target, edges, weight); 118 } 119 120 public List<GraphPath<V, E>> getAllPaths(V sourceVertex, boolean simplePathsOnly, Integer maxPathLength) { 121 return getAllPaths( 122 Collections.singleton(sourceVertex), 123 simplePathsOnly, maxPathLength); 124 } 125 126 public List<GraphPath<V, E>> getAllPaths( 127 Set<V> sourceVertices, boolean simplePathsOnly, 128 Integer maxPathLength) { 129 if ((maxPathLength != null) && (maxPathLength < 0)) { 130 throw new IllegalArgumentException("maxPathLength must be non-negative if defined"); 131 } 132 133 if (!simplePathsOnly && (maxPathLength == null)) { 134 throw new IllegalArgumentException( 135 "If search is not restricted to simple paths, a maximum path length must be set to avoid infinite cycles"); 136 } 137 138 if ((sourceVertices.isEmpty())) { 139 return Collections.emptyList(); 140 } 141 142 // Generate all the paths 143 return generatePaths( 144 sourceVertices, simplePathsOnly, maxPathLength); 145 } 146}