Находя все пути между источником и целью в Graph-Tool, верните ребра вместо вершин

Question

Переполнение стека!

У меня есть ориентированный граф, и мне нужно найти все пути между исходной и целевой вершинами.Между несколькими вершинами есть несколько ребер.Используя graph-tool, можно предложить использовать graph_tool.topology.all_paths(g, source, target), однако списки, содержащиеся в этом вершинном итераторе, предназначены только для вершин;см. некоторые результаты ниже.Из-за того, что между вершинами имеется множество ребер, есть несколько вхождений путей, таких как [ 0 4 8 13] и [0 4 13], и я не могу различить эти пути.

iterator, paths:  [ 0  4  8 13]
iterator, paths:  [ 0  4 13]
iterator, paths:  [ 0  4  8 13]
iterator, paths:  [ 0  4 13]
iterator, paths:  [ 0  4  8 13]
iterator, paths:  [ 0  4 13]

Мне нужны пути в форме ребер, чтобы иметь возможность перебирать свойства ребер вдоль каждого пути.Чтобы решить эту проблему, я могу думать только об одном методе (кроме переписывания больших объемов кода): создании промежуточных вершин, чтобы избежать появления множественных ребер между любыми двумя вершинами.Для любых параллельных ребер между двумя вершинами они будут связаны с каждой своей уникальной промежуточной вершиной, чтобы однозначно определять пути, возвращаемые из graph_tool.topology.all_paths(g, source, target).

Есть ли способ вернуть все пути в виде ребер между исходной и конечной вершинами?

Answer 1

Это было недавно добавлено в Graph-Tool: https://git.skewed.de/count0/graph-tool/commit/5457d04f5f37c7a49e87b67c666c1a865e206b9a

Вам просто нужно передать параметр edges=True:

for p in all_paths(g, u, v, edges=True):
    for e in p:
        print(e)  # e is an edge descriptor

Answer 2

Поиск всех путей довольно затратен в вычислительном отношении (O (N + E), IIRC).Если вас в конечном итоге интересуют комбинации атрибутов данных ваших ребер, то я бы нашел путь на сокращенном графике (без нескольких ребер), а затем посмотрел бы возможные атрибуты данных каждого ребра (это можно сделать за постоянное время).и вычислить возможные комбинации атрибутов данных.Шаг за шагом:

Найдите пути.Преобразовать список узлов в список ребер.

path_edges = zip(path_nodes[:-1], path_nodes[1:])

Создать словарь (dict), сопоставляющий каждое ребро (source, target) со списком атрибутов данных, например, [0.2, 0.7, 42].Каждый атрибут данных соответствует одному многограннику (вероятно, многие из них будут списками длины 1 в вашем случае, так как многогранность кажется редкой из предоставленной вами выборки данных).

Вычислить все комбинации атрибутов данных для всех ребер в пути.

 data = [edge_to_data[edge] for edge in path_edges]
 cartesian_product = itertools.product(*data) # returns an iterator!
 print(list(cartesian_product))

Наконец, примените свою функцию стоимости или что-то еще к списку значений.