COIN-OR::LEMON - Graph Library

Opened 11 years ago

Closed 11 years ago

#91 closed enhancement (fixed)

Add section reader to the LGF tools

Reported by: Alpar Juttner Owned by: Balazs Dezso
Priority: major Milestone: LEMON 1.0 release
Component: core Version: hg main
Keywords: Cc: Akos Ladanyi
Revision id:

Description

Here comes two proposed interface for the reader (we might want to implement booth):

  • sectionStream(std::string name,F f). Here the parameter name is the section name (the word after @), while f is an unary functor, with an std::istream& parameter. When the reader finds a section that matches with name, then it calls f with an istream pointing to right after the section header line. f is required to recognize the end of the section and not to read further. Finally, f should return the number of read lines.
  • sectionLines(std::string name,F f). Here f takes an std::string as argument, an it will simply be called with each line of the matching section.

It would be important to have a section reader in LEMON 1.0, as it is necessary to port glemon.

Attachments (5)

section_reader.patch (9.0 KB) - added by Balazs Dezso 11 years ago.
70694e6bdcac.patch (6.9 KB) - added by Balazs Dezso 11 years ago.
94ebb18ab9c2.patch (16.9 KB) - added by Balazs Dezso 11 years ago.
a63ed81c57ba.patch (17.5 KB) - added by Balazs Dezso 11 years ago.
1e6af6f0843c.patch (16.8 KB) - added by Balazs Dezso 11 years ago.

Download all attachments as: .zip

Change History (27)

comment:1 in reply to:  description ; Changed 11 years ago by Balazs Dezso

Replying to alpar:

Here comes two proposed interface for the reader (we might want to implement booth):

  • sectionStream(std::string name,F f). Here the parameter name is the section name (the word after @), while f is an unary functor, with an std::istream& parameter. When the reader finds a section that matches with name, then it calls f with an istream pointing to right after the section header line. f is required to recognize the end of the section and not to read further. Finally, f should return the number of read lines.
  • sectionLines(std::string name,F f). Here f takes an std::string as argument, an it will simply be called with each line of the matching section.

It would be important to have a section reader in LEMON 1.0, as it is necessary to port glemon.

I support both interfaces, but I think the sectionStream() could not return the line number. It makes harder to process non line oriented formats, which the aim of this function.

comment:2 in reply to:  1 Changed 11 years ago by Alpar Juttner

Replying to deba:

It makes harder to process non line oriented formats, which the aim of this function.

Yes, it makes harder. But

  • I can't see any other good solution for keeping track the line numbers.
  • This interface will only be used by more complex section readers. This readers will probably want to report the line numbers on case of errors, therefore they will count the lines anyhow.

However, this latter bullet shows that this interface is not sufficient. We should also pass the line number offset of the first line of the section.

Changed 11 years ago by Balazs Dezso

Attachment: section_reader.patch added

comment:3 Changed 11 years ago by Balazs Dezso

I have uploaded a patch for section readers. The interface follows closely Alpar's suggestion, but the line number is passed as reference and it should be updated in the section processor.

comment:4 in reply to:  3 Changed 11 years ago by Alpar Juttner

Replying to deba:

I have uploaded a patch for section readers. The interface follows closely Alpar's suggestion, but the line number is passed as reference and it should be updated in the section processor.

Thanks, it looks great. I've already pushed it into the main branch, see [33247f6fff16]. Some questions still remain, however:

  • The documentation needs some spell-checking
  • Don't we also need a section writer? (I'm not sure.)
  • We could also call both sectionStream() and sectionLines() simply just section(). It would have an additional advantage that it would give a little bit less frustrating error message when it is used with a wrong functor.

comment:5 Changed 11 years ago by Balazs Dezso

  • The documentation needs some spell-checking

That's sure.

  • Don't we also need a section writer? (I'm not sure.)

In my opinion, the section writer should not be a member of the GraphWriter?, rather it should be some separate class. However, some support auxiliary class would be helpful.

  • We could also call both sectionStream() and sectionLines() simply just section(). It would have an additional advantage that it would give a little bit less frustrating error message when it is used with a wrong functor.

I'm not sure, but this kind of enable_if solution would be hard, because a functor can be of several types (struct/class, function, function pointer).

comment:6 Changed 11 years ago by Balazs Dezso

I would like to suggest to more classes in the LGF IO: SectionReader? and SectionWriter?. These classes can be used to write or read sections without writing and reading graph, and they contain just sectionLines() and sectionStream() members. On the reading side it is practical if you want to read just one section (for example an Lp problem with LpReader?). On the writing side it would provide the standard method of writing a section.

comment:7 in reply to:  6 Changed 11 years ago by anonymous

Replying to deba:

I would like to suggest to more classes in the LGF IO: SectionReader? and SectionWriter?.

Do we really need a SectionReader? Isn't it enough to make it possible somehow switch of reading the graph component? For example DigraphReader could have a skipArcSection() and a skipNodeSection() member. (Where the latter one would imply the first one.)

comment:8 Changed 11 years ago by Balazs Dezso

I have two reasons, why the SectionReader? is better solution for this task:

  • If we want to use (Dig|G)raphReader for this purpose, then a lot of superfluous parameters and settings should be given to the reader, for example the graph type, a fake graph object, the skip*() functions. It would cause quite a rubbish design.
  • In my opinion, some SectionWriter? is needful class in lemon, and for the symmetricity, the SectionReader? could be also implemented.

However, the skip*() functions would be beneficial features in the Reader class.

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

Replying to deba:

I have two reasons, why the SectionReader? is better solution for this task:

But do we need the section*() members in the GraphReader then?

Changed 11 years ago by Balazs Dezso

Attachment: 70694e6bdcac.patch added

comment:10 Changed 11 years ago by Balazs Dezso

The [70694e6bdcac] contains the skip*() functions. There is a slight difference from Alpar suggestion, the skipNodes() does not implies automatically the skipping of arcs, because the useNodes() functions could provide labels for the nodes.

comment:11 in reply to:  9 ; Changed 11 years ago by Balazs Dezso

Replying to alpar:

Replying to deba:

I have two reasons, why the SectionReader? is better solution for this task:

But do we need the section*() members in the GraphReader then?

In my opinion, this question shows a tradeoff between the simple interface and the multipass reading of the file. I can be persuaded about both options.

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

Replying to deba:

The [70694e6bdcac] contains the skip*() functions. There is a slight difference from Alpar suggestion, the skipNodes() does not implies automatically the skipping of arcs, because the useNodes() functions could provide labels for the nodes.

I don't understand. If you use useNodes(), then it will skip reading the @nodes section, won't it? What is the use case of skipNodes() without skipArcs() then?

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

Replying to deba:

In my opinion, this question shows a tradeoff between the simple interface and the multipass reading of the file. I can be persuaded about both options.

Well, let it be as you like it.

comment:14 in reply to:  12 ; Changed 11 years ago by Balazs Dezso

Replying to alpar:

I don't understand. If you use useNodes(), then it will skip reading the @nodes section, won't it? What is the use case of skipNodes() without skipArcs() then?

No, it won't, the useNodes() is just implies that the reader uses the already constructed nodes instead of creating new ones. But it parse the section, because the node map reading rules will be processed.

I write some examples about usage:

  • Graph with multiple arc sets. First pass: -, Second pass: useNodes() + skipNodes()
  • Reading just the node set. First pass: skipArcs()
  • Reading node map of path (it contains arc labels). First pass: -, Second pass: useNodes(), skipArcs()
  • Reading maps into FullGraph?: useNodes(), useArcs()

comment:15 in reply to:  14 ; Changed 11 years ago by Alpar Juttner

Replying to deba:

No, it won't, the useNodes() is just implies that the reader uses the already constructed nodes instead of creating new ones. But it parse the section, because the node map reading rules will be processed.

To check if I understand correctly: Is is possible the reread a @node section in order to read a new NodeMap and add it to an existing graph using the useNodes() member?

And what happens if there is a discrepancy between the labels passed to useNodes() and those are in the @nodes section? Is there any run-time check?

I write some examples about usage:

  • Graph with multiple arc sets. First pass: -, Second pass: useNodes() + skipNodes()

But why the skipNodes() is necessary here?

comment:16 in reply to:  15 Changed 11 years ago by Balazs Dezso

Replying to alpar:

To check if I understand correctly: Is is possible the reread a @node section in order to read a new NodeMap and add it to an existing graph using the useNodes() member?

Yes, it is possible.

And what happens if there is a discrepancy between the labels passed to useNodes() and those are in the @nodes section? Is there any run-time check?

There is runtime check, when a label in the file does not appear in the label map provided by useNodes(), a DataFormatError? exception is thrown. However, in the case of useArcs(), the correctness of the source and target is not checked.

I write some examples about usage:

  • Graph with multiple arc sets. First pass: -, Second pass: useNodes() + skipNodes()

But why the skipNodes() is necessary here?

It is not necessary, but it could be more efficient, because in this case it is not parsed twice.

Changed 11 years ago by Balazs Dezso

Attachment: 94ebb18ab9c2.patch added

comment:17 Changed 11 years ago by Balazs Dezso

The [94ebb18ab9c2] patch moves the section readers to distinct class.

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

Replying to deba:

The [94ebb18ab9c2] patch moves the section readers to distinct class.

The SectionReader has a copy constructor that has a very suspicious doc. What does it mean? And why do we need a copy constructor? Probably the same question applies to the LgfSections and the (Di)GraphReader classes.

comment:19 Changed 11 years ago by Balazs Dezso

The svn lemon and graph readers could not be copied, because the member data tags were dynamically allocated, and there wasn't support for clone such objects. It made impossible the implementation of an easy functional interface for the class, however it would be more usable, because the template parameters could be omitted. There is two possible solutions to solve the copy constructor problem. The first is to copy each dynamically constructed data members with some cloning support, while the second is to steal the data members. In my opinion the second one is less usual (but there are some examples, for example auto_ptr), but altogether it is more efficient and it does not cause problem in any way. In fine, this copy constructor may be private and graphReader like fucntions could be friend of GraphReader?. As I tried, it works on the gcc-{3.3|4.1|4.2|4.3} compilers, but I am not sure, that it is conform to the standard, and it works on other compilers too.

comment:20 in reply to:  19 Changed 11 years ago by Alpar Juttner

Replying to deba:

As I tried, it works on the gcc-{3.3|4.1|4.2|4.3} compilers, but I am not sure, that it is conform to the standard, and it works on other compilers too.

I think, being compilable with the all major C++ compilers is of a much higher importance than to conform somehow with the C++ standard. Thus, if it seems working, let's incorporate this change into Lemon.

Anyway, the expression "standard conformance of Lemon" is somewhat meaningless for me, for we cannot (and therefore do not want to) check it. It is mainly because the authors of the standard didn't take the hassle of creating a reference compiler or - at least - a reference syntax checker for the standard.

Changed 11 years ago by Balazs Dezso

Attachment: a63ed81c57ba.patch added

Changed 11 years ago by Balazs Dezso

Attachment: 1e6af6f0843c.patch added

comment:21 Changed 11 years ago by Balazs Dezso

I made two new patches:

The [a63ed81c57ba] patch is a replacement of [94ebb18ab9c2]. It defines functional interface for section reader.

The [1e6af6f0843c] patch moves the copy constructors to private.

The [70694e6bdcac] is older patch, but it is not applied yet.

comment:22 in reply to:  21 Changed 11 years ago by Alpar Juttner

Resolution: fixed
Status: newclosed

Replying to deba:

All of the patches are in the main branch now.

Note: See TracTickets for help on using tickets.