mitchmindtree / daggy Goto Github PK
View Code? Open in Web Editor NEWA directed acyclic graph data structure for Rust.
License: Apache License 2.0
A directed acyclic graph data structure for Rust.
License: Apache License 2.0
I'm just wondering if there's a method to update the weight of a node inside the DAG. I can only find a way to update the weight of an edge, but not to the node itself.
Is there a walker method that efficiently returns the elements at the end of the tree (leaves)?
I took a look at the raw nodes and it looks like all of the leaf nodes have a next
value that looks like next: [EdgeIndex(End), EdgeIndex(6)]
. So I could call filter on a recursive walk over all of the nodes in the tree or on .raw_nodes()
and check if next[0] == EdgeIndex(End)
, but that seems like a waste. Is there a better way to do this using the currently available API?
Hello.
I'm here, getting ready to use daggy in a project of mine, when I check Dag's documentation, and find out that removals may change indices. I looked around (docs.rs), and found that because daggy used petgraph 0.2.2, it missed out on petgraph 0.4.3's StableGraph.
I would like to propose updating, and building Dag off of StableGraph, in order to stablize indices.
Idk if this is fixable on your side, but this is what it looks like on https://docs.rs/daggy: (working links are *marked*)
The most prominent type is *Dag* - a wrapper around *petgraph* (http://bluss.github.io/petulant-avenger-graphlibrary/doc/petgraph/index.html)'s [Graph] (http://bluss.github.io/petulant-avenger-graphlibrary/doc/petgraph/graph/struct.Graph.html) data structure, exposing a refined API targeted towards directed acyclic graph related functionality.
roots
returns a struct that let you iterate over all nodes that have no incoming edges. leafs
no outgoing.
Tell me what you think about this, I'll try to implement it then.
new to rust, I have a very simple application that simply won't compile when I use daggy with #![cfg(feature = "stable_dag")]
the stable graph feature enabled. It feels like I am doing something silly here. But if I remove the cfg
and use Dag
instead of StableDag
everything works fine.
src/lib.rs
is as so
#![cfg(feature = "stable_dag")]
extern crate daggy;
pub fn test() {
println!("Test stable dag");
}
--> src/bin/main.rs:1:5
|
1 | use mylib::test;
| ^^^^^^^^^^^^ no `test` in the root
mylib
is defined in my Cargo.toml
like so
[lib]
name = "mylib"
path = "src/lib.rs"
Hi, I'm getting errors when trying to compile Petgraph. I was told upgrading to 0.4.5 would fix the issue but daggy is already specifying 0.4.5. The following is my error message:
error[E0034]: multiple applicable items in scope
--> /home/onix/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.2.9/src/graph.rs:421:17
|
421 | assert!(Ix::max().index() == !0 || NodeIndex::end() != node_idx);
| ^^^^^^^ multiple `max` found
|
note: candidate #1 is defined in the trait `graph::IndexType`
--> /home/onix/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.2.9/src/graph.rs:31:5
|
31 | fn max() -> Self;
| ^^^^^^^^^^^^^^^^^
= help: to disambiguate the method call, write `graph::IndexType::max(...)` instead
note: candidate #2 is defined in the trait `std::cmp::Ord`
= help: to disambiguate the method call, write `std::cmp::Ord::max(...)` instead
error[E0034]: multiple applicable items in scope
--> /home/onix/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.2.9/src/graph.rs:458:17
|
458 | assert!(Ix::max().index() == !0 || EdgeIndex::end() != edge_idx);
| ^^^^^^^ multiple `max` found
|
note: candidate #1 is defined in the trait `graph::IndexType`
--> /home/onix/.cargo/registry/src/github.com-1ecc6299db9ec823/petgraph-0.2.9/src/graph.rs:31:5
|
31 | fn max() -> Self;
| ^^^^^^^^^^^^^^^^^
= help: to disambiguate the method call, write `graph::IndexType::max(...)` instead
note: candidate #2 is defined in the trait `std::cmp::Ord`
= help: to disambiguate the method call, write `std::cmp::Ord::max(...)` instead
error: aborting due to 2 previous errors
error: Could not compile `petgraph`.
warning: build failed, waiting for other jobs to finish...
error: build failed
As a compromise between the status quo and #12, what about adding a transactional add/remove of nodes and edges?
For example, some code like this:
for node_ind in nodes_to_remove.iter() {
tree.remove_node(*node_ind);
}
for edge_ind in edges_to_remove.iter() {
tree.remove_edge(*edge_ind);
}
As I understand it, this code has somewhat random behavior since each run through the loop will cause the tree to change. However, if I could specify something like tree.transact(&nodes_to_remove, tree.remove_node)
, that would solve my own stability needs without needing the whole graph to be redone.
On the other hand, it's a very database thing to do.
Hey,
is there a way to print a DAG generated with this library to the terminal? (git-log style)?
If not, please consider this a feature request.
Please push them.
After resetting a graph's nodes and edges using graph.clear()
after a cycle was detected, no new nodes can be added as the cycle state is not reset. Should graph.clear()
not also reset the cycle state?
This might be useful for performance critical occasions where the user knows for certain that adding an edge would not create a cycle.
Would be great if there was a direct link to the docs from the crate page.
I originally used parents and children as this was how I was used to thinking about DAGs, however it probably makes more sense to match the conventions of petgraph. Petgraph's naming is also a lot less ambiguous in terms of edge direction.
The type invariant that the current DAG is acyclic can be used to speed up incremental checks. A full algorithm is still O(|V| + |E|) though.
Some easy heuristics are:
a
or b
without prior edges?a
to b
with the same directionality?Hello,
Daggy does not properly detect when a node has a node to itself(Loop).
The following test is failing:
#[test]
fn add_edges_err_loop() {
let mut dag = Dag::<Weight, u32, u32>::new();
let root = dag.add_node(Weight);
let a = dag.add_node(Weight);
let b = dag.add_node(Weight);
let c = dag.add_node(Weight);
let add_edges_result = dag.add_edges(
once((root, a, 0))
.chain(once((root, b, 1)))
.chain(once((root, c, 2)))
.chain(once((c, c, 3))),
);
match add_edges_result {
Err(WouldCycle(returned_weights)) => assert_eq!(returned_weights, vec![3, 2, 1, 0]),
Ok(_) => panic!("Should have been an error"),
}
}
Several approaches can be used to fix this. An easy one is making the following modifications
fn must_check_for_cycle<N, E, Ix>(dag: &Dag<N, E, Ix>, a: NodeIndex<Ix>, b: NodeIndex<Ix>) -> bool
where
Ix: IndexType,
{
// Add this check
if a == b {
return true;
}
dag.parents(a).walk_next(dag).is_some()
&& dag.children(b).walk_next(dag).is_some()
&& dag.find_edge(a, b).is_none()
}
This would ensure that the loop is properly checked.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.