About 20 years into my career, I wrote a tracing system for three phase electrical utility networks to help manage and predict outages and their impact. Basically, each phase was a dendritic n-tree with the phases superimposed on each other because of the way the transmission lines were drawn in GIS (where a three phase line with ground was usually represented as a single line feature with attributes designating which phases were present).
So my solution was to turn each phase’s graph into a binary tree by converting the n-tree to a b-tree where each node has a parent, a child, and a sibling to make traversal easy. Then I gathered all of the nodes into a single ordered array of structs and used array indices to reference parent, child, sibling for each phase.
To trace up, you selecting the starting node and the phase and it would walk up the graph to a source or you could specify a source node and transverse down by phases to create a downstream trace showing all affected customers.
Each node also had protective devices, like fuses and switches, that could be activated/deactivated or predicted as sources of outages.
At the time, I could downstream trace to every customer of a substation in a second or less when most GIS based network traces took 10-15 seconds sometimes. Upstream traces were almost instantaneous. Plus, our customers often converted CAD to GIS and the lines lacked spatial connectivity without a lot of cleanup, but my trace engine could handle disconnected lines and devices that weren’t spatially connected by using attributes.
It was the biggest use of my data structures and algorithms knowledge that I’ve used and it was good enough for a software patent.