Вы ищете что-то нестандартное или алгоритмические идеи о том, как реализовать это самостоятельно?Я могу помочь вам с последним.
То, что вы хотите сделать, называется сжатие вершин, которые имеют ровно 2 соседей, то есть имеют степень 2.
Для реализации этого выполните следующие действия:
while exists vertex v with degree 2:
- remove v and the 2 outgoing edges
- add a new edge between the neighbours of v
- the weight of the new edge is the sum of the weights of the deleted edge
То есть, если у вас есть следующая часть графика: u ---2--- v ---5--- w и вы примените сокращение, вы получите u ---7--- w.
Простое итеративное выполнение до тех пор, пока не останется ни одной вершины со степенью 2, преобразует граф на первом изображении в граф на втором.
Точные детали реализации, конечно, будут зависеть откакую структуру данных вы используете для представления своего графа в Python (или любом другом используемом языке).