Graphs

I posted a couple years ago about my adventures applying various graph visualization tools to Decision Diagrams (DD). This is an interesting problem because DDs have characteristics that don’t apply to other graphs. They are layered1 and each arc from a layer n-1 to layer n has the same direction. Nodes in a layer can be merged or split apart, with those operations generally staying within the same layer2. Sub-diagrams can even be peeled off of parent diagrams during branch-and-bound, while maintaining much of their original structure. ...

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. ...