0

次のグラフがあります（対応するエッジ値は括弧内に書かれています）：

L0 -> L1 ('01')
L1 -> L2 ('12')
L1 -> L4 ('14')
L4 -> L5 ('45')
L2 -> L3 ('23')
L3 -> L1 ('31')

から始まる特定の長さのすべての可能なパスのエッジ値のリストが必要ですL0。したがって、length = 3(開始ノードを除く) 場合、次の 2 つのリストを取得する必要があります。

['01', '12', '23'] and ['01', '14', '45'].

1 サイクルでの移動が可能です。グラフを表すために 2 レベルの辞書を使用してみました。

graph = {'L0': {'L1': '01'}, 'L1': {'L2': '12', 'L4': '14'}, 'L2': {'L3': '23'}, 'L3': {'L1': '31'}, 'L4': {'L5': '45'}}

def find_path(graph, start, depth):
    k = 0
    while k < depth:
        a = graph[start]
        for node in graph[start]:
            start = node
        path.append(a[node])
        k+=1 
    return path 
print find_path(graph, 'L0', 4)

明らかに、1 つの可能なパス出力が得られます。しかし、私はすべての可能なものを望んでいます。

4

2 に答える 2

2

制限に達するか、それ以上進行できなくなるまで、再帰的にさらに進行させます。

# graph: Graph we are operating on
# node: Node we are starting from
# hops: Number of hops we can still do (edges we can take)
def findPaths(graph, node, hops):
    # if no further hops should be done, we were successful and
    # can end the recursion
    if hops == 0:
        yield []
        return

    # if the node is not in the graph, we cannot go further, so
    # the current path is invalid
    if node not in graph:
        return

    # for every node we can reach from the current
    for n in graph[node]:
        # find all paths we can take from here
        for path in findPaths(graph, n, hops - 1):
            # and concat the edge names
            yield [graph[node][n]] + path

グラフで（指定された表現で）使用すると、次のようになります。

>>> list(findPaths(graph, 'L0', 3))
[['01', '14', '45'], ['01', '12', '23']]
>>> list(findPaths(graph, 'L0', 4))
[['01', '12', '23', '31']]
>>> list(findPaths(graph, 'L0', 2))
[['01', '14'], ['01', '12']]
于 2013-09-29T01:56:03.647 に答える
1

私はそれを単純なedge:edge辞書として表現します：

links = {
    0: [1],
    1: [2, 4],
    2: [3],
    4: [5],
    3: [1]
}

次に、それを繰り返すことができます：

def get_all_paths(links, length, start=0):
    paths = [[start]]
    for i in range(length):
        newpaths = []
        for path in paths:
            try:
                for next_node in links[path[-1]]:
                    newpaths.append(path + [next_node])
            except KeyError:
                pass
        paths = newpaths

    return paths

get_all_paths(links, 3)
#>>> [[0, 1, 2, 3], [0, 1, 4, 5]]

それぞれの変換は、別のステップで行うこと[0, 1, 2, 3]が[(0,1), (1,2), (2,3)]できます。

グラフでも機能します。

links = {'L0': {'L1': '01'}, 'L1': {'L2': '12', 'L4': '14'}, 'L2': {'L3': '23'}, 'L3': {'L1': '31'}, 'L4': {'L5': '45'}}

def get_all_paths(links, length, start=0):
    paths = [[start]]
    for i in range(length):
        newpaths = []
        for path in paths:
            try:
                for next_node in links[path[-1]]:
                    newpaths.append(path + [next_node])
            except KeyError:
                pass
        paths = newpaths

    return paths

get_all_paths(links, 3, start='L0')
#>>> [['L0', 'L1', 'L4', 'L5'], ['L0', 'L1', 'L2', 'L3']]

['01', '14', '45']その後、各パスをフォームに変換するだけです。

最後の変換を行う方法を知りたいと思われるので、次の方法があります。

paths = [['L0', 'L1', 'L4', 'L5'], ['L0', 'L1', 'L2', 'L3']]

def join_paths(paths, links):
    for path in paths:
        yield [links[a][b] for a, b in zip(path, path[1:])]

list(join_paths(paths, links))
#>>> [['01', '14', '45'], ['01', '12', '23']]

zip(path, path[1:])になり[1, 2, 3, 4]ます[(1, 2), (2, 3), (3, 4)]。

for a, b inは、各ペアとセットを取りa、そのb中のアイテムに移動します。

次にlinks[a][b]、辞書からパス名を検索します。

yieldは各アイテムを一度に 1 つずつ返すため、リストに入れるにlistは の出力を呼び出す必要があります。join_paths

于 2013-09-29T00:59:41.857 に答える