GrALoG is tool for visualising and editing
graph-like-structures as well as visualising the results of algorithms
running on them. Through it's plugins GrALoG is hugely
extendable, i.e. plugin-developers can define their own
graph-like-structures and algorithms running on them.
It is written in Java
and should therefore run on most operating
systems and architectures.
It's principle developers are Sebastian
Ordyniak and Stephan Kreutzer with plugins contributed
by Lukas Moll. The project has been supported
by the Deutsche Forschungsgemeinschaft (DFG) grant KR 2898/1-3.
GrALoG already contains a number of predefined plugins that
provide structures and algorithms related to
logic-, games-, automata- and graph-theory. It's main purpose is
to assist research and education related to algorithms
running on graph-like-structures.
-
To assist in teaching, GrALoG provides
methods for visualising the results and runs
of algorithms on graph-like structures.
-
In terms of research, the aim of GrALoG is
to provide a platform or framework in which
graph-like-structures and algorithms running
on them can be implemented easily. Based on the
powerful Java Collection Classes, the graph
library used ( JGraphT ) and a growing number of implemented
features, implementing an algorithm or structure
in GrALoG is sometimes almost as writing
pseudo code.
The Plugins.
GrALoG currently contains the following plugins.
-
Logic. The logic plugin provides
methods for evaluating formulae of the modal
mu-calculus on transition systems and for
evaluating first-order logic formulae on
undirected and directed graphs as well as on
transition systems. The main feature is
that the evaluation of such formulae can be
visualised so as to assist students in
learning to work with these logics.
-
Two-Player-Games.
This module provides structures and algorithms
for a number of two-player-games played
on graphs. Among others it includes
the Discrete-Strategy-Improvement-Algorithm developed
by Jurdzinksi and Vöge for determining
the winner of a parity game. Again, the plugin
provides intuitive means of visualising the way
this algorithm works.
-
DAG-width. This modules provides very
basic algorithms to compute the number of
cops needed in a cops and robber game on
directed graphs and to compute an associated
DAG-decomposition.
-
Finite-State-Automaton.
This modules provides very basic algorithms
and structures related to finite-automaton.
-
Generator. This plugin
provides algorithms to generate
specific structures like paths, circles,
wheels and random structures.
-
Examples. This plugin is
meant as a starting point for
plugin-developers. It provides well-documented
example-algorithms and -structures.