Как уравнять графы?

Question

[artshelom]

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

Есть ли готовые библиотеки для уравнивания на c# или как написать алгоритм если в одном графе циклов много?

Answer 1

[Wataru]

Я так понял, что ребра задают разницу между "высотами" вершин. "получается, что в сумме не равно 0" означает, что конфликтов нет и можно назначить вершинам какие-то высоты, чтобы все ребра были правильными. Я правильно понял условие?

Тогда задача решается простым обходом в глубину или в ширину, как вам угодно. Просто зафиксируйте одну вершину на высоте 0, и проходя по всем ребрам фиксируйте высоты всех остальных вершин. Если ребро ведет уже к зафиксированной вершине, то можно проверить, что высота остается такой же, но в эту вершину, в любом случае, обход больше не заходит.

В конце, если вам надо, чтобы все вершины имели неотрицаиельную высоту, например, надо найти вершину с минимальной высотой, и если она отрицательна, вычесть ее из высот всех вершин.

Обход надо вызывать в цикле, чтобы обошелся весь граф, даже если он несвязный.

Comments

[artshelom]

Я думал обход делать рекурсией. Вопрос в том, что есть ли готовые библиотеки или решения?

[artshelom]

И есть ещё кое-что, это если к одной вершине есть несколько ребер между которыми нету уравновешивания, то получается придется делать несколько обходов. А это боюсь сведется к бесконечности

[Wataru]

artshelom, Вряд ли есть библиотека для этого - обход такой является весьма тривиальным алгоритмом, а задача довольно спецефическая. Любая библиотека, достаточно гобкая чтобы эту конкретную задачу решить, потребует столько вызывающего кода и настроек, что с нуля написать будет быстрее, проще и короче.

>И есть ещё кое-что, это если к одной вершине есть несколько ребер между которыми нету уравновешивания, то получается придется делать несколько обходов. А это боюсь сведется к бесконечности

Не надо делать несколько обходов. Если уровновесить не получается, то это станет заметно на первом же конфликтущем ребре.

Набросок кода на С++, на C# перепишите сами:

// vector<vector<pair<int, int>> edges - ребра. edges[i][j] j-ое ребро из вершины i. first - конец ребра, second - длина ребра.
// heights - массив для ответа.
// was - массив для пометок о пройденных вершинах
bool Dfs(int v, int height, const vector<vector<pair<int, int>> &edges, int heights[], bool was[]) {
  was[v] = true;
  heights[v] = height;
  for (const auto &edge : edges[v]) {
     int end = edge.first;
     int expected_height = height + edge.second;
     if (was[end]) {
       // Конец уже обработан. Проверить на конфликт в этом ребре.
       if (heights[end] != expected_height)
         return false;
    } else {
      // Конец не обработан, обрабатываем
      if (!Dfs(end, expected_height, edges, heights, was))
        return false;
    }
  }
  return true;
}

...
// как вызывать dfs

was[] <- заполнить false для всех вершин
bool good = true;
for (i = 0; i < n; ++i) {
  // вершина была обработана предыдущим обходом.
  if (was[i])
    continue;
  if (!Dfs(i, 0, edges, heights, was)) {
    good = false;
    break;
  }
}

// тут heights[] уже заполнен правильно, если good == true, иначе - в графе неустранимый конфликт.

Можно все массивы сделать глобальными, а не передавать аргументами функции. edges может быть массивом списков структур {конец, длина} или двумя отдельными двумерныим массивами.

Answer 2

[Владимир Олохтонов]

А для чего вам сводить сумму рёбер графа к нулю? И что такое "высота ребра"?