Improvements for graphs

[Peter Kovacs]

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.

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

[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?

[Alpar Juttner]

Replying to kpeter:

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

• [625b61b1ab13] Add missing 'explicit' keywords.

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

• [7fed44a98e2e] Doc improvements and unification for graph concepts.

This is clear.

• [eef9c32052d0] Doc improvements, fixes and unifications for graphs.

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.

[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)

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

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

[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?

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

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

[Peter Kovacs]

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