4

Problem at hand:

Finding separate subgraphs. Update on adding or removing edges.

First I've been thinking about running DFS after every operation from both ends of the edge, but if I keep information about subgraph in the vertices, then adding edge is O(1); you just join subgraphs of both ends.

Now, if I wanted to remove the edge I would still have to DFS/BFS (O(E+V), I believe) and see if there is another path between the ends of the edge. How do I transfer this responsibility from CPU to RAM? Is it worth it?

Edit: System explanation

Based on Circuitry from the game Factorio. Basically I have objects with input and output. Every tick, if input changed, output is recalculated based on criteria within the object. I can connect inputs, outputs and poles (simple vertex) with two types of wiring, each treated separately, but summed up within input. If I connect multiple outputs with same wire, whole network (subgraph) transfers sum of all outputs. On top of that I want to compile a setup of objects into blueprint, which is basically a new object with custom input and output count.

I treat types of wiring as 2 separate graphs, and find 2 types of networks. Network holds references to all outputs (or single summed up output) and inputs. Basically I only need to divide everything into networks. For removing a wire DFS/BFS would probably work just fine, but I've been wondering if there is a memory based solution.

  • Just keep the connected components in memory, then adding edges is going to be constant time (If the connected components are different, they merge, otherwise stays the same). It's quite difficult to figure out whether a connected graph stays connected after several arbitrary edge removals, I'm not sure you can do much better than running a search every time (although you may get something better if you have more knowledge about the behaviour of the system) – Ordous Jun 2 '16 at 18:14
  • @Ordous I know exactly what I want from it (edit), and it's not a necessity, but learning is fun. :) – Whazz Jun 2 '16 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.