[Lemon-user] Issues using ReverseGraph adaptor - bug?

[David Franz Koza]

Dear all,

I have encountered some issues while using the ReverseGraph adaptor. The code compiles and works well on Windows using MSVC. When compiling on Linux (using gcc 7.1.0) it works well if I compile without any optimization flag. If I compile the same code using any optimization flag (e.g. -O1) I get a segmentation fault. You find the code and valgrind (leak-check=yes) output below. Am I using it incorrectly or is this a bug?

#include <lemon/smart_graph.h>
#include <lemon/adaptors.h>
#include <lemon/maps.h>
#include <lemon/dijkstra.h>

typedef lemon::SmartDigraph Digraph;

int main() {

Digraph dg;

// Add nodes
Digraph::Node u = dg.addNode();
Digraph::Node v = dg.addNode();
Digraph::Node w = dg.addNode();
Digraph::Node x = dg.addNode();

// Add arcs
Digraph::Arc a = dg.addArc(u, v);
Digraph::Arc b = dg.addArc(u, w);
Digraph::Arc c = dg.addArc(u, x);
Digraph::Arc d = dg.addArc(v, w);
Digraph::Arc e = dg.addArc(v, x);
Digraph::Arc f = dg.addArc(w, u);
Digraph::Arc g = dg.addArc(w, v);
Digraph::Arc h = dg.addArc(x, u);
Digraph::Arc i = dg.addArc(x, w);

// Define node and arc maps
Digraph::NodeMap<bool> nm_first(dg, true);
Digraph::ArcMap<bool> am_first(dg, true);
Digraph::ArcMap<int> am_distance(dg, 0);

lemon::Dijkstra<lemon::ReverseDigraph<const Digraph>, Digraph::ArcMap<int> > dijkstra(lemon::reverseDigraph(dg), am_distance);

dijkstra.run(u);

return 0;
}


Valgrind output (part of it):


==13120== Use of uninitialised value of size 8
==13120==    at 0x4E39470: pthread_mutex_lock (in /lib64/libpthread-2.12.so)
==13120==    by 0x404490: lemon::Dijkstra<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::DijkstraDefaultTraits<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> > >::run(lemon::SmartDigraphBase::Node) (lock.h:42)
==13120==    by 0x4016A8: main (Source.cpp:43)
==13120==
==13120== Use of uninitialised value of size 8
==13120==    at 0x4E38F73: __pthread_mutex_lock_full (in /lib64/libpthread-2.12.so)
==13120==    by 0x404490: lemon::Dijkstra<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::DijkstraDefaultTraits<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> > >::run(lemon::SmartDigraphBase::Node) (lock.h:42)
==13120==    by 0x4016A8: main (Source.cpp:43)
==13120==
==13120== Use of uninitialised value of size 8
==13120==    at 0x404496: lemon::Dijkstra<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::DijkstraDefaultTraits<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> > >::run(lemon::SmartDigraphBase::Node) (alteration_notifier.h:337)
==13120==    by 0x4016A8: main (Source.cpp:43)
==13120==
==13120== Invalid read of size 8
==13120==    at 0x50F1E90: std::__detail::_List_node_base::_M_hook(std::__detail::_List_node_base*) (list.cc:131)
==13120==    by 0x403FB8: _ZNSt7__cxx114listIPN5lemon18AlterationNotifierINS1_15DigraphExtenderINS1_16SmartDigraphBaseEEENS4_4NodeEE12ObserverBaseESaIS9_EE7emplaceIJS9_EEESt14_List_iteratorIS9_ESt20_List_const_iteratorIS9_EDpOT_ (list.tcc:92)
==13120==    by 0x4044A7: lemon::Dijkstra<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::DijkstraDefaultTraits<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> > >::run(lemon::SmartDigraphBase::Node) (stl_list.h:1215)
==13120==    by 0x4016A8: main (Source.cpp:43)
==13120==  Address 0xffffff30e9000008 is not stack'd, malloc'd or (recently) free'd
==13120==
==13120==
==13120== Process terminating with default action of signal 11 (SIGSEGV)
==13120==  Access not within mapped region at address 0xFFFFFF30E9000008
==13120==    at 0x50F1E90: std::__detail::_List_node_base::_M_hook(std::__detail::_List_node_base*) (list.cc:131)
==13120==    by 0x403FB8: _ZNSt7__cxx114listIPN5lemon18AlterationNotifierINS1_15DigraphExtenderINS1_16SmartDigraphBaseEEENS4_4NodeEE12ObserverBaseESaIS9_EE7emplaceIJS9_EEESt14_List_iteratorIS9_ESt20_List_const_iteratorIS9_EDpOT_ (list.tcc:92)
==13120==    by 0x4044A7: lemon::Dijkstra<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::DijkstraDefaultTraits<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> > >::run(lemon::SmartDigraphBase::Node) (stl_list.h:1215)
==13120==    by 0x4016A8: main (Source.cpp:43)
==13120==  If you believe this happened as a result of a stack
==13120==  overflow in your program's main thread (unlikely but
==13120==  possible), you can try to increase the size of the
==13120==  main thread stack using the --main-stacksize= flag.
==13120==  The main thread stack size used in this run was 10485760.
==13120==
==13120== HEAP SUMMARY:
==13120==     in use at exit: 73,188 bytes in 11 blocks
==13120==   total heap usage: 17 allocs, 6 frees, 73,452 bytes allocated
==13120==
==13120== 24 bytes in 1 blocks are definitely lost in loss record 6 of 11
==13120==    at 0x4C295BC: operator new(unsigned long) (vg_replace_malloc.c:298)
==13120==    by 0x403F9C: _ZNSt7__cxx114listIPN5lemon18AlterationNotifierINS1_15DigraphExtenderINS1_16SmartDigraphBaseEEENS4_4NodeEE12ObserverBaseESaIS9_EE7emplaceIJS9_EEESt14_List_iteratorIS9_ESt20_List_const_iteratorIS9_EDpOT_ (new_allocator.h:111)
==13120==    by 0x4044A7: lemon::Dijkstra<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int>, lemon::DijkstraDefaultTraits<lemon::ReverseDigraph<lemon::SmartDigraph const>, lemon::DigraphExtender<lemon::SmartDigraphBase>::ArcMap<int> > >::run(lemon::SmartDigraphBase::Node) (stl_list.h:1215)
==13120==    by 0x4016A8: main (Source.cpp:43)
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20170606/53aee383/attachment-0001.html>