[boost] BGL question about districting

Subject: [boost] BGL question about districting
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-02-26 16:43:26

Hi,

We're about an automated districting tool. We want to create Y districts 
from X polygons, all having a specific value (e.g. area or inhabitants), 
where the total value of each district is as similar as possible and 
each district is also as similar as possible. Let's call the value the 
"potential".

Of course this problem is NP-hard so we're glad with the first solution 
or e.g. the first ten solutions.

We thought to implement this by the Boost Graph Library. First we detect 
neighbour relations with our own Geometry Library (using the 
still-to-build "touches" relationship). We've a graph then and can 
divide the graph into subgraphs, each having connected nodes and an 
(nearly) equal "potential".

I've some experience with BGL, having used the "connected_components". 
But I cannot find an appropriate algorithm for this problem, if it is 
available. Actually it even could be a "network flow" algorithm dividing 
the total potential by Y, and starting at some point flowing the 
potential through the graph. But all network flow algorithms seem to be 
on directed graphs. This is an undirected graph.

It it is not possible with a standard BGL algorithm I think we can still 
solve it using BGL and e.g. breadth-sort-first, but just want to verify 
if it is possible or maybe by an unexpected workaround.

Thanks, Barend