COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 10 years ago

#55 closed task (fixed)

Port nauty reader

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

Description

These files are affected:

  • lemon/dimacs.h
  • lemon/nauty_reader.h

Attachments (8)

96f7cc46c91c.patch (4.0 KB) - added by Balazs Dezso 10 years ago.
Port nauty reader
c6c6e1d863c4.patch (1.0 KB) - added by Balazs Dezso 10 years ago.
Swap parameters
nauty1_95df249983db.patch (2.6 KB) - added by Peter Kovacs 10 years ago.
nauty2_c4c933e05fc0.patch (1.8 KB) - added by Peter Kovacs 10 years ago.
nauty3_91e68d590e61.patch (1.2 KB) - added by Peter Kovacs 10 years ago.
nauty4_7c5d8de2eac7.patch (1.8 KB) - added by Peter Kovacs 10 years ago.
fix_636fa2f39f10.patch (848 bytes) - added by Peter Kovacs 10 years ago.
rename_0eec1736ff1d.patch (1.2 KB) - added by Peter Kovacs 10 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 11 years ago by Alpar Juttner

Milestone: LEMON 1.0 releasePost 1.0

Changed 10 years ago by Balazs Dezso

Attachment: 96f7cc46c91c.patch added

Port nauty reader

comment:2 Changed 10 years ago by Balazs Dezso

The patch [96f7cc46c91c] contains the port of the nauty reader.

comment:3 Changed 10 years ago by Peter Kovacs

Owner: changed from Alpar Juttner to Balazs Dezso

comment:4 in reply to:  2 ; Changed 10 years ago by Alpar Juttner

Replying to deba:

The patch [96f7cc46c91c] contains the port of the nauty reader.

This changeset went to the main. Two comments:

  • I would like to suggest swapping the parameters of readNauty() in order to be more conform with the lgf tools
  • What's the use of the current return value? Couldn't we return something useful instead (or just void)?

comment:5 in reply to:  4 Changed 10 years ago by Balazs Dezso

Replying to alpar:

  • I would like to suggest swapping the parameters of readNauty() in order to be more conform with the lgf tools

I will make a patch

  • What's the use of the current return value? Couldn't we return something useful instead (or just void)?

The tool used regularly in while loop, therefore a bool or an std::istream& return can show, that the file is over. However the std::istream& return value is more conventional, like std::getline().

Changed 10 years ago by Balazs Dezso

Attachment: c6c6e1d863c4.patch added

Swap parameters

comment:6 in reply to:  4 ; Changed 10 years ago by Balazs Dezso

Replying to alpar:

  • I would like to suggest swapping the parameters of readNauty() in order to be more conform with the lgf tools

The [c6c6e1d863c4] swaps the parameters

comment:7 in reply to:  6 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: newclosed

Replying to deba:

Replying to alpar:

  • I would like to suggest swapping the parameters of readNauty() in order to be more conform with the lgf tools

The [c6c6e1d863c4] swaps the parameters

It went to the main, thus I close the ticket.

comment:8 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: closedreopened

Oops. The DIMACS loaders hasn't been ported, thus this ticket shouldn't have been closed.

By the way, I find the API of the DIMACS tools very problematic. Do you have any idea how to make it better?

Changed 10 years ago by Peter Kovacs

Attachment: nauty1_95df249983db.patch added

Changed 10 years ago by Peter Kovacs

Attachment: nauty2_c4c933e05fc0.patch added

comment:9 Changed 10 years ago by Peter Kovacs

I attached two improvement patches related to the nauty reader: [95df249983db], [c4c933e05fc0].

comment:10 Changed 10 years ago by Peter Kovacs

From the web site of nauty package:

nauty is a program for computing automorphism groups of graphs and digraphs

However the documentation says that our tool only supports undirected graphs. Is it right? Can't this function be used for directed nauty files? It would be better if it could be.

comment:11 in reply to:  9 ; Changed 10 years ago by Alpar Juttner

Replying to kpeter:

I attached two improvement patches related to the nauty reader: [95df249983db], [c4c933e05fc0].

I dislike whitespace changes, and I really dislike changes that are unrelated from the purpose of the changeset (and from which is written in the commit log). For example [95df249983db] reformats two Doxygen comment blocks which are completely irrelevant to the nauty reader. Line-break changes can result in problems in the generated doc (Doxygen works often in a mysterious way).

It is much easier the locate accidental problems if we do not do nasty things like that.

Changed 10 years ago by Peter Kovacs

Attachment: nauty3_91e68d590e61.patch added

Changed 10 years ago by Peter Kovacs

Attachment: nauty4_7c5d8de2eac7.patch added

comment:12 in reply to:  11 ; Changed 10 years ago by Peter Kovacs

Replying to alpar:

I dislike whitespace changes, and I really dislike changes that are unrelated from the purpose of the changeset (and from which is written in the commit log).

Okay. [91e68d590e61] and [7c5d8de2eac7] are the clarified variants of the two former changesets.

comment:13 in reply to:  12 Changed 10 years ago by Alpar Juttner

Replying to kpeter:

Okay. [91e68d590e61] and [7c5d8de2eac7] are the clarified variants of the two former changesets.

Many thanks.

They are in the main branch now.

comment:14 Changed 10 years ago by Alpar Juttner

Summary: Port supports for other file formatsPort nauty reader

I created a separate ticket for porting the DIMACS readers, see #167.

So, if we consider the nauty reader to be finished, then we can close this ticket.

comment:15 in reply to:  10 Changed 10 years ago by Peter Kovacs

The only question is the support of direct graphs. I think Balazs could answer it.

comment:16 in reply to:  10 ; Changed 10 years ago by Balazs Dezso

Replying to kpeter:

However the documentation says that our tool only supports undirected graphs. Is it right? Can't this function be used for directed nauty files? It would be better if it could be.

Currently, I have found just one algorithm which generates directed graphs in nauty, namely the directg. The file format of this class is not well defined, because the directg cannot write digraph6 file, which should be the default output. The current output is simple text output, but I think it will be changed in the future.

However we can prepare for this format, for example we can rename the readNauty() to readNautyGraph(). What is your opinion?

comment:17 in reply to:  16 ; Changed 10 years ago by Peter Kovacs

Replying to deba:

Currently, I have found just one algorithm which generates directed graphs in nauty, namely the directg. The file format of this class is not well defined, because the directg cannot write digraph6 file, which should be the default output. The current output is simple text output, but I think it will be changed in the future.

Oops. Reading your comment I suppose that I made a faulty change in [7c5d8de2eac7] at line 41, since I thought that the 6 in graph6 is just a tipo. I'm sorry.

However we can prepare for this format, for example we can rename the readNauty() to readNautyGraph(). What is your opinion?

I think it is okay. It won't be so similar to the DIMACS function names, but as far as I understand a nauty file describes graphs, while a DIMACS file describes a problem related to a graph. This difference seems to be enough for this difference in the function names. So I support this renaming.

If you make a patch that renames the function, do not forget to add a corresponding line into the lemon-0.x-to-1.x.sh script.

comment:18 in reply to:  17 Changed 10 years ago by Alpar Juttner

Replying to kpeter:

Replying to deba:

Currently, I have found just one algorithm which generates directed graphs in nauty, namely the directg. The file format of this class is not well defined, because the directg cannot write digraph6 file, which should be the default output. The current output is simple text output, but I think it will be changed in the future.

Oops. Reading your comment I suppose that I made a faulty change in [7c5d8de2eac7] at line 41, since I thought that the 6 in graph6 is just a tipo. I'm sorry.

Please repair it before we all forget.

I think it is okay. It won't be so similar to the DIMACS function names, but as far as I understand a nauty file describes graphs, while a DIMACS file describes a problem related to a graph. This difference seems to be enough for this difference in the function names.

Not to mention that the API of the DIMACS reader is bad as is, so we should not target a compatibility with it.

So I support this renaming.

So do I.

Changed 10 years ago by Peter Kovacs

Attachment: fix_636fa2f39f10.patch added

Changed 10 years ago by Peter Kovacs

Attachment: rename_0eec1736ff1d.patch added

comment:19 Changed 10 years ago by Peter Kovacs

Replying to alpar:

Please repair it before we all forget.

See [636fa2f39f10].

So I support this renaming.

So do I.

See [0eec1736ff1d].

comment:20 Changed 10 years ago by Peter Kovacs

If these patches are accepted, we could close the ticket.

comment:21 Changed 10 years ago by Alpar Juttner

Resolution: fixed
Status: reopenedclosed
Note: See TracTickets for help on using tickets.