Напишите функцию, которая реализует алгоритм обнаружения моста - PullRequest
Новая
       17

Напишите функцию, которая реализует алгоритм обнаружения моста

0 голосов
/ 20 сентября 2019

Алгоритм: Алгоритм обнаружения моста

Требуется: подключенный граф G (V, E)

  1. возврат Мостов края

  2. bridgeSet = {}

3.for e (u, v) ε E do

G '= Удалить e из G

Отключено = Ложь;

, если BFS в G', начиная с u, делаетне посещайте v, тогда

Disconnected = True;

end, если

, если Disconnected затем

bridgeSet = bridgeSet U {e}

конец, если

конец для

Return bridgeSet

  1. Импортирует все соответствующие модули / пакеты (например, NetworkX и т. Д.);

  2. Использует функцию functionnetworkx.read_gml, чтобы загрузить сеть персонажей романа романа «Les Misérable».Данные доступны с домашней страницы профессора Марка Ньюмана, которая находится на сайте www-personal.umich.edu/ mejn / netdata /;

  3. Вызывает реализованную функцию обнаружения моста в сети Misérable Les.и печатает все обнаруженные ребра моста, по одному ребру на строку.

Я использовал networkx.Затем прочитайте:

G = nx.read_gml ('lesmis.gml') print (nx.info (G))

У меня есть идея, но я не знаю, как ее реализоватьjupyter: copy затем удалите из копии, чтобы нам не пришлось делать какие-либо уловки при реализации.Мне действительно нужна помощь, и я застрял ...

Пока это мой вывод: Имя: Тип: График Количество узлов: 77 Количество ребер: 254 Средняя степень: 6,5974 Неверно

1 Ответ

0 голосов
/ 20 сентября 2019

В NetworkX уже есть алгоритм поиска мостов: networkx.algorithms.bridges.bridges: 

import networkx as nx

G = nx.fast_gnp_random_graph(30, 0.08, directed=False, seed=1)
list(nx.bridges(G))

[(0, 2), (10, 12), (12, 28), (13, 24), (15, 28), (23, 24)]

Если вам нужноисходный код, вы можете найти его здесь и здесь : 

@not_implemented_for('multigraph')
@not_implemented_for('directed')
def bridges(G, root=None):
    chains = nx.chain_decomposition(G, root=root)
    chain_edges = set(chain.from_iterable(chains))
    for u, v in G.edges():
        if (u, v) not in chain_edges and (v, u) not in chain_edges:
            yield u, v
...