Author - Gabriel Pellegrino da Silva
Contributors - Guilherme Lubk do Prado, Lucas Akira Morishita
Lucas Akira Morishita
Run this script to create n random graphs and save it on a specific folder. You'll need to specify how many graphs do you intend to create (num_graphs), how many nodes each graph will have (size), and how many connexions each node will have with its neighbours. The number of connexions per node is a random variable with probability distribution function: Uniform (unif), Poisson (poisson), and Heravy-Tail (heavy). Set this p. function by altering the "dist" parameter in the code. If you choose the Poisson p. function, specify the desired rate "lambda". The graphs will be store in a folder with the following name "test_n_num_graphs_dist_choosenDist". If Poisson p. function has been choosen, the folder will be named "test_n_num_graphs_dist_choosenDist_lam_choosenLambda".
This script is called multiple times by create_graphs.py to really create the graph and save it in a file.
This file contains classes to create a Graph and a Node
Run this script to call two solvers: the one developped by https://github.com/tcsprojects/pgsolver Note that you need to follow the instructions present there to be able to use it. The second solver is ours, fait maison. It tests each of the four proposed solutions for each graph created, counting the execution time, average time per method, and the best performing method for each graph, as well as determining the overall best method timewise.
This is our solver for a parity game, based on https://arxiv.org/abs/1904.12446
Pawel Parys improvements over the zielonka's algorithm, a Quasi-polynomial approach. https://www.mimuw.edu.pl/~parys/publications/2018-parity-algorithm.pdf
On the conclusion of his paper, https://www.mimuw.edu.pl/~parys/publications/2018-parity-algorithm.pdf, Pawel Parys commented another five possible optimization. Some of them are implemented below, note that they are incremental, that said, op4 contain the improvements 1, 2, 3 and 4 and the pawel_parys.py initial improvement described on his paper.
Over the years, some optimizations to Zielonka’s algorithm were proposed. Replace the loopguard WO=∅ by WO=AtrO(G,WO) (which ensures that WO will be empty in the next iteration of the loop).
check whether AtrE(G,Nh) contains all nodes of priority h−1, and if so, to extend Nh by nodes of the next highest Even priority (i.e., h−2). It seems that these optimizations can be applied to our algorithm as well.
A straightforward optimization is to decrease pO and pE to |G| at the beginning of every recursive call.
One can also observe that the call to SolveO in line 13 (with the full precision) gets the same subgame H as the last call to SolveO in line 8 (with decreased precision). A very rough idea is to make someuse of the computations performed by the decreased-precision call during the full-precision call.
Zielonka standard implementation with the same improvement as op1.
Zielonka standard implementation with the same improvement as op2.