Как обойти граф не зацикливаясь на связи одного узла с другим?

Question

[glem1337]

Доброго времени суток!

Задача:
Существует набор электростанций и набор домов. Каждый дом может быть подключен к любому количеству электростанций. Электростанция питает дом электричеством. Дом имеет электричество, если он подключен к одному или нескольким электростанциям.

Каждая электростанция по умолчанию активна, но может быть деактивирована. Электростанция, которая деактивирована, не будет генерировать электричество.

Дом может быть связан с домом. Дом, в котором есть электричество также передает его всем подключенным домам.

Моя реализация: https://codesandbox.io/s/electricity-4it7g?file=/s...

Проблема:
Дом1 я связываю со Станцией1. При присоединении дома к дому, я записываю в объект дома – id присоединенного дома. Таким образом получаю, что в Дом1 лежит ссылка на Дом2, а в Дом2 лежит ссылка на Дом1. Передо мной стоит задача, как правильно узнать, если ли электричество в Дом2 (электричество подключено к Дом1).

// Как это выглядит в тестах
var world = new World();
var household1 = world.createHousehold();
var household2 = world.createHousehold();
var powerPlant = world.createPowerPlant();
world.connectHouseholdToPowerPlant(household1, powerPlant);
world.connectHouseholdToHousehold(household1, household2);
assert.equal(world.householdHasEletricity(household1), true);
assert.equal(world.householdHasEletricity(household2), true); // тут false

Проблема заключается в том, что я не могу придумать, как правильно пробегаться по присоединенным к друг другу домам в методе householdHasEletricity не зацикливаясь на проверке одного и того же ребра и не вызывая попутно maximum call stack size exceeded. В теории я понимаю, что нужно создать массив в который я должен записывать проверенные дома, но такое бы сработало, если бы у меня сразу был полный граф. А в данный момент происходит так: в Дом1 лежит ссылка на Дом2, иду в Дом2, а там ссылка на Дом1.

Есть идеи как это можно решить?

Answer 1

[Wataru]

Вам обязательно отвечать на вопрос об электричесвте в конкретном доме по мере добавления ребер/вершин в граф?
Если вам только тесты надо делать, то можно сначала создать весь мир, а потом поспрашивать его о статусах домов. При чем сами вычисления (обход графа) можно сделать только один раз, получить данные по всем домам и потом их проверить.

В этом случае надо, как вы и предположили, хранить массив "посещенности" домов. Можно совместить его с массивом-ответом или статусами домов. Ваш метод уже не принимает конкретный дом как параметр, а просто считатет для всех домов. Он изначально заполняет массив для всех домов и электростанций нулями, что значит, что электричества в доме нет. Потом выполняется DFS (обзод в глубину) или BFS (обход в ширину) от электростанций, которые активны. При этом все посещенные вершины помечаются 1 в массиве. В уже помеченные вершины вы не ходите, поэтому алгоритм незациклиться.

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

Можно сделать гораздо быстрее. Если связи между домами только добавляются (но ни в коем случае не удаляются), то можно использовать систему непересекающихся множеств (DSU). Изначально каждый дом и электростанция - сами себе множество. В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1). Это просто в реализации: у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества. Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов. Точно также в вики по ссылке выше поддерживатеся rank.

При добавлении провода вы должны слить 2 множества. При этом пересчитайте счетчик (прибавьте счетчик нижнего множества к счетчику верхнего множества).

При запросе на статус дома возьмите счетчик активных станций для его множества и проверьте, что он положителен. При выключении/включении электростанции измените счетчик соответствующего множества на +1 или на -1.

Это решение будет фактически работать за O(1) при каждом запросе и добавлении ребра (если использовать эвристику сжатия путей).
Наивное же решение с полным обходом графа каждый раз было бы O(1) при добавлении ребра и O(n) при запросе.

Comments

[glem1337]

Вам обязательно отвечать на вопрос об электричесвте в конкретном доме по мере добавления ребер/вершин в граф?

Да, условие задачи не изменять тесты и публичный интерфейс класса World

[Wataru]

glem1337, Ну тогда или медленно с обходом в глубину/ширину на каждом запросе или с DSU делайте, как я описал.

[glem1337]

wataru,

В каждом множестве поддерживайте счетчик активных электростанций (изначально у домов - 0, у электростанций - 1).

А зачем у электростанций? Электростанции не присоединяются друг к другу.

у вас есть какой-то массив ссылок root, элеметы которого указывают сами на себя только в корне множества.

Совсем не понятен этот момент. Какого именно множества должен быть массив ссылок, предположительно массив Домов? И где он должен хранится, в классе World? То есть это должен быть массив, где ключ это айди дома, а значение это массив присоединенных к нему домов?

Заведите второй массив, который будет по тем же индексам хранить счетчики для элементов.

Я правильно понял, что подразумевается создание массива в классе World, где ключ это айди дома, а значение это кол-во активных станций?

При добавлении провода вы должны слить 2 множества.

Имеется ввиду присоединение дома к дому? Надо объединить два массива электростанций подключенных к этим домам?

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

Так и сделал. Работает.

householdHasEletricity(householdID) {
    const household = this.households.get(householdID);

    return household.getActivePowerPlants() > 0;
  }

При выключении/включении электростанции измените счетчик соответствующего множества на +1 или на -1.

Сделал. Однако теперь отключается только те дома, которые были напрямую подключены к станции, так как в объекте станции доступны только дома с прямым подключением.

killPowerPlant(powerPlantID) {
    const powerPlant = this.powerPlants.get(powerPlantID);
    const connectedHouseholds = powerPlant.getConnectedHouseholds();

    if (powerPlant.getActiveStatus()) {
      connectedHouseholds.forEach(householdID => {
        const household = this.households.get(householdID);
        household.decrementActivePowerPlants();
      });

      powerPlant.setActiveStatus(false);
    }
  }

  repairPowerPlant(powerPlantID) {
    const powerPlant = this.powerPlants.get(powerPlantID);
    const connectedHouseholds = powerPlant.getConnectedHouseholds();

    if (!powerPlant.getActiveStatus()) {
      connectedHouseholds.forEach(householdID => {
        const household = this.households.get(householdID);
        household.incrementActivePowerPlants();
      });

      powerPlant.setActiveStatus(true);
    }
  }

Посмотрите, пожалуйста на текущую реализацию https://codesandbox.io/s/electricity-4it7g?file=/s... . Правильно ли я реализовал хотя бы часть алгоритма?

Сейчас проходит все тесты, кроме последнего:

describe("Households + Households + Power Plants", function() {
  it("2 Households + 1 Power Plant", () => {
    const world = new World();

    const household1 = world.createHousehold();
    const household2 = world.createHousehold();
    const powerPlant = world.createPowerPlant();

    world.connectHouseholdToPowerPlant(household1, powerPlant);
    world.connectHouseholdToHousehold(household1, household2);

    assert.equal(world.householdHasEletricity(household1), true);
    assert.equal(world.householdHasEletricity(household2), true);

    world.killPowerPlant(powerPlant);

    assert.equal(world.householdHasEletricity(household1), false);
    assert.equal(world.householdHasEletricity(household2), false); // тут все еще true, так как дом питался от дома
  });
});

[Wataru]

> А зачем у электростанций? Электростанции не присоединяются друг к другу.

Дом может быть подключен ко многим электростанциям. Какие-то из них могут быть в последствии выключены. Счетчик активных электростанций в компоненте связности позволяет быстро определять, есть ли в этой компоненте электричество или нет.

> овсем не понятен этот момент. Какого именно множества должен быть массив ссылок, предположительно массив Домов?

У вас граф из домов и электростанций. Заведите массив, в котором ключем может быть id дома или id электростанцыы. Фактически - для всех вершин в графе.

Далее, почитайте ссылку в ответе на DSU в вики. Там заводится массив для всех вершин в графе и хранит ссылку на предстваителя множества или на себя, если эта вершина предствляет свое множество. Это массив root. Можно делать это полем в классе вершины (но электростанции и дома должны описыватся одним и тем же классом). Для счетчиков заведите второй массив с теми же ключами, ну или, опять же, поле в классе вершин. Хранится это все в классе мира.

> Имеется ввиду присоединение дома к дому? Надо объединить два массива электростанций подключенных к этим домам?

Прочтите статью в вики про DSU! Все должно стать понятно. Там для каждой вершины (дом, электростанция) хранится ссылка на представителя множества (или ссылка на себя). Чтобы объеденить 2 множества вы находите их представителей, или корни множеств (рекурсивно пройдясь по ссылкам до цикла). Потом для одного корня сделайте ссылку на второй корень.

Фактически это то же самое, как если бы в графе каждая компонента связности была раскрашенна в свой цвет, и при добавлении ребра (связи дом-дом или дом-электростанция) вы бы перекрашивали одну из объедененных компонет в цвет другой. Но DSU делает это сильно быстрее чем проход по всему массиву и заменение цвета1 на цвет2.

> Имеется ввиду присоединение дома к дому? Надо объединить два массива электростанций подключенных к этим домам?

Вы не сделали самого главного - вы не реализовали DSU.

Советуб сделать так:
- в классе дома храните ссылку на HouseId представителя (изначально равно houseid самого дома).

- напишите рекурсивную функцию типа:

GetRoot(id) {
  h = households.get(householdID)
  if (h.root != id)
    h = GetRoot(h.root);
  h.root = h.id; // эвристика сжатия путей
  return h
}

Она по id дома выдает какой-то дом связанный с этим домом. При этом для всех домов в одной компоненте связности она будет выдвавть один и тот же дом (предствитель множества).

- Для всех станций храните список домов, с которыми они напрямую связанны.

- При подключении дома к станции добавьте дом в список для станции, найдтие представителья множества для дома (функция GetRoot выше) и увеличьте счетчик активных станций у того представителя. Важно, тут мы увеличиваем счетчик только у одного дома из всех, с которыми эта станция связанна. Но именно этот дом будет находиться для всех остальных домов функцией GetRoot.

- при соединении двух домов найдите из корни функцией GetRoot.
Если корни - один и тот же дом, то можно ничего не делать. Вы соединили уже связанные дома. Если они разные, то сделайте h1.root = h2; h2.counter += h1.counter. Опять же, важно, что тут вы не сами соединяемые дома меняете, а то, что GetRoot вернуло.

- при запросе на статус дома - найдите корень через GetRoot и посмотрите у него counter.

- при изменении статуса электростанции пройдитесь по всем связанным с ней напрямую домам (вы их в списке должны хранить уже), найдите представителя через GetRoot, и у него инкриментируйте/декрементируйте счетчик.

[glem1337]

wataru, спасибо большое! Конечный вариант выполненной задачи https://codesandbox.io/s/electricity-4it7g?file=/s... . Может кому-то пригодится.

Answer 2

[Karpion]

Алгоритм зависит от ситуации и от организации графа.

Если нам надо выяснить наличие электричества с нуля для уже построенной сети:

1. Все работающие электростанции считаются - имеют электричество.
   
2. Перебираем линии, подключённые к работающим электростанциям; их надо собирать в отдельную очередь. Каждый дом на конце линии, который ещё не в списке - заносим в список имеющих электричество.
   
3. При добавлении каждого дома - в очередь заносятся линии, подключённые к этим домам.
   
4. Когда очередь стала пустой - список построен окончательно.
   

Если Вам надо добавить линию - то смотрим, есть ли на одном конце этой линии дом с электричеством, а на другом конце - дом без электричества. Если в дом1 имел электричество, а дом2 не имел - то применяем вышеизложенный алгоритм, но уже от дома2, где оно появилось. Ну и обратную проверку тоже надо сделать.

Если включается электростанция - то запускаем поиск от неё.

А вот если рвётся линия или отключается электростанция - то придётся строить список с нуля.

PS: Есть алгоритмы динамической маршрутизации пакетов в сетях передачи данных (в т.ч. в Internet). Они умеют чётко обрабатывать добавление и удаление узлов и связей между узлами. Но они хранят намного больше информации - т.е. такие алгоритмы требуют больше памяти.
Ну и надо добавить, что эти алгоритмы предназначены для распределённого выполнения на узлах, причём связь между узлами может отсутствовать.