Boost logo

Boost :

From: jsiek_at_[hidden]
Date: 2000-05-23 12:55:59

Hi Paul,

Moore, Paul writes:
> From: jsiek_at_[hidden] [mailto:jsiek_at_[hidden]]
> >
> > I think there needs to be two separate incidence iterator types in the
> > graph_traits class, one for out-edges an one for in-edges.
> > Here are some ideas for naming the types:
> >
> > 1. out_edge_iterator
> > in_edge_iterator
> >
> > 2. incidence_iterator (for out-edges, same as before)
> > in_edge_iterator (for in-edges)
> >
> > 3. incidence_iterator (for out-edges, same as before)
> > incident_to_iterator (for in-edges)
> >
> > 4. incident_from_iterator (for out-edges)
> > incident_to_iterator (for in-edges)
> >
> >
> > Thoughts?
> As a non-expert in graph algorithms, option (1) works best for me.
> "incidence" doesn't immediately mean "edges connecting to this vertex" to
> me. If you don't go for (1), I'd suggest (4) - keep it clear and explicit
> for non-experts.

I'm also leaning towards (1).

> On a related note, I've not used GGCL yet, but I have read through the
> documentation, and it looks good, but it's hard going because I don't know
> the terminology or the practical applications. I don't know if this is a
> problem as such - after all, you could argue that if I don't know what
> Djikstra's algorithm is, I don't need it - but it does make it harder for me
> to see just how I'd use GGCL for practical problems.
> As an example of a practical problem which is not restricted to graph
> "experts", consider file dependencies. It's basically graph construction,
> plus topological sort, but it might make a nice "tutorial" example. Build a
> dependency graph of files, then use the algorithms to do things like
> 1. Produce a full recompilation order (topological sort, by modified date)
> 2. Produce a "parallel" recompilation order (same as above, but group files
> which can be built in parallel)
> 3. Change analysis (if I change file x, which others need recompiling)
> 4. Dependency changes (if I add a dependency between file x and file y, what
> are the effects)

Heh, that's a great idea for an example! It could go after the "quick
tour", as an extended example.

> This sort of example is very concrete (everyone has seen make) and would
> give a nice solid introduction to why "normal users" would want to use the
> graph classes. It's a bit like the STL map class - out of context, it is
> just an obscure theoretical construct, but when linked with the idea of
> associative arrays, it suddenly becomes very clear why it's important...

> [[ Actually, in general, C++ could do with more concrete examples of how the
> library can be used in real world problems... ]]
> Anyway, I hope this is of some use,
> Paul.



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