inst/enumpart/README.md

In redist: Simulation Methods for Legislative Redistricting

Enumpart

Program that computes the ZDD representing all graph partitions of a given graph using the TdZdd library

This program computes the ZDD representing all graph partitions of a given graph. This program uses the TdZdd library, mainly developed by Dr. Hiroaki Iwashita. The file enumpart.cpp is based on graphillion_example in TdZdd library also written by Dr. Hiroaki Iwashita.

Usage

Build

make

Run

./enumpart <graph_file> [<weight_file>] [some options]

example

The following command constructs the ZDD representing all graph partitions of the 2x2 grid graph.

./enumpart grid2x2.dat

The following command constructs the ZDD representing all graph partitions of the 2x2 grid graph such that the number of components is 2.

./enumpart grid2x2.dat -k 2

The following command constructs the ZDD representing all graph partitions of the 2x2 grid graph with weight indicated by grid2x2_v.dat such that the weight of each component is between 3 and 8.

./enumpart grid2x2.dat grid2x2_v.dat -k 2 -lower 3 -upper 8

The following command constructs the ZDD representing all graph partitions of the 2x2 grid graph with weight indicated by grid2x2_v.dat such that the number of components is 2 and the ratio of the maximum weight to the minimum weight is at most 2.0.

./enumpart grid2x2.dat grid2x2_v.dat -k 2 -ratio 2.0

File format

graph_file

Example:

1 2
1 3
2 3
2 4

The format of is a so-called edge list. One line corresponds to an edge and consists of two integers representing the vertex numbers of the endpoints. In the above example, there are four vertices 1, 2, 3 and 4, and four edges connecting 1 with 2, 1 with 3, 2 with 3 and 2 with 4.

weight_file

Example:

1 2 4 8

The weight_file specifies weights of vertices. Each number is separated by a white space.

output file

If you specify the "-allsols" option, you obtain all the solutions.

For example,

./enumpart grid2x2.dat -k 2 -allsols

outputs the following texts:

3 4
2 4
2 3
1 4
1 3
1 2

A line corresponds to a solution. The numbers in a line represent edge numbers in the corresponding solution. For example, the solution corresponding to the first line "3 4" consists of the 3rd edge "2 3" and the 4th edge "2 4" in "grid2x2.dat". As a result, the graph includes an isolated component (vertex 1) and the other component (consists of vertices 2,3 and 4).

This command and its output indicate that the number of ways how to divide the 2x2 grid graph into two components is six.

The "-comp" option together with "-allsols" outputs solutions in the "component" format as follows.

Command:

./enumpart grid2x2.dat -k 2 -allsols -comp

Output:

0 1 1 1
0 1 0 0
0 1 0 1
0 0 1 1
0 0 1 0
0 0 0 1

A line corresponds to a solution. The i-th number in a line represents which component the i-th vertex belongs to. For example, "0 1 1 1" means that vertex 1 belongs to component 0 and vertices 2,3,4 belong to component 1. If you use "-comp" option, the input graph has vertex numbers 1,2,...,n (n is the number of vertices).

Random sampling

If you specify the "-sample" (with an integer) option, random sampling from all the solutions is carried out and the specified number of solutions are output.

The following command outputs three random solutions.

./enumpart grid2x2.dat -k 2 -sample 3

Storing the constructed ZDD into a file

We can store the constructed ZDD into a file, and then by using the stored ZDD we can enumerate/sample solutions. By adding the "-export" option, enumpart outputs the ZDD to the standard output.

The following command outputs the ZDD to "zdd.txt" file.

./enumpart grid2x2.dat -export >zdd.txt

The "sample" program reads the ZDD file and enumerate/sample solutions.

The following command reads "zdd.txt" file and output all solutions.

./sample grid2x2.dat zdd.txt -allsols

The "sample" program supports the "count", "allsols", "solutions ", "comp", "drawsol ", and "sample " options. Their usages are the same as those of the enumpart program.

Link

• TdZdd
• Jun Kawahara, Takashi Horiyama, Keisuke Hotta, and Shin-ichi Minato, "Generating All Patterns of Graph Partitions within a Disparity Bound," In Proceedings of the 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017), vol. 10167, pp. 119--131, 2017, doi:10.1007/978-3-319-53925-6_10.

redist documentation built on April 3, 2023, 5:46 p.m.