Python图形lis

Question

一般来说，问题是什么，有一个列表（图）。如果你运行这个代码。这个结果不会是完整的，但我希望结果将是箭头所示的地方。如何解决我的问题？如果你能重写这段代码。我试着用一个以上的键列表（成对的第一个数字），找到这个并重写到第二个列表。我想沿着图表往下看。RESULT

link = [[1, 3], [3, 2], [2, 6], [1, 4], [4, 3], [3, 7], [7, 8], [8, 9]]

link_keys = []
cpy_link = []
number = 0
diametr = 0
k = len(link)
m = 0

def circle_for_net(number):
    for j in range(k):
        while number == link[j][0]:
            number = link[j][1]
            cpy_link.append(number)
            circle_for_net(number)
            number = 0
            break

def create_keys(link):
    for j in range(k):
        link_keys.append(link[j][0])

for i in range(k - 1):
    for j in range(k - i - 1):
        if link[j][0] > link[j + 1][0]:
            link[j], link[j + 1] = link[j + 1], link[j]

create_keys(link)
for i in range(k):
    number = link[i][1]
    cpy_link.append(link[i][0])
    cpy_link.append(number)
    circle_for_net(number)
    print(cpy_link)
    if(diametr < len(cpy_link)):
        diametr = len(cpy_link)
    cpy_link.clear()

print(diametr)

Answer 1

似乎要在有向无环图（DAG）中找到从源节点到汇节点的所有可能路径。这有一个答案here，但仅适用于一对节点：

def paths(source_node, sink_node, memo_dict = None):
    if memo_dict is None:
        # putting {}, or any other mutable object
        # as the default argument is wrong
        memo_dict = dict()

    if source_node == sink_node or source_node not in nodes_children: # Don't memoize trivial case
        return frozenset([(source_node,)])
    else:
        pair = (source_node, sink_node)
        if pair in memo_dict: # Is answer memoized already?
            return memo_dict[pair]
        else:
            result = []
            for new_source in nodes_children[source_node]:
                p = paths(new_source, sink_node, memo_dict)
                for path in p:
                    path = (source_node,) + path
                    result.append(path)
            #result = frozenset(result)
            # Memorize answer
            memo_dict[(source_node, sink_node)] = result
            return result

假设你有一本字典 nodes_children = {1: [3, 4], 3: [2, 7], 2: [6], 4: [3], 7: [8], 8: [9]}将节点映射到它的子节点，以及一个数组sinks = [6, 9]和DAG中的接收器，这可以很容易地扩展以找到所有这样的路径：

def allpaths(nodes_children, sinks):
    result = []
    for sink in sinks:
        for source in nodes_children:
            result.append(paths(source, sink))
    # flatten the list
    result = [r for res in result for r in res]

    # remove duplicates while keeping order
    seen = set()
    seen_add = seen.add
    result = [x for x in result if not (x in seen or seen_add(x))]
    return result

最后，如果您不想手工计算nodes_children和sinks，可以编写

def get_sinks(link):
    sinks = []  # will store 6 and 9
    for edge in link:
        potential_sink = edge[1]
        is_sink = True
        for edge in link:
            if edge[0] == potential_sink:
                is_sink = False
        if is_sink:
            sinks.append(potential_sink)
    return sinks
# [6, 9]
sinks = get_sinks(link)

def dict_children(link):
    nodes_children = {}
    for edge in link:
        l_node = edge[0]
        r_node = edge[1]
        if l_node in nodes_children:
            nodes_children[l_node].append(r_node)
        else:
            nodes_children[l_node] = [r_node]
    return nodes_children
# {1: [3, 4], 3: [2, 7], 2: [6], 4: [3], 7: [8], 8: [9]}
nodes_children = dict_children(link)