Re: [boost] BGL question about districting

Subject: Re: [boost] BGL question about districting
From: Andrew Finkenstadt (pbrane_at_[hidden])
Date: 2009-02-26 17:21:33

And boy, wouldn't it be nice if our election districts here in the United
States gave a weighting to least area vs circumference while keeping
population the same within.  Gerrymandering would be over with.
--andy

On Thu, Feb 26, 2009 at 3:43 PM, Barend Gehrels <barend_at_[hidden]> wrote:

> 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
>
>
>
> _______________________________________________
> Unsubscribe & other changes:
> http://lists.boost.org/mailman/listinfo.cgi/boost
>