Поиск циклов во взвешенном ориентированном мультиграфе (Gephi, Jython, Python)

У меня есть ориентированный, мультивзвешенный граф. Я хочу найти циклы, где 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]]

python cycle gephi jython directed-graph
person Aidis    schedule 18.03.2014    source источник
comment
Не могли бы вы опубликовать образец графика для справки?   -  person Hyperboreus    schedule 18.03.2014
comment
Я разместил это. Это в правильном формате? Какие форматы вам подходят?   -  person Aidis    schedule 19.03.2014

Ответы (1)


arrow_upward
0
arrow_downward

Конечно, некоторые графические библиотеки предоставят эту функциональность. Если вы хотите сделать это вручную, возможно, этот (быстрый и грязный, Дейкстра меня убьет) фрагмент может дать вам некоторые подсказки:

(Я добавил еще одну вершину из 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 () )
person Hyperboreus    schedule 19.03.2014
comment
Дейкстра не одобряет ООП! - person Niklas B.; 19.03.2014
comment
@НикласБ. Чак Норрис нашел более короткий путь, чем Эдсгер Дейкстра. - person Hyperboreus; 19.03.2014