[Lemon-user] Memory error in MaxWeightedMatching?

[Kovács Péter]

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