The PathStar-Algorithm

For the circuit simulator I need a way to find parallel paths in a graph. To prepare the actual parallel path detection I first need to split a given path into a set of subpaths wich start and end at nodes spawning multiple branches. After some thinking I found out following algorithm:

public Set<Path<V>> apply(Graph<V> graph, PathStar.Parameters<V>... parameters) {
    assert graph != null;
    assert parameters != null;
    assert parameters.length > 0;

    PathStar.Parameters<V> params = parameters[0];
    Set<Path<V>> paths = new HashSet<>();

    List<Node<V>> subPath = new LinkedList<>();
    Iterator<Node<V>> pathIterator = params.getPathToSplit().iterator();
    while (pathIterator.hasNext()){
        Node<V> node = pathIterator.next();
        subPath.add(node);
        Set<Edge<V>> edges = new HashSet<>(graph.getEdges(node));
        if (pathIterator.hasNext()){
            Iterator<Edge<V>> iterator = edges.iterator();
            while (iterator.hasNext()){
                Edge<V> edge = iterator.next();
                Node<V> previousNode = params.getPathToSplit().getPredecessor(node);
                try {
                    if (previousNode != null && edge.getTarget(node).equals(previousNode)){
                        iterator.remove();
                    }
                } catch (DestinationNotExistsException ignored){
                }
                catch (EdgeException e) {
                    throw new RuntimeException(e);
                }
            }
        }
        if (edges.size() > 1){
            if (subPath.size() > 1){
                paths.add(new Path<>(subPath));
            }
            if (!pathIterator.hasNext()){
                subPath = new LinkedList<>();
                break;
            }
            subPath = new LinkedList<>(Collections.singleton(node));
        }
    }
    if (subPath.size() > 0){
        subPath.add(params.getPathToSplit().iterator().next());
        paths.add(new Path<>(subPath));
    }

    return paths;
}

 

How it works

1. Init new list of nodes representing the current subpath
2. For every node of the given path do following steps:
   1. Add the node to the subpath
   2. If the currrent node is not the end node to the following steps:
      1. If the current node has multiple successors:
         1. Add current subpath to the list of found subpaths
         2. If the current node is the end node do the following steps:
            1. Create new empty subpath
            2. If the current subpaths has more than 1 node, add it to the list of found subpaths
            3. Return the list of found subpaths
         3. Create new subpath containing current node as its starting node
3. If the current subpaths has more than 1 node, add it to the list of found subpaths
4. Return the list of found subpaths

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