Handle Graph::remove_node index-shifting behaviour

[mitchmindtree]

Graph::remove_node causes indices to shift if index isn't the last node.

Options to handle this are:

1. Leave behaviour but document it.
2. Make each Slot an Option<Slot> and simply make remove_node set the Option<Slot> to None. Document the assumption that user never calls add_node more than MAX_NODES number of times.

I'm currently leaning towards option 2 - any ideas / input appreciated :)

[mitchmindtree]

Additionally to option 2, we could have the add_node method first check for Option<Slot>s that are set to None and fill those before calling the underlying petgraph::Graph::add_node method. This would add a slight amount of extra work to the add_node method, but would ensure the petgraph::Graphs Vecs never grow larger than necessary.

[mitchmindtree]

Following option 2, a description of what remove_node(idx) would look like might be:

• Set the node at idx to None.
• Remove all incoming and outgoing connections to the Node.

[bluss]

Eddyb actually brought up an interesting datastructure to make such reuse cheap: keep the free slots linked to the next free slot with an enum like enum Entry<T> { Free(NodeIndex /* next */), Occupied(T) }

[bluss]

Here's a proof of concept for the free-slots solution.

#[derive(Clone, Debug)]
pub enum Entry<T> {
    Empty(usize),
    Occupied(T),
}

pub struct EntryGraph<N, E, Ty = Directed, Ix = DefIndex>
    where Ix: IndexType
{
    g: Graph<Entry<N>, Entry<E>, Ty, Ix>,
    free_node: usize,
    free_edge: usize,
}
impl<N, E, Ty, Ix> fmt::Debug for EntryGraph<N, E, Ty, Ix> where
    N: fmt::Debug, E: fmt::Debug, Ty: EdgeType, Ix: IndexType
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        try!(writeln!(f, "{:?}", self.g));
        try!(writeln!(f, "free_node={}", self.free_node));
        try!(writeln!(f, "free_edge={}", self.free_edge));
        Ok(())
    }
}

impl<N, E, Ty=Directed, Ix=DefIndex> EntryGraph<N, E, Ty, Ix>
    where Ty: EdgeType,
          Ix: IndexType,
{
    pub fn new() -> Self {
        EntryGraph {
            g: Graph::with_capacity(0, 0),
            free_node: !0,
            free_edge: !0,
        }
    }

    pub fn add_node(&mut self, weight: N) -> NodeIndex<Ix> {
        if self.free_node != !0 {
            let node_idx = self.free_node;
            let next = replace(&mut self.g.nodes[node_idx].weight, Entry::Occupied(weight));
            self.free_node = match next {
                Entry::Empty(i) => i,
                Entry::Occupied(_) => unreachable!(),
            };
            NodeIndex::new(node_idx)
        } else {
            let node = Node{weight: Entry::Occupied(weight), next: [EdgeIndex::end(), EdgeIndex::end()]};
            let node_idx = NodeIndex::new(self.g.nodes.len());
            // check for max capacity, except if we use usize
            assert!(Ix::max().index() == !0 || NodeIndex::end() != node_idx);
            self.g.nodes.push(node);
            node_idx
        }
    }

    pub fn remove_node(&mut self, a: NodeIndex<Ix>) -> Option<N>
    {
        // FIXME: As a PoC, only do compact map for nodes, not edges
        match self.g.nodes.get(a.index()) {
            None => return None,
            _ => {}
        }
        for d in DIRECTIONS.iter() {
            let k = *d as usize;

            // Remove all edges from and to this node.
            loop {
                let next = self.g.nodes[a.index()].next[k];
                if next == EdgeIndex::end() {
                    break
                }
                let ret = self.g.remove_edge(next);
                debug_assert!(ret.is_some());
                let _ = ret;
            }
        }

        let node_weight = replace(&mut self.g.nodes[a.index()].weight, Entry::Empty(self.free_node));
        self.g.nodes[a.index()].next = [EdgeIndex::end(), EdgeIndex::end()];
        self.free_node = a.index();

        match node_weight {
            Entry::Occupied(w) => Some(w),
            Entry::Empty(_) => panic!("tried to remove vanished node"),
        }

    }
}

#[test]
fn entry_graph() {
    let mut g = EntryGraph::<_, ()>::new();
    let a = g.add_node(0);
    let b = g.add_node(1);
    let c = g.add_node(2);
    println!("{:?}", g);
    g.remove_node(b);
    println!("{:?}", g);
    let d = g.add_node(3);
    println!("{:?}", g);
    g.remove_node(a);
    g.remove_node(c);
    println!("{:?}", g);
}

debug output from the test:

Graph<Directed> {
    0: Node(Occupied(0)),
    1: Node(Occupied(1)),
    2: Node(Occupied(2)),
}
free_node=18446744073709551615
free_edge=18446744073709551615

Graph<Directed> {
    0: Node(Occupied(0)),
    1: Node(Empty(18446744073709551615)),
    2: Node(Occupied(2)),
}
free_node=1
free_edge=18446744073709551615

Graph<Directed> {
    0: Node(Occupied(0)),
    1: Node(Occupied(3)),
    2: Node(Occupied(2)),
}
free_node=18446744073709551615
free_edge=18446744073709551615

Graph<Directed> {
    0: Node(Empty(18446744073709551615)),
    1: Node(Occupied(3)),
    2: Node(Empty(0)),
}
free_node=2
free_edge=18446744073709551615

As you can see there is a "linked list" of indices, free_node pointing to 2, which points to 0, which points to usize::MAX, i.e it's the end.

[mitchmindtree]

Nice one!

I had considered making the nodes Option<N> and adding a separate deque containing the indices of available nodes, but this is a much nicer idea!

Have you considered adding EntryGraph to petgraph?

Or perhaps the option could be added as a type parameter to Graph somehow, maybe something along these lines:

pub trait NodeContainer<N, Ix>
    where Self: Index<Ix, Target=N> + IndexMut,
{
    fn add_node(&mut self, N) -> NodeIndex<Ix>;
    fn remove_node(&mut self, NodeIndex<Ix>) -> Option<N>;
    // etc...
}

pub type Entries<N> = Vec<Entry<N>>;

impl<N, Ix> NodeContainer<N, Ix> for Vec<N> { ... }
impl<N, Ix> NodeContainer<N, Ix> for Entries<N> { ... }

pub struct Graph<N, E, Ty, Nc=Vec<N>, Ix=usize>
    where Nc: NodeContainer<N>,
{
    nodes: Nc,
    ...
}


pub type EntryGraph<N, E, Ty, Ix> = Graph<N, E, Ty, Entries<N>, Ix>;
pub type VecGraph<N, E, Ty, Ix> = Graph<N, E, Ty, Vec<N>, Ix>;

I guess the same idea could be applied to an EdgeContainer also?

[bluss]

I think I want to add it to petgraph, it should be very useful, pretty exciting.

The new kind of graph will not have entirely the same properties as the Graph.

• Edge / Neighbor walking will be the same
• Algorithms that need the compact set of node indices will not work the same way, so many of the graph theory algorithms will not work as in the current version (is_isomorphic etc).

The NodeContainer idea is a bit interesting, it's also how boost graph library does (it's generic over different kinds of containers).

I think it's better to not over-parameterize, we don't really have a nice way to do this. We don't have HKT, so we can't have a type parameter to indicate "Use Vec" instead we need both "Use Vec<E>" and "use Vec<N>". And the algorithm behaviors may be too different, mainly that there is no non-borrowing iterator to list all node or edge indices, maybe that's not such a big deal.

Details will of course become clearer during implementation.