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

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