Boost logo

Boost :

Subject: [boost] [metagraph]
From: Kitten, Nicholas (nkitten_at_[hidden])
Date: 2012-01-27 11:07:56

Hi Gordon (and whoever else is involved),

What's the current status of metagraph / mpl_graph? I've been using
msm::mpl_graph for error-checking/scheduling in a compile-time filter
graph framework (similar to state machines, but focus is on data
flow), and I'd certainly like to see more. As is, I've already
implemented a topological sort based on the BFS which doesn't yield
errors on cyclic graphs (which I'd be happy to contribute if you don't
already have one), and I have some thoughts on improvement. I saw the
BoostCon slides and the current state of the sandbox, and I was
wondering if there's more code lurking out there somewhere,

Anyway, the single biggest flaw I see with the current BFS and DFS
(and the BGL models they're based on) is that there is no way for the
user to specify a termination condition in the base algorithm. It
seems silly that an algorithm called "Search" can't end without
traversing the whole connected component! Indeed, if there were
simply an optional predicate determining whether a candidate vertex
should be added to the stack/queue, I wouldn't have needed to write a
separate algorithm for topo sort.

The other thing is that not all of the listed visitor operations are
called in the current implementations. Adding things like
"initialize_vertex" and "non_tree_edge" to BFS is an easy fix.

Nick Kitten

Software Engineer
Center for Video Understanding Excellence
ObjectVideo, Inc.

Boost list run by bdawes at, gregod at, cpdaniel at, john at