Recursive algorithm for generating a graph

Question

I have some database objects that are fully linked to each other as dependencies. What i want to do is to write an algorithm to retrieve that information and represent all this as a graph. Right now a pseudocode should do the trick for me , then after i should be able to write the python implementation. This seems like a recursive algorithm and this is where i am stuck!

 Input (Obj)
 list = obj.getDependencies():
 if list is empty:
   return obj
 else
   for items in list:
     list1 = item.getDependencies()
     if list1 is empty:
       return item
     else:
       list2 = item.getDependencies()
       ......

My mind blows up at this point!!! how can i re-write this algorithm

You said you wanted "to write an algorithm to retrieve that information and represent all this as a graph" but your code does just get some item's dependencies. Start with a graph class that allows you to add nodes and edges and the whole problem will be much easier. — Jochen Ritzel
– Jochen Ritzel, Commented Feb 25, 2011 at 13:41

tokland · Accepted Answer · 2011-02-25 14:49:54Z

If I understood correctly, you want only the leaf nodes of the tree (those with no more dependencies). Is that the case? An example using an auxiliar struct to make it runnable:

class Struct:
    def __init__(self, **entries): 
        self.__dict__.update(entries)        

obj = Struct(
    name="1",
    get_dependencies=lambda: [
        Struct(name="11", get_dependencies=lambda: []), 
        Struct(name="12", get_dependencies=lambda: [
            Struct(name="121", get_dependencies=lambda: [])
        ])
    ])

def get_all_dependencies(obj):
    ds = obj.get_dependencies()
    if not ds:
        yield obj
    for o in ds:
        for o2 in get_all_dependencies(o):
            yield o2

print [x.name for x in get_all_dependencies(obj)]
# ['11', '121']

If you like the compact code that itertools makes possible, a different implementation with the exact same idea:

import itertools

def flatten(it):
    return itertools.chain.from_iterable(it)

def get_all_dependencies(obj):
    ds = obj.get_dependencies()
    return ([obj] if not ds else flatten(get_all_dependencies(o) for o in ds))

print [x.name for x in get_all_dependencies(obj)]
# ['11', '121']

Collectives™ on Stack Overflow

Recursive algorithm for generating a graph

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related