Reference, but object unchanged?
Hello,
in an recursion I try to change the elements called "Knoten" in a vector
vector<Knoten> vecKnoten.
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<Knoten> vecKnoten;
..
..
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).getKnotennummer()+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).getKnotennummer()+1 <<endl;
findKomponenten(&(*k).getNachbarknoten(nachbarCounter));
}
nachbarCounter++;
}
}
}
By the way, this line
findKomponenten(&(*k).getNachbarknoten(nachbarCounter)); 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