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

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

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

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?

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

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

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

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! 😸

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!

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.

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?

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?

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., A → B, A → C, 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.

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.

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.

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?