COIN-OR::LEMON - Graph Library

Opened 10 years ago

Closed 10 years ago

#55 closed task (fixed)

Port nauty reader

Reported by: alpar Owned by: deba
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 deba 10 years ago.
Port nauty reader
c6c6e1d863c4.patch (1.0 KB) - added by deba 10 years ago.
Swap parameters
nauty1_95df249983db.patch (2.6 KB) - added by kpeter 10 years ago.
nauty2_c4c933e05fc0.patch (1.8 KB) - added by kpeter 10 years ago.
nauty3_91e68d590e61.patch (1.2 KB) - added by kpeter 10 years ago.
nauty4_7c5d8de2eac7.patch (1.8 KB) - added by kpeter 10 years ago.
fix_636fa2f39f10.patch (848 bytes) - added by kpeter 10 years ago.
rename_0eec1736ff1d.patch (1.2 KB) - added by kpeter 10 years ago.

Download all attachments as: .zip

Change History (29)

comment:1 Changed 10 years ago by alpar

  • Milestone changed from LEMON 1.0 release to Post 1.0

Changed 10 years ago by deba

Port nauty reader

comment:2 follow-up: Changed 10 years ago by deba

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

comment:3 Changed 10 years ago by kpeter

  • Owner changed from alpar to deba

comment:4 in reply to: ↑ 2 ; follow-ups: Changed 10 years ago by alpar

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 deba

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 deba

Swap parameters

comment:6 in reply to: ↑ 4 ; follow-up: Changed 10 years ago by 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

comment:7 in reply to: ↑ 6 Changed 10 years ago by alpar

  • Resolution set to fixed
  • Status changed from new to closed

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

  • Resolution fixed deleted
  • Status changed from closed to reopened

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 kpeter

Changed 10 years ago by kpeter

comment:9 follow-up: Changed 10 years ago by kpeter

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

comment:10 follow-ups: Changed 10 years ago by kpeter

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 ; follow-up: Changed 10 years ago by alpar

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 kpeter

Changed 10 years ago by kpeter

comment:12 in reply to: ↑ 11 ; follow-up: Changed 10 years ago by kpeter

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

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

  • Summary changed from Port supports for other file formats to Port 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 kpeter

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

comment:16 in reply to: ↑ 10 ; follow-up: Changed 10 years ago by deba

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 ; follow-up: Changed 10 years ago by 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.

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

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 kpeter

Changed 10 years ago by kpeter

comment:19 Changed 10 years ago by kpeter

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 kpeter

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

comment:21 Changed 10 years ago by alpar

  • Resolution set to fixed
  • Status changed from reopened to closed
Note: See TracTickets for help on using tickets.