Nano Hash - криптовалюты, майнинг, программирование

Как извлечь все пути, начиная с и заканчивая одним и тем же узлом

Я сделал простую сеть:

import networkx as nx
G=nx.Graph()
G.add_node("a")
G.add_nodes_from(["b","c"])

G.add_edge(1,2)
edge = ("d", "e")
G.add_edge(*edge)
edge = ("a", "b")
G.add_edge(*edge)

print("Nodes of graph: ")
print(G.nodes())
print("Edges of graph: ")
print(G.edges())


# adding a list of edges:
G.add_edges_from([("a","c"),("c","d"), ("a",1), (1,"d"), ("a",2)])
nx.draw(G)
plt.show() # display

Я хотел бы составить список всех возможных путей, начиная с и заканчивая одними и теми же узлами для всех узлов. Например, начиная с узла «а» и заканчивая узлом «а», можно:

a-2-1-a, a-c-b-1-a, ....

начиная с узла «2» и заканчивая узлом «2» могут быть:

2-a-1-2, 2-1-d-c-a-2, ....

Как мне это сделать?

networkx
21.01.2019

Ответы:


1

Путь, начинающийся и заканчивающийся в одном узле, называется циклом. Поскольку циклы могут повторяться, всякий раз, когда у вас есть цикл, количество возможных путей бесконечно. Вы можете найти список циклов, которые составляют основу циклов G, вызвав nx.cycle_basis(G).

Если вы хотите явно вычислить все пути без повторений узлов, это можно сделать следующим образом:

import networkx as nx

G=nx.Graph()
G.add_edges_from([("d", "e"), ("a", "b"), ("a","c"), ("c","d"), ("a",1), (1,"d"), ("a",2), (1,2)])

node_to_cycles = {}
for source in G.nodes():
    paths = []
    for target in G.neighbors(source):
        paths += [l + [source] for l in list(nx.all_simple_paths(G, source=source, target=target)) if len(l) > 2]
    node_to_cycles[source] = paths

print(node_to_cycles['a'])

Эта реализация основана на nx.all_simple_paths. Поскольку простой путь имеет только один экземпляр каждого узла, мы ищем пути к каждому соседу узла, а затем объединяем сам узел.

21.01.2019
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..