RE: [boost] graphs: incidence_iterator

From: Moore, Paul (paul.moore_at_[hidden])
Date: 2000-05-23 03:37:57

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.

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)

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.