feat(parser): allow parsing graphs from Dot/Graphviz files #653

Bromind · 2024-07-10T16:28:42Z

This is a PR that adds support for Dot/Graphviz parsing. Parsing can happen both at runtime and at compile time (i.e. there are functions and macros).

It fixes #446 and #466 .

Internally, it uses the dot_parser crate (https://crates.io/crates/dot-parser), the implementation is simply a thin wrapper over that crate. This wrapper is a trait (ParseFromDot), introduced in a new module crate::dot::dot_parser. I also added a feature dot_parser to gate this module.

The modifications do not introduce breaking changes.

TODO List (this is just what I have on the top of my head right now, feel free to edit if you think of other items):

Add more tests.
Implement ParseFromDot for existing graph types.
Discuss on exposed (and re-exported) items.
Improve the documentation. (If need be, I'll also improve the doc on the dot_parser crate side).

Bromind · 2024-07-13T15:48:33Z

I added tests for parsing from both a string and an existing file (I used graph-example.dot in the root of the project).

Bromind · 2024-07-13T15:51:55Z

In addition, I implemented ParseFromDot for StableGraph (trivially, there's nothing to do).

bluss · 2024-07-14T16:08:12Z

Cargo.toml

 serde = { version = "1.0", optional = true }
 serde_derive = { version = "1.0", optional = true }
 rayon = { version = "1.5.3", optional = true }
+dot-parser = { version = "0.3", optional = true}


I'm sorry, I don't have full bandwidth to review well, but I hope others do.

dot-parser already optionally depends on petgraph. How does it all interact, when petgraph optionally depends on dot-parser?

Hi bluss,

dot-parser depends on petgraph for a single thing: to export parsed graphs as petgraph's Graph. (see here : https://codeberg.org/bromind/dot-parser/src/branch/master/src/canonical.rs#L156 ).

Basically, this is a poor attempt to do what I intend to do (in a cleaner way) with this PR: to get petgraphs directly from Dot files. However, implementing that in dot-parser is intrinsically bad (imho), since it wouldn't be very flexible in terms of petgraph's version (e.g. as of today, dot-parser exports Graphs from petgraph 0.6.5, which causes issues if the user wants/needs to use an other version).

Eventually, if this PR gets accepted, I'll removed the dependency.

From a more practical aspect, the current status is not so much of a problem, since the PR does not uses the petgraph feature of dot-parser, so petgraph should not even appear down the dependency tree/there is not cyclic dependency issue.

Bromind · 2024-10-20T20:16:06Z

Hi, I've been looking to implement the trait for other graph types. However, I think it is reasonable to have it implemented only for Graph and StableGraph. The reason is that the trait extends Create which has only 3 implementors: Graph, StableGraph and GraphMap. For GraphMap, the node weight must implement Copy, which graph payloads from the Dot-parser library do not.
Therefore, I think it simpler to keep it that way. If a user wants GraphMap, if think it is reasonible to leave them the burden to create a Graph or a StableGraph with the default weights (i.e. dot-parser's Node<...> and Edge<...>), to convert those types into the type they want (which they'll probably do anyways), and then to create a GraphMap from the Graph.

Bromind · 2024-10-20T20:41:41Z

I would like your opinion on re-exported items. So far, this PR re-export/show the following types from the dot-parser crate:

Node and AList, which appear in the weights of Nodes and Edges bounds of Create, when extending the trait with `
AstGraph, i.e. dot_parser::ast::Graph. It is not re-exported, but it is visible in the signature of from_dot_graph.

I'm also thinking about making pest errors directly visible, or nesting them in a wrapper.

Is there any opinion on those re-exports? I haven't think about it too much yet, and I'm not really happy with the current situation. Any suggestion?

Bromind · 2025-03-27T15:08:56Z

So, regarding my previous comment about reexported items from the dot-parser library, I hid them behind type aliases. I think it is a good tradeoff. Also, parsing errors are now used: if an incorrect DOT string/file is used, an error will be displayed. This is simply using errors from the dot-parser lib and hiding them in ad-hoc opaque DotParsingError.

starovoid · 2025-03-30T06:20:01Z

Hi, is it possible to add more tests with graph isomorphism checks? This will make it possible to more strictly check the correctness of parsing in order to avoid possible regressions in the future.

src/dot.rs

Bromind · 2025-03-31T20:37:37Z

Hi, is it possible to add more tests with graph isomorphism checks? This will make it possible to more strictly check the correctness of parsing in order to avoid possible regressions in the future.

I added a few more tests in 8ff3d6e . Only 3 are related to isomorphism (checking isomorphism, isomorphism of subgraph, and not isomorphism), but I also included checks with cyclic graphs.

Bromind · 2025-04-07T20:21:49Z

I just tested the semver-checks failure, and it definitively seems to be a false positive. In a new and separate project, I wrote a dummy graph to implement Create and Build, and both work like a charm. So I think we could ignore this warning.

(For reference: obi1kenobi/cargo-semver-checks#1200)

use petgraph::data::{Build, Create};
use petgraph::visit::{Data, GraphBase, NodeCount};
use petgraph::dot::dot_parser::{ParseFromDot, DotNodeWeight, DotAttrList};
use std::marker::PhantomData;

#[derive(Default)]
struct MyDummyGraph<'a> {
    a: PhantomData<&'a ()>
}

impl<'a> GraphBase for MyDummyGraph<'a> {
    type EdgeId = ();
    type NodeId = ();
}

impl<'a> Data for MyDummyGraph<'a> {
    type NodeWeight = DotNodeWeight<'a>;
    type EdgeWeight = DotAttrList<'a>;
}

impl<'a> NodeCount for MyDummyGraph<'a> {
    fn node_count(&self) -> usize {
        0
    }
}

impl<'a> Build for MyDummyGraph<'a> {
    fn add_node(&mut self, _data: <Self as Data>::NodeWeight) -> <Self as GraphBase>::NodeId {
        return ();
    }

    fn update_edge(
        &mut self,
        _from: <MyDummyGraph as GraphBase>::NodeId,
        _to: <MyDummyGraph as GraphBase>::NodeId,
        _weight: <MyDummyGraph as Data>::EdgeWeight,
    ) -> <Self as GraphBase>::EdgeId {
        return ();
    }
}

impl<'a> Create for MyDummyGraph<'a> {
    fn with_capacity(_n: usize, _e: usize) -> Self {
        Self::default()
    }
}

impl<'a> ParseFromDot<'a> for MyDummyGraph<'a> {}

fn main() {
    println!("Hello, world!");
}

…to statically import them.

The code is modified to accomodate any graph type that implements Create.

…epends on petgraph

0.5.1 fixes a minor bug with token generation of dotgraphs with anonymous subgraphs.

starovoid · 2025-04-08T07:31:54Z

Please apply cargo fmt to satisfy the formatting lint

Resolved

ABorgna

Nice!

src/dot.rs

## 🤖 New release * `petgraph`: 0.8.1 -> 0.8.2 (✓ API compatible changes) <details><summary>Changelog</summary> <blockquote> ## [0.8.2](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.1...petgraph@v0.8.2) - 2025-06-06 ### Bug Fixes - Ford Fulkerson sometimes Panics on StableGraphs ([#793](#793)) - Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical ([#800](#800)) - Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs ([#801](#801)) - Quickcheck random01 function only outputs 0 ([#798](#798)) ### Documentation - Specify that Acyclic::try_udpate_edge may add an edge ([#770](#770)) - Update remove_node doc comment in graphmap.rs ([#663](#663)) - Add examples to minimum spanning tree functions ([#808](#808)) - Minimal typo fix in comments ([#803](#803)) - Update docs.rs ([#807](#807)) - Add note about `StableGraph::edge_indices` behaviour ([#812](#812)) - Clarification of references to nodes and V (refresh #358) ([#814](#814)) - Fix link and mention Dfs and Bfs as special case in examples ([#816](#816)) - Unify algo docs ([#815](#815)) ### New Features - *(parser)* allow parsing graphs from Dot/Graphviz files ([#653](#653)) - Implement `DataMap` for `GraphMap` graphs ([#776](#776)) - Add Johnson's algorithm ([#741](#741)) - Add algorithm to find bridge edges ([#590](#590)) ### Performance - Reuse queue allocation in `maximum_matching` main loop ([#817](#817)) ### Refactor - Fix new clippy warnings ([#791](#791)) </blockquote> </details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: starovoid <prototyperailgun@gmail.com>

## 🤖 New release * `petgraph`: 0.8.1 -> 0.8.2 (✓ API compatible changes) <details><summary>Changelog</summary> <blockquote> ## [0.8.2](https://github.com/petgraph/petgraph/compare/petgraph@v0.8.1...petgraph@v0.8.2) - 2025-06-06 ### Bug Fixes - Ford Fulkerson sometimes Panics on StableGraphs ([petgraph#793](petgraph#793)) - Run Maximal Cliques Quickcheck only on Digraphs which are symmetrical ([petgraph#800](petgraph#800)) - Run Steiner Tree Quickcheck on the connected components to properly support disconnected graphs ([petgraph#801](petgraph#801)) - Quickcheck random01 function only outputs 0 ([petgraph#798](petgraph#798)) ### Documentation - Specify that Acyclic::try_udpate_edge may add an edge ([petgraph#770](petgraph#770)) - Update remove_node doc comment in graphmap.rs ([petgraph#663](petgraph#663)) - Add examples to minimum spanning tree functions ([petgraph#808](petgraph#808)) - Minimal typo fix in comments ([petgraph#803](petgraph#803)) - Update docs.rs ([petgraph#807](petgraph#807)) - Add note about `StableGraph::edge_indices` behaviour ([petgraph#812](petgraph#812)) - Clarification of references to nodes and V (refresh petgraph#358) ([petgraph#814](petgraph#814)) - Fix link and mention Dfs and Bfs as special case in examples ([petgraph#816](petgraph#816)) - Unify algo docs ([petgraph#815](petgraph#815)) ### New Features - *(parser)* allow parsing graphs from Dot/Graphviz files ([petgraph#653](petgraph#653)) - Implement `DataMap` for `GraphMap` graphs ([petgraph#776](petgraph#776)) - Add Johnson's algorithm ([petgraph#741](petgraph#741)) - Add algorithm to find bridge edges ([petgraph#590](petgraph#590)) ### Performance - Reuse queue allocation in `maximum_matching` main loop ([petgraph#817](petgraph#817)) ### Refactor - Fix new clippy warnings ([petgraph#791](petgraph#791)) </blockquote> </details> --- This PR was generated with [release-plz](https://github.com/release-plz/release-plz/). --------- Co-authored-by: github-actions[bot] <41898282+github-actions[bot]@users.noreply.github.com> Co-authored-by: starovoid <prototyperailgun@gmail.com>

bluss reviewed Jul 14, 2024

View reviewed changes

Bromind force-pushed the dot_parser branch from 4f2ea71 to bb2e325 Compare March 27, 2025 09:24

Bromind changed the title ~~Parsing from Dot/Graphviz files~~ feat(parser): allow persing graphs from Dot/Graphviz files Mar 27, 2025

Bromind changed the title ~~feat(parser): allow persing graphs from Dot/Graphviz files~~ feat(parser): allow parsing graphs from Dot/Graphviz files Mar 27, 2025

Bromind marked this pull request as ready for review March 29, 2025 23:50

Bromind changed the base branch from master to release-0.8.0 March 29, 2025 23:56

starovoid mentioned this pull request Mar 30, 2025

feat!: Release 0.8.0 #753

Merged

8 tasks

starovoid added this to the 0.8 milestone Mar 30, 2025

starovoid previously requested changes Mar 31, 2025

View reviewed changes

src/dot.rs Outdated Show resolved Hide resolved

starovoid force-pushed the release-0.8.0 branch from 05afdda to 31cc29c Compare March 31, 2025 19:21

Bromind changed the base branch from release-0.8.0 to master March 31, 2025 20:11

Bromind force-pushed the dot_parser branch from b471f6f to 0911600 Compare March 31, 2025 20:29

starovoid modified the milestones: 0.8, 0.8.1 Apr 1, 2025

Bromind added 8 commits April 7, 2025 22:34

Implement import of graphs from dot files/strings, as well as macros …

76e55fa

…to statically import them.

Move the dot parsing code in a submodule of dot.

24d611c

The code is modified to accomodate any graph type that implements Create.

Use dot_parser 0.3

dfb832e

Wrap dot_parser errors

47f6c4c

Sanitize macro and add test

3f257e8

Add doc for ParseFromDot

63fd893

Fix types for Dot parser

acba5bd

Fix dot parser macros

61b43c4

Bromind added 13 commits April 7, 2025 22:34

Remove incorrect links

1bcae33

Implement ParseFromDot for StableGraph

01dbdcf

Document the two methods of the ParseFromDot trait

d25a886

Uses new version of dot-parser for compatibility with no_std

c62b4e2

Add ill formed test

f808d2b

Hide Dot types behind aliases

57fd0ea

update dot-parser dependency to 0.5.0, which no longer (optionally) d…

bf1e307

…epends on petgraph

Fix config

dec30aa

RustFmt

2a159c4

Fix config in tests

ea3dea2

Add tests (isomorph, cyclic)

845d565

update dot-parser dependency to 0.5.1

f2daada

0.5.1 fixes a minor bug with token generation of dotgraphs with anonymous subgraphs.

Make clippy happy :-)

35579b6

Bromind force-pushed the dot_parser branch from ea2056c to 35579b6 Compare April 7, 2025 20:35

Add feature explanation in the doc

eacf23e

format sources

c4aaef8

starovoid approved these changes Apr 8, 2025

View reviewed changes

starovoid requested a review from ABorgna April 8, 2025 08:08

ABorgna approved these changes Apr 8, 2025

View reviewed changes

src/dot.rs Outdated Show resolved Hide resolved

Bromind added 2 commits April 8, 2025 14:21

Put dot module in subfolder with separate file for dot_parser

6bb7dea

Format code

3d4c8e8

ABorgna added this pull request to the merge queue Apr 8, 2025

Merged via the queue into petgraph:master with commit 8dac216 Apr 8, 2025
10 checks passed

github-actions bot mentioned this pull request Apr 8, 2025

chore: release v0.8.2 #768

Merged

RaoulLuque mentioned this pull request Jun 11, 2025

[Question / Feature Request] Adding support for reading in a graph from a dotfile #466

Open

feat(parser): allow parsing graphs from Dot/Graphviz files #653

feat(parser): allow parsing graphs from Dot/Graphviz files #653

Uh oh!

Conversation

Bromind commented Jul 10, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Bromind commented Jul 13, 2024

Uh oh!

Bromind commented Jul 13, 2024

Uh oh!

bluss Jul 14, 2024

Choose a reason for hiding this comment

Uh oh!

Bromind Jul 17, 2024

Choose a reason for hiding this comment

Uh oh!

Bromind commented Oct 20, 2024

Uh oh!

Bromind commented Oct 20, 2024

Uh oh!

Bromind commented Mar 27, 2025

Uh oh!

starovoid commented Mar 30, 2025

Uh oh!

Uh oh!

Bromind commented Mar 31, 2025

Uh oh!

Bromind commented Apr 7, 2025

Uh oh!

starovoid commented Apr 8, 2025

Uh oh!

ABorgna left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

Bromind commented Jul 10, 2024 •

edited

Loading