CODEWITHSUNDEEP
pythonrecursionhashgraphnodes
John Zrobin
John Zrobin

Reputation: 45

Generating a graph recursively - Python

Here is my code right now:

   hasht= {"A":["B", "D", "E"], "B":["C"], "C":["D", "E"], "D":["C", "E"], "E":["B"]}
   paths=[]
   def recusive(start, finish, val):
      if start==finish and val!=1:
        return start
    else:
        for i in hasht[start]:
            path= start+ recusive(i,finish,2)
            paths.append(path)
print (recusive("C","C",1))
print paths

#[CDC, CDEBC, CEBC]

I am trying to generate a table like the one on the bottom, but am running into the problem of the string and the array not being able to concatenate. When I just return however, it returns CDC and works, however, exiting the function as return is meant to do. I am wondering how I can improve my code here to 1) make it work, 2) why my logic was faulty. For example, I understand that it genereates say [DC], but I am confused as to how to go around that. perhaps index the value returned?

Upvotes: 0

Views: 2802

Answers (3)

Corley Brigman
Corley Brigman

Reputation: 12401

why not just use networkx? this is what it is for...

hasht = \
{
    "A" : ["B", "D", "E"],
    "B" : ["C"],
    "C" : ["D", "E"], 
    "D" : ["C", "E"], 
    "E" : ["B"]
}

import networkx as nx
G = nx.DiGraph(hasht)

list(nx.all_simple_paths(G, 'C', 'C'))
[['C', 'E', 'B', 'C'], ['C', 'D', 'C'], ['C', 'D', 'E', 'B', 'C']]

if this is homework... well then obviously you can't do this, but it's a lot easier to use imho...

Upvotes: 1

RMcG
RMcG

Reputation: 1095

The main issue here is that you are not returning anything when you reach end of an inner for loop. Because of this a NoneType is returned from the previous recursion leading to your error:

Lets look through your code and see what this happens: We will do this by substituting in the lists to the for loops so we can fully see what's happening (This is not valid python code it is merely for demonstration purposes :D)

rec('C','C',1)

for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['C','E']
    path_j = 'D' + rec('C','C',2)
      'C'=='C' and 2!=1
       return 'C'

Ok so far so good, we have the Path (path_j) 'DC' so we append this to paths and now looking at the inner most loop where j is now set to 'E'

rec('C','C',1)

for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['E']
    path_j = 'D'+rec('E','C',2)
    for k in ['B']
      path_k = 'B'+rec('B','C',2)
      for l in ['C']
          'C'=='C' and 2!=1
           return 'C'

Ok we have another path. This time it is path_k = 'BC', so lets append this to paths. but now that we have run out of elements for k we need to return something

rec('C','C',1)
for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['E']
    path_j = 'D'+rec('E','C',2)
    for k in []
        return ???

Currently you are returning nothing so python returns a 'NoneType' object for you

rec('C','C',1)
for i in ['D','C']
  path_i = 'C'+rec('D','C',2)
  for j in ['E']
    path_j = 'D'+NoneType

unfortunately you are now trying to concatenate this NoneType with a string and hence your error:

TypeError: cannot concatenate 'str' and 'NoneType' objects

In order to correct you can just return the path string: (This is actual valid python code now)

hasht= {"A":["B", "D", "E"], "B":["C"], "C":["D", "E"], "D":["C", "E"], "E":["B"]}
paths=[]

def recusive(start, finish, val):
if start==finish and val!=1:
    return start
else:
    for i in hasht[start]:
        path= start+ recusive(i,finish,2)
        paths.append(path)
    return path

print (recusive("C","C",1))
print paths

This returns the paths:

['DC', 'BC', 'EBC', 'DEBC', 'CDEBC', 'BC', 'EBC', 'CEBC']

Upvotes: 0

dilbert
dilbert

Reputation: 3098

A couple of things:

  • formatting: putting a graph on a single line is awful
  • the reason your function was failing was because recursive function returns either a string or None but concatenation is undefined between between a string and None. Always make sure a recursive function either always returns a given data type or always returns nothing.
  • Unless a call to a recursive function can be made cleanly, use a helper function to hide unnecessary variable initialisation.
  • the val variable is unnecessary; none of the nodes loop to themselves (it doesn't properly prevent that anyway)
  • why print the function call ? You're calling function to discover paths and it doesn't return them.
  • why write to a global variable ? Running the function multiple times will accumulate unrelated paths together.
  • why does the function return nothing to the original call ?

I changed the function to pass the path variable instead of the start variable, as recursive functions are easier to understand when they don't return data but instead write to a variable (the paths list) (this is another benefit of nesting a helper function).

I also nested the helper function so to provide a clean calling interface but also flat return structure to a local variable without using the stack.

This structure is also easier to see how the path is extended; that is, path is always a list of strings and i is always a string, so concatenation of a list encapsulated string to a list will always work.

hasht = \
{
    "A" : ["B", "D", "E"],
    "B" : ["C"],
    "C" : ["D", "E"], 
    "D" : ["C", "E"], 
    "E" : ["B"]
}

def recursive(start, finish):
    paths=[]
    def recursive_helper(path, finish):
        for i in hasht[path[-1]]:
            if i == finish:
                paths.append(path + [i])
                continue
            else:
                recursive_helper(path + [i], finish)
    recursive_helper([start], finish)
    return paths

print recursive("C", "C")

Upvotes: 1

Related Questions