Check if a changing undirected graph has at least one circle

Question

I have an undirected graph which initially has no edges. Now in every step an edge is added or deleted and one has to check whether the graph has at least one circle. Probably the easiest sufficient condition for that is

connected components + number of edges <= number of nodes.

As the "steps" I mentioned above are executed millions of times, this check has to be really fast. So I wonder what would be a quick way to check the condition depending on the fact that in each step only one edge changes.

Any suggestions?

One question: if you detect are cycle, are you going to add that edge anyway? — pentadecagon, Jan 29 '14 at 19:25
Is the number of nodes fixed? You didn't mention the initial nodes condition. — A. I. Breveleri, Jan 29 '14 at 19:27
You should definitely try to implement the second half of my answer then, it might just be enough. — Niklas B., Jan 30 '14 at 15:56
Oh and do you get the ops one at a time (online) and need to achieve a certain throughput? Because if you process them in batches that probably allows for a decently efficient algorithm. — Niklas B., Jan 30 '14 at 15:58

Niklas B. · Answer 1 · 2014-01-30T00:32:21.713

If you are keen, you can try to implement a fully dynamic graph connectivity data structure like described in "Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree" by Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup.

When adding an edge, you check whether the two endpoints are connected. If not, the number of connected components decreases by one. After deleting an edge, check if the two endpoints are stil connected. If not, the number of connected components increases by one. The amortized runtime of edge insertion and deletion would be O(log^2 n), but I can imagine the constant factor is quite high.

There are newer result with better bounds. There is also an experimental evaluation of some of the dynamic connectivity algorithms that considers implementation details as well. There is also a Javascript implementation. I have no idea how good it is.

I guess in practice you can have it much easier by maintaining a spanning forest. You get edge additions and non-tree edge deletions (almost) for free. For tree edge deletions you could just use "brute force" in the form of BFS or DFS to check whether the end points are still connected. Especially if the number of nodes is bounded, maybe that works well enough in practice, BFS and DFS are both O(n^2) for dense graphs and you can charge some of that work to the operations where you got lucky and didn't have a lot to do.

score 1 · Answer 2 · answered Jan 29 '14 at 20:27

I suggest you label all the nodes. Use integers, that's easiest.

At any point, your graph will be divided into a number of disjoint subgraphs. Initially, each node is in its own subgraph.

Maintain the condition that each subgraph has a unique label, and all the nodes in the subgraph carry that label. Initially, just give each node a unique label. If your problem includes adding nodes, you might want to maintain a variable to hold the next available label.

If and only if a new edge would connect two nodes with identical labels, then the edge would create a cycle.

Whenever you add an edge, you will connect two previously disjoint subgraphs. You must relabel one of the subgraphs to match the other, which will require visiting all the nodes of one subgraph. This is the highest computatonal burden in this scheme.

If you don't mind allocating more space, you should also maintain a list of labels in use, associated with a count of the nodes carrying that label. This will allow you to choose the smaller subgraph when relabeling.

What you describe can be implemented using a disjoint-set data structure much more efficiently. However, what do you do if an edge is deleted? — Niklas B., Feb 05 '14 at 16:33
Deleting an edge always splits a subgraph into two disjoint subgraphs. If you maintain a node count for each label, then you must visit all the nodes of both new subgraphs, relabeling one of them while counting both. (I was wrong before: this is the highest computational burden in this scheme.) — A. I. Breveleri, Feb 06 '14 at 22:02

score 0 · Answer 3 · edited May 23 '17 at 11:56

0

If you know which two nodes are being connected by the new edge, you could use some sort of path finding algorithm to detect an alternative path between the two nodes. In other words, if a path exists which connects the two nodes of your new edge before you add the new edge, adding the new edge will create a circle.

Your problem then reduces to finding the paths between two given nodes.

edited May 23 '17 at 11:56

Community

1
1

answered Jan 29 '14 at 17:19

philngo

913
7
12

1

I think this is way too slow. – J Fabian Meier Jan 29 '14 at 17:34

Check if a changing undirected graph has at least one circle

3 Answers3