[Lemon-user] Memory error in MaxWeightedMatching?

[Gereon Kremer]

Hi,

thanks for the hint.
I was able to fix this by checking for
	eulerg.valid(cur)
before calling m.matching().
This resolved the issue...

Thanks,
Gereon

On 12/11/2011 09:05 AM, Alpár Jüttner wrote:
> 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
>>>>
>>>
>>>
> 
>