Networkx: поиск кратчайшего пути к одному из нескольких узлов в Graph - PullRequest
Новая
       4

Networkx: поиск кратчайшего пути к одному из нескольких узлов в Graph

0 голосов
/ 06 июня 2018

У меня есть график различных мест: 

import networkx as nx

G = nx.Graph()
for edge in Edge.objects.all():
    G.add_edge(edge.from_location, edge.to_location, weight=edge.distance)

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

Есть ли какой-нибудь метод в библиотеке Networkx, чтобы решить это без циклов?Что-то вроде: 

nx.shortest_path(
     G,
     source=start_location,
     target=[first_location, second_location],
     weight='weight'
)

Результатом будет кратчайший путь к first_location или second_location, если оба местоположения относятся к одному и тому же типу.

И есть ли какой-нибудь метод, который также возвращаетдлина пути?

1 Ответ

0 голосов
/ 12 июня 2018

Мы сделаем это в три шага.

  • Шаг 1: Давайте создадим фиктивный график, чтобы проиллюстрировать
  • Шаг 2: нанесите на график граф и узлы цвета, чтобы указать длину ребер испециальные типы узлов (туалеты, входы и т. д.)
  • Шаг 3: Из любого заданного узла (источника) вычислите кратчайший путь ко всем достижимым узлам, затем установите подмножество для интересующих типов узлов и выберите путь с минимальной длиной.

Код, приведенный ниже, определенно может быть оптимизирован, но за ним может быть проще следовать.

Шаг 1: Создать график 

edge_objects = [(1,2, 0.4), (1, 3, 1.7), (2, 4, 1.2), (3, 4, 0.3), (4 , 5, 1.9), 
(4 ,6, 0.6), (1,7, 0.4), (3,5, 1.7), (2, 6, 1.2), (6, 7, 0.3), 
(6, 8, 1.9), (8,9, 0.6)]

toilets = [5,9] # Mark two nodes (5 & 9) to be toilets
entrances = [2,7] # Mark two nodes (2 & 7) to be Entrances
common_nodes = [1,3,4,6,8] #all the other nodes

node_types = [(9, 'toilet'), (5, 'toilet'),
              (7, 'entrance'), (2, 'entrance')]

#create the networkx Graph with node types and specifying edge distances
G = nx.Graph()

for n,typ in node_types:
    G.add_node(n, type=typ) #add each node to the graph

for from_loc, to_loc, dist in edge_objects:
    G.add_edge(from_loc, to_loc, distance=dist) #add all the edges

Шаг 2: Рисоватьграфик 

#Draw the graph (optional step)
pos = nx.spring_layout(G)
nx.draw(G, pos, with_labels=True)
edge_labels = nx.get_edge_attributes(G,'distance')
nx.draw_networkx_edge_labels(G, pos, edge_labels = edge_labels)
nx.draw_networkx_nodes(G, pos, nodelist=toilets, node_color='b')
nx.draw_networkx_nodes(G, pos, nodelist=entrances, node_color='g')
nx.draw_networkx_nodes(G, pos, nodelist=common_nodes, node_color='r')
plt.show()

enter image description here

Шаг 3: создать небольшие функции для поиска кратчайшего пути к типу узла 

def subset_typeofnode(G, typestr):
    '''return those nodes in graph G that match type = typestr.'''
    return [name for name, d in G.nodes(data=True) 
            if 'type' in d and (d['type'] ==typestr)]

#All computations happen in this function
def find_nearest(typeofnode, fromnode):

    #Calculate the length of paths from fromnode to all other nodes
    lengths=nx.single_source_dijkstra_path_length(G, fromnode, weight='distance')
    paths = nx.single_source_dijkstra_path(G, fromnode)

    #We are only interested in a particular type of node
    subnodes = subset_typeofnode(G, typeofnode)
    subdict = {k: v for k, v in lengths.items() if k in subnodes}

    #return the smallest of all lengths to get to typeofnode
    if subdict: #dict of shortest paths to all entrances/toilets
        nearest =  min(subdict, key=subdict.get) #shortest value among all the keys
        return(nearest, subdict[nearest], paths[nearest])
    else: #not found, no path from source to typeofnode
        return(None, None, None)

Тест: 

 find_nearest('entrance', fromnode=5)

производит: 

 (7, 2.8, [5, 4, 6, 7])

Значение: Ближайший «входной» узел из 5 - 7, длина пути - 2,8, а полный путь: [5, 4,6, 7].Надеюсь, это поможет вам двигаться вперед.Пожалуйста, спросите, если что-то не ясно.

...