Reference, but object unchanged?

[Markus Pitha]

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

 

[Puppet_Sock]

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

}

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,

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

 

[James Kanze]

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.

This is more of a meta comment, but...

In German, Knoten is the translation for the English word Node.
Nodes are typically elements in a graph, and your mention of
"depth-first search" seems to confirm this. If this is the
case, nodes have identity, and so shouldn't be copiable. And if
they're not copiable, then you can't have a vector<Knoten>.

I think your real problem is more at that level; you're copying
objects which have identity, and shouldn't be copied. (You
might have a lot of lower level problems as well, but until
you've fixed this one, I suspect that it is a waste of time to
talk about them.)

 

[Markus Pitha]

Hello,

I think your real problem is more at that level; you're copying
objects which have identity, and shouldn't be copied. (You
might have a lot of lower level problems as well, but until
you've fixed this one, I suspect that it is a waste of time to
talk about them.)

You were right. I just copied the content of the vector. I can solve the
problem when i use vecKnoten.at(kBez) in my method instead of (*k).
The algorithm finds the right components now. Ok, some nodes are still
print out twice, but that's some logical problem I should be able to
solve easily.


Markus

 

[James Kanze]

You were right. I just copied the content of the vector. I can solve the
problem when i use vecKnoten.at(kBez) in my method instead of (*k).

In other words, a reference to the value in the array, instead
of a copy of it.

I'm not sure exactly what you're doing, but it still sounds
suspicious to me. Every time I've had to program something
which looked like a graph, my node elements have been
uncopiable, with the copy constructor declared private, and not
implemented. Which, of course, means that I can't have a vector
of the nodes, only pointers to the nodes.

If the vector is being used for some sort of memory management
scheme, it can be made to work. But be very, very careful; some
operations on the vector will invalidate pointers to elements in
the vector. Except in very, very special cases, I'd use a
vector of pointers to the nodes, to avoid such problems. In
fact, I'd only reference the nodes through pointers. (If you
really need to copy nodes at some point, for algorithmic
reasons, you can always add a clone function, which accesses the
private copy constructor. This allows explicit copy, but you
won't accidentally get any implicit copies.)

The algorithm finds the right components now. Ok, some nodes
are still print out twice, but that's some logical problem I
should be able to solve easily.

Probably, but it could also be a curious side effect of an
invalid pointer, due to vector invalidating a pointer or a
reference to a node. (The behavior of using such a pointer or
reference is undefined. Which means that it can sometimes seem
to work.)

Unless you're a real expert, I think you should start by making
your nodes (Knoten) uncopiable, and go from there. That will
force you to think in terms of identity (objects), and will
prevent any accidental copying. That will also mean that you
need to use vector<Knoten*>, rather than simply vector<Knoten>,
and if the vector is "owner" of the nodes, you'll have to run
through it deleting all of the elements before allowing
destruction of the vector.

More generally, that means that you will have to consider memory
management issues. The simplest solution in your case is
probably to just install the Boehm collector, and use it.
Barring that, if any given node will only be used in a single
graph (no sharing), you can have the nodes belonging to the
Graph object: the only way to create a node in that case should
be through a factory function in the Graph object; that function
new's the node *and* adds it to a list of all nodes
(vector< Knoten* >). The destructor of Graph then delete's all
of the nodes in the list.

 

[Alf P. Steinbach]

* James Kanze:

Unless you're a real expert, I think you should start by making
your nodes (Knoten) uncopiable, and go from there. That will
force you to think in terms of identity (objects), and will
prevent any accidental copying. That will also mean that you
need to use vector<Knoten*>, rather than simply vector<Knoten>,
and if the vector is "owner" of the nodes, you'll have to run
through it deleting all of the elements before allowing
destruction of the vector.

It may be an explicit representation of nodes is not needed.

Anyway, the OP would probably benefit from using the Boost Graph library.

More generally, that means that you will have to consider memory
management issues. The simplest solution in your case is
probably to just install the Boehm collector, and use it.

That adds the complication of non-deterministic destruction (and zombie
objects, watered down class invariants etc. that programmers typically
introduce to deal with it) to the complications of the C++ deterministic
model, and it doesn't help with maintaining the graph structure on
removal of nodes. When you already have code that maintains the
structure correctly, doing correct C++ deterministic destruction is
almost trivial. So the Boehm collector doesn't really solve any problem
here, it just introduces new ones, both at the tool usage level and at
the programming level.

Instead, if automatic garbage collection is needed, i.e. if C++ is too
complicated for the combination of this development team / developer and
the problem at hand, then using a higher level language such as Java or
C#, or even a functional language, is the practical way to go.

That means dealing only with the problems of one resource handling
paradigm instead of dealing with the problems of many paradigms fighting
it out plus one of the most complicated programming languages in
widespread use.

Barring that, if any given node will only be used in a single
graph (no sharing), you can have the nodes belonging to the
Graph object: the only way to create a node in that case should
be through a factory function in the Graph object; that function
new's the node *and* adds it to a list of all nodes
(vector< Knoten* >). The destructor of Graph then delete's all
of the nodes in the list.

Yes, that's one way to do it from scratch. If nodes are ever removed,
however, back pointers will have to be introduced in order to do that
efficiently. As mentioned, it's not just about reclaiming memory but
also about maintaining the graph, and solving the latter (which is
necessary anyway) has a high chance of also solving the former.

Cheers,

- Alf

 

[James Kanze]

* James Kanze:

It may be an explicit representation of nodes is not needed.
Really?

Anyway, the OP would probably benefit from using the Boost Graph library.

<url:http://www.boost.org/libs/graph/doc/quick_tour.html>

Maybe, maybe not. (His goal may be to learn how to manage
dynamic structures himself, for example.)

That adds the complication of non-deterministic destruction

You must be kidding. Since when does a node have a non-trivial
destructor.

(and zombie objects, watered down class invariants etc. that
programmers typically introduce to deal with it) to the
complications of the C++ deterministic model, and it doesn't
help with maintaining the graph structure on removal of nodes.

What's the problem on removal of nodes?

When you already have code that maintains the structure
correctly, doing correct C++ deterministic destruction is
almost trivial.

That's why everyone gets it wrong here. Handling cycles (which
are typical in a graph) is non-trivial. There's no point in
making things harder than there have to be.

So the Boehm collector doesn't really solve any problem here,
it just introduces new ones, both at the tool usage level and
at the programming level.

Obviously, you're mind's made up, and you don't want to be
confused by facts. The fact is that the Boehm collector solves
all of the memory management problems (as always). It doesn't
solve any of the other problems, but it doesn't introduce any
new problems either---again, it *never* introduces new problems.

Instead, if automatic garbage collection is needed, i.e. if C++ is too
complicated for the combination of this development team / developer and
the problem at hand, then using a higher level language such as Java or
C#, or even a functional language, is the practical way to go.

It's not necessarily a question of being "too complicated".
It's just a question of using the most appropriate tool; the one
which requires the least work.

That means dealing only with the problems of one resource
handling paradigm instead of dealing with the problems of many
paradigms fighting it out plus one of the most complicated
programming languages in widespread use.

As I said above, you're mind's made up, and you don't want to be
confused by the facts. In practice, most resources needs
different handling anyway. The Boehm collector handles memory,
completely. The other resources still have to be handled.
Except, of course, that in the case of a graph, there aren't
usually any other resources.

 

[Kai-Uwe Bux]

Maybe, maybe not. (His goal may be to learn how to manage
dynamic structures himself, for example.)



You must be kidding. Since when does a node have a non-trivial
destructor.

I think that can happen in any graph whose nodes carry labels. In
particular, if the nodes have labels that involve containers like
std::vector<> or std::string<>, then the question arises as to how the
garbage collector interacts with the allocator used by the container. I
would also contend that at least string labeled nodes are not uncommon.

[snip]


Best

Kai-Uwe Bux

 

[James Kanze]

I think that can happen in any graph whose nodes carry labels.
In particular, if the nodes have labels that involve
containers like std::vector<> or std::string<>, then the
question arises as to how the garbage collector interacts with
the allocator used by the container. I would also contend that
at least string labeled nodes are not uncommon.

Good point. Obviously, you have to configure things so that the
garbage collector also collects memory allocated by such
containers.

The simplest solution is simply to route all allocations to the
garbage collector, and let it take care of all deallocations.
Delete still works as usual, of course, but you rarely need it,
except for entity objects with an explicit lifetime. This
doesn't work if you have third party libraries which "mask"
pointers in some way, of course, but such libraries are fairly
rare.