Port the special graph structures (full, hypercube and grid)

[Alpar Juttner]

The following files are affected

• lemon/full_graph.h
• lemon/grid_ugraph.h
• lemon/hypercube_graph.h

[Balazs Dezso]

The patch [37557a46e298] contains the port of FullDigraph? and FullGraph?. The FullGraph? is reworked, in the new implementation the edge-id mapping does not use floating point operations (std::sqrt). The idea comes from Alpar, and it is more efficient than the old solution (dfs 3-4x faster). The testing is also much better.

[Peter Kovacs]

[9654fcabeb82] contains the port of the hypercube digraph structure.

I suggest renaming HyperCubeDigraph to HypercubeDigraph, since hypercube is usually one word. (The file name is hypercube_graph.h not hyper_cube_graph.h.)

There is no undirected hypercube graph structure. So should we call the header file hypercube_digraph.h or keep the hypercube_graph.h name? Maybe the former one would be better.

[Peter Kovacs]

[0549a6719af9] renames HyperCubeDigraph to HypercubeDigraph.

[Peter Kovacs]

[ada5f74d1c9e] contains the port of the grid graph structure. It depends on [c760d691fe3c] (see #141).

In some functions explicit conversions (int-->Node or int-->Arc) seem to be missing. E.g. _left(), _right(), _source(), _target() in GridGraphBase (compared to _up(), _down() which use explicit conversion). Balazs, could you please check it?

[Balazs Dezso]

Improvements on grid graph

[Balazs Dezso]

I have uploaded the patch [109f3948dcc3], which contains some improvements on the patch [ada5f74d1c9e]. It basically implements the grid graph without the UndirGraphExtender?, and improves the testing.

[Peter Kovacs]

More improvements

[Peter Kovacs]

[fb41d1fb4641] contains improvements (it depends on [109f3948dcc3]). These two changesets could be merged with a more detailed log message (that describes the improvements).

Could we add (x,y) type labels for the four corners on the eps image?

[Balazs Dezso]

New patch for grid graph

[Balazs Dezso]

Replying to kpeter:

[fb41d1fb4641] contains improvements (it depends on [109f3948dcc3]). These two changesets could be merged with a more detailed log message (that describes the improvements).

Could we add (x,y) type labels for the four corners on the eps image?

I made the changes in the [dc254811acac].

[Peter Kovacs]

Replying to deba:

Replying to kpeter:

Could we add (x,y) type labels for the four corners on the eps image?

I made the changes in the [dc254811acac].

The image looks pretty good, but the origin should be the bottom-left corner.

The image conflicts the documentation that says: "the bottom-left corner is the origin". The implemantation is changed in your changesets to support this orientation, but you forget to apply this change to the image, too. (The only difference is the meaning of up() and down() functions.)

Moreover I miss my fixes (see [fb41d1fb4641]) from your changeset.

[Peter Kovacs]

You change the nodeshape_x.eps files in [dc254811acac]. Why don't we introduce these images in e.g. half size then? IMHO they are just too big in the documentation of GraphToEps.

[Balazs Dezso]

Replying to kpeter:

You change the nodeshape_x.eps files in [dc254811acac]. Why don't we introduce these images in e.g. half size then? IMHO they are just too big in the documentation of GraphToEps.

The size of the graph to eps images didn't change, because the resolution of png generation is increased to 36.

[Balazs Dezso]

Correct image and commit log

[Balazs Dezso]

Replying to kpeter:

Replying to deba:

Replying to kpeter:

Could we add (x,y) type labels for the four corners on the eps image?

I made the changes in the [dc254811acac].

The image looks pretty good, but the origin should be the bottom-left corner.

The image conflicts the documentation that says: "the bottom-left corner is the origin". The implemantation is changed in your changesets to support this orientation, but you forget to apply this change to the image, too. (The only difference is the meaning of up() and down() functions.)

Moreover I miss my fixes (see [fb41d1fb4641]) from your changeset.

I corrected the image in the [7d23fd7b4b4e]. There were to approaches, which could be followed in the grid graph implementation, the nodes are integer points on the plane or elements of a matrix. Unfortunately, I reworked the graph as plane points, and I made the image as matrix representation. Now it should be right.

[Peter Kovacs]

New (merged) improvement changeset

[Peter Kovacs]

Replying to deba:

I corrected the image in the [7d23fd7b4b4e]. ... Now it should be right.

The image is right now, but I still miss my former fixes.

[0438942f8930] merges my fixes into your changeset using your name, since you made the major part of the improvement. Please check it.

[Peter Kovacs]

Replying to deba:

The size of the graph to eps images didn't change, because the resolution of png generation is increased to 36.

I see, but I would prefer smaller images.

[Alpar Juttner]

Replying to kpeter:

[0438942f8930] merges my fixes into your changeset using your name, since you made the major part of the improvement. Please check it.

Why don't you do your own changes in your own changeset under your own name?

[Alpar Juttner]

[0549a6719af9] renames HyperCubeDigraph? to HypercubeDigraph?.

I don't like this changeset. The implemented graph _is_ an undirected graph, even if the implementation is incomplete. We should not rename it but instead we should write a ticket in order not to forget finishing it sooner or (more probably) later.

[Alpar Juttner]

I started to merge grid_graph into the main branch in the last two days (I was offline), but now I'm getting lost here. Could someone list me the changesets, that are superseded by another one (therefore should be thrown away)?

[Alpar Juttner]

Replying to kpeter:

[0438942f8930] merges my fixes into your changeset using your name, since you made the major part of the improvement. Please check it.

As far as I see now, the latest version [0438942f8930] posted by kpeter (using a pseudonym 'deba' in the changeset) contains only minor changes compared to [fb41d1fb4641] (in the Makefiles). Could you create a changeset on the top of [fb41d1fb4641] containing only these changes (under the real author)?

[Alpar Juttner]

Replying to kpeter:

Moreover I miss my fixes (see [fb41d1fb4641]) from your changeset.

And it is well done. Your changes should take place in your changeset, not elsewhere. (With some very rare exceptions.)

[Alpar Juttner]

One more thing: I can't understand why did you changed the nodeshape*.eps files? The image sizes can (and should) be set in the Makefile.

[Alpar Juttner]

I did the following with this GridGraph stuff

• I tweaked deba's last changeset ([7d23fd7b4b4e]) a bit: instead of double-rescaling everything in order to make grid_graph.png of the correct size, I rescaled only grid_graph.eps. Moreover, I cropped the image, thus that awful wide border disappeared. The result is in [160bf92c7cdc].
• Then I applied the changes of Peter on the top of it. It is in [052cecabcb71]

Both changesets are in the main branch now, so I hope we can put an end to this story.

[Peter Kovacs]

Replying to alpar:

Why don't you do your own changes in your own changeset under your own name?

I'm sorry. I had two reasons for that:

• First make check fails on all of Balazs's patches [109f3948dcc3], [dc254811acac] and [7d23fd7b4b4e] because of a missing friend class declaration. And it is a strong guideline not to commit such changesets into the main repository. But it's true, that I did not explain this problem in my ticket comments, I just note it in the commit log saying: "fixes and improvements".
• Second I just thought that there are so many variations that it would be easier for you to deal with only one improvement patch, instead of two.

And it is well done. Your changes should take place in your changeset, not elsewhere. (With some very rare exceptions.)

I thought that it might be a rare exception, but maybe I was wrong. :)

[Peter Kovacs]

Replying to alpar:

Both changesets are in the main branch now, so I hope we can put an end to this story.

I think, that's all right now.

[Peter Kovacs]

Replying to alpar:

[0549a6719af9] renames HyperCubeDigraph to HypercubeDigraph.

I don't like this changeset. The implemented graph _is_ an undirected graph, even if the implementation is incomplete. We should not rename it but instead we should write a ticket in order not to forget finishing it sooner or (more probably) later.

I renamed HyperCube to Hypercube, which is nothing to do with graph or digraph. So there are two separate questions:

1. Do we find Hypercube better than HyperCube?
2. Do we want to have an undirected hypercube graph instead of a directed one?

I really prefer using Hypercube instead of HyperCube, since it is only one word, see e.g. ​http://en.wikipedia.org/wiki/Hypercube.

If you prefer having an undirected implementation, then I will make a patch about this change.

[Peter Kovacs]

And what about the full graph structures? See [37557a46e298].

[Alpar Juttner]

Replying to kpeter:

I renamed HyperCube to Hypercube, which is nothing to do with graph or digraph.

Yes, I overlooked something. I assumed it was renamed from undirected to directed because I saw the signs of the renaming, especially the signs of a faulty one. (These tools are now in a nonexistent module called digraphs).

1. Do we find Hypercube better than HyperCube?

I'm happy with both.

2. Do we want to have an undirected hypercube graph instead of a directed one?

Yes.

I really prefer using Hypercube instead of HyperCube, since it is only one word, see e.g. ​http://en.wikipedia.org/wiki/Hypercube.

Then let's do so.

If you prefer having an undirected implementation, then I will make a patch about this change.

IMHO, this is not a matter of preference. The implemented graph _is_ undirected.

[Alpar Juttner]

Replying to kpeter:

I'm sorry. I had two reasons for that:

• First make check fails on all of Balazs's patches [109f3948dcc3], [dc254811acac] and [7d23fd7b4b4e] because of a missing friend class declaration. And it is a strong guideline not to commit such changesets into the main repository.

Yes, it is a strong guideline. Now make check passes on all added changesets, do they?

But it's true, that I did not explain this problem in my ticket comments,

Yes, you'd rather have explained it. But then I'm confused again, because - as far as I see - the changesets that are now in the repo compiles perfectly.

[Alpar Juttner]

Replying to kpeter:

And what about the full graph structures? See [37557a46e298].

Could you elaborate this question a bit more? Should I read it as "please review it"? Or does it mean that you are interested in this port and want to spend some time to review it thus you want to make sure nobody else has already done it?

[Balazs Dezso]

Latex image parameter fix

[Balazs Dezso]

I have fixed the latex includegraphics parameter in [b77fb8c32707]. However, do we need this line? I could not find any make parameter, for ps, pdf or dvi generation.

[Peter Kovacs]

Replying to alpar:

Yes, it is a strong guideline. Now make check passes on all added changesets, do they?

No, they don't. I tried to explain it. make check fails on [160bf92c7cdc], but it passes on [052cecabcb71], which contains the missing friend class declaration at line 187. That is why I wanted to merge these two changeset.

Yes, you'd rather have explained it. But then I'm confused again, because - as far as I see - the changesets that are now in the repo compiles perfectly.

[160bf92c7cdc] not, but all the others do compiles perfectly.

[Alpar Juttner]

Replying to kpeter:

No, they don't. I tried to explain it. make check fails on [160bf92c7cdc], but it passes on [052cecabcb71], which contains the missing friend class declaration at line 187.

I checked it again and I can confirm that for me make check reports

======================================================
All 19 tests behaved as expected (1 expected failures)
======================================================

on [160bf92c7cdc]. (With g++ (SUSE Linux) 4.3.3 20081002 (prerelease).)

A bit mysterious.

[Alpar Juttner]

Replying to kpeter:

And what about the full graph structures? See [37557a46e298].

Now, I had some time to look into them.

I basically like the full graph implementations. My only concern is the difference between FullGraph and FullDigraph has very little to do with they are directed or not, but instead, it has to do with the existence of loop edges. A better name would be better (as always), but at least this difference should be clearly (and noticeably) reflected in the doc.

Before you ask: I cannot tell you a better name.

[Peter Kovacs]

Replying to alpar:

I checked it again ...

I checked it again on lime.cs.elte.hu (64bit, gcc 4.1.0, SUSE Linux), it reports:

./lemon/grid_graph.h: In member function ‘lemon::GridGraphBase::Arc::operator lemon::GridGraphBase::Edge() const’:
./lemon/grid_graph.h:191: error: ‘lemon::GridGraphBase::Edge::Edge(int)’ is protected
./lemon/grid_graph.h:212: error: within this context

And I checked it on limetta.cs.elte.hu (32bit, gcc 4.1.2 20061115 (prerelease), SUSE Linux), it reports:

All 19 tests behaved as expected (1 expected failures)

It is really mysterious.

[Peter Kovacs]

I'm going to review the full graph implementations and rework the hypercube implementation to be undirected.

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

I checked it again ...

I checked it again on lime.cs.elte.hu (64bit, gcc 4.1.0, SUSE Linux), it reports:

On my openSuse 11.0, it compiles with gcc version 4.1.3 and with 4.3.3, but not with 3.3.3.

[Balazs Dezso]

Replying to kpeter:

I'm going to review the full graph implementations and rework the hypercube implementation to be undirected.

I were thinking about undirected hypercube graph, but it is not so obviuos, how can we make it. First of all, efficient static graph implementation can be made, when there is a efficiently computable mapping from [0..m-1] to the edges. I could not find such function, which can be computed in O(1) time.

[Alpar Juttner]

Replying to deba:

I were thinking about undirected hypercube graph, but it is not so obviuos, how can we make it. First of all, efficient static graph implementation can be made, when there is a efficiently computable mapping from [0..m-1] to the edges. I could not find such function, which can be computed in O(1) time.

For example you can do it as follows.

For a hypercube of dimension N, Let id be from the range [0..N*2^(N-1)], then node1 and node2 in the following code will point to the two endpoints of the edge corresponding to id.

int n = id && ((1<<N-1)-1);
int k = id >> N-1;
int node1 = ((n>>k)<<k+1) + (n && ((1<<k)-1));
int node2 = node1 + (1<<k);

[Balazs Dezso]

int n = id && ((1<<N-1)-1);
int k = id >> N-1;
int node1 = ((n>>k)<<k+1) + (n && ((1<<k)-1));
int node2 = node1 + (1<<k);

It is a very nice solution. I am just a bit sad, that I could not find out it. I think the undirected hypercube graph would be better than the current directed one.

[Peter Kovacs]

Replying to deba:

It is a very nice solution. I am just a bit sad, that I could not find out it. I think the undirected hypercube graph would be better than the current directed one.

I agree. This is so very nice, that I would like to implement it. :)

[Peter Kovacs]

Small improvements for full graphs

[Peter Kovacs]

[a598f74ea87e] contains small improvements for full graphs.

[Peter Kovacs]

Replying to kpeter:

[a598f74ea87e] contains small improvements for full graphs.

It contains faulty changes.

[80a4d0742e98] is a clear and better variant of the patch, use it instead of [a598f74ea87e].

[Peter Kovacs]

Small improvements for full graphs

[Peter Kovacs]

Replying to alpar:

I basically like the full graph implementations.

I also reviewed them, and I think they are all right.

A better name would be better (as always),

I can't find any better name. What about something like FullDigraphWithLoops? It seems to be too complicated.

but at least this difference should be clearly (and noticeably) reflected in the doc.

[80a4d0742e98] also improves the doc in this aspect.

[Alpar Juttner]

Replying to kpeter:

Replying to kpeter:

[a598f74ea87e] contains small improvements for full graphs.

It contains faulty changes.

[80a4d0742e98] is a clear and better variant of the patch, use it instead of [a598f74ea87e].

I encountered some problems when merging [80a4d0742e98] to the main branch. Could anyone create a merge changeset (and submit here, of course)?

[Alpar Juttner]

Replying to alpar:

I encountered some problems when merging [80a4d0742e98] to the main branch.

Namely, I merged it back to the main (see [77c7868019b0] in the attached bundle file), it compiles but digraph-test fails. Could anyone fix it? Please commit the fix simply on the top of [77c7868019b0], then I will do the dirty part of "changeset hacking".

[Peter Kovacs]

Replying to alpar:

Namely, I merged it back to the main (see [77c7868019b0] in the attached bundle file), it compiles but digraph-test fails. Could anyone fix it?

Which is more intresting, that it fails on limetta (32 bit), but it passes on lime (64 bit). I'm currently trying to find the problem.

[Peter Kovacs]

Replying to kpeter:

Which is more intresting, that it fails on limetta (32 bit), but it passes on lime (64 bit).

I was wrong here, I just forgot the hg up after hg unbundle on lime. :)

The attached patches fix the bug. [49a8e07e5702] is on the of [80a4d0742e98], [595de3a81389] is on the top of [77c7868019b0], otherwise they are exactly the same. Push one of them or do some changeset hackings, as you wish.

[Alpar Juttner]

Replying to kpeter:

The attached patches fix the bug. [49a8e07e5702] is on the of [80a4d0742e98], [595de3a81389] is on the top of [77c7868019b0], otherwise they are exactly the same. Push one of them or do some changeset hackings, as you wish.

Many thanks. In fact, pushed a third one into the main branch with a bit more informative commit log, see [aa75d24ba7d0]. But now full graphs are in the main.

As far as I see, the only pending issue in this ticket is the Hypercube Graph.

[Peter Kovacs]

Replying to alpar:

But now full graphs are in the main.

Many thanks.

As far as I see, the only pending issue in this ticket is the Hypercube Graph.

Yes, it is. I'm going to implement it in a few days using your ideas.

[Peter Kovacs]

Replying to kpeter:

As far as I see, the only pending issue in this ticket is the Hypercube Graph.

Yes, it is. I'm going to implement it in a few days using your ideas.

Here it is:

• [b4a01426c0d9] ports the directed version from svn (on the top of [3fb8ed1322de]).
• [a12eef1f82b2] reworks the implementation to be undirected (HypercubeDigraph --> HypercubeGraph).

[Alpar Juttner]

Replying to kpeter:

Here it is:

• [b4a01426c0d9] ports the directed version from svn (on the top of [3fb8ed1322de]).
• [a12eef1f82b2] reworks the implementation to be undirected (HypercubeDigraph --> HypercubeGraph).

• [efbd0ab50a77] merges them to the main branch.