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}