Daggy not detecting loop cycles

[jdeschenes]

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.