search

MetroCS / redistricting

Experimentation with geopolitical redistricting
GNU Affero General Public License v3.0
5 stars 75 forks source link

Complete TODO in generateDistricts(); in Redistrictor.java #22

Closed Jessica-Trujillo closed 2 years ago

Jessica-Trujillo commented 5 years ago

User Story

Essential components

Story

As a User
I want the TODO in generateDistricts() in Redistrictor.java to be completed so that the program can distinguish contiguity of a district

Acceptance Criteria

The product correctly addresses contiguity

Scenario 1
Given The the region to be redistricted and the number of districts for the region when the program runs then it will create a set of properly-contiguous districts matching the parameters

Supporting Information

Refer to Redistrictor.java method generateDistricts()

Dependencies

Depends On

Bug #60

Dependents

N/A

Jessica-Trujillo commented 5 years ago

Please assign to Fred and Zach

jody commented 5 years ago

Please provide the GitHub ID for "Zach".

Jessica-Trujillo commented 5 years ago

GitHub ID is @zmorlan1

jody commented 4 years ago

Contiguity aspect addressed by PR #44.

Title and acceptance criteria of this UserStory is more general, although the rationale was focused on contiguity only.

Will keep this issue open since there is still a TODO (dealing with the potential for non-rectangular or "snaked" districts).

Estrada303 commented 4 years ago

Can we get this issue assigned to Ernesto, Joaquin, and Jonathan.

Also it seems that there are two issues here: 1. Testing to make sure the districts are all contiguous 2. Allow for non square sets of locations.

jody commented 4 years ago

Did the assignment to @Estrada303 . Need to know the GitHub identities for others. Best to use the @ form to ensure the right ID.

Estrada303 commented 4 years ago

@JonathanGrant92 @JA2016

jody commented 4 years ago

Have tried to add @JonathanGrant92 and @JA2016 but can't do that unless they themselves have posted a comment to this issue. I'm sorry for not knowing that restriction earlier.

nicholasmatthews-dev commented 3 years ago

Is this issue still active? I'd like to be assigned to this issue. I have an idea of how to solve this issue using a graph-based approach.

jody commented 3 years ago

I'd like to be assigned to this issue. I have an idea of how to solve this issue using a graph-based approach.

Sounds good; I assume this is on behalf of your team. (Note that I cannot add additional individuals to an issue unless they themselves have made a comment directly on the issue.)

Please provide an estimate of effort and/or targeted estimate of completion.

nicholasmatthews-dev commented 3 years ago

Yes, this issue is for my team. We'll comment with our names when the other team members begin working on this, it's just me for now.

Also, this post was quite long, so I've split it into two sections. Briefly, is the intent of this issue to check a given district for contiguity in the case of a non-contiguous region, or to generate some different set of valid districts each time it is called?

Checking for Contiguity

I think the contiguity question needs more clarification. After some digging, there does appear to be a method (District.contiguityValid()) which seems to be able to check for contiguity for a district, so that part of the user story is accomplished in the program, just not implemented into Redistrictor.generateDistricts(). Should this issue be interpreted as needing to solve the problem with districts in a non-contiguous region (islands, enclaves, etc.)?

In this case, we might need to redefine what a region is, since it may be impossible to create a valid set of districts in regions which aren't contiguous (for example having an "island" that is smaller than the desired district size). So regions may need to also contain information about how locations are connected (eg, if an island is considered "connected" to another location for the purpose of redistricting). As I was thinking, this may be where a graph is sensible, since it encapsulates the idea of locations being connected without relying on spatial proximity alone.

Providing More Than One Set of Districts

Also, Redistrictor.generateDistricts() also fails to generate any different configurations of districts, it will only generate one configuration for any given region. Is that within the scope of this user story? The acceptance scenario seems to imply this.

This case would probably be an effort 13 story point issue. Although, I still think it's doable, and would be interested in tackling it.

jody commented 3 years ago

The meaning of contiguity is not well-defined in this project. For electoral districts, all parts of the district must be in physical contact with some other part of the district, where waterways are not barriers as long as there is a continuously operated method of transport such as a bridge, tunnel, or ferry. By geometric definitions, this may be a single "point" of contact.

The issue specifically cites a single TODO in the source code, so that is the only objective to be addressed. The method API specifies that it always returns only a single set of districts, empty unless such a set exists. So there is no intent for that method to explore beyond finding the first feasible set of districts.)

The key element of this issue and associated TODO is addressing non-rectangular districts. In particular, this becomes necessary for non-rectangular regions (because the "snake" algorithm always creates districts with contiguous locations when the region itself is rectangular).

What is the confusion about the acceptance scenario? It specifies the appropriate return value as "a set of properly-contiguous districts".

I note that a separate issue, not yet created, involves "compactness", another characteristic of electoral districts: constituents within a district should live as near to one another as possible. (The compactness principle is not well-addressed by the snake algorithm.)

jody commented 3 years ago

"A district is generally thought to be contiguous if it is possible to travel between any two points in a district without crossing into a different district." — Congressional Redistricting Criteria and Considerations

ShayneKaiser commented 3 years ago

We (Team CRIT) believe this issue can be changed to an EPIC. Currently, the way Redistrictor.generateDistricts() functions requires that the region is a rectangle to generate contiguous districts. We believe the best way to deal with the contiguity of a non-rectangular region requires creating a representation of the region as a graph (associating locations to connected locations) and performing operations on this newly generated graph. This is since the representation, associating locations to connected locations, is robust against discontinuous regions, as well as agnostic to the specific distribution of locations, allowing for redistricting to work on any region which can be represented as a graph. This would require changing the whole generateDistricts method/algorithm and adding new helper methods, which can take advantage of this representation.

jody commented 3 years ago

We (Team CRIT) believe this issue can be changed to an EPIC.

Agreed. The "epic" label has been added to this User Story.

jody commented 3 years ago

Currently, the way Redistrictor.generateDistricts() functions requires that the region is a rectangle to generate contiguous districts.

That simplification is definitely one to be addressed. I note that two of the Region constructors already allow arbitrarily-shaped regions. https://github.com/MetroCS/redistricting/blob/ce3be9429c739900d389eb784d7f75180622676e/src/swdmt/redistricting/Region.java#L75-L80 https://github.com/MetroCS/redistricting/blob/ce3be9429c739900d389eb784d7f75180622676e/src/swdmt/redistricting/Region.java#L91-L100

We believe the best way to deal with the contiguity of a non-rectangular region requires creating a representation of the region as a graph (associating locations to connected locations) and performing operations on this newly generated graph.

The current representation does treat regions as graphs, using (x,y) coordinate representation. This representation permits the simplified presumption that adjacency is determinable using that graph representation.

This is since the representation, associating locations to connected locations, is robust against discontinuous regions, as well as agnostic to the specific distribution of locations, allowing for redistricting to work on any region

This appears to concern information that is missing from the data currently stored for Regions, Voters, and Locations.

any region which can be represented as a graph.

Again, Regions are currently represented as graphs, using (x,y) coordinate pairs. This issue appears to be about identifying and representing missing information.

This would require changing the whole generateDistricts method/algorithm and adding new helper methods, which can take advantage of this representation.

Probably more than that given that this involves new information, not just a new representation of existing information.

nicholasmatthews-dev commented 2 years ago

The current representation does treat regions as graphs, using (x,y) coordinate representation. This representation permits the simplified presumption that adjacency is determinable using that graph representation. Again, Regions are currently represented as graphs, using (x,y) coordinate pairs. This issue appears to be about identifying and representing missing information.

I think we concur that this issue is about representing missing information. In fact, our approach so far has implicitly been about handling that information. For instance, the (x,y) co-ordinate system implies an assumption that the space of locations is a grid of squares with length 1, and that each location corresponds to one of those squares. However, it seems that what we really care about in terms of contiguity and redistricting, is how these locations encapsulate ideas of adjacency and contiguity. Thus an approach to the contiguity problem in redistricting could act solely on that information, i.e., which locations are considered adjacent and contiguous with which other locations.

This has been our approach so far in tackling this issue, and the algorithms we have designed for redistricting act on this premise. That is to say, the reason we feel a graph works best to solve this problem is that you can define any idea of contiguity as locations connected to other locations which they are considered adjacent to. Since you can meet the traveling criteria (as per your comment) between adjacent locations, and if you can traverse between all locations in a set of locations in this manner, that set of locations must be contiguous. This is, in terms of a graph, that from any location you can find a path to all other locations in the set of locations that defines that graph. We've simply incorporated the previous assumption (that locations are squares on a grid) into how we build that graph, but that's simply a method to help the algorithm which then partitions the graph, with these partitions then representing contiguous districts.

However, this approach would work for any region, so long as you had information about adjacency. Thus this solution would be robust enough to handle the concept of bridges, waterways, geometry that isn't perfectly orthogonal, or any other number of complications, provided that adjacency information can be supplied. This adjacency information can be created explicitly, as we've done in some of our test classes, or provided implicitly, as the program currently does, by some rule or assumption (such as the grid of squares assumption).

jody commented 2 years ago

Handling this through the Location.isAdjacentTo predicate seems appropriate.

The flexibility to allow different definitions of adjacency could be trivially addressed by subclassing Location for a particular application.

Another approach is along the lines of the design of Comparator.

For example, define an Adjacency<T> interface with the predicate method adjacent(T o1, T o2) that returns a boolean.

Interface Adjacency<T> {
    /**
     * Determines adjacency of two objects.
     * @param o1 the first object
     * @param o2 the second object
     * @return true if the two objects are adjacent; false otherwise.
    public boolean adjacent(T o1, To2);

This allows us to write adjacency code external to the Location class and (in effect) pass the method as a parameter.

The Location.isAdjacentTo predicate could take an optional additional parameter, an Adjacency object whose adjacent predicate will be used in comparing two Location objects. This could be done by overloading the isAdjacentTo method public boolean isAdjacentTo(final Location loc, final Adjacency adj)