## Efficient graph based networks (electronics and transport)

orwell
Member

Posts: 778
Joined: Wed Jun 24, 2015 18:45
Location: Raxacoricofallapatorius
GitHub: orwell96
IRC: orwell96_mt
In-game: orwell

### Re: Efficient graph based networks (electronics and transpor

I have plans for an advanced electrics mod (called advelectric) since about a year, that would use exactly that system. There would be "distribution boxes" or other actors that would correspond to Graph nodes and cables between them, forming the graph edges. Each connected sub-graph would then form a "network" of a certain voltage, as it was described here.
However, I've not progressed because I had been obsessed with Advtrains and real-life things.
Lua is great!
List of my mods
I like singing. I like dancing. I like ... niyummm...

neoh4x0r
Member

Posts: 56
Joined: Wed Aug 29, 2018 20:16
GitHub: neoh4x0r

### Re: Efficient graph based networks (electronics and transpor

Nore wrote:Hmmmm, that is a good question. I'm not sure we can even get something even remotely as good with dynamic shortest paths compared to dynamic connectivity; the problem seems much harder. There seems to be no polylogarithmic algorithm, unfortunately...

Pre-calculating the shortest path (or doing so on the fly) would be an intensive cpu-bound operation and depending on the path-finding algorithm would be done in polynomial time: O(n^2) or greater (way too slow).

I personally think the problem would be more approachable and manageable by treating it as an OO (object-oriented) problem; something is passed into a node and this node is responsible for sending it onto the next node such that the passage from one node to next would eventually narrow-down to the ultimate destination.

If the shortest path is still needed at that point, then the algorithm for selecting the next-best node is greatly simplified.

Previous