Subject: [boost] BGL question about districting
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-02-26 16:43:26
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
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.