Python3 / NetworkX. Как найти только один правильный путь (подграф) в графе по заданному списку известных вершин? - PullRequest
Новая
       28

Python3 / NetworkX. Как найти только один правильный путь (подграф) в графе по заданному списку известных вершин?

0 голосов
/ 24 февраля 2020

Задача:

Дан ориентированный граф с циклами: 

g = nx.MultiDiGraph()
g.add_nodes_from(["<FrFric>","<OpFric>","<OpPull>",'<Spd2>','<Spd1>','<Dist>','<Time>','<Accl>','<Mass>','<FrPull>','<KinEn2>','<KinEn1>','<CfFric>'])
g.add_edges_from([ ("<FrFric>",'<FrPull>'), ("<FrFric>",'<Mass>'), ("<FrFric>",'<Accl>'), ("<FrFric>",'<Cfg>'), ("<FrFric>",'<Mass>'), ("<FrFric>",'<CfFric>'), ("<FrFric>",'<OpFric>'), ("<FrFric>",'<Dist>'),  ("<OpFric>",'<FrFric>'), ("<OpFric>",'<Dist>'), ("<OpFric>",'<OpPull>'), ("<OpFric>",'<KinEn2>'),("<OpFric>",'<KinEn1>'),  ("<OpPull>",'<FrPull>'), ("<OpPull>",'<Dist>'), ("<OpPull>",'<KinEn2>'),("<OpPull>",'<KinEn1>'), ("<OpPull>",'<OpFric>'),  ('<Spd2>','<Spd1>'),('<Spd2>','<Accl>'),('<Spd2>','<Time>'),('<Spd2>','<Dist>'),('<Spd2>','<Spd1>'),('<Spd2>','<KinEn2>'),('<Spd2>','<Mass>'),  ('<Spd1>','<Spd2>'),('<Spd1>','<Accl>'),('<Spd1>','<Time>'),('<Spd1>','<Dist>'),('<Spd1>','<Time>'),('<Spd1>','<Accl>'),('<Spd1>','<Spd2>'),('<Spd1>','<Accl>'),('<Spd1>','<Dist>'),('<Spd1>','<KinEn1>'),('<Spd1>','<Mass>'),  ('<Dist>','<Spd1>'),('<Dist>','<Time>'),('<Dist>','<Accl>'),('<Dist>','<Time>'),('<Dist>','<Spd2>'),('<Dist>','<Spd1>'),('<Dist>','<Accl>'),('<Dist>','<OpPull>'),('<Dist>','<FrPull>'),('<Dist>','<OpFric>'),('<Dist>','<FrFric>'),  ('<Time>','<Spd2>'),('<Time>','<Spd1>'),('<Time>','<Accl>'),('<Time>','<Spd1>'),('<Time>','<Accl>'),('<Time>','<Dist>'),  ('<Accl>','<Spd2>'),('<Accl>','<Spd1>'),('<Accl>','<Time>'),('<Accl>','<Dist>'  ),('<Accl>','<Spd1>'),('<Accl>','<Time>'),('<Accl>','<Spd2>'),('<Accl>','<Spd1>'),('<Accl>','<Dist>'),('<Accl>','<FrPull>'),('<Accl>','<FrFric>'),('<Accl>', '<Mass>'),  ('<Mass>','<FrPull>'),('<Mass>',  '<FrFric>'),('<Mass>',  '<Accl>'),('<Mass>', '<KinEn2>'),('<Mass>',  '<Spd2>'),('<Mass>', '<KinEn1>' ),('<Mass>', '<Spd1>'),('<Mass>','<FrFric>'),('<Mass>',  '<Cfg>'),('<Mass>','<CfFric>'),  ('<FrPull>','<FrFric>'),('<FrPull>',  '<Mass>'),('<FrPull>',  '<Accl>'),('<FrPull>', '<OpPull>'),('<FrPull>',  '<Dist>'),  ('<KinEn2>','<Mass>'),('<KinEn2>',  '<Spd2>'),('<KinEn2>', '<OpPull>'),('<KinEn2>',  '<OpFric>'),('<KinEn2>',  '<KinEn1>'),  ('<KinEn1>','<Mass>'),('<KinEn1>',  '<Spd1>'),('<KinEn1>', '<KinEn2>'),('<KinEn1>',  '<OpPull>'),('<KinEn1>',  '<OpFric>'),  ('<CfFric>','<FrFric>'),('<CfFric>', '<Mass>'),('<CfFric>',  '<Cfg>') ])

Известная начальная вершина для поиска:

Frfri c

Также известны несколько вершин, которые содержатся (должны быть) в пути:

{Dist, KinEn1, KinEn2, FrPull}

Необходимо как-то go обойти .. за наименьшее время O (n ^ 2) O (n) O (logn) и найти правильный путь! те. также необходимо найти связанные вершины, из которых выходят известные вершины, и построить как бы целую цепочку вывода пути!

Для вершины FrFri c вы должны получить такую цепочка пути:

FrFri c => OpFri c => OpPull

те, начиная с FrFri c, мы начинаем поиск. мы встречаем Dist из набора известных вершин .. затем OpFri c - и из него KinEn1, KinEn2 они знают и OpPull .. мы смотрим на OpPull и из него известны FrPull и Dist! и ответ получен!

те, мы пошли путем - и нашли там несколько неизвестных вершин, которые связаны с известными и ... Если вы развернете весь путь, ответ таков:

FrFri c = (((FrPull, Dist), KinEn2, KinEn1), Dist)

И так, как написать такой эффективный алгоритм вывода ?? в Python3 и NetWorkX!

Какие есть варианты ??

...