graphlang - graph languages defined by graph grammars

NOTE: This crate is still highly experimental and API changes should be expected! Performance is currently also not a concern. I highly discourage any use except for experiments.

For the API documentation refer to TODO. This project contains a library that can be used to define and use graph grammars as well as some helper functions for generating random graphs given a graph grammar. It also has some predefined ones to aid the creation of custom ones and to play around with. It comes with an extensive test suite[^1] and a good documentation with many examples[^1].

The project also has an application that utilises the library to display generated graphs and graphically create custom ones[^1].

The intermediate format to define and read graph grammars is a simple JSON file.

[^1]: Not yet implemented.

TODO's

The following list contains all crucial things and the

• Library: Better documentation & examples
• Project: Write a useful README.md
• Library: Eventually use the graph_builder-crate
• Application: Lift limitation that the edges can't be labeled
• Application: Add (interactive) gui startoption
• Application: Add graphical force graph plotting

This list denotes 'good-to-have' things that improve the project, but are not necessary:

• Library: Implement a better partial isomorphism algorithm - maybe VL2? Should be a major speedup
• Library: Make it more generic s.t. it is actually usable by other projects
• Library: Reevaluate the public API
• Project: Upload to crates.io s.t. it can be easily used/installed
• Library: Improve performance to the point where it is useful and not only a neat library to try things.

Basic introduction to graph grammars

TODO: DPO-approach - This should be enough s.t. everybody could understand and work with the basic building blocks.

Basic usage of the library

TODO: The documentation also has many examples ( that are actually there instead of just more todos ).

let grammar = graphlang::predefined::string_grammar();
let mut g = grammar.start_graph.clone();

for _ in 0..10 {
  grammar.productions["extend"].apply_inplace(&mut g)?;
}
grammar.productions["finalize"].apply_inplace(&mut g)?;

assert!(grammar.is_valid(&g));

Installation of the binary

To install the application simply run

cargo install graphlang

The application should then be in the binary folder of cargo, which can be added to the PATH variable for convenience.

Basic usage of the binary

The binary uses a graph grammar, that can be specified using a json format or a predefined grammar can be used, and generates a sample graph of the corresponding graph language.

Example:

graphlang input_file.json --output generated -t "10min" -v

This reads the file input_file.json and produces the file generated.dot. The graph is constructed by using the starting graph and applying random productions for 10min or until the graph becomes valid -v(i.e. part of the languege generated by the grammar).

The predefined grammars can be used by

graphlang Ladder3 --output generated -t "1min 30s" -v

The following options are available:

• String: Trivial string grammar
• LadderN: Basically a string with width N

All options of the v1.2 binary:

USAGE:
    graphlang [OPTIONS] <INPUT>

ARGS:
    <INPUT>    Either a JSON file of a graph grammar or the name of a predefined grammar.
               Possible predefined grammars are: String, LadderN; Where N is a positive Integer
               >= 1

OPTIONS:
    -a, --asap                 (*) Quit evolution as soon as the graph is valid w.r.t. the grammar
    -h, --help                 Print help information
    -m, --max <MAX>            (*) Maximal number of productions. Example: `100`
    -o, --output <OUTPUT>      Optional output path. If given a dot-file of the graph is generated
    -t, --timeout <TIMEOUT>    (*) Maximal runtime for graph evolution. Example: `1h 2min 3s 4ns`
    -v, --verbose              Enable additional output
    -V, --version              Print version information

Please note that at least one starred (*) option has to be used.