A chain where each pair of left and right edges of a My::Branch reference the same next Rc<My> node. Without shared-structure detection, it would be traversed like a perfect binary tree with 2^(depth+1)-2 recursions, but with the shared-structure detection of this crate, it is traversed with only 2*depth recursions.

```rust use graphsafecompare::{robust, utils::RefId, Node}; use std::rc::Rc; use My::*;

[derive(Eq)]

enum My { Leaf { val: i32 }, Branch { left: Rc, right: Rc }, }

impl My { fn newdegenerateshared_structure(depth: usize) -> Self { let next = Leaf { val: 1 }; (0..depth).fold(next, |next, _| { let next = Rc::new(next); Branch { left: Rc::clone(&next), right: next } }) } }

impl PartialEq for My { fn eq(&self, other: &Self) -> bool { robust::equiv(self, other) } }

impl Node for &My { type Cmp = bool; type Id = RefId; type Index = usize;

fn id(&self) -> Self::Id { RefId(*self) }

fn get_edge(&self, index: &Self::Index) -> Option<Self> {
    match (self, index) {
        (Branch { left, .. }, 0) => Some(left),
        (Branch { right, .. }, 1) => Some(right),
        _ => None,
    }
}

fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
    match (self, other) {
        (Leaf { val: v1 }, Leaf { val: v2 }) => v1 == v2,
        (Branch { .. }, Branch { .. }) => true,
        _ => false,
    }
}

}

fn main() { // A depth that is fast with the robust variant of this crate, but that // would be infeasible and either take forever, due to the great degree of // shared structure, or cause stack overflow, due to the great depth, if // another variant were used. let depth = 1000000; let a = My::newdegeneratesharedstructure(depth); let b = My::newdegeneratesharedstructure(depth); assert!(a == b);

// Prevent running the drop destructor, to avoid the stack overflow it would
// cause due to the great depth.  (A real implementation would need a `Drop`
// designed to properly avoid that.)
std::mem::forget((a, b));

} ```

A very-simple cycle. Without shared-structure detection, it would infinitely recurse and overflow the stack, but with the shared-structure detection of this crate, it does not and it completes efficiently.

The types involved are more complicated, to be able to construct cycles.

```rust use graphsafecompare::{cycle_safe, utils::RefId, Node}; use std::{cell::{Ref, RefCell}, rc::Rc}; use Inner::*;

[derive(Clone)]

struct My(Rc>);

enum Inner { Leaf { val: i32 }, Branch { left: My, right: My }, }

impl My { fn leaf(val: i32) -> Self { My(Rc::new(RefCell::new(Leaf { val }))) }

fn set_branch(&self, left: My, right: My) {
    *self.0.borrow_mut() = Branch { left, right };
}

fn new_cyclic_structure() -> Self {
    let cyc = My::leaf(0);
    cyc.set_branch(My::leaf(1), cyc.clone());
    cyc
}

fn inner(&self) -> Ref<'_, Inner> { self.0.borrow() }

}

impl PartialEq for My { fn eq(&self, other: &Self) -> bool { cycle_safe::equiv(self.clone(), other.clone()) } } impl Eq for My {}

impl Node for My { type Cmp = bool; type Id = RefId>>; type Index = u32;

fn id(&self) -> Self::Id { RefId(Rc::clone(&self.0)) }

fn get_edge(&self, index: &Self::Index) -> Option<Self> {
    match (index, &*self.inner()) {
        (0, Branch { left, .. }) => Some(left.clone()),
        (1, Branch { right, .. }) => Some(right.clone()),
        _ => None,
    }
}

fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
    match (&*self.inner(), &*other.inner()) {
        (Leaf { val: v1 }, Leaf { val: v2 }) => v1 == v2,
        (Branch { .. }, Branch { .. }) => true,
        _ => false,
    }
}

}

fn main() { let a = My::newcyclicstructure(); let b = My::newcyclicstructure(); assert!(a == b);

// (A real implementation would need to break the cycles, to allow them to
// be dropped.)

} ````

```rust use graphsafecompare::{basic, utils::RefId, Node}; use std::cmp::Ordering;

[derive(Eq)]

struct My(Vec);

impl Ord for My { fn cmp(&self, other: &Self) -> Ordering { basic::equiv(self, other) } } impl PartialOrd for My { fn partialcmp(&self, other: &Self) -> Option { Some(self.cmp(other)) } } impl PartialEq for My { fn eq(&self, other: &Self) -> bool { self.cmp(other).iseq() } }

impl Node for &My { type Cmp = Ordering; type Id = RefId; type Index = u8;

fn id(&self) -> Self::Id { RefId(*self) }

fn get_edge(&self, _: &Self::Index) -> Option<Self> { None }

fn equiv_modulo_edges(&self, other: &Self) -> Self::Cmp {
    self.0.iter().cmp(other.0.iter())
}

}

fn main() { let mut array = [My(vec![1, 2, 3]), My(vec![3]), My(vec![1, 2])]; array.sort(); assert!(array == [My(vec![1, 2]), My(vec![1, 2, 3]), My(vec![3])]) } ````