[Lemon-user] Memory error in MaxWeightedMatching?

[Alpár Jüttner]

Hi,

the problem is on your side. The culprit is this piece of code (the end
of tsp.cpp):

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);
}

Now, here you go through the edges of (the copy of) the original graph,
and check whether or not it is a matching edge. However, the matching
graph is only a subgraph of the full one, thus edgemap[] is not defined
for each edge.

Instead, you should iterate through the matching subgraph (matchg) and
use crossrefs instead of refs for obtaining the corresponding original
edges. In this way, you and also avoid creating a list of edges and then
iterating through it.

Btw, I believe using 'vector' instead of 'list' would be both faster and
need less memory, even if you don't know the size in advance, therefore
use push_back().


Regards,
Alpar


On Sat, 2011-12-10 at 17:41 +0100, Gereon Kremer wrote:
> Hi,
> 
> It's a bit difficult to take this completely out of the context. I
> attached an archive with the relevant code. Unfortunately, there is
> quite a lot of stuff done before, but I removed everything clearly
> irrelevant or after the "error" (actually, it's only a warning).
> As compensation, there is a Makefile :-)
> with "make memtest", valgrind is called with the arguments I used.
> 
> If the code is still to much, I can try to cut off some more lines :-)
> 
> Gereon
> 
> On 12/10/2011 08:02 AM, Alpár Jüttner wrote:
> > Hi Gereon,
> > 
> > Thank you for reporting the issue.
> > 
> > May I ask you to send us a simple compilable .cc file that shows this
> > symptom? It would be a great help in investigating the problem.
> > 
> > Regards,
> > Alpar
> > 
> > On Thu, 2011-12-08 at 20:03 +0100, 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
> >>
> > 
> >