CODEWITHSUNDEEP
python
carte blanche
carte blanche

Reputation: 11476

Recursive algorithm for generating a acyclic directed graph

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

Upvotes: 2

Views: 808

Answers (1)

poof
poof

Reputation: 69

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.

Upvotes: 1

Related Questions