0
\$\begingroup\$

I have a c# unity game (using quikGraph, but I don't believe it fits my needs here). I'm adding wires which connect power sources to power destinations. All devices and wires will be nodes in a graph. I'm looking for a graph structure / accompanying algorithm to efficiently maintain incrementally updated components

Operations which should be quick:

  • When an edge is added, any merged components ('circuits') should be updated
  • When an edge is removed, any separated components ('circuits') should be updated
  • When components are 'updated,' I'll want to operate on each components, then each member of the component
    • I.e. Whenever components merge or separate within the graph, I need to take each affected component, compute the new wattage and update individual devices accordingly
    • As such, maintaining a distinct object/enumerable collection for graph components is strongly preferred

I've considered using quikGraph's IncrementalConnectedComponentsAlgorithm, but it does not support removing edges and the data structure it returns doesn't allow me to easily single out components which need updates (instead, just giving me a mapping of nodes to arbitrary circuits)

Additional info: This is all simple undirected edges, wires are all the same, 'wattage' is always the same for circuits (not trying to do a realistic simulation of electricity here)

First idea I had:

  • Maintain HashSet<Circuit> where 'Circuit' is a HashSet<Node> and have every Node point to its Circuit
  • On edge add, if the nodes have different circuits, make them the same, iterate over the smaller circuit adding all of them to the new one
  • On edge remove, bidirectional bfs to rebuild each circuit, (terminate early if frontiers touch?)
    • THIS IS THE PART that I'm worried about being inefficient
Improve this question
\$\endgroup\$
3
  • 1
    \$\begingroup\$ How big are your graphs & how often are you updating them? Some algorithms aren't efficient in terms of big O(n), but if the n is small &/or you're not trying to run the algorithm every frame, it doesn't matter enough to impact the gameplay. How badly is the BFS hurting gameplay? \$\endgroup\$
    – Pikalek
    Dec 23, 2021 at 4:01
  • 1
    \$\begingroup\$ You might find some helpful concepts in this previous Q&A on maintaining connectedness information for a road network as bridging segments are added/removed. \$\endgroup\$
    – DMGregory ♦
    Dec 23, 2021 at 14:18
  • \$\begingroup\$ @Pikalek fairly large, could be 1000s of nodes. Each wire segment (on a grid) is a segment. I haven't implemented it yet, because I'm still trying to see if there's some off-the-shelf graph structure which would be more appropriate. Might be a pre-mature optimization. \$\endgroup\$
    – pixelpax
    Dec 23, 2021 at 19:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .