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 = 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]
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_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:
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:
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):
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