I need to find all paths from a given graph. I can do that for now, however my recursive code is not efficient and my graphs are very complicated, hence I need a better algorithm.

def findLeaves(gdict):
    # takes graph and find its leaf nodes
    leaves = []
    for endNode in gdict.iterkeys():
        if not gdict[endNode]:
            leaves.append(endNode)
    return leaves

graphPaths = {}

def findPaths(gname, gdict, leave, path):
    # finds all noncycle paths
    if not gdict:
        return []
    temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path] 
    if temp:
        for node in temp:
            findPaths(gname, gdict, node, [node] + path) 
    else:
        graphPaths[gname].append(path)   


graph = {}
graph['graph'] = {0: {1: {}}, 1: {2: {}, 3: {}}, 2: {3: {}}, 3: {4: {}}, 4: {5: {}}, 5: {6: {}}, 6: {7: {}}, 7: {6: {}, 5: {}, 8: {}}, 8: {}}
graph['name'] = 'nameofthegraph'


# main
leaves = findLeaves(graph['graph'])
graphPaths['nameofthegraph'] = []

seenNodes = []
for leave in leaves:
    findPaths(graph['name'], graph['graph'], leave, [leave])

for path in graphPaths.values()[0]:
    print path

There is only one starting node, which makes things easier for recursive function. Every leaf needs to arrive there if a leaf is followed in reverse order. The starting node is the one which does not have an incoming edge.

These structures are taken from pygraphviz, which simply shows the outgoing edges from any nodes. Keys are the nodes and values are outgoing edges to the nodes. However, when I have very complicated graphs as below, this code could not find all paths.

complex graph example

Is there any better algorithm that you can suggest? Or is there any way to optimize my algorithm for complicated graphs?

  • Welcome to CodeReview! Can you please tell us more about how we are suppose to run your code ? Trying to put your functions and you data in a script to run it, I first get different errors. – Josay Jul 1 '14 at 7:53
  • thanks @Josay . I editted the question, just copy the last code, it will run. Sorry about late reply. – genclik27 Jul 1 '14 at 9:51
  • You say you want to compute "all paths" but in general there are exponentially many paths in a graph. What are you really trying to achieve? – Gareth Rees Jul 1 '14 at 17:17
  • Yes I know, there are exponentially many paths. I just need to find all possible paths somehow to see every behavior of system. If that's not possible, finding a sample of paths that will cover all edges may be alternative. @GarethRees – genclik27 Jul 1 '14 at 20:02
  • Can you say more about your problem? What does your graph represent and what are you trying to do with it? – Gareth Rees Jul 1 '14 at 20:15
up vote 14 down vote accepted

1. Introduction

Your goal (if I understand correctly, of generating all the execution paths in a state transition graph for a Java thread and then using those execution paths to test the code) seems unrealistic to me.

Even in an acyclic graph (or with the condition that you must not revisit a state) there may be exponentially many paths. In a graph with cycles (like any realistic state transition graph) there are infinitely many paths.

You cannot afford the time to generate all these path, let alone the time to run the test cases based on the paths: the best you can hope for is to intelligently (or randomly) sample the space of paths.

2. Detailed review

  1. There are no docstrings. What do your functions do, what data structures do they act on, and how do I call them?

  2. The singular of leaves is leaf in English (not leave).

  3. Your program has code at the top level of the module. This makes it inconvenient to test the code from the interactive interpreter: each time you reload the module, the program runs. It would be better to put the top-level code into a function and call this function inside the guard if __name__ == '__main__':.

  4. Your program relies on a global variable graphPaths. This makes it inconvenient to test the program repeatedly, as you have to ensure that this variable is reinitialized each time you want to run the test case. Instead of passing gname and appending to graphPaths[gname] inside findPaths, it would be better to pass the list as an argument to findPaths.

  5. But it would be even better not to append paths to a list, but instead to generate them one at a time using Python's yield instruction. That would allow you to interleave the generation of the paths with their further processing, and would avoid attempting to store exponentially many paths in memory.

  6. There's a global variable seenNodes which is not used.

  7. There's no point in writing:

    for endNode in gdict.iterkeys():
    

    when you could achieve the same thing by writing:

    for endNode in gdict:
    

    This also has the advantage of being portable to Python 3.

  8. The lines:

    if not gdict:
        return []
    

    are unnecessary. You can't call findPaths unless you can give it a vertex for the leave argument, which means that the graph must be non-empty.

  9. The argument leave to findPaths is poorly named. On the first call to the function it is (what you call) a leaf, but thereafter it can be any vertex.

  10. The leave argument to findPaths is always the first element of the argument path. So why not get it from there and avoid repeating yourself?

  11. Your algorithm searches backwards through the graph from its sinks. This is inconvenient because in order to prepare the list temp of vertices that might appear on the path before the current vertex, you have to search the whole graph. It would be simpler to search forwards because then you could look up the neighbours directly.

  12. Your choice of graph data structure is not one of the standard representations such as adjacency list (a map from a vertex to a list or set of its neighbouring vertices). It looks to me as though your representation is "map from vertex to map from neighbouring vertex to the empty map". Why did you choose this representation?

    Instead of the representation:

    {0: {1: {}}, 1: {2: {}, 3: {}}, 2: {3: {}}, 3: {4: {}}, 4: {5: {}}, 5: {6: {}}, 6: {7: {}}, 7: {6: {}, 5: {}, 8: {}}, 8: {}}
    

    I would use:

    {0: [1], 1: [2, 3], 2: [3], 3: [4], 4: [5], 5: [6], 6: [7], 7: [6, 5, 8], 8: []}
    

    or the similar alternative with sets instead of lists.

  13. Your test case is very small: it only has two paths. This means that it does not really exercise the code. See §4 below for some more thorough test cases.

3. Revised code

def paths(graph, v):
    """Generate the maximal cycle-free paths in graph starting at v.
    graph must be a mapping from vertices to collections of
    neighbouring vertices.

    >>> g = {1: [2, 3], 2: [3, 4], 3: [1], 4: []}
    >>> sorted(paths(g, 1))
    [[1, 2, 3], [1, 2, 4], [1, 3]]
    >>> sorted(paths(g, 3))
    [[3, 1, 2, 4]]

    """
    path = [v]                  # path traversed so far
    seen = {v}                  # set of vertices in path
    def search():
        dead_end = True
        for neighbour in graph[path[-1]]:
            if neighbour not in seen:
                dead_end = False
                seen.add(neighbour)
                path.append(neighbour)
                yield from search()
                path.pop()
                seen.remove(neighbour)
        if dead_end:
            yield list(path)
    yield from search()

Notes:

  1. This uses the yield from statement and so requires Python 3.3 or later. If you have to use an earlier Python, you can rewrite yield from search() as:

    for p in search():
        yield p
    
  2. seen is a collection containing the same vertices as path, but in a set for efficient computation of neighbour not in seen. It would be nice to be able to use a single data structure here (an ordered set), but Python does not provide one. We might consider using the keys of an OrderedDict or Raymond Hettinger's ordered set recipe.

  3. This implementation maintains the search state on the Python call stack (the current position in the iteration over the neighbouring vertices, and the value of dead_end) and so a large graph could exceed the recursion limit. In this case you could increase sys.setrecursionlimit, or maintain your own stack (for example, using the stack of iterators pattern).

4. Test cases

from itertools import chain, permutations
from unittest import TestCase

class PathTest(TestCase):
    def test_complete(self):
        # The maximal paths in a complete graph are the permutations
        # of the vertices.
        n = 8
        vertices = list(range(n))
        g = {v: vertices for v in vertices}
        found = sorted(chain.from_iterable(paths(g, i) for i in vertices))
        expected = map(list, permutations(vertices))
        for p, q in zip(found, expected):
            self.assertEqual(p, q)

    def test_binary(self):
        # Two alternatives at each of n places yields 2 ** n paths.
        n = 10
        g = {n * 2: [], n * 2 + 1: []}
        g.update({i: [i + 2, i + 3] for i in range(0, 2 * n, 2)})
        g.update({i: [i + 1, i + 2] for i in range(1, 2 * n, 2)})
        found = sorted(paths(g, 0))
        def expected():
            for i in range(2 ** n):
                p = []
                for j in reversed(range(0, 2 * n + 2, 2)):
                    p.append(j + i % 2)
                    i //= 2
                yield p[::-1]
        for p, q in zip(found, expected()):
            self.assertEqual(p, q)
  • Thanks for the detailed answer and review. I will try this on larger sized graphs and let you know the results. What I want to say about your comments are: (1) I am using pygraphviz representation. In their representation, dictionaries are used as outgoing edges for nodes. However, converting the values of dictionary into list is better, I agree on that. – genclik27 Jul 8 '14 at 15:51
  • (2) I wont use these paths directly in testing, sine it is not realistic as you said. This is called exhaustive testing which is all the time desirable but not realistic. – genclik27 Jul 8 '14 at 15:52
  • Instead, I am planning to generate the test suite to test them in such a way that all t-way interleaving threads and all n-way nodes are covered. This is called combinatorial interaction testing. For further info, you may look for Sequnece Covering Arrays. – genclik27 Jul 8 '14 at 15:52

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.