[Lemon-user] Memory error in MaxWeightedMatching?

[Gereon Kremer]

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