Recursive algorithm for generating a acyclic directed graph

Question

INPUT:-
mainlist:[12345,23456,09768]

Need to construct the following dependency graph

12345 has 01242(internal dep),34567(externaldep)
01242 has  23456(internaldep),56789,32345(externaldep)
34567  has 11111(internal dep),no external dependencies
23456 has 33456(internaldep),no external dependencies
56789 no dependencies
32345 no dependencies
11111 no dependencies
33456 no dependencies
09768 has 12222(internal dep),34333(External dep)
12222 no dependencies
34333 no dependencies 

OUTPUT:-

[12345,01242,34567,23456,56789,32345,11111,33456,09768,12222,34333]

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

For every item in the main list am trying to find out the internal dependency and external dependency recursively until there are no dependencies and create a list with all the changes.

build_dep_list=[]
local_list=[]
for each item in mainlist:
         local_list.append(item)
    build_dep_list.append(item)
    for  each localitem in local_list:
        head = localitem
        internal_dep_list =getinternaldep(change)
        external_dep_list= getexternaldep(change)
        append.internal_dep_list.local_list
        append.external_dep_list.local_list
        append.internal_dep_list.build_dep_list
        append.external_dep_list.build_dep_list
        delete(head).local_list

def getinternaldep:
    //code1

def getexternaldep:
    //code2

Regarding your output, why do you have '34567' twice? Also, does the order of '56789,32345,11111,33456' has to be exactly this or can it be, let's say, '56789,32345,33456,11111'? — gatto
– gatto, Commented Apr 26, 2013 at 7:59
@gatto - I edited it...34567 should be printed only once..yes order is imp..ideally it should be in the order of change and its dependencies — carte blanche
– carte blanche, Commented Apr 26, 2013 at 8:03
@tripleee - there is a database where for every change it lists the internal and external dependencies — carte blanche
– carte blanche, Commented Apr 26, 2013 at 17:01

poof · Accepted Answer · 2013-04-26 10:46:08Z

A possible recursive solution.

Here is mock dependency data stored as lists in a dictionary. Depending upon the format of the data returned to you from the database, modify the marked lines such that they convert the returned data into a list.

mainlist = ['12345', '23456' , '09768']

internal_dep = {
    '12345': ['01242'],
    '01242': ['23456'],
    '34567': ['11111'],
    '23456': ['33456'],
    '56789': [],
    '32345': [],
    '11111': [],
    '33456': [],
    '09768': ['12222'],
    '12222': [], 
    '34333': [],
    }

external_dep = {
    '12345': ['34567'],
    '01242': ['56789', '32345'],
    '34567': [],
    '23456': [],
    '56789': [],
    '32345': [],
    '11111': [],
    '33456': [],
    '09768': ['34333'],
    '12222': [],
    '34333': []
    }

Recursive functions to separately get the internal and external dependency data

def getinternaldep(item):
    local_list = []
    temp_list = []
    # Change this line depending on data format
    temp_list.extend(internal_dep[item])
    local_list.extend(temp_list)
    for new_item in temp_list:
        internal_dep_list = getinternaldep(new_item)
        local_list.extend(internal_dep_list)
    return local_list

def getexternaldep(item):
    local_list = []
    temp_list = []
    # Change this line depending on data format
    temp_list.extend(external_dep[item])
    local_list.extend(temp_list)
    for new_item in temp_list:
        external_dep_list = getexternaldep(new_item)
        local_list.extend(external_dep_list)
    return local_list

The main function to call the recursive functions

build_dep_list = []
for item in mainlist:
    build_dep_list.append(item)
    internal_dep_list = getinternaldep(item)
    external_dep_list = getexternaldep(item)
    build_dep_list.extend(internal_dep_list)
    build_dep_list.extend(external_dep_list)
print build_dep_list

And the output

['12345', '01242', '23456', '33456', '34567', '23456', '33456', '09768', '12222', '34333']

The order is mainlist item -> int dep -> ext dep -> next mainlist item -> int dep -> ext dep and so on.

EDIT:

Here is a slightly cleaner solution with one recursive function.

def _getdep(item):
    local_list, temp_list = [], []
    temp_list.extend(internal_dep[item])
    temp_list.extend(external_dep[item])
    local_list.extend(temp_list)
    for new_item in temp_list:
        local_list.extend(_getdep(new_item))
    return local_list

build_dep_list = []
for item in mainlist:
    build_dep_list.append(item)
    build_dep_list.extend(_getdep(item))

print build_dep_list

['12345', '01242', '34567', '23456', '56789', '32345', '33456', '11111', '23456', '33456', '09768', '12222', '34333']

The output still isn't exactly what you are looking for. You may be able to adjust it with some data structure work.

Collectives™ on Stack Overflow

Recursive algorithm for generating a acyclic directed 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