用於生成無環有向圖的遞歸算法

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 

主要功能調用遞歸函數

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

輸出仍然不是你正在尋找的。您可以使用某些數據結構工作來調整它。