[Lemon-devel] Renaming basic classes

[Kovács Péter]

Dear Developers,

According to our consultations with Alpar and Balazs, now I also support
renaming edge-uedge to arc-edge. With the arc-edge distinction it will be
easier to use undirected graphs, and directed graphs won't be more difficult
to use. We can avoid all the problems with the forgotten 'U' letters when
using UEdgeMap<>, UEdgeIt, etc.. 

I searched for the usage of these two concepts and I found that 'arc' is
tipically used for the directed case and 'edge' is used for the undirected
case or both. For example:
http://en.wikipedia.org/wiki/Graph_(mathematics)#Graph
http://www-math.cudenver.edu/~wcherowi/courses/m4408/glossary.htm#Arc
So it would be reasonable to use the arc-edge distinction.

However the renaming of graph types isn't so clear for me. Is it really the
best way to use 'digraph' for directed graphs? In this way our most general
graph type would be ListDigraph (or ListDiGraph). Isn't it too complicated,
especially for those who start using LEMON? And I think directed graphs are
used more frequently, so it is important to use simple names for them.

I think it could be good if we use Arc-Edge and Graph-Ugraph or
Graph-UndirGraph or something else. UEdge, UEdgeMap, UEdgeIt, etc. are used
frequently, but UGraph is used rare, so Ugraph could be a good choice instead
of UGraph. Does someone know a better name for undirected graphs?

Moreover I think Digraph-Graph renaming would cause much more problems than
Arc-Edge renaming when we would like to convert source codes to the new
version. For example if we forget to change Edge to Arc somewhere, we will get
a compiler error, because the graph type doesn't have such typedef any more.
However if we forget to change e.g. ListGraph to ListDigraph, the code will
remain correct width Edge, EdgeIt, etc. but it does something very different,
because it became undirected. Or this whole theory isn't correct? 

> > On the other hand I find the use of anode() and bnode() for
> > this purpose very misleading.
> In my point of view the source() and target() are more misleading 
> than the anode() and bnode().

I agree with Balázs, source() and target() should be used only for the
directed case (arc). For undirected edges anode() and bnode() or
first() and second() would be better in my opinion.

I think getting rid of all the names like anode(), bnode(), ugraph, etc. isn't
necessary. However they should be considered one word: Ugraph, Bigraph,
Anode, Bnode.


So I support the following rename mappings:
UGraph => Ugraph
BpUGraph => Bigraph
(Graph => Graph)

Edge => Arc
UEdge => Edge

uEdge...() => edge...()
aNode...() => anode...()
bNode...() => bnode...() 

For edges (undirected):
source(), target() => anode(), bnode() or first(), second()
(or something else, e.g.  one() and other())

Peter


On Tue, 11 Sep 2007 14:09:29 +0200, Balazs Dezso wrote
> Dear Developers,
> 
> > On the other hand I find the use of anode() and bnode() for
> > this purpose very misleading.
> In my point of view the source() and target() are more misleading 
> than the anode() and bnode(). In addition, if we cast an edge to 
> uedge then the source could be change. // g.source(e) != 
> g.source(UEdge(e))
> 
> The boost library has undirected graphs (controlled by tag template 
> parameters), but it has a little different meaning than lemon 
> undirected graph. There are just unidrected edges and undirected 
> edge property maps in the graph. The leda has a forall_inout_edges() 
> function to use the graphs as undirected ones. And there is 
> make_undirected() function which removes all self loops and it moves 
> the splices the InEdge list of the node to the OutEdgeList.
> 
> Eventually, we should finalize our renaming and redesign proposals 
> asap. Could somebody summarize the ideas and naming suggestions? I 
> think we should conclude in few days.
> 
> Balazs
> 
> On Monday 10 September 2007 12.32.21 Alpár Jüttner wrote:
> > > The source() and target() functions could be changed in the undirected
> > > graphs to first() and second(), or anode() and bnode().
> >
> > I do not support this. I agree that source() and target() of an
> > undirected edge semms a bit strange for the first time, but they aren't
> > really confusing.
> > So it isn't worth introducing new function names for that (first() and
> > second()). On the other hand I find the use of anode() and bnode() for
> > this purpose very misleading.
> >
> > Alpar
> >