python networkx: создать случайный путь на графе с максимальной длиной, заканчивающейся в его начальной точке - PullRequest
Новая
       9

python networkx: создать случайный путь на графе с максимальной длиной, заканчивающейся в его начальной точке

0 голосов
/ 30 октября 2018

У меня был вопрос относительно networkx и создания случайного пути на этом графике. Однако, скажем, я хочу создать случайный путь на графе, который заканчивается в начале.

Этот пост: ( python networkx: как получить случайный путь? ) объясняет, как вы можете получить случайный путь. Однако использование path = next(nx.all_simple_paths(G, source=0, target=5)) занимает очень много времени для вычисления, поскольку у меня есть график с 5000 узлами и ребрами, и он не учитывает, что путь может иметь максимальную длину и должен возвращаться в исходную точку.

Пример MVC, скажем, я хотел вычислить случайный маршрут от случайной начальной точки, которая может иметь длину 5 или меньше и должна вернуться к исходному начальному значению в конце пути из следующего графика: 

import random
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import math
import pandas as pd
from matplotlib import animation
#from JSAnimation import IPython_display
%matplotlib inline

# initialise graph object
G = nx.Graph()
color_map =[]
G.add_node(1, pos=(1, 0)); color_map.append('r')
G.add_node(2, pos=(2, 0)); color_map.append('r')
G.add_node(3, pos=(3, -1)); color_map.append('r')
G.add_node(4, pos=(3, 1)); color_map.append('r')
G.add_node(5, pos=(4, -1)) ;color_map.append('r')
G.add_node(6, pos=(4, 1)); color_map.append('r')
G.add_node(7, pos=(5, 0)); color_map.append('r')
G.add_node(8, pos=(6, 0));  color_map.append('r')

e = [(1, 2, 1), 
    (2, 3, 1), 
    (2, 4, 2), 
    (3, 5, 5), 
    (4, 6, 2), 
    (5, 7, 1), 
    (4,5, 2),
    (6,3, 1),
     (7,2, 3),
    (6, 7, 2), 
    (7, 8, 1)]

G.add_weighted_edges_from(e)
labels = nx.get_edge_attributes(G,'weight')

nx.draw(G,nx.get_node_attributes(G, 'pos'))
nx.draw_networkx_edge_labels(G,nx.get_node_attributes(G, 'pos'),edge_labels=labels)
nx.draw_networkx_labels(G,nx.get_node_attributes(G, 'pos')

Как бы вы настроили код для этого?

...