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

Author: 1337codersblog

I’m a passioned programmer and electronics tinkerer, who likes the challenge of realising complex programs. I learned programming in the age of 13 and in my free time I like to code and develop own circuits.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s