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.

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?

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.

This might be useful for performance critical occasions where the user knows for certain that adding an edge would not create a cycle.

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?

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"

Would be great if there was a direct link to the docs from the crate page.

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.

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.

Heya, please could we get a new release with:

• #33

It would also contain the fix for #28

Thank you

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.

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:

• is either a or b without prior edges?
• is there already an edge from a to b with the same directionality?

Please push them.