For the circuit simulator I currently work on, I needed an algorithm for finding all paths between two given nodes in a graph. One problem was, that the graph can have loops and its edges are bidirectional, so the algorithm should be able to detect loops. I spent some time searching on google for adequate algorithms but I didn’t find some, so I had to develop it on my own:

public Set<Path<V>> apply(Graph<V> graph, Parameters<V>... parameters) { assert parameters.length == 1; Parameters<V> params = parameters[0]; Set<Path<V>> currentPaths = new HashSet<>(); currentPaths.add(new Path<>(Collections.singletonList(params.getStart()))); Set<Path<V>> nextPaths = new HashSet<>(); Set<Path<V>> pathsFound = new HashSet<>(); while(currentPaths.size() > 0){ for (Path<V> path : currentPaths){ Node<V> node = path.getEndNode(); if (node.equals(params.getEnd())){ pathsFound.add(path); continue; } for (Edge<V> edge : graph.getEdges(node)){ Node<V> nextNode; try { nextNode = edge.getTarget(node); nextPaths.add(path.attachNode(nextNode)); } catch (EdgeException | CircularPathException e) { } } } currentPaths = nextPaths; nextPaths = new HashSet<>(); } return pathsFound; }

# How it works

- Create an empty set of currently tracked paths
- Add the starting node to the set of currently tracked paths
- Create an empty set of paths to be tracked in the next iteration
- Create an empty set of found paths
- While set of currently tracked paths is not empty do following steps:
- For each path in the set of currently tracked paths do following steps:
- Get the last node of the path
- If the last node is the end node, add the current path to the set of found paths and continue with the next path
- Get all edges the last node of the path is connected to
- For every edge the last node of the path is connected to do following steps:
- Get the node of the edge the last node of the path is connected to
- If the retrieved node is not yet in the path:
- Copy the current path
- Add the retrieved node to the new path
- Add the new path to the list of paths to be tracked in the next iteration

- Assign the set of paths to be tracked in the next iteration to the set of currently tracked paths
- Create a new set of paths to be tracked in the next iteration

- For each path in the set of currently tracked paths do following steps:
- Return the set of found paths

Advertisements