Re: [boost] BGL question about districting

Subject: Re: [boost] BGL question about districting
From: Andrew Sutton (andrew.n.sutton_at_[hidden])
Date: 2009-02-27 08:22:47

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

That's actually a really good problem. I don't know of any canned algorithms
for this particular problem, however.

You could probably look at it as a special case of graph partitioning where
you're weighting vertices and have the constraint that all vertices have
roughly the same weight. This is somewhat related to flow algorithms (a
partition is a cut).

Another view would be to generate a hypergraph (which the BGL doesn't
natively support) such that each hyperedge is a set of combined districts.
You could write some algorithm that selected a set of disjoint hyperedges
all of similar weight.

Hope that help,

Andrew Sutton
andrew.n.sutton_at_[hidden]