2
$\begingroup$

This puzzle was inspired by thinking about how to implement a system like Factorio's power grid.

Start with an infinite connected undirected acyclic graph.

  • Graph = A set of nodes (called "vertices") with connections (called "edges") between them.
    • Alternatively: A set of power poles connected by wires.
  • Undirected = Edges are bidirectional; if vertex 1 connects to vertex 2, then vertex 2 also connects to vertex 1 by the same edge.
  • Infinite = The graph has an infinite number of vertices
  • Connected = A path (consisting of 1 or more edges) exists from any vertex to any other vertex
  • Acyclic = No path (consisting of 1 or more edges) exists from any vertex back to itself.

You know the structure of this graph. Even if you can't fit the whole graph in your head at the same time (because it's infinite), given any vertex, you can know what other vertices it is connected to.

After that, an outside entity makes a finite number of modifications to the edges of the graph (e.g. removing or adding edges). Adding edges might make the graph stop being acyclic, removing edges might make the graph stop being connected. You can observe these changes (you know what edges were added or removed), but you cannot influence them or modify the graph yourself.

Design an algorithm such that after any number of modifications is made, you can tell whether or not any pair of vertices remain connected.

The algorithm must complete in finite time in all cases.

$\endgroup$
2
  • $\begingroup$ Does the outside entity make finitely many modifications? $\endgroup$
    – Gareth McCaughan
    Feb 1 at 23:16
  • $\begingroup$ Yes, finitely many modifications. I will add this to the question. $\endgroup$
    – Tim C
    Feb 1 at 23:16

3 Answers 3

4
$\begingroup$

The original graph

is a tree.

Suppose we want to know whether vertices A and B (after finitely many known additions and removals of edges) are connected. Then:

let S consist of A, B, and all vertices that are part of added or removed edges. Search outward from the vertices in S, breadth-first, in the original tree, until you have a single subtree T containing all those vertices. (If d is the maximum distance-in-the-tree between any two of the finitely many vertices in S, then after you have explored to distance d everything you've found will be connected. You don't know ahead of time what d is, but you do know it exists.)

Now

any two vertices in modified-T are connected in the (whole) modified graph if, and only if, they are connected in modified-T. Proof: "if" is trivial; suppose "only if" fails, and let x,y be vertices in modified-T that are connected in the whole modified graph but not in modified-T, chosen so that the distance from x to y is as short as possible. Then the shortest path joining x and y lies entirely outside modified-T, which means it is a path in the original tree. But in the original tree there is exactly one path joining x and y, and it lies entirely inside T: contradiction.

So

we can now test whether A and B are connected by searching only within modified-T, which is finite.

$\endgroup$
2
  • $\begingroup$ Drat. I made the graph infinite in order to try and prevent flood-fill style algorithms. The reduction to finite is clever. I believe there is another algorithm which will allow you to halt the flood fill as soon as you find any member of the modified set from each of the test points, instead of needing to find all of them. I'll post that in a couple days if no one else finds it first. $\endgroup$
    – Tim C
    Feb 1 at 23:49
  • 1
    $\begingroup$ Yeah, I suspected you might have something less pedestrian in mind. It's bedtime now but I'll think about it later unless someone else finds something neat first :-). $\endgroup$
    – Gareth McCaughan
    Feb 2 at 2:45
1
$\begingroup$

It turns out that we can mostly ignore finiteness or lack thereof since the relevant feature, the unique connecting path between any two vertices, is always finite.

Let's look at removals of edges first:

Let us call two vertices sub-connected if their original (unique, finite) connecting path does not contain any of the removed edges. This is clearly an equivalence relation. The equivalence classes are the connected components of the reduced graph and they are all trees. Further, the endpoints of removed edges form a full set of (not necessarily unique) representative vertices.

For any added edge

we can now simply check whether their endpoints reside in different connected components and if so merge those components.

To make this step more concrete: 1. retrieve the original connecting path. 2. check if any of it was removed. 3. if so take the first vertex of the first removed edge and the second vertex of the last removed edge and merge (i.e. mark as merged) the trees they represent.

The final test for connectedness of two arbitrary vertices is similar:

1. retrieve their original connecting path. 2. check whether any of it was removed. If not return yes. 3. check whether the connected components represented by the first vertex of the first removed edge and the second vertex of the last removed edge were marked as merged. If so return yes, if not return no.

$\endgroup$
8
  • 1
    $\begingroup$ Hm, the adding of edges doesn't have to keep the graph as a tree, right. If I added two edges then remove one, how do you know that the result is still a tree or two components with one of them having a cycle? $\endgroup$
    – justhalf
    Feb 2 at 4:36
  • $\begingroup$ @justhalf FIrst thing to note is we are only referencing paths in the original unmodified graph. In particular, we are only using the treeness of the unmodified graph. Further, as the order in which modifications are made is irrelevant we do all the removals first which gives us well defined identifiable connected components and only then we treat additions and whether they merge components or not. $\endgroup$
    – loopy walt
    Feb 2 at 4:49
  • $\begingroup$ Hm, I read the question as that there can be multiple rounds of adding and removing and question answering happening. But yeah, I can see where you're coming from too. But it is true that if addition is done first, this algorithm may fail, right? $\endgroup$
    – justhalf
    Feb 2 at 5:39
  • $\begingroup$ @justhalf The algorithm doesn't even reference the order in which modifications are made; so no, it cannot fail because of that. $\endgroup$
    – loopy walt
    Feb 2 at 5:46
  • $\begingroup$ This is very similar to the algorithm I had in mind when I posted the question. Mathematically, I think they're equivalent - mine would only be more efficient on a computer if the additions and removals had to be processed in real-time (re-ordering not possible). $\endgroup$
    – Tim C
    Feb 2 at 19:32
0
$\begingroup$

Original Solution

Here is the algorithm I had in mind when I posted the question.

During the modification phase, we need to keep track of

Connected components and cycles.
For cycles, we track each as an ordered list of vertices for each cycle which does not include other cycles. A cycle is said to include another cycle if every vertex from the smaller cycle is in the larger cycle.
For connected components, we will consider one vertex as the "canonical" member of the component. As long as every component contains exactly one canonical vertex, we can flood-fill from any vertex and will reach that component's canonical vertex in finite time.

To begin with:

The list of cycles is empty.
All vertices are part of the same component, so there is only a single canonical vertex.

Whenever an edge is added:

If each end is in a different component, combine the components by un-marking the canonical vertex of one of the two components.
If both ends are currently part of the same cycle, split that cycle into two smaller cycles.
Otherwise, add a cycle to the list containing the shortest path from one end to the other that does not include the newly added edge.

Whenever an edge is removed:

If it is part of exactly one cycle, remove that cycle.
If it is part of exactly two cycles, combine those cycles into one larger cycle.
I do not believe it is possible for a single edge to be part of more than two minimal cycles.
If it is not part of a cycle, then it must be creating a new connected component. Flood fill from each end until we find a canonical vertex. Mark the vertex which did not find a canonical vertex as a new connected component.

Whenever a query is issued:

Flood fill from both ends until either both ends find different canonical vertices (disconnected), or the two searches cross eachother (connected).


Commentary

The original problem, as mentioned in the question, is tracking "what's plugged in to what" in a game like Factorio - the player is adding and removing wires, and every time a wire is created or removed, we need to immediately update the network - maybe one of the sub-grids needs to shut down for lack of power, etc.

While examining this problem, I noticed an interesting property:

Every time an edge is added, either the number of minimal cycles increases by 1, or the number of disjoint components decreases by one.
Every time an edge is removed, the reverse happens.

This property is likely well known in graph theory and I'm re-inventing the wheel. I'm sure I could look it up if I knew the proper mathematical name for what I'm calling a "minimal cycle." It would likely be phrased as something like:

Count of vertices = Count of edges + Count of disjoint components - Count of minimal cycles

I wanted to pose a puzzle that would lead people to this property.

Unfortunately, there's a very obvious brute force algorithm (flood filling the entire graph every time a modification occurs) which does not utilize this property. In translating from "programming" to "pure math," I attempted to rewrite the problem so that "too slow" would become "infinitely slow," but I didn't account for ways to reduce the space to finite, nor that it was possible to ignore cycles entirely by processing all additions after all removals.

$\endgroup$
4
  • $\begingroup$ your property follows from the fact that in a tree, the number of vertices = number of edges + 1 $\endgroup$
    – justhalf
    Feb 3 at 4:47
  • $\begingroup$ @justhalf - I would say that that property about trees is a special case of the property I observed: 1 connected component and 0 cycles - but mine's more general and doesn't follow trivially. $\endgroup$
    – Tim C
    Feb 3 at 6:33
  • $\begingroup$ Well, certainly you can say so, since there could be multiple ways of proving it. But since a tree can be defined by using the number of components, edges, and vertices, I'd say the relation between trees (and forest in general) and the number of vertices and edges and the number of trees is the more basic one. The property you observe is this property on forest in general plus allowing non-trees, so yours also includes the number of cycles. $\endgroup$
    – justhalf
    Feb 3 at 8:16
  • 2
    $\begingroup$ Related: en.wikipedia.org/wiki/Planar_graph#Euler's_formula $\endgroup$
    – loopy walt
    Feb 3 at 11:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.