COIN-OR::LEMON - Graph Library

Opened 5 years ago

Last modified 4 years ago

#462 new enhancement

Extended run time checking in debug mode

Reported by: alpar Owned by: alpar
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

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

Attachments (1)

81d113c593ef.patch (27.7 KB) - added by alpar 4 years ago.

Download all attachments as: .zip

Change History (11)

comment:1 Changed 5 years ago by kpeter

I like this proposal.

comment:2 follow-up: Changed 5 years ago by 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.

comment:3 in reply to: ↑ 2 ; follow-up: Changed 5 years ago by alpar

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.

comment:4 Changed 5 years ago by kpeter

I see, that's true.

comment:5 in reply to: ↑ 3 Changed 4 years ago by alpar


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.

comment:6 follow-up: Changed 4 years ago by alpar

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.

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

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?

comment:8 follow-up: Changed 4 years ago by kpeter

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.

Last edited 4 years ago by kpeter (previous) (diff)

Changed 4 years ago by alpar

comment:9 in reply to: ↑ 8 Changed 4 years ago by alpar

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!

comment:10 Changed 4 years ago by alpar

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.

Note: See TracTickets for help on using tickets.