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
Advertisements