Running the project

A standalone executable is provided in the releases-folder:

• Linux GLIBC
• Linux Musl: For incompatible GLIBC-versions, an executable compiled with MUSL is provided as well. This one runs on the zid-architecture of the university.
• Windows

Run ./project02 --help to see the command-line-options.

Input-file

The input uses the DOT-graph-format. An example-graph looks like this:

digraph lecture {
    1 [player=red]
    2 [player=green]
    3 [player=red]
    4 [player=green]
    5 [player=red, state=final]
    6 [player=green, state=final]
    1->2->3->4->5
    2->1->6->6
    4->3->5
}

The file is provided here.

First the nodes are listed, then the edges. A chain of edges is supported.
For the nodes, two custom attributes are used:

• player=green|red to set which player this node belongs to.
• state=final to set this node as a winning position for the green player.

Output-files

Generating the output-graphs using the --out and --out-solved-options requires a working graphviz installation.

The --out-option renders the input-graph:

The --out-solved render this graph, with winning positions in orange:

Graphviz is not installed on the zid-computers of the university, so this feature can not be used there.

Output

The standard output is sparse, it shows the winning positions of this arena:

> ./project02 lecture.dot
Winning positions are: 1, 2, 3, 4, 5, 6

If more in-depth outputs are desired, they can be gradually enabled via the -v-flag:

• ./project02 lecture.dot -v
• ./project02 lecture.dot -vv

Running in docker

Build the image:

./scripts/docker/build.sh

Running the program requires using a shared folder for the files. The docker_volume-folder is provided for this. Move the input files there, and specify the folder for the output-files as well:

./scripts/docker/run.sh docker_volume/lecture.dot --out docker_volume/out.svg --out-solved docker_volume/out_solved.svg

When done, remove the image:

./scripts/docker/remove.sh

Algorithm

1. All red nodes have their counter initialized by the amount of outgoing edges.
2. The algorithm starts by adding the accepting nodes to the winning set.
3. It then loops over the remaining green nodes in each iteration.
   • It checks if some successor of the green node is in the winning set.
   • If that is the case, the green node is added to the winning set, and removed from the nodes being iterated on.
   • Any time a node is added to the winning set, any red nodes that are a predecessor of this newly added node have their counter reduced by 1.
   • If the counter of a red node reaches 0, it is added to the winning set.
   • The loop runs until no new nodes are added in the pre-step.

Libraries used

The project is written in rust and is using the following libraries:

• graphviz-rust for the (de)serialization of the dot-format, and for the svg-generation.
• clap for the cli.
• tracing for the error, info and debug-outputs.

Git-repo

Can be found here.