python之生成无环有向图的递归算法

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] 

我有一些数据库对象完全相互链接，就像上面的依赖关系...我想做的是编写一个算法来检索该信息并将所有这些表示为图形。现在我正在编写一个伪代码，然后我应该能够编写 python 实现这似乎是一个递归算法，这就是我被卡住的地方!

对于主列表中的每个项目，我都试图递归地找出内部依赖和外部依赖，直到没有依赖并创建一个包含所有更改的列表。

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 

请您参考如下方法:

一个可能的递归解决方案。

这是在字典中存储为列表的模拟依赖数据。根据从数据库返回给您的数据的格式，修改标记的行，以便它们将返回的数据转换为列表。

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': [] 
    } 

分别获取内部和外部依赖数据的递归函数

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 

调用递归函数的main函数

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 

和输出

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

顺序是 mainlist item -> int dep -> ext dep -> next mainlist item -> int dep -> ext dep 等等。

编辑:

这是一个带有一个递归函数的稍微简洁的解决方案。

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'] 

输出仍然不是您要查找的内容。您可以通过一些数据结构工作来调整它。