用於生成圖形的遞歸算法

我有一些數據庫對象作爲依賴項完全鏈接到彼此。我想要做的是編寫一個算法來檢索這些信息，並將其作爲一個圖表來表示。現在，一個僞代碼應該爲我執行這個技巧，然後我應該能夠編寫python實現。這看起來像一個遞歸算法，這是我卡住的地方！用於生成圖形的遞歸算法

Input (Obj) 
list = obj.getDependencies(): 
if list is empty: 
    return obj 
else 
    for items in list: 
    list1 = item.getDependencies() 
    if list1 is empty: 
     return item 
    else: 
     list2 = item.getDependencies() 
     ......

我的頭腦在這一點上爆炸！我怎麼能重新寫這個算法

來源

2011-02-25 cocit

你說你希望「編寫一個算法來檢索這些信息，並將所有這些信息表示爲一個圖表「但是你的代碼只是獲取某個項目的依賴關係。從圖形類開始，允許您添加節點和邊，整個問題將變得更加容易。 – 2011-02-25 13:41:41

如果我理解正確，你只需要樹的葉節點（那些沒有更多的依賴）。是這樣嗎？使用附配結構的一個例子，以使其可以運行：

class Struct: 
    def __init__(self, **entries): 
     self.__dict__.update(entries)   

obj = Struct(
    name="1", 
    get_dependencies=lambda: [ 
     Struct(name="11", get_dependencies=lambda: []), 
     Struct(name="12", get_dependencies=lambda: [ 
      Struct(name="121", get_dependencies=lambda: []) 
     ]) 
    ]) 

def get_all_dependencies(obj): 
    ds = obj.get_dependencies() 
    if not ds: 
     yield obj 
    for o in ds: 
     for o2 in get_all_dependencies(o): 
      yield o2 

print [x.name for x in get_all_dependencies(obj)] 
# ['11', '121']

如果你喜歡緊湊的代碼，itertools成爲可能，不同的實現具有完全相同的想法：

import itertools 

def flatten(it): 
    return itertools.chain.from_iterable(it) 

def get_all_dependencies(obj): 
    ds = obj.get_dependencies() 
    return ([obj] if not ds else flatten(get_all_dependencies(o) for o in ds)) 

print [x.name for x in get_all_dependencies(obj)] 
# ['11', '121']

來源

2011-02-25 14:43:33 tokland

用於生成圖形的遞歸算法

回答

相關問題