[Lemon-user] Memory error in MaxWeightedMatching?

[Gereon Kremer]

Hi,

I'm well aware of various extensions. You might notice that the MST I'm
using is not one out of lemon. The whole code is for some (extended)
university exercises, so the purpose is to write some heuristic for some
problem (where TSP seems to fit in quite well...). Therefore, we are
allowed to use the Matching algorithm, but not a tsp heuristic.

Thanks anyway,
Gereon

On 12/09/2011 05:13 PM, Kovács Péter wrote:
> Hi,
> 
> I can't answer the issue you encountered, but I would like to draw your
> attention to a LEMON contribution that provides TSP heuristic
> implementations, including Christofides' algorithm. You may be
> interested in it.
> 
> You can find the repository here:
> http://lime.cs.elte.hu/~kpeter/hg/hgwebdir.cgi/lemon-tsp/
> 
> In particular, you can download christofides_tsp.h from here:
> http://lime.cs.elte.hu/~kpeter/hg/hgwebdir.cgi/lemon-tsp/raw-file/dfaf4ebd7d46/lemon/christofides_tsp.h
> 
> 
> Currently, these codes are not part of the official LEMON releases, but
> they probably will be.
> 
> Best regards,
> Peter
> 
> 
> On 2011.12.08. 20:03, Gereon Kremer wrote:
>> Hi,
>>
>> I'm trying to use the MaxWeightedMatching class. While running the
>> program seems to work properly, some errors show up when running the
>> code with valgrind. I'm actually implementing a tsp heuristic
>> (christofides). below is the error message that valgrind gives me.
>>
>> ==20368== Memcheck, a memory error detector
>> ==20368== Copyright (C) 2002-2010, and GNU GPL'd, by Julian Seward et al.
>> ==20368== Using Valgrind-3.6.1-Debian and LibVEX; rerun with -h for
>> copyright info
>> ==20368== Command: ./main_2.exe
>> ==20368==
>> ==20368== Conditional jump or move depends on uninitialised value(s)
>> ==20368==    at 0x4267F5: lemon::ListGraphBase::Arc::operator
>> lemon::ListGraphBase::Edge() const (list_graph.h:859)
>> ==20368==    by 0x42CCBA: lemon::MaxWeightedMatching<lemon::ListGraph,
>> lemon::GraphExtender<lemon::ListGraphBase>::EdgeMap<int>
>>> ::matching(lemon::ListGraphBase::Edge const&) const (matching.h:1961)
>> ==20368==    by 0x429C54: TSP::tsp() (tsp.cpp:97)
>> ==20368==    by 0x402F76: main (main_2.cpp:27)
>> ==20368==
>> ==20368== Conditional jump or move depends on uninitialised value(s)
>> ==20368==    at 0x429C57: TSP::tsp() (tsp.cpp:97)
>> ==20368==    by 0x402F76: main (main_2.cpp:27)
>> ==20368==
>> ==20368==
>> ==20368== HEAP SUMMARY:
>> ==20368==     in use at exit: 0 bytes in 0 blocks
>> ==20368==   total heap usage: 142,120 allocs, 142,120 frees, 9,170,970
>> bytes allocated
>> ==20368==
>> ==20368== All heap blocks were freed -- no leaks are possible
>> ==20368==
>> ==20368== For counts of detected and suppressed errors, rerun with: -v
>> ==20368== Use --track-origins=yes to see where uninitialised values come
>> from
>> ==20368== ERROR SUMMARY: 6190 errors from 2 contexts (suppressed: 4
>> from 4)
>>
>> the corresponding part of tsp.cpp looks like this, line 97 being "if
>> (m.matching(cur))". this->g is the listgraph I'm working on. p.mst is a
>> set of edges that describe an mst on this graph.
>>
>>
>> MaxWeightedMatching<ListGraph, ListGraph::EdgeMap<int>>  m(matchg,
>> matchw);
>> m.init();
>> m.start();
>> m.run();
>>
>> ListGraph eulerg;
>> ListGraph::EdgeMap<ListGraph::Edge>  eulermap(eulerg);
>> ListGraph::NodeMap<ListGraph::Node>  eulernodemap(eulerg);
>> ListGraph::NodeMap<bool>  visited(eulerg);
>>
>> GraphCopy<ListGraph, ListGraph>  copy2(this->g, eulerg);
>> copy2.nodeCrossRef(eulernodemap);
>> copy2.edgeCrossRef(eulermap);
>> copy2.run();
>>
>> list<ListGraph::Edge>  edges;
>> for (ListGraph::EdgeIt e(eulerg); e != INVALID; ++e) edges.push_back(e);
>>
>> for (list<ListGraph::Edge>::iterator it = edges.begin(); it !=
>> edges.end(); ++it)
>> { // copy edges in matching
>>     ListGraph::Edge cur = edgemap[eulermap[*it]];
>>     if (m.matching(cur))
>>     {
>>         eulerg.addEdge(eulerg.u(*it), eulerg.v(*it));
>>     }
>>     if (p.mst->count(eulermap[*it]) == 0) eulerg.erase(*it);
>> }
>>
>>
>> what exactly is wrong with this code?
>> (if something is wrong that has nothing to do with the actuall error,
>> I'd be happy to hear this too ;-) ).
>>
>> thanks,
>> gereon
>> _______________________________________________
>> Lemon-user mailing list
>> Lemon-user at lemon.cs.elte.hu
>> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user