GGames, short for Graph Games, is a Python package that provides functions to study games on static or time-varying graphs. The project was first created to help students to answer questions about the cop-number of edge-periodic graph.
The user must have minimum knowledge of graph theory and time-varying graph to enjoy this package. Depending on the field of study of the user, he/she should be familiar with the Cops and Robbers game and the reachability game. More references are available at the end of this document.
The Cops and Robbers game was first introduced independently by Quilliot, and by Nowakowski and Winkler. This game is played by k cops and a robber who place themselves on vertices of a graph and take turns moving along an edge. Cops play first. They win if at any moment a cop occupies the same vertex as the robber. If the robber can avoid capture forever, he wins. A good survey on the subject has been written by Bonato and Nowakowski.
There exist a lot of different variants of this game. One involves playing on time-varying graphs: more specifically, on discrete ones. This variant was first introduced by Erlebach and Spooner. Because of its recency, a lot of questions about it have yet to be answered.
The reachability game is played by two players, Player 0 and Player 1, on a graph. The set of vertices is partitioned into two sets, S0 and S1. A token is placed on a vertex of the graph. When the token is on a vertex of S0, Player 0 moves the token to an adjacent vertex. Player 1 does the same if the token is on a vertex of S1. There is also a subset of S1, F. Player 0 wins if the token occupies a vertex of F, and Player 1 wins if he can avoid that forever. Because many important problems can be reduced to a reachability game, this topic is constantly being studied. To learn more about reduction and the theory of computation, a nice and short introduction on the reachability game has been written by Berwanger.
You can easily install the package via pip with the following command:
pip install ggamesor you can download the sources. The program requires Python 3.9+. The program probably works on older versions of Python 3.0+, but hasn't been tested.
GGames can be used by importing it into a Python session.
from ggames import cop_robber_game as crg
# Create a cycle of length 4.
V = list(range(4))
E = [(i, (i+1)%4) for i in range(4)]
print(crg.is_kcop_win(V, E, k=1)) # prints False
print(crg.is_kcop_win(V, E, k=2)) # prints True
# You can add a presence mapping for the edges.
tau = {(0, 1): '1', (1, 2): '001', (2, 3): '1', (3, 0): '1'}
print(crg.is_kcop_win(V, E, tau, 1)) # prints TrueYou can reduce a Cops and Robbers game to a reachability game.
Vgg, Agg = crg.get_game_graph(V, E, tau, 1)
S0, S1, A, F = crg.game_graph_to_reachability_game(Vgg, Agg)By computing the attractor set of the reachability game, you can extract a winning strategy for the winner.
from ggames import reachability_game as rg
attractor = rg.get_attractor(S0, S1, A, F)
current_config_vertex = (0, 2, False, 0)
# ^^ (cop position, robber position, False := cop's turn, time step)
next_moves = rg.get_next_winning_moves(current_config_vertex, A, attractor)
print(next_moves) # prints [(0, 2, True, 0), (1, 2, True, 0), (3, 2, True, 0)]
# ^^ Doesn't give only the best winning strategy.
next_moves = rg.get_next_winning_moves((3, 2, True, 0), A, attractor,
player0_move=False)
print(next_moves) # prints []. The robber will lose in any case.To get more information, see the documentation.
Also, by having a static of an edge-periodic graph into JSON format, a console script can easily be called to answer basic questions.
kcop-win 1 outerplanar_graph.json # prints False
kcop-win 2 outerplanar_graph.json --output output.txt
cat output.txt # prints Truewhere outerplanar_graph.json contains
{
"V": [ 1, 2, 3, 4, 5, 6, 7, 8 ],
"E": [ [1, 2], [1, 8], [2, 3], [2, 4], [2, 8], [3, 4], [4, 5], [4, 6],
[5, 6], [6, 7], [6, 8], [7, 8] ]
}To get help on a console script, you can use the --help arguments.
kcop-win --help # prints the help sectionComputes the game graph where the "k"-cops and robber game takes place on the edge periodic graph (V, E, tau). If "tau" is not specified, then the graph is considered to be static. Returns the list of vertices and arcs of the game graph.
| Parameters | Description |
|---|---|
| V | The list of vertices |
| E | The list of edges |
| tau | The presence function of the edges in E in dict. If the graph is static, defaults to 'None'. |
| k | The number of cops in the game |
Computes and returns a reachable game corresponding to the game graph G = (V_gg, A_gg).
| Parameters | Description |
|---|---|
| V_gg | A list of vertices of a game graph |
| A_gg | A list of edges of a game graph |
Computes if the time-varying graph ("V", "E", "tau") is "k"-cop win by turning the game into a reachability game.
| Parameters | Description |
|---|---|
| V | A set of vertices |
| E | A set of edges |
| tau | A map from E to a set of bit sequences |
| k | The number of cops that play on the time-varying graph |
Computes the attractor set.
| Parameters | Description |
|---|---|
| S0 | A list of vertices |
| S1 | A list of vertices (must be disjointed of S0) |
| A | A sub-list (subset) of S0×S1 ∪ S1×S0 |
| F | A sub-list (subset) of S1 as list. |
Compute a list of next moves that lead to a winning game for the player 0 if "player0_move" with respect to the game on the graph with the set of arcs "A", its attractor set "attractor" and the vertex "current_vertex" the token is on.
| Parameters | Description |
|---|---|
| current_vertex | A vertex |
| A | A list of arcs |
| attractor | A list representing the attractor set. |
| player0_move | A flag meaning that it's Player 0's turn to play.` |
[1] Bondy, J. A. & Murty, U. S. R. (1976). Graph Theory With Applications. North-Holland.
[2] Casteigts, A. (2018). A Journey Through Dynamic Networks (with Excursions). Université de Bordeaux.
[3] Berwanger, D. (2013). Graph games with perfect information [Lecture notes]. ENS Cachan, Cachan.
[4] Bonato, A. & Nowakowski, R. J. (2011). The Game of Cops and Robbers on Graphs. American Mathematical Society. http://dx.doi.org/10.1090/stml/061.
[5] Erlebach, T & Spooner, J. T. (2019). A Game of Cops and Robbers on Graphs with Periodic Edge-Connectivity. arXiv:1908.06828
[6] Quilliot, A. (1978). Jeux et pointes fixes sur les graphes. PhD thesis, University of Paris VI.
[7] Nowakowski, R. & Winkler, P. (1983). Vertex-to-vertex pursuit in a graph. Discrete Mathematics, 32(2-3), 235-239. https://doi.org/10.1016/0012-365X(83)90160-7.
[8] Sipser, M. (2013). Introduction to the Theory of Computation (3rd ed.). Cengage Learning.
Feel free to contribute by adding new modules for other graph games, creating more efficient algorithms for some classes of graphs, or even improving the existing algorithms! For more information on how to contribute to this project, read How to Contribute.
If you have any further questions or want to contribute, feel free to send an email to Gabriel.