Re: [boost] BGL question about districting

Subject: Re: [boost] BGL question about districting
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-03-06 05:30:43

Hi Luke,

> First off your graph is a planar graph, that makes things easier.  Planar graph partitioning is computationally less expensive than general graph partitioning because min-cut is shortest path in a planar graph.  Constructing the graph ought to be trivial if the polygons that the districts are modeled as share a identical edge where they abut.  Just sort the edges with district ID and make graph edges between districts when identical edge geometries end up adjacent in the sorted sequence.
>   
As long as I feed the graph with neighbouring polygons it should result 
in a planar graph... Actually I don't understand why you would sort the 
nodes. However, indeed this is the easy part, I know which polygons 
share borders, so which to feed. In the Netherlands we have 6 islands so 
as soon as I have the graph I will call the BGL "connected components" 
to determine islands, and from the islands determine the nearest 
polygon, then make a "pseudo-edges" between them (so a real edge in the 
graph).
> The hard part is the NP-hard part, of course.  For that I think you can model it as ILP and use a commerical (or free) solver.  It kind of depends on the scale.  You can partition the problem and use the ILP within sufficiently small partitions to recover runtime if the the scale of the problem is too large for the solvers and the optimality you sacrifice is small.  If you aren't concerned too much about optimality you can just implement a huristic partitioning algorithm, perhaps multi-level partitioning, that will be very speedy and produce good quality results.
>   
Thanks for the hint, I planned to solve it using backtracking but will 
have a look to this first.

Regards, Barend

>