Metadata-Version: 2.4
Name: reconfillion
Version: 1.1.0
Summary: Solving combinatorial reconfiguration problems.
Author-email: Jun Kawahara <junkawahara@users.noreply.github.com>
License: License
        =======
        Reconfillion is distributed with the MIT License.
        
        ::
        
           Copyright (c) 2024, project "Fusion of Computer Science, Engineering
           and Mathematics Approaches for Expanding Combinatorial
           Reconfiguration"
           Jun Kawahara and other contributors
           All rights reserved.
        
           Permission is hereby granted, free of charge, to any person obtaining
           a copy of this software and associated documentation files (the
           "Software"), to deal in the Software without restriction, including
           without limitation the rights to use, copy, modify, merge, publish,
           distribute, sublicense, and/or sell copies of the Software, and to
           permit persons to whom the Software is furnished to do so, subject to
           the following conditions:
        
           The above copyright notice and this permission notice shall be
           included in all copies or substantial portions of the Software.
        
           THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
           EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
           MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
           NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
           LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
           OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
           WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
        
Project-URL: Homepage, https://github.com/junkawahara/reconfillion
Keywords: graph algorithm,combinatorial reconfiguration,graphillion
Requires-Python: >=3.9
Description-Content-Type: text/markdown
License-File: LICENSE.txt
Requires-Dist: graphillion>=1.7
Provides-Extra: test
Requires-Dist: pytest; extra == "test"
Dynamic: license-file

# Reconfillion - Python interface for combinatorial reconfiguration problems

Reconfillion was released as version 1.0.0 on April 22, 2024. The older version of reconfillion before that date exists on https://github.com/junkawahara/reconfillion-kari , but is not compatible with this version.

Reconfillion is a tool for solving combinatorial reconfiguration problems. It works with [graphillion](https://github.com/takemaru/graphillion), which means that combinatorial reconfiguration problems of graph classes that are supported by graphillion can be solved by reconfillion.

## Requirements

* Python 3.9 or higher.
* [Graphillion version v1.7 or higher](https://github.com/takemaru/graphillion/) is needed.

## License

MIT License

## Quick install

You can install reconfillion via pip.

```
pip install reconfillion
```

## Tutorial

A *combinatorial reconfiguration problem* asks, given a start state `s` and a
goal state `t` (each a subset of elements such as edges or vertices) drawn from a
search space of valid states, for a step-by-step *reconfiguration sequence* that
transforms `s` into `t` so that every intermediate state is valid and consecutive
states differ by a single legal *move*. What counts as a move is decided by the
chosen **model**; reconfillion supports token jumping (`tj`), token
addition/removal (`tar`), and token sliding (`ts`).

Let's consider to solve the spanning tree reconfiguration problem.
In reconfillion (and graphillion), an edge is represented by a tuple of two vertices, and a graph is represented by a list of edges.

```
# complete graph with 4 vertices [1, 2, 3, 4]
graph = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]
```

We import graphillion and reconfillion, and make
GraphSet of all the spanning trees on the graph.

```
from graphillion import GraphSet
from reconfillion import reconf

GraphSet.set_universe(graph) # See the graphillion manual.
spanning_trees = GraphSet.trees(is_spanning = True)
```

### Token jumping (`tj`)

Under the **token jumping** model a single move *removes* one token and *adds*
one token at the same time, so the size of the state stays fixed (`|s|` must
equal `|t|`). Thinking of each element in a state as a token, one move picks up a
token and drops it anywhere else, as long as the resulting state is still valid.

By doing the following method, we can obtain the reconfiguration sequence
between `s` and `t`.

```
s = [(1, 2), (1, 3), (1, 4)] # start spanning tree
t = [(1, 4), (2, 4), (3, 4)] # goal spanning tree

# obtain a reconfiguration sequence between s and t under the token jumping model.
reconf_sequence = reconf.get_reconf_seq(s, t, spanning_trees, model = 'tj')

# obtained [[(1, 4), (2, 4), (3, 4)], [(1, 2), (1, 4), (2, 4)], [(1, 2), (1, 3), (1, 4)]]
```

The returned list is a shortest sequence: consecutive spanning trees differ by
exactly one swapped edge, and the first/last entries are `t`/`s`. If `t` is
unreachable from `s`, `get_reconf_seq` returns `[]`.

### Token addition/removal (`tar`)

Under the **token addition/removal** model a single move *adds* one token or
*removes* one token, so the size of the state changes by one each step (and `s`
and `t` may even have different sizes). To keep states meaningful you bound the
state size with the keyword arguments `lower` and `upper`: every intermediate
state must have size within `[lower, upper]`. Use a lower bound for problems
whose feasible states are downward closed (e.g. independent sets, where you must
keep at least `k` tokens) and an upper bound for upward-closed problems (e.g.
dominating sets). Either bound may be `None`, meaning "no bound in that
direction".

```
from graphillion import VertexSetSet

VertexSetSet.set_universe()
independent_sets = VertexSetSet.independent_sets(graph)

s = [1, 3] # start independent set
t = [2, 4] # goal independent set

# reconfigure under token addition/removal, keeping the size in [1, 2].
reconf_sequence = reconf.get_reconf_seq(
    s, t, independent_sets, model = 'tar', lower = 1, upper = 2)
```

If `s` or `t` has a size outside `[lower, upper]`, `get_reconf_seq` raises
`ValueError`.

### Token sliding (`ts`)

Under the **token sliding** model a single move slides one token along an edge
to an *adjacent* vertex, keeping the state size fixed (so `|s|` must equal
`|t|`). Adjacency cannot be derived from the search space alone, so the `ts`
model requires a `graph` argument: a list of `(a, b)` pairs of adjacent
elements. For independent set reconfiguration this is simply the underlying
graph's edges.

```
from graphillion import GraphSet, VertexSetSet

path = [(1, 2), (2, 3), (3, 4), (4, 5)] # path graph 1-2-3-4-5
GraphSet.set_universe(path)
VertexSetSet.set_universe(list(range(1, 6)))
independent_sets = VertexSetSet.independent_sets(path)

s = [1] # start: a single token on vertex 1
t = [5] # goal:  the token on vertex 5

# slide the token along the path; `graph` defines which moves are legal.
reconf_sequence = reconf.get_reconf_seq(
    s, t, independent_sets, model = 'ts', graph = path)

# obtained [{1}, {2}, {3}, {4}, {5}]
```

The token can only step to a neighbour, so unlike token jumping it walks
`1 -> 2 -> 3 -> 4 -> 5` instead of jumping straight to `5`. Omitting `graph` for
`ts` (or passing it for any other model) raises `ValueError`.

### Farthest state from a single start (`get_longest_shortest_seq`)

Sometimes you have only a start state `s` and want the *hardest* target to reach
from it: a state whose shortest reconfiguration distance from `s` is as large as
possible (the *eccentricity* of `s` in the move graph). `get_longest_shortest_seq`
takes only `s` (no `t`), explores every state reachable from `s`, picks a
farthest one, and returns a shortest sequence to it.

```
# reuse the spanning trees from the tutorial above
s = [(1, 2), (1, 3), (1, 4)] # start spanning tree

# a shortest sequence from s to one of the farthest spanning trees (tj model).
reconf_sequence = reconf.get_longest_shortest_seq(s, spanning_trees, model = 'tj')

# reconf_sequence[0] == s, and its length - 1 is the farthest distance from s.
```

It supports the same `tj`, `tar`, and `ts` models (`tar` takes the same `lower`
/ `upper` bounds; `ts` takes the same required `graph`). If `s` cannot make a
single legal move, `[s]` is returned.

## Tests

A pytest suite under `tests/` exercises the token jumping (`tj`), token
addition/removal (`tar`), and token sliding (`ts`) models on a small set of
independent set reconfiguration instances bundled in `tests/data/`
(a subset of the [Core Challenge 2022 benchmark](https://github.com/core-challenge/2022benchmark);
see `tests/data/README.md`). Install the test dependencies and run pytest:

```
pip install -e ".[test]"
pytest -s tests/
```

The `-s` flag shows a per-instance summary (reachability and sequence length).

## Note

This software (and graphillion) needs a lot of memory to solve problems with large-size instances.

## Authors

Reconfillion has been developed by Jun Kawahara and Hiroki Yamazaki.

## Acknowledgment

This project is/was partially supported by JSPS KAKENHI Grant Numbers JP18H04091, JP20H05794, and JP23H04383.
