Graphs

I attended DPSOLVE 2023 recently and found lots of good inspiration for the next version of Nextmv’s Decision Diagram (DD) solver, Hop. It’s a few years old now, and we learned a lot applying it in the field. Hop formed the basis for our first routing models. While those models moved to a different structure in our latest routing code, the first version broke ground combining DDs with Adaptive Large Neighborhood Search (ALNS), and its use continues to grow organically. ...

Note: A reader pointed out that Union-Find is a very efficient way to accomplish this task. Start there if you have the same problem! Last week, Paul Rubin wrote an excellent post on Extracting a Connected Graph from an existing graph. Lately I’ve been performing related functions on data from OpenStreetMap, though without access to a solver. In my case I’m taking in arbitrary network data and splitting it into disconnected sub-networks. I thought it might be a good case study to show an algorithmic way doing this and some of the performance issues I ran into. ...

Note: This post was updated to work with NetworkX and for clarity. It’s possible this will turn out like the day when Python 2.5 introduced coroutines. At the time I was very excited. I spent several hours trying to convince my coworkers we should immediately abandon all our existing Java infrastructure and port it to finite state machines implemented using Python coroutines. After a day of hand waving over a proof of concept, we put that idea aside and went about our lives. ...