Поиск по кратчайшему пути - с использованием типов Edge [NetworkX, igraph]

Question

Я использую DirectGed MultiGraph в качестве структуры данных (между двумя узлами может быть более одного края).

Я хотел бы назначить ребра в разных типах MultiDiGraph. Например, edge (u, v_1) может быть type_1, другое ребро (u, v_2) может быть типом 2.

После сборки этой структуры данных я хотел бы найти кратчайший путь, но путь должен содержать только ребра определенный тип (например, тип 1). Возможно ли это в библиотеках NetworkX или python-igraph?

Answer 1

Как предложено @Gabor Csardi в networkx, для добавления ребер типа 1: добавьте атрибуты type_1 со значением, которое вы хотите, и добавьте атрибут type_2 к максимальному int (чтобы игнорировать в расчете кратчайшего пути, как если бы он не был существовать). Аналогичным образом, сделайте то же самое, чтобы создать край типа_2.

Следующий код показывает простой график, в котором выражается идея о том, что кратчайший путь от 1 до 4 короче через 2 в рельефе type_1 и короче через 3 в edge_2.

g=nx.MultiDiGraph() 
g.add_edge(1,2,type1=2,type2=sys.maxint) # add edge of type 1 
g.add_edge(1,2,type1=sys.maxint,type2=3) # add edge of type 2 
g.add_edge(2,4,type1=2,type2=sys.maxint) 
g.add_edge(2,4,type1=sys.maxint,type2=4) 
g.add_edge(3,4,type1=3,edge_type2=sys.maxint) 
g.add_edge(3,4,type1=sys.maxint,type2=1) 
g.add_edge(1,3,type1=sys.maxint,type2=1) 
print nx.shortest_path(g,1,4,weight='type1') 
print nx.shortest_path(g,1,4,weight='type2') 

Результат:

[1, 2, 4] 
[1, 3, 4] 

Кроме того, прилагается созданный график, чтобы иметь возможность визуализировать его проще.