COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

Last modified 9 years ago

#311 closed defect (fixed)

Improvements for graphs

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description


Attachments (11)

311-1-625b61b1ab13.patch (1.9 KB) - added by Peter Kovacs 9 years ago.
311-2-7fed44a98e2e.patch (59.8 KB) - added by Peter Kovacs 9 years ago.
311-3-eef9c32052d0.patch (62.2 KB) - added by Peter Kovacs 9 years ago.
311-4-e8953d052534.patch (3.0 KB) - added by Peter Kovacs 9 years ago.
311-5-eb8f6284708a.patch (3.4 KB) - added by Peter Kovacs 9 years ago.
311-6-63ba9934ba2f.patch (1.7 KB) - added by Peter Kovacs 9 years ago.
311-7-76b4dbb83521.patch (1.4 KB) - added by Peter Kovacs 9 years ago.
311-625b61b1ab13--76b4dbb83521.bundle (14.4 KB) - added by Peter Kovacs 9 years ago.
311-rebased-bd72f8d20f33--941f92a6fa2b.bundle (14.0 KB) - added by Peter Kovacs 9 years ago.
311-309-32baeb8e5c8f.patch (1.4 KB) - added by Peter Kovacs 9 years ago.
311-restore-alt-819ca5b50de0.patch (2.0 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (23)

Changed 9 years ago by Peter Kovacs

Attachment: 311-1-625b61b1ab13.patch added

Changed 9 years ago by Peter Kovacs

Attachment: 311-2-7fed44a98e2e.patch added

Changed 9 years ago by Peter Kovacs

Attachment: 311-3-eef9c32052d0.patch added

Changed 9 years ago by Peter Kovacs

Attachment: 311-4-e8953d052534.patch added

Changed 9 years ago by Peter Kovacs

Attachment: 311-5-eb8f6284708a.patch added

Changed 9 years ago by Peter Kovacs

Attachment: 311-6-63ba9934ba2f.patch added

Changed 9 years ago by Peter Kovacs

Attachment: 311-7-76b4dbb83521.patch added

Changed 9 years ago by Peter Kovacs

comment:1 Changed 9 years ago by Peter Kovacs

Status: newassigned

I attached seven changesets (both in patch files and in a bundle file).

  • [625b61b1ab13] Add missing 'explicit' keywords.
  • [7fed44a98e2e] Doc improvements and unification for graph concepts.
  • [eef9c32052d0] Doc improvements, fixes and unifications for graphs.
  • [e8953d052534] Add reserve functions to ListGraph and SmartGraph. (The digraph structures, namely ListDigraph and SmartDigraph already have such functions.)
  • [eb8f6284708a] Add a resize() function to HypercubeGraph just like the similar functions in other static graph structures, and extend the test files to check these functions.
  • [63ba9934ba2f] Much better implementation for node splitting in ListDigraph according to the solution used in SmartDigraph. It is much faster and does not invalidate any iterator like the former implementation.
  • [76b4dbb83521] Enable and check repeated restore() for snapshots in ListDigraph and ListGraph. Thus you can use snapshots like that:
      ListDigraph::Snapshot snapshot(digraph);
      // Add nodes and/or arcs
      snapshot.restore();
      // Add nodes and/or arcs
      snapshot.restore();
      ...
    
    For smart graph structures it works immediately, but for list graphs the snapshots have to be reattached after restoring. After a single use of restore() the modifications of the (di)graph is observed further until the snapshot object is destroyed, so it takes extra time in such cases. Therefore it is not obvious that this modification is good or not. However I suggest either applying it or adding a note to the doc saying such usage is not allowed and you have to call save() again if you need repeated restore.

comment:2 Changed 9 years ago by Peter Kovacs

According to the doc of ListDigraph, its ArcIt iterator must work using the node list and the outgoing arc lists instead of the incomming arc lists. See e.g. the notes for changeSource() and changeTarget(). Apart from that the notes for split() and contract() functions are erroneous, and if they are fixed (like in the attached patch [eef9c32052d0]), then they will also depend on the implementation of ArcIt.

Therefore the implementation or the doc must be modified. I do prefer modifying the implementation, i.e. applying changeset [c6157e490d8c] in #309 for two reasons:

  1. It would be consistent with ListGraph.
  2. I think it would cause better performance results in typical cases when the outgoing arcs of the nodes are added to the graph close to each other. See #309 for more details.

Note that the doc in the attached patch [eef9c32052d0] is valid only if this modification is also applied. I could rebase that patch on the top of these patches if it is important.

comment:3 Changed 9 years ago by Peter Kovacs

Another question: there are three iterator classes MapIt, ConstMapIt and ItemIt for all standard graph maps, however they are neither documented nor tested in the concept classes. Why? Should these features be hidden or should we document and test them?

comment:4 in reply to:  1 ; Changed 9 years ago by Alpar Juttner

Replying to kpeter:

I attached seven changesets (both in patch files and in a bundle file).

This changeset has been merge to branch 1.1 as [a27356ceb5bd].

This is clear.

I need some time to digest this.

  • [e8953d052534] Add reserve functions to ListGraph and SmartGraph. (The digraph structures, namely ListDigraph and SmartDigraph already have such functions.)

This is clear and good again.

  • [eb8f6284708a] Add a resize() function to HypercubeGraph just like the similar functions in other static graph structures, and extend the test files to check these functions.

Ditto.

  • [63ba9934ba2f] Much better implementation for node splitting in ListDigraph according to the solution used in SmartDigraph. It is much faster and does not invalidate any iterator like the former implementation.

One more nice changeset.

  • [76b4dbb83521] Enable and check repeated restore() for snapshots in ListDigraph and ListGraph. Thus you can use snapshots like that:

I'm not sure if it is a good idea, exactly because of the performance problem you mentioned. I would like to see a way to stop the function of the Snapshot without deallocating. Can't we find a way to provide both functionality at the same time (while keeping the API compatibility with SmartDigraph::Snapshot).

It may also happen that I'm just overly worrying about the performance issues here. Would be good to hear other's voices.

Changed 9 years ago by Peter Kovacs

comment:5 in reply to:  4 Changed 9 years ago by Peter Kovacs

Replying to alpar:

This changeset has been merge to branch 1.1 as [a27356ceb5bd].

The attached bundle file contains the rebased versions of the remaining 6 changesets:

  1. [bd72f8d20f33] Doc improvements and unification for graph concepts (#311)
  2. [853fcddcf282] Doc improvements, fixes and unifications for graphs (#311)
  3. [2e20aad15754] Add reserve functions to ListGraph and SmartGraph (#311)
  4. [9d6c3e8b2421] Add a resize() function to HypercubeGraph (#311)
  5. [456fa5bc3256] Much better implementation for node splitting (#311)
  6. [941f92a6fa2b] Enable and check repeated restore() for snapshots (#311)

Changed 9 years ago by Peter Kovacs

Attachment: 311-309-32baeb8e5c8f.patch added

comment:6 Changed 9 years ago by Peter Kovacs

[32baeb8e5c8f] is a rebased verson of [c6157e490d8c] from #309. It modifies the implementation of ListDigraph::ArcIt to use out-arc lists to make it consistent with the doc and the implementation of ListGraph. Moreover it could be typically faster.

Note that the doc in the above patches is valid only if they are merged with this changeset.

Changed 9 years ago by Peter Kovacs

comment:7 Changed 9 years ago by Peter Kovacs

[819ca5b50de0] is an alternative solution for [941f92a6fa2b]. It does not support repeated restore() calls in List(Di)Graph::Snapshot classes, it rather extends the doc that save() must be called again in such use cases.

This solution is "safer" with respect to the efficiency questions. On the other hand, it doesn't narrows the usability of snapshots, it is just less convenient in special cases.

comment:8 Changed 9 years ago by Peter Kovacs

The proposed changesets went to the main branch. [819ca5b50de0] was chosen instead of [941f92a6fa2b].

There is only one question left here:

Another question: there are three iterator classes MapIt, ConstMapIt and ItemIt for all standard graph maps, however they are neither documented nor tested in the concept classes. Why? Should these features be hidden or should we document and test them?

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

Replying to kpeter:

There is only one question left here:

Another question: there are three iterator classes MapIt, ConstMapIt and ItemIt for all standard graph maps, however they are neither documented nor tested in the concept classes. Why? Should these features be hidden or should we document and test them?

I propose closing this ticket and making a follow-up about this issue, targeting the 1.3 milestone.

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

Replying to alpar:

I propose closing this ticket and making a follow-up about this issue, targeting the 1.3 milestone.

See #318.

comment:11 Changed 9 years ago by Peter Kovacs

Resolution: fixed
Status: assignedclosed

comment:12 Changed 9 years ago by Peter Kovacs

An other improvement for graph structures can be found in [a143f19f465b]. It is attached to #68, since it also modifies StaticDigraph.

Note: See TracTickets for help on using tickets.