Simple but powerful graph library for Rust

Overview

Graphlib

Build Status Discord Badge Latest Version Documentation

Graphlib is a simple and powerful Rust graph library.


This library attempts to provide a generic api for building, mutating and iterating over graphs that is similar to that of other data-structures found in Rust i.e. Vec, HashMap, VecDeque, etc.

Using Graphlib

use graphlib::Graph;

let mut graph: Graph<usize> = Graph::new();

// Add two vertices to the graph
let id1 = graph.add_vertex(1);
let id2 = graph.add_vertex(2);

// Add an edge between the two vertices
graph.add_edge(&id1, &id2);

assert_eq!(*graph.fetch(&id1).unwrap(), 1);
assert_eq!(*graph.fetch(&id2).unwrap(), 2);

// The graph has 2 vertices and one edge at this point
assert_eq!(graph.vertex_count(), 2);
assert_eq!(graph.edge_count(), 1);

// Remove one of the connected vertices
graph.remove(&id1);

assert_eq!(graph.vertex_count(), 1);
assert_eq!(graph.edge_count(), 0);

Using without std

In Cargo.toml:

[dependencies]
graphlib = { version = "*", features = ["no_std"] }

Contributing

We welcome anyone wishing to contribute to Graphlib! Check out the issues section of the repository before starting out.

License

Graphlib is licensed under the MIT license.

Comments
  • fix: Add capacity api #7

    fix: Add capacity api #7

    fixex #7, though a few points -

    1. Cannot implement Graph::shrink_to() in stable rust (currently only possible in nightly)
    2. Cannot implement Graph::reserve_exact() as Hashbrown cannot implement reserve_exact

    Was able to complete all others with complete documentation and example

    I also added capacity_v() to give more verbose result about Graph capacity complete with example and documentation

    opened by sn99 8
  • Setup for benchmarks complete with travis

    Setup for benchmarks complete with travis

    fixes #1 ~~I still need to figure out the best way for benchmarks and how they should be done but now it's just a matter of creating those functions~~, though running benches on travis could give wrong results but anyhow I have added the script

    opened by sn99 7
  • clippy + rustfmt

    clippy + rustfmt

    Made a few tweaks to the code that do not change the end product. Though a few points

    1. In src/graph.rs a Default implementation for graph::Graph<T> can be better (using #[derive(Default)])
    2. In src/iterators/dfs on line 34 the loop does not really loop, it breaks after one loop
    opened by sn99 6
  • Can't compile in no std environment

    Can't compile in no std environment

    I tried using the graphlib on a embedded project I'm working on, but failed to compile it due to dependencies to the std crate.

    For reproducibility, I set up the environment the same as described in the embedded rust book: https://docs.rust-embedded.org/book/start/qemu.html

    The std features should be disabled:

    [dependencies]
    graphlib = {version = "0.6.1", features = ["no_std"]}
    

    When compiled with:

    cargo +nightly build --target thumbv7m-none-eabi
    

    I got the following error:

       Compiling lazy_static v1.4.0
       Compiling hex v0.4.2
       Compiling num_cpus v1.12.0
       Compiling ahash v0.2.18
    error[E0463]: can't find crate for `std`
      |
      = note: the `thumbv7m-none-eabi` target may not be installed
    
    error: aborting due to previous error
    
    For more information about this error, try `rustc --explain E0463`.
    error[E0463]: can't find crate for `std`
      |
      = note: the `thumbv7m-none-eabi` target may not be installed
    
    error: aborting due to previous error
    
    For more information about this error, try `rustc --explain E0463`.
    error: could not compile `hex`.
    
    To learn more, run the command again with --verbose.
    warning: build failed, waiting for other jobs to finish...
    error: could not compile `num_cpus`.
    
    To learn more, run the command again with --verbose.
    warning: build failed, waiting for other jobs to finish...
    error[E0463]: can't find crate for `std`
     --> /Users/schuepbs/.cargo/registry/src/github.com-1ecc6299db9ec823/lazy_static-1.4.0/src/inline_lazy.rs:9:1
      |
    9 | extern crate std;
      | ^^^^^^^^^^^^^^^^^ can't find crate
      |
      = note: the `thumbv7m-none-eabi` target may not be installed
    
    error: aborting due to previous error
    
    For more information about this error, try `rustc --explain E0463`.
    error: could not compile `lazy_static`.
    
    To learn more, run the command again with --verbose.
    warning: build failed, waiting for other jobs to finish...
    error: build failed
    

    I believe that this is due to a dependency in the hashbrow crate. Do you know anything about this?

    opened by samuel-schuepbach 4
  • add `no_std` support

    add `no_std` support

    solves #20

    use cargo build --features no_std

    Or In Cargo.toml:

    [dependencies]
    graphlib = {version = "*", features = ["no_std"]}
    

    I also removed cargo.lock as it may cause conflict if someone git clones it and in general not a good idea to have around Though Rand still depends on std, issue as of implementation

    We can permanently remove std from Rand or use a no_std random crate or do as the above stackoverflow solution, removing std from rand seems to be the simplest

    opened by sn99 4
  • Graphviz feature

    Graphviz feature

    Graphviz makes it possible to draw diagrams. I implemented a function render_to which creates a .dot file. Based on the .dot file you can generate graph jpg, png, ...

    HOWTO

    cargo run --features "graphviz" --example dot Then you should have a example.dot file in your directory.

    dot -Tps example.dot -o example.pdf

    opened by kper 4
  • Improve labeling to support edges and use dot's labels instead of IDs

    Improve labeling to support edges and use dot's labels instead of IDs

    The current dot implementation from #13 is overly restrictive about which strings are allowed for labels, returning an InvalidLabel Err in many cases where the label should be allowed (e.g. even just by having a space in the label).

    This is caused by incorrectly using dot::Id/ node_id() for labels and not just for node IDs.

    In this pull request I made the following changes:

    • Made labels less restrictive by implementing node_label() which uses dot::LabelText instead of dot::Id
    • Added support for edge labelling
      • After doing this, I found the naming a bit confusing: label_vertex() (set), vertex_label() (get), label_edge() (set), edge_label() (get)
      • I think the naming add_vertex_label() (set), vertex_label() (get) is clearer
    • Restructured the dot integration to be based on the Graph itself. This is a more extensible approach, and since dot::Labeller supports many other features (e.g. node_color()) it's possible additional data from the graph will be needed in the future

    I ran the example:

    $ cargo run --example dot --features dot
    $ dot -Tpdf example1.dot -o example1.pdf
    

    Which produces the following result

    screenshot-graphlib

    opened by matt-snider 3
  • Some library feedback

    Some library feedback

    Hey @octavonce !

    First of all, thank you so much for putting the time and effort to release the library in the wild. I was on the hunt for a graph library while evaluating alternatives to petgraph and this one has been on my radar for a while now, and looks very promising 😉

    I have some (unsolicited 😁 ) feedback which I hope you might find useful. In particular:

    1. It would be very nice to be able to have edges as "first class" citizens of the library. At the moment one can only add a "plain" edge or a weighted one, but using an f32 is a bit limiting, as users might want to embed arbitrary metadata at the edge level. Have you ever thought about parametrising your Graph over some edge type E? If so, how did it go?

    2. In some circumstances, it might be necessary to allow parallel edges between nodes. At the moment, if I understand correctly, add_edge is idempotent and cannot create more than one edge between two nodes. This makes sense as the function neither create ids internally (I believe) nor exposes the newly-created edge id to the outside (like add_node does) so it's not possible to reference back to an edge after its construction.

    Do you think 1 & 2 would be features worth adding and, if yes, would you accept external contributions to your library? Thanks a lot for your time! 😸

    opened by adinapoli-mndc 3
  • Compilation fails: cannot find function `encode` in crate `hex`

    Compilation fails: cannot find function `encode` in crate `hex`

    Hey folks,

    Thanks for your work on graphlib! I love how simple and straightforward it is.

    I'm running into a snag when I try and compile:

    error[E0425]: cannot find function `encode` in crate `hex`
     --> /Users/noisemachines/.cargo/registry/src/github.com-1ecc6299db9ec823/graphlib-0.6.2/src/vertex_id.rs:9:40
      |
    9 |         write!(f, "VertexId({})", hex::encode(self.0))
      |                                        ^^^^^^ not found in `hex`
    
    For more information about this error, try `rustc --explain E0425`.
    error: could not compile `graphlib` due to previous error
    

    I'm seeing this on Rust 1.55 stable, as well as Rust 1.54. Downgrading to graphlib 0.5.3 fixes the issue.

    Here's a small repo that reproduces the error: https://github.com/photon-garden/reproduce-graphlib-compilation-error

    You can see it by cloning the repo and running cargo run or cargo run --release.

    Let me know if I can help with anything else!

    opened by photon-garden 2
  • Make Clone and Debug requirement optional

    Make Clone and Debug requirement optional

    I would like to use this library for a project of mine, however I need the nodes in it to be of some Box<dyn MyTrait> type object, which cannot be cloned, as their Size is not known at compile time.

    According to the std docs, using #[derive(Clone)] only implements Clone on a templated struct if all template types also implement clone. Therefore the Clone requirement of the node type can be dropped.

    While I was at it, I also made the debug trait optional, the std::fmt::Debug docs, don't mention that it behaves the same as Clone, but it compiles fine after removal of the requirement, so I guess this works the same.

    The Graph can still be cloneable when the node type can be cloned, otherwise it won't be able to be cloned.

    Please note that I whilst I am an experienced programmer, I am a rust rookie, so if I make any newbie mistakes, please correct me.

    opened by LeonMatthes 2
  • Add support for a topological ordering

    Add support for a topological ordering

    Topological ordering (https://en.wikipedia.org/wiki/Topological_sorting) is useful for a Graph Library.

    I've got an implementation of Kahn's algorithm which is based on the approach you used for your current Dfs implementation. Would you like me to create a PR?

    enhancement 
    opened by garyanaplan 2
  • Support Postorder DFS

    Support Postorder DFS

    Thanks for the wonderful work. I am looking for an alternative to DfsPostOrder in petgraph: https://docs.rs/petgraph/0.6.2/petgraph/visit/struct.DfsPostOrder.html I wonder if it can be supported in the future version or is it already supported?

    opened by chaosprint 0
  • Improve graphlib::iterators::Dijkstra API

    Improve graphlib::iterators::Dijkstra API

    The Dijkstra::new() API computes the single-source shortest path between a given source and every other vertex in the graph. For a consumer that cares about the shortest path between a given source and two or more other graph nodes (e.g., AB, AC, etc), the SSSP computation can be reused. This is more efficient than recomputing it for every destination node (and part of why SSSP is a great algorithm).

    These changes make reuse more ergonomic by not consuming the value, and referencing the Dijkstra object immutably rather than mutably.

    Previously, one could reuse the results of the SSSP computation only by clone()ing the entire Dijkstra object, which is inefficient.

    Tests continue to pass.

    opened by cemeyer 0
  • iterator::Dijkstra::get_distance() does not need &mut self

    iterator::Dijkstra::get_distance() does not need &mut self

    It doesn't mutate self, so it could just take an immutable &self ref.

    Also, it seems like get_path_to shouldn't need to consume self -- &mut self would be fine, and allow reusing the SSSP calculation without cloning the entire Dijkstra structure. But maybe I'm missing something.

    opened by cemeyer 0
  • Track the vertex ids for items internally

    Track the vertex ids for items internally

    It would be useful to have has_vertex and to have the library track the item to vertex id mapping internally instead of needing to do this wherever it's used.

    opened by VioletDarkKitty 0
  • Add support for serde

    Add support for serde

    I'd like to be able to serialise/deserialise my graphs.

    I've taken a look at it and the work to add naive support is fairly trivial. Enabling hash brown serialize/deserialize support, adding serde support to the lib and specifying some derives is pretty much all that's required.

    If we want to implement it as a feature for (similar to the existing "dot" feature), I think that would also be fairly straightforward.

    This would then tie in the library to a long term serialisation format that exposes details about implementation and that might not be desirable. It might be better to have a discussion about the implications of this before going ahead and adding support. One solution could be to provide an implementation that checks for incompatibilities (perhaps version based) and fails if incompatible. That would be more work than just using the derive macros.

    What do you think?

    enhancement 
    opened by garyanaplan 7
Releases(v0.6.3)
Owner
Purple Protocol
The Global Decentralized Ledger Infrastructure
Purple Protocol
A simple and elegant, pipewire graph editor

pw-viz A simple and elegant, pipewire graph editor This is still a WIP, node layouting is kinda jank at the moment. Installation A compiled binary is

null 180 Dec 27, 2022
Simple, performant graph generator for Feynman diagrams* ⚛️

Feynman diagram generator ⚛️ A simple generator of "Feynman diagram" permutations (as defined by problem 781). Incrementally builds isomorphically uni

eugene huang 3 Jan 1, 2023
Graph data structure library for Rust.

petgraph Graph data structure library. Supports Rust 1.41 and later. Please read the API documentation here Crate feature flags: graphmap (default) en

null 2k Jan 9, 2023
A graph library for Rust.

Gamma A graph library for Rust. Gamma provides primitives and traversals for working with graphs. It is based on ideas presented in A Minimal Graph AP

Metamolecular, LLC 122 Dec 29, 2022
Rust library for of graph ensembles

Rust library for random graph ensembles Minimal Rust version: 1.55.0 Implements simple sampling and monte carlo (or rather markov-) steps, that can be

Yannick Feld 2 Dec 14, 2022
🦀 Rust Graph Routing runtime for Apollo Federation 🚀

Apollo Router The Apollo Router is a configurable, high-performance graph router for a federated graph. Getting started Follow the quickstart tutorial

Apollo GraphQL 502 Jan 8, 2023
Graph API client writen in Rust

graph-rs Now available on stable Rust at crates.io graph-rs-sdk = "0.1.0" 0.1.0 and above use stable Rust. Anything before 0.1.0 uses nightly Rust. M

Sean Reeise 56 Jan 3, 2023
GraphScope: A One-Stop Large-Scale Graph Computing System from Alibaba

A One-Stop Large-Scale Graph Computing System from Alibaba GraphScope is a unified distributed graph computing platform that provides a one-stop envir

Alibaba 2.2k Jan 1, 2023
A graph crate with simplicity in mind

A graph crate with simplicity in mind. Prepona aims to be simple to use (for users of the crate) and develop further (for contributors). Nearly every

Mohamad Amin Rayej 80 Dec 15, 2022
Theorem relational dependencies automatic extraction and visualization as a graph for Lean4.

Lean Graph Interactive visualization of dependencies for any theorem/definitions in your Lean project. How to use In your browser: lean-graph.com Or r

Patrik Číhal 8 Jan 3, 2024
Kiss3d - Keep it simple, stupid 3d graphics engine for Rust.

Kiss3d - Keep it simple, stupid 3d graphics engine for Rust.

Sébastien Crozet 1.2k Dec 26, 2022
The library provides basic functions to work with Graphviz dot lang from rust code.

Description The library provides the basic access to the graphs in graphviz format with ability to import into or export from it. Base examples: Parse

Boris 28 Dec 16, 2022
Generic framebuffer implementation in Rust for use with embedded-graphics library

Fraramebuffer implementation for Rust's Embedded-graphics Framebuffer approach helps to deal with display flickering when you update multiple parts of

Bernard Kobos 9 Nov 29, 2022
A 2D vector graphics library optimized for GUIs, written in Rust and wgpu

RootVG A 2D vector graphics library optimized for GUIs, written in Rust and wgpu How it Works Unlike other 2D vector graphics libraries which have a s

Meadowlark 14 Jul 10, 2024
An SVG rendering library.

resvg resvg is an SVG rendering library. Purpose resvg can be used as a Rust library, a C library and as a CLI application to render SVG files based o

Evgeniy Reizner 1.8k Jan 7, 2023
Library for Rubik's cube applications.

Rubik Master cube-demo3.mov Do you like to solve Rubik's cube? I do. As a cuber and programmer, I want to build a toolset to build applications like S

Akira Hayakawa 12 Nov 3, 2022
Sub-pixel precision light spot rendering library for astronomy and video tracking applications.

Planetarium Sub-pixel precision light spot rendering library for astronomy and video tracking applications. Example usage use planetarium::{Canvas, Sp

Sergey Kvachonok 5 Mar 27, 2022
Small, lightweight and fast library for rendering text with wgpu.

wgpu-text wgpu-text is a wrapper over glyph-brush for fast and easy text rendering in wgpu. This project was inspired by and is similar to wgpu_glyph,

Leon 20 Nov 30, 2022
Python library for embedding large graphs in 2D space, using force-directed layouts.

Graph Force A python/rust library for embedding graphs in 2D space, using force-directed layouts. Installation pip install graph_force Usage The first

Niko Abeler 159 Dec 29, 2022