Extended run time checking in debug mode

[Alpar Juttner]

When using more graph instances of the same time (e.g. ListDigraph) in a code, it is a very common error that a Node or Arc is used with a different graph that they actually belong to. For example a NodeMap may be indexed by a node belonging to another graph. These kind of errors remain hidden during the compilation.

I propose adding a pointer to the owner graph to each Node and Arc objects, and check their the validity of the relevant graph and map operations. This feature would be turned on in debug mode only.

Two things are worth checking:

• The item should belong to the corresponding graph
• The item should be valid (i.e. not INVALID and point to an existing item)

Here is a --- maybe incomplete --- list where checking could be made:

• source(), target(), u(), v(), runningNode(), baseNode()
• id()
• constructors of the iterators
• operator++() of the iterators (validity check only)
• *Map<>::operator[]()', *Map<>::set()',
• changeSource(), changeTarget(), reverse()

[Peter Kovacs]

I like this proposal.

[Peter Kovacs]

An additional idea: I think this checking functionality could be made available through the public API of graph structures regardless of the current debug mode. It would allow the client codes to make consistency checking whenever they find it reasonable.

[Alpar Juttner]

Replying to kpeter:

An additional idea: I think this checking functionality could be made available through the public API of graph structures regardless of the current debug mode. It would allow the client codes to make consistency checking whenever they find it reasonable.

This won't work, because it needs additional data in the Node/Arc? class (i.e. a pointer to the graph), which would be an unacceptable overhead in optimized mode.

[Peter Kovacs]

I see, that's true.

[Alpar Juttner]

This won't work, because it needs additional data in the Node/Arc? class (i.e. a pointer to the graph), which would be an unacceptable overhead in optimized mode.

Alternatively, these checking functions would always answer true in Release mode.

[Alpar Juttner]

I started implementing this feature. A short question - is it ok if this feature is turned of if LEMON_ENABLE_DEBUG is set or do we need a more fine-grained control?

Note that these checks have quite some memory and cpu time overhead.

[Alpar Juttner]

Replying to alpar:

I started implementing this feature.

And it immediately revealed a bug in digraph_test.cc. A nice challenge comes here - who can find it w/o this debug tool?

[Peter Kovacs]

Just a guess: in checkDigraphErase(), after deleting node n4, the code checks its outgoing and incoming arc list, which is obviously invalid. (The behavior of this should be undefined, but in the current implementation, the connecting arcs are deleted before node deletion, so the test passes unless new nodes are added again.)

Anyway, it seems to be a copy-paste bug.

[Alpar Juttner]

Replying to kpeter:

Just a guess: in checkDigraphErase(), after deleting node n4, the code checks its outgoing and incoming arc list, which is obviously invalid.

Congratulation, you got it!

[Alpar Juttner]

The the chgset [81d113c593ef] in the attached patch​ is a preliminary implementation of the idea. The path should be applied on the top of [ce896fa7fd65], see #477.

Currently, the extra debug checks are implemented in ListDigraph and ListGraph only. I keen on hearing your opinion before running ahead with implementing it in the other graphs, as well.