find all non-repeating paths through a set of connected nodes/process diagram

I am trying to understand if its possible in any reasonable way to establish a set of non-repeating paths through a given process diagram.

here are some basic facts about the process diagrams i开发者_JAVA百科 have:

• they have one or more start points
• they have one or more end points
• all start points have one connector leading from them
• all steps have at least one or more inbound connectors and one or more outbound connectors
• if there is more than one of the following each must be named:
  • Start terminators
  • End Terminators
  • Connections leading from a step

I have access to all of the data I can imagine being required (finding all start points, getting all connections, names of connections etc).

I basically want to find as many unique paths through the process from start point to end point where you don't go round in a circle repeatedly. so you can go through the same step several times but you cannot repeat a complete circuit more than once in any given route through.

This seems like the type of thing people would have written papers about and have proofs for why it can or cannot be done, I just dont know the magic words I need to google that ;-) Sudo code or similar would be ideal (and amazing) but I am happy to do my own reading if someone can point me in the right direction.

ANY SEARCH TERMS SUGGESTIONS VERY WELCOME AND GREATLY APPRECIATED

Note I would be interested solutions that suggest lots of extra "silly" possibilities that have to be reviewed by a human afterwards - it would still be interesting to see what it generated.

An bit of an example to clarify things:

        G<--2-E<--1-F-2--|
        |     |     ^    |
        |     1     |    |
        |     |     2    |
        \/   \/     |   \/
start--->A--->B---->C-1->D---end

some routes through:

• start,A,B,C:1,D,end
• start,A,B,C:2,F:1,E:1,B,C:1,D,end
• start,A,B,C:2,F:1,E:2,G,A,B,C:1,D,end
• start,A,B,C:2,F:2,D,end

nice but what about a more interesting one:

• start,A,B,C:2,F:1,E:2,G,A,B,C:2,F:1,B,C:2,F:2,D,end

I hit C three times and each time I choose option two and there is no repeating.

Extra points: I was thinking that I can mark some of the nodes with multiple outbound connectors as being consistent within any given execution of a process.. e.g. if there is a "write code" process that has a decision point "language" with two outbound connectors "c#" and "java" I could say that within any given execution of this process it will always be either c# or java - that will never change during the execution of the process. as opposed to something that may change like "are there bugs?" which on first pass through might have a yes, then on the second pass through (after some fix bugs steps ;-) might have the outcome no.

Do you know any terms or techniques relating to this type of extra analysis / processing / definition?

EDIT: I added a example solution implemented in JS as an ansewer based on @Ishtar's answer.

How about a depth first search? This would walk through all the possible paths. The only difficult part is ignoring paths that would lead to the same cycle again. If you're at a node, you check if you been there before (a cycle), and make sure the same sequence isn't in the path already.

For example

start,A,B,C:2,F:1,E:1,B,C:2,F:1,E:1,B

From here, we can only go to C. Looking back(the last 4 nodes), we find the cycle C:2,F:1,E:1,B. The cycle exists already, so we can't go to node c. Since we can't go anywhere else, this branch doesn't give a correct path.

Pseudocode:

allpaths(path,node)
  cycle = path.substring(path.lastIndex(node)) + node
  if path.contains(cycle)
    return
  path = path + node
  if node.isEndNode
    print path
    return
  for child in node.children
    allpaths(path, child)

is this relevant? finding all the elementary circuits of a directed graph. even if it's not the algorithm you use, it may help with appropriate definitions and names.

a complete example in a web page of @Ishtars solution, the graph is the one from the question... It seems to work, not extensively tested it. Its a far simpler solution than I was expecting ;-)

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
<head>
    <title></title>
    <script type="text/javascript">

        function connection(name, endPoint) {
            this.name = name;
            this.endPoint = endPoint;
        }

        function node(name) {
            this.name = name;
            this.connections = [];

            this.addConnection = function (conn) {
                this.connections[this.connections.length] = conn;
            }
        }


        function printPath(path) {
            document.getElementById('output').innerHTML = 
              document.getElementById('output').innerHTML
              + path + '<br />';
        }

        function allPaths(path, node) {
            if (node.name == "end") {
                printPath(path + ',' + node.name);
                return;
            }
            cycle = path.substring(path.lastIndexOf(node.name)) + ',' + node.name;
            if (cycle.length > 1 && path.indexOf(cycle) > 0) {
                return;
            }
            for (var i = 0; i < node.connections.length; i++) {
               allPaths(path + ',' + node.name + ":" + 
                   node.connections[i].name
                   ,node.connections[i].endPoint);
            }
       }

        var start = new node("start");
        var a = new node("A");
        var b = new node("B");
        var c = new node("C");
        var d = new node("D");
        var e = new node("E");
        var f = new node("F");
        var g = new node("G");
        var end = new node("end");

        start.addConnection(new connection("1", a));
        a.addConnection(new connection("1", b));
        b.addConnection(new connection("1", c));
        c.addConnection(new connection("1", d));
        c.addConnection(new connection("2", f));
        d.addConnection(new connection("1", end));
        f.addConnection(new connection("1", e));
        f.addConnection(new connection("2", d));
        e.addConnection(new connection("1", b));
        e.addConnection(new connection("2", g));
        g.addConnection(new connection("1", a));

    </script>
</head>
<body onload="javascript:allPaths('start', a)";>
    <div id="output"></div>
</body>
</html>

and here is the output (just in case anyone can spot a mistake ;-):

start,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:1,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:1,E:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:1,E:2,G:1,A:1,B:1,C:2,F:2,D:1,end
start,A:1,B:1,C:2,F:2,D:1,end

Guess I didn't know about jsFiddle when I wrote this, here is a fiddle with the above code in it:

http://jsfiddle.net/6bWMp/1/