14,022,853 members
Tip/Trick
alternative version

#### Stats

5K views
2 bookmarked
Posted 30 Mar 2017
Licenced CPOL

# Path Finding Despite Cycles

, 1 Apr 2017
Find routes from any node of a directed graph to leaves, when cycles may be present in graph

## Introduction

When you have a network of objects that are linked to one another, you may need to find all the routes from a given object to all other reachable objects. In this memo, I show a simple recursion sufficient to solve the problem when cycles are not present in the network, and then the small changes necessary and sufficient when cycles may be present.

## Background

Say you represent your networked objects by a `Node` class that can have a list of `Link` objects. Each Link can have one "source" node. In Python, this could be implemented like this:

```from typing import List, Tuple

pass

class Node:
self.id = id

def __str__(self):
return 'node_' + str(self.id)

def __init__(self, source: Node):
self.source_node = source```

The ID and "string conversion" method are merely for logging purposes. This implementation would allow you to write the following network:

```# root <- 1 <- 11 <- final
#           <- 12 <-
#      <- 2 <- 21 <-
#           <- 22 <-

root = Node('root')

node_final = Node('final',
)```

What are all the routes from a given node (say node 11 or node "final") to the various "source" nodes?

## Using the Code

When the network does not have any cycles, the problem is very easy to solve using recursion:

```Route = List[Node]

def find_routes_to_sources_dag(node: Node) -> List[Route]:
"""
Find all routes to source nodes.
Will recurse until RecursionError if cycles are present.
"""
routes = []
if routes_from_source:
for route_from_source in routes_from_source:
routes.append(route_start + route_from_source)
else:
routes.append(route_start)

return routes```

This function takes a node of class `Node` and returns a list of routes, each route being a list of nodes. For the example network in the previous section, the routes are:

```Routes from node_1
route:  ['node_root']
Routes from node_2
route:  ['node_root']
Routes from node_11
route:  ['node_1', 'node_root']
route:  ['node_2', 'node_root']
Routes from node_12
route:  ['node_1', 'node_root']
route:  ['node_2', 'node_root']
Routes from node_21
route:  ['node_1', 'node_root']
route:  ['node_2', 'node_root']
Routes from node_22
route:  ['node_1', 'node_root']
route:  ['node_2', 'node_root']
Routes from node_final
route:  ['node_11', 'node_1', 'node_root']
route:  ['node_11', 'node_2', 'node_root']
route:  ['node_12', 'node_1', 'node_root']
route:  ['node_12', 'node_2', 'node_root']
route:  ['node_21', 'node_1', 'node_root']
route:  ['node_21', 'node_2', 'node_root']
route:  ['node_22', 'node_1', 'node_root']
route:  ['node_22', 'node_2', 'node_root']```

The function that printed this was defined as follows:

```def print_routes_from(node):
print('Routes from {}'.format(node))
# routes = find_routes_to_sources(node)
routes = find_routes_to_sources_dag(node)
for route in routes:
print('route: ', [str(node) for node in route])```

What if cycles are allowed in the network? Such as, a node A linked to a node B linked back to A? As the comment indicates in the above function definition, any cycle present in the network will cause the recursion to be endless. In Python, this will cause a recursion error after about 50 levels of recursion.

To handle this situation, it is sufficient to extend the route finder so that it ignores nodes that have already been visited:

```def find_routes_to_sources(node: Node, route_head: List[Node]=None) -> List[Route]:  # ***
"""
Find all routes to source node.
Handles cycles by ignoring nodes already visited.
"""
routes = []
continue

if routes_from_source:
for route_from_source in routes_from_source:
routes.append(route_start + route_from_source)
else:
routes.append(route_start)

return routes```

The lines that have "`# ***`" indicate the lines that had to change from the `find_routes_to_sources_dag()`:

• The function needs to know what nodes have already been visited, i.e., the "route head"
• The function needs skip any node that is in the route head or is the node
• The function needs to provide the "extended route head" to the recursion

The simple network "A <=> B" can be represented like this using the above classes:

```nodeA = Node('A')

For such a simple network, there is really only one route from A: it can go to B (because the route that returns to A is not of interest); and one route from B: it can go to A. Using the same print function defined above (but make it call the new function instead of the DAG version), the routes are:

```Routes from node_A
route:  ['node_B']
Routes from node_B
route:  ['node_A']```

A slightly more complicated network:

```# simple cycle  A <=> B -> C
nodeA = Node('A')

This one has the following routes:

```Routes from node_A
route:  ['node_B']
Routes from node_B
route:  ['node_A']
Routes from node_C
route:  ['node_B', 'node_A']```

Another one:

```# simple cycle  A <=> B <=> C
nodeA = Node('A')
nodeC = Node('C')

which has the following routes:

```Routes from node_A
route:  ['node_B', 'node_C']
Routes from node_B
route:  ['node_A']
route:  ['node_C']
Routes from node_C
route:  ['node_B', 'node_A']```

And finally a network where a cycle has more than 2 objects (B to C to D back to B):

```# simple cycle  A <=> B <- C <- D
#                       <------

nodeA = Node('A')
nodeD = Node('D')

The route finder finds all routes, omitting cycles:

```Routes from node_A
route:  ['node_B', 'node_C', 'node_D']
route:  ['node_B', 'node_D']
Routes from node_B
route:  ['node_A']
route:  ['node_C', 'node_D']
route:  ['node_D']
Routes from node_C
route:  ['node_D']
Routes from node_D```

## Points of Interest

Nothing comes to mind just now, maybe based on questions/feedback.

## History

• 2017-03-31: Draft submitted