Алгоритм Хортона, который я кодировал, не работает хорошо - PullRequest
Новая
       6

Алгоритм Хортона, который я кодировал, не работает хорошо

0 голосов
/ 10 мая 2019

Я пытался кодировать алгоритм Хортона, чтобы получить минимальную основу цикла для невзвешенного неориентированного 2-связного графа. Однако в основе часто лежат все ребра графа. Полагаю, что программа могла правильно сделать настройку Хортона. Так как исправить мой код для правильной работы? 

for v in G.nodes():
    T = BFS_Tree(G,v)
    for x,y in G.edges():
        path_vtox = nx.shortest_path(T,source=v,target=x)
        path_vtoy = nx.shortest_path(T,source=v,target=y)
        if set(path_vtox) & set(path_vtoy) == {v}:
            cycel = []
            for i in range(len(path_vtox)-1):
                cycle.append(path_vtox[i],path_vtox[i+1])
            for i in range(len(path_vtoy)-1):
                cycle.append(path_vtoy[i],path_vtoy[i+1])
            cycle.append((x,y))
            g = nx.Graph()
            g.add_edges_from(cycle)
            try:
                nx.find_cycle(g)
                Cycles.append(cycle)
            except:
                pass

1 Ответ

0 голосов
/ 13 мая 2019

Спасибо за размещение вопроса.

Сначала несколько комментариев о том, как задавать вопросы и касаться вашего кода: Вы должны написать самостоятельный пример. Это включает рабочий код, проблему с игрушкой и ожидаемый результат. В вашем случае я пропускаю строку, как import networkx as nx вверху. Кроме того, вы ссылаетесь на классы BFS_Tree и Cycles в строках 2 и 17 без их определения ранее. Есть опечатка. В строке 7 должно быть написано cycle вместо cycel. Самое главное, я бы ожидал краткий рабочий пример того, как определяется ваш график G и что вы ожидаете получить в качестве вывода кода.

Теперь я попытаюсь что-то сказать об алгоритме, хотя, возможно, мне не хватает нескольких понятий. Хортон задал циклическую основу самой короткой длины? В общем, я не вижу проблемы, когда базис может покрывать все ребра графа, предполагая, что все ребра являются частью некоторого цикла. Или вы имеете в виду, что базовые элементы покрывают все ребра графа, но должны быть короче? Я не смог найти уникальную ссылку на алгоритм Хортона, и я предполагаю, что вы реализуете его из p. 360 в оригинальная бумага . В этой ссылке Хортон описывает алгоритм как:

1) Найдите минимальный путь P (x, y) между каждой парой точек x, y

2) Для каждой вершины v и ребра {x, y} в графе создайте цикл C (v, x, y) = P (v, x) + P (v, y) + {x, y } и рассчитать его длину. Вырожденные случаи, когда P (v, x) и P (v, y) имеют общие вершины, отличные от v, могут быть опущены.

3) Порядок циклов по весу

4) Используйте жадный алгоритм, чтобы найти минимальную основу цикла из этого набора циклов

В вашем коде я вижу только шаги 1) и 2). 3) тривиально для невзвешенного случая, так как каждый цикл взвешивается по своей длине. Но, похоже, шаг 4) отсутствует. Хортон предлагает решение на странице 362 ссылки.

Надеюсь, это поможет.

...