# Smithy
*A simple Smith set solver for ranked-choice ballots.* 

The [Smith set](https://en.wikipedia.org/wiki/Smith_set) is the minimal set of election candidates which can beat all others pairwise
(by simple majority ranking preference) - if there is a single winner in the set they are 
guaranteed the standard [Condorcet i.e. Majority winner](https://en.wikipedia.org/wiki/Condorcet_winner) (they beat all others pairwise).

`smithy` identifies the Smith set via graph Strongly Connected Component (SCC) analysis of
the pairwise majority graph using [`rustworkx`](https://www.rustworkx.org/). 
Pairwise majority comparisons scale quadratically in the number of candidates and linearly 
in the number of ballots, while the SCC and condensation graph analysis is 
approximately quadratic in the number of candidates for the dense tournament graphs typical 
of Condorcet elections. Internally, repeated ballots are compressed/cache-counted before 
pairwise evaluation to improve performance over duplicate rankings.
This is all overkill for small elections, but is fun.

Optionally, `smithy` can try to further resolve a nontrivial Smith set (a majoritarian tie or cycle) by running all-paths IRV within the set - at least reducing to an IRV winner set (the set of candidates that win at least one IRV elimination path) within the Smith set that are not only pairwise competitive but can also build competitive plurality
coalitions within the set; in practice this often resolves cycles and is likely to result in a unique delegate (if they win all IRV elimination paths) which can claim a plurality coalition amongst the majority winners. This should identify a winning candidate as the best possible focal point for voluntary coordination; if your elections have other priorities you may want to resolve nontrivial Smith sets differently.


## Usage
`smithy` can be used a few different ways: as a CLI command, via a web form upload, 
or imported as a python package (TODO: a small [GUI](https://doc.qt.io/qtforpython-6/)).


### CLI Command
`smithy` provides a [`click`](https://click.palletsprojects.com/en/stable/) 
CLI command defined in `src/smithycmd.py` which can be invoked a couple of ways:

- The [GitHub Releases Page](https://github.com/tgorordo/smithy/releases) provides standalone
CLI executables bundled using [PyInstaller](https://pyinstaller.org/en/stable/index.html)
for linux and windows on `x86_64` and linux on `aarch64`. Downloading the appropriate
executable should give you access to the `smithycmd` CLI command.

- Alternatively, if you are using `uv` (see [Development](#Development)), you can invoke 
this in your shell as `uv run src/smithycmd.py [...]` from within the repo after cloning it locally.

In either case, the command expects the same argument structure:
```bash
$ uv run src/smithycmd.py --help
Usage: smithycmd.py [OPTIONS] BALLOTS

  Compute the Smith set from a box of ranked-choice ballots -- .csv or
  .xls(x).

  The Smith set is the minimal set of candidates which can beat all others
  pairwise (simple ranking majority) - if there is a single winner in the set,
  they are guaranteed the Condorcet i.e. Majority winner.

Options:
  -b, --show-ballots  Show relevant ballots (after selections).
  -p, --pretty        Pretty-print output.
  --help              Show this message and exit.
```
where the ballots file should be a `.csv` or `.xls`(`x`) whose columns are candidates and whose
rows are numerical RCV ballot rankings (lower number is best, 1st, 2nd, 3rd, etc.).
(see the [web deployment](https://pages.uoregon.edu/tgorordo/files/smithy/src/cgi/form.html)
or `test/` for some examples).

If you want a 'None' option in your election, it should be included as a candidate.

While plain output is the default, so that the command can easily be used in a unix-pipe
or `stdio` workflows, it can also pretty-print its output for your reading pleasure
using [`rich`](https://rich.readthedocs.io/en/stable/introduction.html) if you pass it the 
`--pretty` (or `-p`) flag. Whether to show the input ballots during output is also
controlled by a corresponding flag.


### UOregon CGI Application
[**This** `pages.uoregon.edu` page](https://pages.uoregon.edu/tgorordo/files/smithy/src/cgi/form.html)
hosts a [CGI form](https://service.uoregon.edu/TDClient/2030/Portal/KB/ArticleDet?ID=43069)
which accepts a `.csv` or `.xls`(`x`) upload of a ballot-box and responds with the resulting
Smith set. The application can typically handle ~100s of candidates and ~10ks of votes 
before running into hosting resource limitations and timing out.

No ballot data is retained on the server after execution.


### Python Package
The `smithy` python package primarily provides the function `smith_set(ballot_box_df)` 
(defined in `src/smithy`), which returns the smith set given a 
[polars](https://docs.pola.rs/api/python/stable/reference/index.html) 
dataframe `ballot_box_df` whose columns are candidates and whose rows are RCV ballots.

e.g. `smithy` can be imported into a [marimo](https://docs.marimo.io/#highlights) notebook
as seen in `test/test_nb.py` - if you're using `uv` you can launch marimo via 
`uv run marimo --edit` and navigate to that example notebook 
(`just marimo` is an available shorthand if you are using the `just` taskrunner -- 
see [Development](#Development)). Cloning `smithy` then working in scratch notebooks within the repo
(e.g. makeing your own `nbs/` directory)
is probably the easiest way to use it if you need to do some of cleanup of the tabular 
data before invocation - just do your cleanup in a notebook using 
[polars](https://docs.pola.rs/py-polars/html/reference/) then pass a tidy dataframe to `smith_set(df)`.

Of course, you can also import into any python script or package for a more involved project
as well:
- If you're using `uv` adding `smithy` should be as simple as
```bash
uv add git+https://github.com/tgorordo/smithy.git
```
- Alternatively, if you're using the more default `pip` you can make it available by
```bash
git clone https://github.com/tgorordo/smithy.git # or submodule add somewhere appropriate in your project
cd smithy
pip install .
```
(if you're new to pip-venvs, 
[this brief guide might be helpful](https://pages.uoregon.edu/tgorordo/courses/uoph410-510a_Image-Analysis/setup.html)).


(The core algorithm is also pretty dead simple, and you could just copy it over into your project too).

## Development
Current development tooling is based on the [`uv`](https://docs.astral.sh/uv/) Python package and
project manager. A [`justfile`](https://github.com/casey/just) lists some common useful
task commands. A simple [`shell.nix`](https://nix.dev/tutorials/first-steps/declarative-shell.html)
can be used to load these tools into a local environment, and you might find
[`direnv`](https://github.com/direnv/direnv) a convenient pairing to `nix` - but just having a 
system-provided `uv` available is more than enough to use and develop `smithy`.



### Formatting, Checking, Testing and Locking
Source can be formatted using [`ruff`](https://docs.astral.sh/ruff/) by running
```bash
uv run ruff format src test
```
(or `just format`)
which should be done before any `git` commit.

This is not really taken full advantage of at the moment, but type hints can be checked
by running [pyright](https://github.com/microsoft/pyright)
```bash
uv run pyright src
```
(or `just check`).

A [pytest](https://docs.pytest.org/en/stable/) test suite can be run as
```bash
uv run pytest -vvv --tb=short --log-cli-level=INFO
```
(or `just test`).

Dependencies can be locked by running
```bash
uv lock
uv pip compile pyproject.toml -o requirements.txt --group dev
```
(or `just lock`).


### Bundling, Releases, Deployment and Cleanup
Bundling the CLI command with [PyInstaller](https://pyinstaller.org/en/stable/index.html) can be done by
```bash
uv run --with-requirements src/smithycmd.py pyinstaller --clean -F src/smithycmd.py
```
(or `just compile`)
which will output an executable `smithycmd` for the CLI in `dist/`, which can be uploaded
to the latest [GitHub Releases Page](https://github.com/tgorordo/smithy/releases).

Deploying the main CGI page at 
[`pages.uoregon.edu/tgorordo/files/smithy/src/cgi`](https://pages.uoregon.edu/tgorordo/files/smithy/src/cgi)
requires shell or SFTP access to [my `pages.uoregon.edu`](https://pages.uoregon.edu/tgorordo),
which you won't get unless you're [me](https://github.com/tgorordo).

If you want to deploy it to your own `pages.uoregon.edu` page, then it should be enough to
ensure you have [CGI set up](https://service.uoregon.edu/TDClient/2030/Portal/KB/ArticleDet?ID=43069)
then SFTP into `sftp.uoregon.edu` and `put -r smithy` (or git clone when `ssh`ed into 
`shell.uoregon.edu`) wherever you'd like in your `public_html`, ensure `smithy.cgi` has
`chmod 755` permissions, 
[standalone install `uv` for your user](https://docs.astral.sh/uv/getting-started/installation/) 
then run `uv sync` from somewhere inside the `smithy` directory. Navigating to the `smithy.cgi`
 file in `pages.uoregon.edu/YOUR_USER/.../cgi/smithy.cgi` should give you a working form.

If you're using `just` you can cleanup working files by running `just clean` and can fully
wipe your `uv` generated `.venv` with `just wipe` (if you want manual versions of those,
check the `justfile` definition). It's probably best to do this before any commit as well,
though probably not required if you're careful or have `.gitignore` updated appropriately
for any changes you made.