ILP Part 64 – BFS, graph connectivity, spanning tree

This is the sixtieth fourth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Last time we actually implemented BFS-like algorithm in the graph with ILP which can be also used for testing graph connectivity (if two nodes are connected transitively) or building any spanning tree. Today a simplified and clear solution for the BFS in ILP. We take this graph:

Graph

Black numbers represent nodes. Green numbers represent edge identifiers (we number edges for simplicity). Red numbers are calculated distances increased by one (to differentiate between no distance and calculated distance, so between zero and one).

The code:

We do the same thing as last time but let’s walk through it again.

First, in lines 3-16 we describe our graph. We specify edges by their ending nodes so for instance line 5 says there is an edge between node zero and node two. Next, in line 18 we transform this to an adjacency list for simplicity.

Next, in lines 20-29 we define variables for nodes. Each node has an identifier (distance from the source), degree (how many edges from the spanning tree it is connected to), flag whether this node is a BFS source, and a number of lower neighbours (neighbours with lower distance to the source).

In lines 31-36 we define variables for edges. Each edge can be included in the path (in the spanning tree) or not.

Finally, we can specify the BFS root in line 38-39 (if needed). That wraps the data preparation, now let’s build constraints.

In lines 41-47 we calculate degrees. For each node we take edges ending in the node and then check if they are included in the spanning tree.

In line 50 we make sure there is one starting point in the graph.

In lines 52-57 we make sure all nodes have positive degree so all of them are included in the spanning tree.

Next, we start building the BFS. In lines 59-66 we specify that distance must increase by one for each node (so neighbours differ by one).

In lines 68-73 we specify that each node has some distance calculated.

In lines 75-84 we count lower neighoburs for each node. We then use this value in lines 86-91 to specify that the BFS root has no lower neighbours (it has the lowest distance) and that inner nodes (lines 93-98) have exactly one lower neighbour (to avoid loops).

Now the crucial part for BFS: in lines 101-102 we sum the identifiers and minimize the result. This is to make sure all nodes have shortest path in graph with loops. If your graph has no loops (is a tree) then you don’t need this constraint as there is exactly one path between all node pairs. Obviously, it’s not required for connectivity so don’t use it if you don’t care about the distnaces.

Finally, we print the solution. It looks like this:

You can check that it matches red numbers in the picture.

Obviously, you can generalize this algorithm same way we did last time to match your needs. However, it is generic enough to be used to build continuous paths between nodes.