Reference, but object unchanged?

[Markus Pitha]

Hello,

in an recursion I try to change the elements called "Knoten" in a vector
vector<KnotenvecKnoten.
It's some kind of depth-first search. What I want to do is to find the
nodes of a graph which are connected. I think my algorithm works, but
changing the values to "visited = true" doesn't work due to any
reference problem.

First of all, I fill up the vector with every node (getWert() does this
job, j is a value of the column of the adjacency matrix which describes
the graph, so every value != 0 is a neighbour node of *k)

================================================== =
CLASS Adjazenzmatrix:
..
..

vector<KnotenvecKnoten;
..
..

for (int i = 0; i < groesse; i++) {
Knoten *k = new Knoten(i);
for (int j = 0; j < groesse; j++) {
if (getWert(i,j) != 0)
k->addNachbarknoten(j);
}
vecKnoten.push_back(*k);

}

---------------------------------

Now, this loop searches for components. So if every node is connected to
each other in my graph, findKomponenten() must only be invoke at once by
this loop, but it doesn't and this is not all as you will see then.

for (int kBez = 0; kBez < groesse; kBez++) {
if (vecKnoten.at(kBez).isVisited() == false) {
cout << "new Component" <<endl;
findKomponenten(&vecKnoten.at(kBez));
}
}

This is this function and the algorithm. Here you can see very good,
that the changing of the nodes doesn't even work in the same loop?
So no wonder why it doen't work outside the loop either. But what's the
problem?

void Adjazenzmatrix::findKomponenten(Knoten *k) {

if ((*k).isVisited() == false) {
(*k).setVisited();
cout << "Knoten " << (*k).getKnotennummer()+1 << ": (auf visited
gesetzt)" <<endl;
int nachbarCounter = 0;

while (nachbarCounter < (*k).getNachbarknotenAnzahl()) {

if ((*k).getNachbarknoten(nachbarCounter).isVisited() == false) {

cout << "Not visited yet: " <<
(*k).getNachbarknoten(nachbarCounter).getKnotennum mer()+1 <<endl;
(*k).getNachbarknoten(nachbarCounter).setVisited() ;
//ATTENTION: This following if is not needed for this program, but I
added it for testing and to see if setVisited() work, but it doesn't!
if
if ((*k).getNachbarknoten(nachbarCounter).isVisited() == false)
cout << "STILL NOT VISITED: " <<
(*k).getNachbarknoten(nachbarCounter).getKnotennum mer()+1 <<endl;

findKomponenten(&(*k).getNachbarknoten(nachbarCoun ter));
}
nachbarCounter++;
}
}
}

By the way, this line
findKomponenten(&(*k).getNachbarknoten(nachbarCoun ter)); leads to a
weird warning:
"Adjazenzmatrix.cpp:264: Warnung: Adresse eines temporären Wertes wird
ermittelt"
It means something like: address of a teporary value determined.
I guess it is ok due to the recursion, isn't it?
==================================================

For the better understanding, here are the invoked methods.
==================================================
CLASS Knoten

#include "Knoten.h"

Knoten::Knoten() {
knotenNr = 0;
visited = false;
}

Knoten::Knoten(int nr) {
knotenNr = nr;
visited = false;
}

Knoten::~Knoten() {
}

void Knoten::setKnotennummer(int n) {
knotenNr = n;
}

int Knoten::getKnotennummer() {
return knotenNr;
}

void Knoten::addNachbarknoten(Knoten k) {
nachbarknoten.push_back(k);
}

int Knoten::getNachbarknotenAnzahl() {
return nachbarknoten.size();
}

Knoten Knoten::getNachbarknoten(int knr) {
return nachbarknoten.at(knr);
}

void Knoten::setVisited() {
visited = true;
}

bool Knoten::isVisited() {
return visited;
}
=================================================
I have no clue what's wrong with the references, but I hope you will see
my mistakes.

Thanks,
Markus

[Puppet_Sock]

On Oct 26, 11:35 am, Markus Pitha <[e-mail]:
[snip]

vector<KnotenvecKnoten;
.
.

for (int i = 0; i < groesse; i++) {
Knoten *k = new Knoten(i);
for (int j = 0; j < groesse; j++) {
if (getWert(i,j) != 0)
k->addNachbarknoten(j);
}
vecKnoten.push_back(*k);

}

This is a memory leak, isn't it? A copy of the
object gets put in the vector. Each time you go
through this loop you will lose some memory that
never gets deleted.

I dunno what your problem is with not having the
content of the vector changed. Maybe you can reduce
the program to a minimal compilable code that shows
the problem.
Socks

[Markus Pitha]

Hello,

Puppet_Sock wrote:

This is a memory leak, isn't it? A copy of the
object gets put in the vector. Each time you go
through this loop you will lose some memory that
never gets deleted.

You are right. I corrected this mistake in my main program.

I dunno what your problem is with not having the
content of the vector changed. Maybe you can reduce
the program to a minimal compilable code that shows
the problem.
Socks

Ok, I've done it.
YOu can download the files here: http://test.pithax.net/referencetest.zip

It simulates a graph with actually 2 component.
Component 1 is a line where node 1 is connected to node 4.
Component 2 is a triangle of node 2, 3 and 5.

You will see that setVisited() won't work, so it passes every "visited"
node too.
Markus