COIN-OR::LEMON - Graph Library

Opened 16 years ago

Closed 15 years ago

#57 closed task (fixed)

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

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.1 release
Component: core Version:
Keywords: Cc:
Revision id:

Description (last modified by Alpar Juttner)

The following files are affected

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

Attachments (17)

37557a46e298.patch (21.4 KB) - added by Balazs Dezso 16 years ago.
hypercube_9654fcabeb82.patch (11.3 KB) - added by Peter Kovacs 16 years ago.
hypercube_0549a6719af9.patch (3.9 KB) - added by Peter Kovacs 16 years ago.
grid_ada5f74d1c9e.patch (17.9 KB) - added by Peter Kovacs 16 years ago.
109f3948dcc3.patch (41.8 KB) - added by Balazs Dezso 15 years ago.
Improvements on grid graph
fb41d1fb4641.patch (2.3 KB) - added by Peter Kovacs 15 years ago.
More improvements
dc254811acac.patch (48.6 KB) - added by Balazs Dezso 15 years ago.
New patch for grid graph
7d23fd7b4b4e.patch (48.6 KB) - added by Balazs Dezso 15 years ago.
Correct image and commit log
grid_0438942f8930.patch (48.0 KB) - added by Peter Kovacs 15 years ago.
New (merged) improvement changeset
b77fb8c32707.patch (657 bytes) - added by Balazs Dezso 15 years ago.
Latex image parameter fix
full_a598f74ea87e.patch (9.5 KB) - added by Peter Kovacs 15 years ago.
Small improvements for full graphs
full_80a4d0742e98.patch (10.3 KB) - added by Peter Kovacs 15 years ago.
Small improvements for full graphs
77c7868019b0.bundle (1.4 KB) - added by Alpar Juttner 15 years ago.
fulll_bugfix_49a8e07e5702.patch (559 bytes) - added by Peter Kovacs 15 years ago.
full_bugfix_595de3a81389.patch (559 bytes) - added by Peter Kovacs 15 years ago.
hypercube_port_b4a01426c0d9.patch (11.0 KB) - added by Peter Kovacs 15 years ago.
hypercube_rework_a12eef1f82b2.patch (22.1 KB) - added by Peter Kovacs 15 years ago.

Download all attachments as: .zip

Change History (69)

comment:1 Changed 16 years ago by Alpar Juttner

Description: modified (diff)
Summary: Port the special graph structures (full and grid)Port the special graph structures (full, hypercube and grid)

comment:2 Changed 16 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

comment:3 Changed 16 years ago by Peter Kovacs

Owner: changed from Alpar Juttner to Peter Kovacs
Status: newassigned

Changed 16 years ago by Balazs Dezso

Attachment: 37557a46e298.patch added

comment:4 Changed 16 years ago by 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.

Changed 16 years ago by Peter Kovacs

comment:5 Changed 16 years ago by 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.

Changed 16 years ago by Peter Kovacs

comment:6 Changed 16 years ago by Peter Kovacs

[0549a6719af9] renames HyperCubeDigraph to HypercubeDigraph.

Changed 16 years ago by Peter Kovacs

Attachment: grid_ada5f74d1c9e.patch added

comment:7 Changed 16 years ago by 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?

Changed 15 years ago by Balazs Dezso

Attachment: 109f3948dcc3.patch added

Improvements on grid graph

comment:8 Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

Attachment: fb41d1fb4641.patch added

More improvements

comment:9 Changed 15 years ago by 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?

Changed 15 years ago by Balazs Dezso

Attachment: dc254811acac.patch added

New patch for grid graph

comment:10 in reply to:  9 ; Changed 15 years ago by 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].

comment:11 in reply to:  10 ; Changed 15 years ago by 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.

comment:12 Changed 15 years ago by 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.

comment:13 in reply to:  12 ; Changed 15 years ago by 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.

Changed 15 years ago by Balazs Dezso

Attachment: 7d23fd7b4b4e.patch added

Correct image and commit log

comment:14 in reply to:  11 ; Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

Attachment: grid_0438942f8930.patch added

New (merged) improvement changeset

comment:15 in reply to:  14 ; Changed 15 years ago by 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.

comment:16 in reply to:  13 Changed 15 years ago by 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.

comment:17 in reply to:  15 ; Changed 15 years ago by 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?

comment:18 Changed 15 years ago by 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.

comment:19 Changed 15 years ago by 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)?

comment:20 in reply to:  15 Changed 15 years ago by 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)?

comment:21 in reply to:  11 Changed 15 years ago by 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.)

comment:22 Changed 15 years ago by 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.

comment:23 Changed 15 years ago by 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.

comment:24 in reply to:  17 ; Changed 15 years ago by 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. :)

comment:25 in reply to:  23 Changed 15 years ago by 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.

comment:26 in reply to:  18 ; Changed 15 years ago by 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.

comment:27 Changed 15 years ago by Peter Kovacs

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

comment:28 in reply to:  26 Changed 15 years ago by 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.

  1. 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.

comment:29 in reply to:  24 ; Changed 15 years ago by 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.

comment:30 in reply to:  27 Changed 15 years ago by 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?

Changed 15 years ago by Balazs Dezso

Attachment: b77fb8c32707.patch added

Latex image parameter fix

comment:31 Changed 15 years ago by 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.

comment:32 in reply to:  29 ; Changed 15 years ago by 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.

comment:33 in reply to:  32 ; Changed 15 years ago by 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.

comment:34 in reply to:  27 ; Changed 15 years ago by 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.

comment:35 in reply to:  33 ; Changed 15 years ago by 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.

comment:36 Changed 15 years ago by Peter Kovacs

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

comment:37 in reply to:  35 Changed 15 years ago by 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.

comment:38 in reply to:  36 ; Changed 15 years ago by 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.

comment:39 in reply to:  38 ; Changed 15 years ago by 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);

comment:40 in reply to:  39 ; Changed 15 years ago by 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.

comment:41 in reply to:  40 Changed 15 years ago by 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. :)

Changed 15 years ago by Peter Kovacs

Attachment: full_a598f74ea87e.patch added

Small improvements for full graphs

comment:42 in reply to:  34 ; Changed 15 years ago by Peter Kovacs

[a598f74ea87e] contains small improvements for full graphs.

comment:43 in reply to:  42 ; Changed 15 years ago by 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].

Changed 15 years ago by Peter Kovacs

Attachment: full_80a4d0742e98.patch added

Small improvements for full graphs

comment:44 Changed 15 years ago by 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.

comment:45 in reply to:  43 ; Changed 15 years ago by 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)?

Changed 15 years ago by Alpar Juttner

Attachment: 77c7868019b0.bundle added

comment:46 in reply to:  45 ; Changed 15 years ago by 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".

comment:47 in reply to:  46 Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

Changed 15 years ago by Peter Kovacs

comment:48 Changed 15 years ago by 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.

comment:49 in reply to:  48 ; Changed 15 years ago by 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.

comment:50 in reply to:  49 ; Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

Changed 15 years ago by Peter Kovacs

comment:51 in reply to:  50 ; Changed 15 years ago by 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:

comment:52 in reply to:  51 Changed 15 years ago by Alpar Juttner

Resolution: fixed
Status: assignedclosed

Replying to kpeter:

Here it is:

Note: See TracTickets for help on using tickets.