Traversing through all the available paths in a diagraph

Question

There is a graph structure with numbers like below.

To load this structure in a graph object in python. I have made it as a multi line string as below.

myString='''1
2 3
4 5 6
7 8 9 10
11 12 13 14 15'''

Representing it as a list of lists.

>>> listofLists=[ list(map(int,elements.split())) for elements in myString.strip().split("\n")]
>>> print(listofLists)
[[1], [2, 3], [4, 5, 6], [7, 8, 9, 10], [11, 12, 13, 14, 15]]

creating a graph structure using the below Node and edge class in python

Node Class, it requires position as a tuple and a value Example: elements and its position , value

1 --- position (0,0) and value is 1
2 --- position (1,0) and value is 2
3 --- position (1,1) and value is 3

The node class

class node(object):
    def __init__(self,position,value):
        '''
        position : gives the position of the node wrt to the test string as a tuple
        value    : gives the value of the node
        '''
        self.value=value
        self.position=position

    def getPosition(self):
        return self.position

    def getvalue(self):
        return self.value

    def __str__(self):
        return 'P:'+str(self.position)+' V:'+str(self.value)

The edge class creates an edge between two nodes.

class edge(object):
    def __init__(self,src,dest):
        '''src and dest are nodes'''
        self.src = src
        self.dest = dest

    def getSource(self):
        return self.src

    def getDestination(self):
        return self.dest
    #return the destination nodes value as the weight
    def getWeight(self):
        return self.dest.getvalue()

    def __str__(self):
        return (self.src.getPosition(),)+'->'+(self.dest.getPosition(),)

The Directed graph class is as below. The graph structure is build as a dict adjacency list. {node1:[node2,node3],node2:[node3,node4]......}

class Diagraph(object):

    '''the edges is a dict mapping node to a list of its destination'''
    def __init__(self):
        self.edges = {}

    '''Adds the given node as a key to the dict named edges ''' 
    def addNode(self,node):
        if node in self.edges:
            raise ValueError('Duplicate node')
        else:
            self.edges[node]=[]

    '''addEdge accepts and edge class object checks if source and destination node are present in the graph '''     
    def addEdge(self,edge):
        src = edge.getSource()
        dest = edge.getDestination()
        if not (src in self.edges and dest in self.edges):
            raise ValueError('Node not in graph')
        self.edges[src].append(dest)

    '''getChildrenof returns  all the children of the node'''   
    def getChildrenof(self,node):
        return self.edges[node]

    '''to check whether a node is present in the graph or not'''    
    def hasNode(self,node):
        return node in self.edges

    '''rootNode returns the root node i.e node at position (0,0)''' 
    def rootNode(self):
        for  keys in self.edges:
            return keys if keys.getPosition()==(0,0) else 'No Root node for this graph'

A function to create and return the graph object on which to work.

def createmygraph(testString):
    '''input is a multi-line string'''

    #create a list of lists from the string
    listofLists=[ list(map(int,elements.split())) for elements in testString.strip().split("\n")]
    y = Diagraph()
    nodeList = []

    # create all the nodes and store it in a list nodeList
    for i in range(len(listofLists)):
        for j in range(len(listofLists)):
            if i<=j:
                mynode=node((j,i),listofLists[j][i])
                nodeList.append(mynode)
                y.addNode(mynode)

    # create all the edges
    for srcNode in nodeList:
    # iterate through all the nodes again and form a logic add the edges
        for destNode in nodeList:
            #to add the immediate down node eg : add 7 (1,0) to 3 (0,0) , add 2 (2,0) to 7 (1,0)
            if srcNode.getPosition()[0]==destNode.getPosition()[0]-1 and srcNode.getPosition()[1]==destNode.getPosition()[1]-1:
                y.addEdge(edge(srcNode,destNode))
            #to add the bottom right node eg :add 4 (1,1) to 3 (0,0) 
            if srcNode.getPosition()[0]==destNode.getPosition()[0]-1 and srcNode.getPosition()[1]==destNode.getPosition()[1]:
                y.addEdge(edge(srcNode,destNode))

    return y

How to list all the paths that are available between two nodes.Specifically between 1---->11 , 1---->12 , 1---->13 , 1---->14 , 1---->15 I tried for a left first depth first approach for this case. But it failing to get the paths.

def leftFirstDepthFirst(graph,start,end,path,valueSum):
    #add input start node to the path
    path=path+[start]
    #add the value to the valueSum variable
    valueSum+=start.getvalue()
    print('Current Path ',printPath(path))
    print('The sum is ',valueSum)
    # return if start and end node matches.
    if start==end:
        print('returning as start and end have matched')
        return path

    #if there are no further destination nodes, move up a node in the path and remove the current element from the path list.
    if not graph.getChildrenof(start):
        path.pop()
        valueSum=valueSum-start.getvalue()
        return leftFirstDepthFirst(graph,graph.getChildrenof(path[-1])[1],end,path,valueSum)
    else:
        for aNode in graph.getChildrenof(start):
            return leftFirstDepthFirst(graph,aNode,end,path,valueSum)
    print('no further path to explore')

Testing the code.

#creating a graph object with given string
y=createmygraph(myString)

function to return terminal nodes like 11,12,13,14,15.

def fetchTerminalNode(graph,position):
    terminalNode=[]
    for keys in graph.edges:
        if not graph.edges[keys]:
            terminalNode.append(keys)
    return terminalNode[position]

Running the depth first left first function.

source=y.rootNode() # element at position (0,0)
destination=fetchTerminalNode(y,1) #ie. number 12
print('Path from ',start ,'to ',destination)
xyz=leftFirstDepthFirst(y,source,destination,[],0)

The path is fetched for the elements 11 and 12 but not for 13 or 14 or 15. i.e destination=fetchTerminalNode(y,2) does not work.Can please anyone suggest a way to approach this problem.

Answer 1

PFB the function that I could come up with that uses the breathfirstSearch to print all the availble paths between the root node and the end nodes.

Google Colab/github link

def breathfirstalgo(graph,tempPaths,finalPath):
## iterates over all the lists inside the tempPaths and checks if there are child nodes to its last node.
condList=[graph.getChildrenof(apartList[-1]) for apartList in tempPaths if graph.getChildrenof(apartList[-1])]

tempL=[]    
if condList:

    for partialList in tempPaths:
        #get the children of the last element of partialList
        allchild=graph.getChildrenof(partialList[-1])

        if allchild:
            noOfChild=len(allchild)
            #create noOfChild copies of the partialList
            newlist=[partialList[:] for _ in range(noOfChild)]      
            #append the a child element to the new list
            for i in range(noOfChild):
                newlist[i].append(allchild[i])

            #append each list to the temp list tempL
            for alist in newlist:
                tempL.append(alist)

        else:
            pass

    #after completion of the for loop i.e iterate through 1 level
    return breathfirstalgo(graph,tempL,finalPath)
else:
    #append all the lists from tempPaths to finalPath that will be returned
    for completePath in tempPaths:
        finalPath.append(completePath)
    return finalPath

Testing the breathfirstsearch solution as below.

mygraph=createmygraph(myString)
print('The graph object is ',mygraph)
print('The root node is ',mygraph.rootNode())
#print(mygraph)
all_list=breathfirstalgo(mygraph,tempPaths=[[mygraph.rootNode()]],finalPath=[])

print('alllist is ')
for idx,partlist in enumerate(all_list):
    print(printPath(partlist))

The output is as below after modifying the __str__ of node class as str(self.value)

The graph object is  <__main__.Diagraph object at 0x7f08e5a3d128>
The root node is  1
alllist is 
-->1-->2-->4-->7-->11
-->1-->2-->4-->7-->12
-->1-->2-->4-->8-->12
-->1-->2-->4-->8-->13
-->1-->2-->5-->8-->12
-->1-->2-->5-->8-->13
-->1-->2-->5-->9-->13
-->1-->2-->5-->9-->14
-->1-->3-->5-->8-->12
-->1-->3-->5-->8-->13
-->1-->3-->5-->9-->13
-->1-->3-->5-->9-->14
-->1-->3-->6-->9-->13
-->1-->3-->6-->9-->14
-->1-->3-->6-->10-->14
-->1-->3-->6-->10-->15

Answer 2

Given a tree

tree = \
  [ [1]
  , [2, 3]
  , [4, 5, 6]
  , [7, 8, 9, 10]
  , [11, 12, 13, 14, 15]
  ]

And a traverse function

def traverse (tree):
  def loop (path, t = None, *rest):
    if not rest:
      for x in t:
        yield path + [x]
    else:
      for x in t:
        yield from loop (path + [x], *rest)
  return loop ([], *tree)

Traverse all paths...

for path in traverse (tree):
  print (path)

# [ 1, 2, 4, 7, 11 ]
# [ 1, 2, 4, 7, 12 ]
# [ 1, 2, 4, 7, 13 ]
# [ 1, 2, 4, 7, 14 ]
# [ 1, 2, 4, 7, 15 ]
# [ 1, 2, 4, 8, 11 ]
# [ 1, 2, 4, 8, 12 ]
# ...
# [ 1, 3, 6, 9, 15 ]
# [ 1, 3, 6, 10, 11 ]
# [ 1, 3, 6, 10, 12 ]
# [ 1, 3, 6, 10, 13 ]
# [ 1, 3, 6, 10, 14 ]
# [ 1, 3, 6, 10, 15 ]

Or collect all of the paths in a list

print (list (traverse (tree)))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , [ 1, 2, 4, 7, 14 ]
# , [ 1, 2, 4, 7, 15 ]
# , [ 1, 2, 4, 8, 11 ]
# , [ 1, 2, 4, 8, 12 ]
# , ...
# , [ 1, 3, 6, 9, 15 ]
# , [ 1, 3, 6, 10, 11 ]
# , [ 1, 3, 6, 10, 12 ]
# , [ 1, 3, 6, 10, 13 ]
# , [ 1, 3, 6, 10, 14 ]
# , [ 1, 3, 6, 10, 15 ]
# ]

Above, we used generators which are a high-level feature in Python. Maybe you wish to understand how to implement a solution using more primitive features...

The generic mechanism we're looking for here is the list monad, which captures the idea of ambiguous computation; some procedure that can return potentially more than one value.

Python already provides lists and a way to construct them using []. We only need to supply the binding operation, named flat_map below

def flat_map (f, xs):
  return [ y for x in xs for y in f (x) ]

def traverse (tree):
  def loop (path, t = None, *rest):
    if not rest:
      return map (lambda x: path + [x], t)
    else:
      return flat_map (lambda x: loop (path + [x], *rest), t)
  return loop ([], *tree)

print (traverse (tree))
# [ [ 1, 2, 4, 7, 11 ]
# , [ 1, 2, 4, 7, 12 ]
# , [ 1, 2, 4, 7, 13 ]
# , ... same output as above ...
# ]

Oh and Python has a built-in product function which happens to work exactly as we need. The only difference is that the paths will be output as tuples () instead of lists []

from itertools import product

tree = \
  [ [1]
  , [2, 3]
  , [4, 5, 6]
  , [7, 8, 9, 10]
  , [11, 12, 13, 14, 15]
  ]

for path in product (*tree):
  print (path)

# (1, 2, 4, 7, 11)
# (1, 2, 4, 7, 12)
# (1, 2, 4, 7, 13)
# (1, 2, 4, 7, 14)
# (1, 2, 4, 7, 15)
# ... same output as above ...

In your program you attempt to abstract this mechanism through various classes, node and edge and diagraph. Ultimately you can structure your program however you want, but know that it doesn't need to be more complex than we have written it here.

---

Update

As @user3386109 points out in the comments, my program above generates paths as if each parent was connected to all children. This is a mistake however as your graph shows that parents are only connected to adjacent children. We can fix this with a modification to our program – changes below in bold

def traverse (tree):
  def loop (path, i, t = None, *rest):
    if not rest:
      for (j,x) in enumerate (t):
        if i == j or i + 1 == j:
          yield path + [x]
    else:
      for (j,x) in enumerate (t):
        if i == j or i + 1 == j:
          yield from loop (path + [x], j, *rest)
  return loop ([], 0, *tree)

Above we use an indices i and j to determine which nodes are "adjacent" but it cluttered up our loop a bunch. Plus the new code looks like it introduces some duplication. Giving this intention a name adjacencies keeps our function cleaner

def traverse (tree):
  def adjacencies (t, i):
    for (j, x) in enumerate (t):
      if i == j or i + 1 == j:
        yield (j, x)

  def loop (path, i, t = None, *rest):
    if not rest:
      for (_, x) in adjacencies (t, i):
        yield path + [x]
    else:
      for (j, x) in adjacencies (t, i):
        yield from loop (path + [x], j, *rest)

  return loop ([], 0, *tree)

Using it is the same, but this time we get the output specified in the original question

for path in traverse (tree):
  print (path)

# [1, 2, 4, 7, 11]
# [1, 2, 4, 7, 12]
# [1, 2, 4, 8, 12]
# [1, 2, 4, 8, 13]
# [1, 2, 5, 8, 12]
# [1, 2, 5, 8, 13]
# [1, 2, 5, 9, 13]
# [1, 2, 5, 9, 14]
# [1, 3, 5, 8, 12]
# [1, 3, 5, 8, 13]
# [1, 3, 5, 9, 13]
# [1, 3, 5, 9, 14]
# [1, 3, 6, 9, 13]
# [1, 3, 6, 9, 14]
# [1, 3, 6, 10, 14]
# [1, 3, 6, 10, 15]

The reason this simple adjancies function works is because your input data is uniform and valid. You can visualize the indices i and i + 1 clearly by color-coding the paths in your image. We never have to worry about an index-out-of-bounds error because you can see i + 1 is never computed on nodes without children (ie, the last row). If you were to specify invalid data, traverse does not guarantee a valid result.