BGL question about districting
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
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@geodan.nl> 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
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@gmail.com
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.
Thanks! Yes, this helps, these are exactly the right terms. I'll look further and let you know what I find or create. May take a while. Regards, Barend
Barend Gehrels wrote:
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.
What a fun problem! 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. 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. Luke
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
participants (4)
-
Andrew Finkenstadt -
Andrew Sutton -
Barend Gehrels -
Simonson, Lucanus J