Metadata-Version: 2.1
Name: reconfillion
Version: 0.9.9
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.
        
Keywords: graph algorithm,combinatorial reconfiguration,graphillion
Description-Content-Type: text/markdown
License-File: LICENSE.txt

# Reconfillion - Python interface for combinatorial reconfiguration problems

Reconfillion was released as version 1.0.0 on April 8, 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

* Graphillion version [v1.7](https://github.com/takemaru/graphillion/) is needed. Since v1.7 is the latest version and has not been registered into PyPI yet, you need to build it manually.

## License

MIT License

## Install

First, clone and install latest [Graphillion](https://github.com/takemaru/graphillion/),

```
git clone https://github.com/takemaru/graphillion.git
```

and build it according to the [instruction](https://github.com/takemaru/graphillion/?tab=readme-ov-file#installing-from-source).

Then, clone and install reconfillion:

```
git clone https://github.com/junkawahara/reconfillion.git
cd reconfillion
pip install .
```

## Tutorial

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)
```

Then, 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)]]
```

## 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.
