Алгоритм упрощения / уменьшения графика

Question

Алгоритм упрощения / уменьшения графика

[Д0] НЕТ. Один простой пример счетчика: шаблоны соответствуют пространствам имен, макросы игнорируют пространства имен (поскольку они являются инструкциями препроцессора).

namespace foo {
    template <class NumberType>
    NumberType add(NumberType a, NumberType b)
    {
        return a+b;
    }

    #define ADD(x, y) ((x)+(y))
} // namespace foo

namespace logspace 
{
    // no problemo
    template <class NumberType>
    NumberType add(NumberType a, NumberType b)
    {
        return log(a)+log(b);
    }

    // redefintion: warning/error/bugs!
    #define ADD(x, y) (log(x)+log(y))

} // namespace logspace

0

graph graph-theory graph-algorithm

задан AlexT 2 March 2019 в 02:23

1 ответ

Другие вопросы по тегам:

graph graph-theory graph-algorithm

Похожие вопросы:

score 0 · Answer 1

Вы ищете что-то нестандартное или алгоритмические идеи о том, как реализовать это самостоятельно? Я могу помочь вам с последним.

То, что вы хотите сделать, называется сжатие вершин, которые имеют ровно 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. [ 1110]

Простое итеративное выполнение до тех пор, пока не останется степень вершины 2, преобразует граф на первом изображении в граф на втором.

Точные детали реализации, конечно, будут зависеть от того, какую структуру данных вы используете для представления своего графа в Python (или любого другого языка, который используется).