RE: [boost] graphs: incidence_iterator

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.

Thanks!

Jeremy