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

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]

我有一些数据库对象完全相互链接，就像上面的依赖关系...我想做的是编写一个算法来检索该信息并将所有这些表示为图形。现在我正在编写一个伪代码，然后我应该能够编写 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

Answer 1

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

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

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

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