The GraphWalker-Algorithm

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

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