Parse Graphviz .dot file to Graph?

[mankinskin]

Summary

Extension to petgraph::dot::Dot to parse graph from dot file.

Motivation

There currently is a way to write Graphs to dot files but there is no way to read a Graph from a dot file into your program.

Details

The best I could find was dot_parse which seems to implement a low level parser for dot files. Maybe this can help reading dot files to petgraph graphs.

[TheZalli]

That crate seems kinda WIP and abandoned, no readme or even a repository and the last update was over a year ago. I think it's best to use a custom dotfile parser in this crate, and maybe add it behind a feature gate if it has extra dependencies, like parsing libraries.

[mankinskin]

There is also graphviz-dot-parser, which is also incomplete, but seem a bit better structured. It even already converts to petgraph.

I think it would be good to have a stand-alone crate to parse dot files into memory without having to use petgraph, which might be useful for other projects. Petgraph can then import this crate to parse dot files and build a petgraph::Graph from it.

I have never written a full parser like this, but I used nom before, which is a pretty cool library making heavy use of macros to build pretty ergonomic parsers. This is also used by graphviz-dot-parser.

There is also pest which uses a "parsing expression grammar" file to define the parser, which I haven't used yet.

I think it would be a good start to try to implement this in petgraph using graphviz-dot-parser, and then contribute any missing features over there.

This seems like a good test suite to use: https://github.com/ellson/MOTHBALLED-graphviz/tree/master/rtest/graphs

[TheZalli]

I've used pest in some small script language parser experiments, it's maybe too much for this project and I think nom's better. That crate however looks promising and could be useful, though it's still needing work.

[l-monninger]

Is this still a WIP?

[mankinskin]

I only looked into it but didn't finish through with it.. I have many other to-do's, so I can't say when I can find time for this. I have a project which could use this, so some day I might implement it, but anyone ready to make a move is more than welcome to.

[l-monninger]

Good to know! I may give it a try if my schedule opens up. I have some experience writing parsers.

[daniel-pfeiffer]

Not exactly what you're asking for, but related:
RustDOT: graph! { A -- A -- B; A -- C; }

[daniel-pfeiffer]

I have generalised those ideas and published them as crate rust_dot. Still a plain macro, not yet a proc-macro, but built around that technology. Turns out this now allows parsing strings or files.

[dlight]

I have generalised those ideas and published them as crate rust_dot. Still a plain macro, not yet a proc-macro, but built around that technology. Turns out this now allows parsing strings or files.

Maybe that's not the right place to ask, but since we are in the petgraph issue tracker.. is there a preferred form to convert this into petgraph graphs?

[Bromind]

Hi,
@daniel-pfeiffer, I see that you are working on this. I've been writing a dot parser (dot_parser on crates.io, though the version on crates.io is quite outdated) which sticks quite closely to the formal definition on graphviz website.

I've been thinking for quite some time about extending my library to offer a way to export dot graphs as petgraphs, which seems to be very close to what you are doing (in a nutshell, I'm thinking to add Into<PetGraph> for MyGraph).

Would you be interested in such library ? I see that you have already started writing a parser. I don't know how complete it is, but if need be, it would be fairly easy to use mine. Would you be interested in collaborating on this issue?

[Bromind]

Hi,
to continue on my previous comment, I've now extended my dot parser with proc macros and conversion traits to petgraph's graphs (essentially impl From<DotGraph> for PetGraph). The doc is available here for the general library and here for the macros.

This results in being able to parse dot graph into petgraph with a single (long) line:

use dot_parser_macros::from_dot_string;
use petgraph::graph::Graph as PetGraph;
use dot_parser::canonical::Graph as CanonicalGraph;

let petgraph: PetGraph<_, _> =
    CanonicalGraph::from(from_dot_string!("digraph { A -> B}")).into();

The example above parses the given string at compile time, but the two crates contains alternatives to read the graph from a file, both at compile time or at runtime.

This seems to (more or less) meet the need of the original request (and also the need from #466).

I'm planning to propose a PR shortly, to integrate that better with petgraph. @bluss, reading from the Contributing document, I see you're in charge of deciding whether PR are ok for inclusion. Would you be interested in such PR? If yes, do you have any preference/suggestion regarding where I should implement the thing? (maybe extending the petgraph::dot module, possibly gated with a feature?)