PyGrates

A functional and lazy mini-framework for local search on combinatorial problems.

About

PyGrates arose out of a research project to explore switching actions in a power grid, or generally, alterations to the topology of a graph: Python for Graph Topology Enumerations. The space of changes to a graph inductively defines a graph of graphs, usually exponentially large and possibly infinite. Besides the specific types of possible changes, which are manifold and not included here, this package defines an interface for their lazy enumeration and filtering.

The goal is general usability for local search on combinatorial problems: rerouting or rescheduling problems, games, or anything with a discrete space of states where the path of intermediate states is relevant. Three features are especially important for this:

A protocol for user-defined state representations with custom logic for enumerating neighboring states, which can be arbitrarily complex and tailored to the problem.
Lazy enumeration functions, making heavy use of Python’s iterator protocol, to be able to pass around objects that logically represent a very large or infinite number of states without evaluating or storing more than necessary.
User-defined filter functions, representing constraints or heuristics, that are applied at intermediate stages of iteration to be able to prune the space of solutions as early as possible.

Install

The package is available from PyPI:

pip install pygrates

For running the tests and building the documentation:

pip install pygrates[test, doc]

Short Example

First, import the package. This example also uses the dataclasses.dataclass decorator from the standard library:

>>> import pygrates as pg
>>> from dataclasses import dataclass

To use the library functions, you need to create a class of coordinates that implements one of the abstract base classes from the pygrates.abc submodule. An instance of this class represents the state of your combinatorial problem. Your implementation provides the logic for iterating over neighboring states in one or more directions.

Here, we implement a coordinate class that behaves like a directed graph: pygrates.abc.DGCoords, with a children and a parents direction. For the sake of example, the coordinates will simply lie on a two-dimensional grid, with the children of a point lying towards the positive x and y directions, and the parents towards the negative x and y directions:

>>> @dataclass(frozen=True)
... class Point2D(pg.abc.DGCoords):
...   x: int
...   y: int
...
...   def children(self):
...     return Point2D(self.x + 1, self.y), Point2D(self.x, self.y + 1)
...
...   def parents(self):
...     return Point2D(self.x - 1, self.y), Point2D(self.x, self.y - 1)

If we now call one of the functions from pygrates.moves on an instance of our coordinate class, we get a lazy iterator with coordinates from one or more directions, up to a certain depth:

>>> coords = pg.descendants(Point2D(0, 0), depth=2)
>>> set(coords) == {Point2D(x=1, y=0), Point2D(x=0, y=1),
...                 Point2D(x=2, y=0), Point2D(x=0, y=2),
...                 Point2D(x=1, y=1)}
True

We can also pass a guard function to the functions in pygrates.moves to filter out coordinates during iteration. Such a function maps from a coordinate instance to a boolean, and is applied before subsequent layers of search:

>>> coords = pg.neighborhood(Point2D(0, 0), 3, lambda p: p.y % 2 == 0)
>>> set(coords) == {Point2D(x=-3, y=0), Point2D(x=-2, y=0),
...                 Point2D(x=-1, y=0), Point2D(x=1, y=0),
...                 Point2D(x=2, y=0), Point2D(x=3, y=0)}
True

Here, we obtain the coordinates on the line y=0, excluding our input coordinate. Some coordinates on the lines y=2 and y=-2 are within the specified depth of three moves, but are not reached because the coordinates it would take to get there are filtered out during iteration.

In real usage, the trivial Point2D class defined above is replaced with a problem-specific state representation: for example, the coordinate class could have a field to store which lines have been taken out of service in a power grid, and two corresponding direction methods could iterate which lines can further be taken out of service and which lines can be put back in service. In addition, there could be other fields and directions in the coordinate class to represent the state space of the power grid as a whole.

Regardless of the problem, the iteration and filtering functions as shown above will work in the same way, providing a foundation for implementing search strategies.

Development

The source code is hosted on Codeberg: https://codeberg.org/kbvw/pygrates.

License

PyGrates is distributed under the MIT license:

MIT License

Copyright (c) 2022-2023 Koen van Walstijn

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.