0

我有一个有向的、多重的、加权的图。我想找到 a -> b -> c -> a 的循环

我的图表样本。我希望它清楚：

v1 -> v2
v2 -> v3
v3 -> v1
v1 -> v4
v2 -> v5

如何仅迭代作为目标的节点？这是我的短

results = []

for n in g.nodes: # iterates all nodes
    x = n #marks the first node
    for n1 in n.neighbors: #iterates neighbors, but this part should include only neighbors that are targets.
        y = n1 # marks second node
        for n2 in n.neighbors: #same as above, should select only target neighbors.
            if n2 == x:
                print "FOUND"

我认为应该通过使用 Gython 语法来做出决定，摘自 Jython 教程：

v1 -> v2 (or v2 <- v1): selects the directed edge from node v1 to node v2.

我的最终结果应该是：

results = [[v1,v2,v3]]
4

1 回答 1

0

当然，一些图形库会带来这个功能。如果你想手工做，也许这个（又快又脏，Dijkstra 会杀了我）片段可能会给你一些提示：

（我添加了从 v5 到 v2 的另一个顶点，以便获得多个循环）

#! /usr/bin/python3

class Node:
    def __init__ (self, name):
        self.name = name
        self.neighbours = []

    def connect (self, other):
        self.neighbours.append (other)

    def paths (self, path = None):
        path = path [:] if path else []
        if self in path: return [path + [self] ]
        path.append (self)
        paths = []
        for neighbour in self.neighbours:
            paths.extend (neighbour.paths (path) )
        return paths if paths else [path]

    def cycles (self):
            paths = self.paths ()
            return [path for path in paths if len (path) > 1 and path [-1] == self]

    def __repr__ (self):
        return self.name

nodes = [Node ('v1'), Node ('v2'), Node ('v3'), Node ('v4'), Node ('v5') ]
nodes [0].connect (nodes [1] )
nodes [1].connect (nodes [2] )
nodes [2].connect (nodes [0] )
nodes [0].connect (nodes [3] )
nodes [0].connect (nodes [4] )
nodes [4].connect (nodes [1] )

for node in nodes:
    print (node, node.cycles () )
于 2014-03-19T18:25:10.847 回答