How to bypass the graph without getting hung up on the connection of one node with another?

Question

JavaScript

Good day!

Problem:
There is a set of power plants and a set of houses. Each house can be connected to any number of power plants. The power plant supplies the house with electricity. A house has electricity if it is connected to one or more power stations.

Each power plant is active by default, but can be disabled. A power plant that is deactivated will not generate electricity.

A house can be associated with a house. A house that has electricity also transmits it to all connected houses.

My implementation: https://codesandbox.io/s/electricity-4it7g?file=/s...

Problem:
I connect House1 with Station1. When joining a house to a house, I write to the house object the id of the attached house. Thus, I get that in Dom1 there is a link to Dom2, and in Dom2 there is a link to Dom1. The task before me is how to correctly find out if there is electricity in Dom2 (electricity is connected to Dom1).

// Как это выглядит в тестах
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

The problem is that I can't figure out how to correctly iterate through the houses attached to each other in the method householdHasEletricitywithout getting hung up on checking the same edge and without calling maximum call stack size exceeded along the way . In theory, I understand that I need to create an array in which I must write the checked houses, but this would work if I immediately had a complete graph. And at the moment it happens like this: in Dom1 there is a link to Dom2, I go to Dom2, and there is a link to Dom1.

Any ideas how this can be solved?

Answer 1

Do you have to answer the question about electricity in a particular house as you add edges/vertices to the graph?
If you only need to do tests, then you can first create the whole world, and then ask him about the status of the houses. Moreover, the calculations themselves (bypassing the graph) can be done only once, get data for all houses and then check them.
In this case, it is necessary, as you suggested, to store an array of "attendance" of houses. You can combine it with an array response or house statuses. Your method no longer accepts a specific house as a parameter, but simply counts for all houses. It initially fills the array for all houses and power plants with zeros, which means that there is no electricity in the house. Then a DFS (Deep Walk) or BFS (Breadth Walk) is performed from the power plants that are active. In this case, all visited vertices are marked with 1 in the array. You do not go to already marked vertices, so the algorithm does not loop.
If you absolutely need to find out the status of houses after each graph change, then you can do the same, but it will be slow, because after each change you will bypass the entire graph.
Can be done much faster. If links between houses are only added (but never removed), then a disjoint set system ( DSU ) can be used. Initially, each house and power plant is its own set. In each set, maintain a counter of active power plants (initially 0 for houses, 1 for power plants). This is simple to implement: you have some kind of array of root references whose elements point to themselves only at the root of the set. Get a second array that will store counters for elements at the same indexes. Likewise, the wiki at the link above supports rank.
When adding a wire, you must merge 2 sets. At the same time, recalculate the counter (add the counter of the lower set to the counter of the upper set).
When asking for home status, take the active station counter for its set and check that it is positive. When turning off / on the power plant, change the counter of the corresponding set to +1 or to -1.
This solution will actually run in O(1) for each query and edge addition (using path compression heuristics).
A naive solution with a full graph traversal each time would be O(1) when adding an edge and O(n) when querying.

Answer 2

The algorithm depends on the situation and on the organization of the graph.
If we need to find out the availability of electricity from scratch for an already built network:

1. All operating power plants are considered to have electricity.
   
2. We sort through the lines connected to the operating power plants; they must be collected in a separate queue. Each house at the end of the line that is not yet on the list is listed as having electricity.
   
3. When adding each house, lines connected to these houses are added to the queue.
   
4. When the queue is empty, the list is finally built.
   

If you need to add a line, then we look to see if there is a house with electricity at one end of this line, and a house without electricity at the other end. If house1 had electricity, but house2 did not, then we apply the above algorithm, but already from house2, where it appeared. Well, you also need to do a reverse check.
If the power plant turns on, then we start the search from it.
But if the line breaks or the power plant is turned off, then you have to build the list from scratch.
PS: There are algorithms for dynamic packet routing in data networks (including the Internet). They can clearly handle adding and removing nodes and links between nodes. But they store a lot more information - ie. such algorithms require more memory.
Well, I must add that these algorithms are designed for distributed execution on nodes, and there may be no connection between nodes.