Path Finding Despite Cycles

• Download source code - 1 KB

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

class Link:
    pass


class Node:
    def __init__(self, id: int, *in_links: Tuple[Link]):
        self.in_links = in_links
        self.id = id

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


class Link:
    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')

node1 = Node(1, Link(root))
node2 = Node(2, Link(root))

node11 = Node(11, Link(node1), Link(node2))
node12 = Node(12, Link(node1), Link(node2))

node21 = Node(21, Link(node1), Link(node2))
node22 = Node(22, Link(node1), Link(node2))

node_final = Node('final',
                  Link(node11), Link(node12),
                  Link(node21), Link(node22),
                  )

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 = []
    for link in node.in_links:
        routes_from_source = find_routes_to_sources_dag(link.source_node)
        route_start = [link.source_node]
        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 = []
    route_head = (route_head or []) + [node]  # ***
    for link in node.in_links:
        if link.source_node in route_head:  # ***
            continue

        routes_from_source = find_routes_to_sources(link.source_node, route_head)  # ***
        route_start = [link.source_node]
        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')
nodeB = Node('B', Link(nodeA))
nodeA.in_links = [Link(nodeB)]

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')
nodeB = Node('B', Link(nodeA))
nodeA.in_links = [Link(nodeB)]
nodeC = Node('C', Link(nodeB))

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')
nodeB = Node('B', Link(nodeA), Link(nodeC))
nodeA.in_links = [Link(nodeB)]
nodeC.in_links = [Link(nodeB)]

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')
nodeC = Node('C', Link(nodeD))
nodeB = Node('B', Link(nodeA), Link(nodeC), Link(nodeD))
nodeA.in_links = [Link(nodeB)]

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