Open mitchmindtree opened 9 years ago
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::Graph
s Vec
s never grow larger than necessary.
Following option 2, a description of what remove_node(idx)
would look like might be:
None
.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) }
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.
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?
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.
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.
Graph::remove_node
causes indices to shift if index isn't the last node.Options to handle this are:
Slot
anOption<Slot>
and simply makeremove_node
set theOption<Slot>
toNone
. Document the assumption that user never callsadd_node
more thanMAX_NODES
number of times.I'm currently leaning towards option 2 - any ideas / input appreciated :)