Dear readers,

I'm in the process of learning C++ with the scarce resources that I have and I 
decided to make just a simple program in C++ to understand the issues involved.

The program implements a simple graph data structure with adjacency lists and is 
quite incomplete at this point. The source code is available at:
<http://www.ime.usp.br/~rbrito/graphs.cpp>.

I know many things that are still missing from it, but for my first purposes it 
seems to run fine. The compiler (GCC, in my case, from Debian's sid 
distribution) shows *no* warnings even when activating all that I know (which 
may not be sufficient).

Unfortunately (and this is the reason why I'm writing here) is that when I run 
it under valgrind (which is a tool to analyze memory leaks), I see that I have 
lost 240 bytes and more may be wasted with bigger graphs. It seems like the 
destructor is not performing all the actions that I wanted to.

I am *very* biased towards programming in C and programming with classes is a 
new thing for me. I would be grateful if anybody could help me with suggestions 
and comments on how to improve the program, so that I can use the language 
efficiently.


Thanks in advance, Rog�rio Brito.

-- 
Rog�rio Brito : rbrito@{mackenzie,ime.usp}.br : GPG key 1024D/7C2CAEB8
http://www.ime.usp.br/~rbrito : http://meusite.mackenzie.com.br/rbrito
Projects: algorithms.berlios.de : lame.sf.net : vrms.alioth.debian.org


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Rog�rio Brito wrote:
> Dear readers,
> 
> I'm in the process of learning C++ with the scarce resources that I have 
> and I decided to make just a simple program in C++ to understand the 
> issues involved.
> 
> The program implements a simple graph data structure with adjacency 
> lists and is quite incomplete at this point. The source code is 
> available at:
> <http://www.ime.usp.br/~rbrito/graphs.cpp>.
> 


I trusted you (I usually do not follow links provided by strangers but I
made an exception)

Of course you source is just a jumble when read in Windows (different
end of line code). I know you were well intentioned and did not want to
clutter up a newsgroup with code. However as long as the code is
reasonably short it is far better to post it here (means people do not
have to follow links provided by strangers, and there will be no
problems with format of your code.)

FWIW I do not consider your task to be a simple one, certainly not one
for writing as your first program but show us the code here and I at
least will try to comment on it.


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Rog�rio Brito wrote:

> I know many things that are still missing from it, but for my first 
> purposes it seems to run fine. The compiler (GCC, in my case, from 
> Debian's sid distribution) shows *no* warnings even when activating all 
> that I know (which may not be sufficient).
> 
> Unfortunately (and this is the reason why I'm writing here) is that when 
> I run it under valgrind (which is a tool to analyze memory leaks), I see 
> that I have lost 240 bytes and more may be wasted with bigger graphs. It 
> seems like the destructor is not performing all the actions that I 
> wanted to.

valgrind will help you to detect where the memory has been allocated, so
you get at least a clue where the error is.

> I am *very* biased towards programming in C and programming with classes 
> is a new thing for me. I would be grateful if anybody could help me with 
> suggestions and comments on how to improve the program, so that I can 
> use the language efficiently.

Allow me a couple of comments:

class Vertex {
private:
        int l;
        Vertex *following;

public:
        Vertex(int n=0): l(n), following(NULL) {}
        int label() { return l; }
        int label(int l_) { l = l_; return l; }
        Vertex* next() { return following; }
        Vertex* next(Vertex *v) { following = v; return v; }
};

First of all, I would add a copy constructor and an assignment operator.
Or at least make them private, because the compiler default
implementation does not what you want (it does a raw copy, including the
 linkage pointer). I would further recommend to represent a list of
vectors by one of the containers of the STL, and not by hand, unless you
have very very good reasons for why the STL is not suitable for you.
Third, I would make the program const-correct, i.e. add const qualifiers
where necessary. Naming getters and setters the same is probably a bit
misleading (at least to me). Probably you want to return a reference, so
you could write vertex->next() = w? (If at all, I would recommend using
the STL containers).

class Graph {
        int n;
        int m;
        Vertex **vertices;

public:
        Graph(int n_): n(n_), m(0), vertices(new Vertex *[n]) {
                for (int i = 0; i < n; i++)
                        vertices[i] = NULL;
        }


See above. Raw arrays should be substituted by vectors, or by any other
suitable container.


        Graph(const Graph& g): n(g.n), m(g.m), vertices(new Vertex *[n]) {
                // Now, perform deep copy
                for (int i = 0; i < n; i++) {

                        Vertex *v = g.vertices[i];
                        vertices[i] = NULL;

                        while (v != NULL) {
                                Vertex *w = new Vertex(v->label());
                                vertices[i]->next(w);
                                v = v->next();
                        }
                }
        }


This is not exception-safe. Consider what would happen if "new Vertex()"
throws. Then, the vertex-array is not yet initialized (or partially
initialized) and the class destructor will follow invalid pointers.
Furthermore, you access here vertices[i], while having initialized this
to NULL before. This will cause a segfault, at best, but is at least
undefined.




int main(void)
{
        Graph *g = new Graph(5);

        g->add_edge(1, 3);
        g->add_edge(1, 4);
        g->add_edge(2, 4);
        g->add_edge(3, 4);

        g->print_graph();

        return 0;
}

Here you allocate a new g, but never release it. Why do you allocate it
on the heap anyhow, wouldn't it be easier to use an automatic variable
for g?

As a remark, even though C++ *looks* like C, it is nevertheless very
different. It *can* be used similar to C, but it might be better (and
easier) to follow a different programming paradigm. Hints: Avoid raw
pointers, and raw arrays. Unless you have very specific needs, there are
better alternatives waiting for you.

So long,
	Thomas


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Thu,  3 Jan 2008 17:29:49 CST, Rog�rio Brito <rbrito@ime.usp.br>
wrote:

>Dear readers,
>
>I'm in the process of learning C++ with the scarce resources that I have
and I 
>decided to make just a simple program in C++ to understand the issues
involved.
>
>The program implements a simple graph data structure with adjacency lists
and is 
>quite incomplete at this point. The source code is available at:
><http://www.ime.usp.br/~rbrito/graphs.cpp>.
>
>I know many things that are still missing from it, but for my first
purposes it 
>seems to run fine. The compiler (GCC, in my case, from Debian's sid 
>distribution) shows *no* warnings even when activating all that I know
(which 
>may not be sufficient).
>
>Unfortunately (and this is the reason why I'm writing here) is that when I
run 
>it under valgrind (which is a tool to analyze memory leaks), I see that I
have 
>lost 240 bytes and more may be wasted with bigger graphs. It seems like the

>destructor is not performing all the actions that I wanted to.
>
>I am *very* biased towards programming in C and programming with classes is
a 
>new thing for me. I would be grateful if anybody could help me with
suggestions 
>and comments on how to improve the program, so that I can use the language 
>efficiently.
>
>
>Thanks in advance, Rog�rio Brito.
Well, the most obvious thing I see is that you have a 'new' without a
corresponding 'delete'...

	Graph *g = new Graph(5);
	
	g->add_edge(1, 3);
	g->add_edge(1, 4);
	g->add_edge(2, 4);
	g->add_edge(3, 4);
	
	g->print_graph();

	return 0;

You never seem to delete the object you created, Graph *g.

HTH


-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

In article <flisvl$h8a$1@aioe.org>, Rog�rio Brito <rbrito@ime.usp.br>
wrote:

> <http://www.ime.usp.br/~rbrito/graphs.cpp>.

Well I would hide the new operations in the standard library containers,
for starters,  Then the allocation/deallocation of heap entries becomes
automatic.  Also copy constructors, assignment operators, and
destructors become easier.
for example:

typedef std::vector<int> Vertex;

class Graph
{
   std::vector<Vertex>  vertices;
public:
   Graph(){}
   explicit Graph(int n):vertices(n){}
   // default copy ctor,assignment, dtor ok.
   void add_arc(int v1,int v2)
   {
      // place v2 at the back end of vertices[v1];
      vertices[v1].push_back(v2);
   }

   void print_graph(std::ostream &os)
   {
      for(int i=0;i!=vertices.size();++i)
      {
         os << "Vertex " << i << '\n';
         for(int j=0;j!=vertices[i].size();++j)
         {
            os << '\t' << vertices[i][j] << '\n';
         }
      }
   }
   void add_edge(int v1,v2)
   {
      add_arc(v1,v2);
      add_arc(v2,v1);
   }
};
Bye to memory leaks!!

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Jan 3, 6:29 pm, Rog�rio Brito <rbr...@ime.usp.br> wrote:

> Unfortunately (and this is the reason why I'm writing here) is that when I
run
> it under valgrind (which is a tool to analyze memory leaks), I see that I
have
> lost 240 bytes and more may be wasted with bigger graphs. It seems like
the
> destructor is not performing all the actions that I wanted to.

It shall perform them once it is called. Your code just never invokes
it. Use either automatic variable for your object or, if you insist on
the heap one (although there's no reason for it in this example), then
call delete on it. Since you are biased toward C, this should hardly
be a surprise - every malloc needs free.

For example:

int main(void)
{
	Graph g(5);

	g.add_edge(1, 3);
	g.add_edge(1, 4);
	g.add_edge(2, 4);
	g.add_edge(3, 4);

	g.print_graph();

	return 0;
}

Will give following output:

Vertex 0:
Vertex 1: 4 3
Vertex 2: 4
Vertex 3: 4 1
Vertex 4: 3 2 1
Graph Destructor called

HTH

Alex





-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Rog�rio Brito <rbrito@ime.usp.br> wrote:

> I'm in the process of learning C++ with the scarce resources that I have
and 
> I 
> decided to make just a simple program in C++ to understand the issues 
> involved.
> 
> The program implements a simple graph data structure with adjacency lists
and 
> is 
> quite incomplete at this point. The source code is available at:
> <http://www.ime.usp.br/~rbrito/graphs.cpp>.
> 
> I know many things that are still missing from it, but for my first
purposes 
> it 
> seems to run fine. The compiler (GCC, in my case, from Debian's sid 
> distribution) shows *no* warnings even when activating all that I know
(which 
> may not be sufficient).
> 
> Unfortunately (and this is the reason why I'm writing here) is that when I

> run 
> it under valgrind (which is a tool to analyze memory leaks), I see that I 
> have 
> lost 240 bytes and more may be wasted with bigger graphs. It seems like
the 
> destructor is not performing all the actions that I wanted to.

That is because the destructor isn't being called, put "delete g;" in 
main, or make it an auto variable to fix the leak. Generally, I must 
second all of Thomas Richter's comments.

Thomas missed a leak though...

   // operator=(const Graph&)
   Graph & operator=(const Graph &g) {
      n = g.n;
      m = g.m;
      vertices = new Vertex *[n];

      // Now, perform deep copy
      for (int i = 0; i < n; i++) {

         Vertex *v = g.vertices[i];
         vertices[i] = NULL;

         while (v != NULL) {
            Vertex *w = new Vertex(v->label());
            vertices[i]->next(w);
            v = v->next();
         }
      }
      return *this;
   }

What if *this has already been initialized with a set of vertices? You 
are throwing away the 'vertices' pointer without deleting it, or its 
contents.

The canonical op= looks something like this:

Graph& operator=( const Graph& g ) {
   Graph tmp( g ); // use copy constructor to copy 'g'
   swap( tmp ); // swap the contents of *this with the contents of tmp
   return *this;
      // upon return, the contents of tmp will be destroyed
      // with the destructor.
}

Or more compactly as:

Graph& operator=( Graph g ) { // 'g' is a copy of the incoming parameter
   swap( g );
   return *this;
}

In some cases, you can make a more efficient version of the op= than the 
above, but the above will always work (if the copy constructor, 
destructor and swap work of course.)

==== other issues ====
Graph has a member-variable 'm' that is assigned to properly, but never 
seems to be used for anything. Remove it, unless it has some purpose I 
didn't see.

Graph has a member-variable 'n' which seems to track the size of the 
'vertices' array. It should probably have a more descriptive name. 
Actually, both 'vertices' and 'n' can be replaced by a vector<Vertex*>. 
If you make that substitution, the code can be vastly simplified, and 
made much more dynamic as well.

Basically, your "Graph" class consists of 'n' single linked lists with 
'n' determined at object construction and it is up to Graph's clients to 
make sure they don't try to write past the bounds of Graph's array. The 
Graph class should guard against such errors.

Check this out:

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>
#include <map>

using namespace std;

typedef map<int, list<int> > VerticeMap;

void print_vertice(const VerticeMap::value_type& vert) {
   cout << "Vertex " << vert.first << ": ";
   copy(vert.second.begin(), vert.second.end(),
        ostream_iterator<int>(cout, " "));
   cout << endl;
}

class Graph {
   int m;
   VerticeMap vertices;
public:
   Graph(int n): m(0) { }
   
   void add_arc(int v1, int v2) {
      vertices[v1].push_front(v2);
   }
   
   void add_edge(int v1, int v2) {
      add_arc(v1, v2);
      add_arc(v2, v1);
   }
   
   void print_graph() {
      for_each(vertices.begin(), vertices.end(), &print_vertice);
   }
};

int main()
{
   Graph g(5);
   g.add_edge(1, 3);
   g.add_edge(1, 4);
   g.add_edge(2, 4);
   g.add_edge(3, 4); 
   g.print_graph();
}

The above code has slightly different behavior than yours, can you spot 
it?

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

In article <flisvl$h8a$1@aioe.org>, rbrito@ime.usp.br says...
> Dear readers,
> 
> I'm in the process of learning C++ with the scarce resources that I have
and I 
> decided to make just a simple program in C++ to understand the issues
involved.
> 
> The program implements a simple graph data structure with adjacency lists
and is 
> quite incomplete at this point. The source code is available at:
> <http://www.ime.usp.br/~rbrito/graphs.cpp>.
> 
> I know many things that are still missing from it, but for my first
purposes it 
> seems to run fine. The compiler (GCC, in my case, from Debian's sid 
> distribution) shows *no* warnings even when activating all that I know
(which 
> may not be sufficient).
> 
> Unfortunately (and this is the reason why I'm writing here) is that when I
run 
> it under valgrind (which is a tool to analyze memory leaks), I see that I
have 
> lost 240 bytes and more may be wasted with bigger graphs. It seems like
the 
> destructor is not performing all the actions that I wanted to.

That may not be the source of the problem. Just glancing through your 
code, one piece jumps out as a potential problem. Your Graph::operator= 
does not appear to work correctly when/if a Graph already contains 
anything. For example, it starts with:

		n = g.n;
		m = g.m;
		vertices = new Vertex *[n];

If vertices already points at some allocated memory, this will leak that 
memory. You never assign a Graph in your code, so I don't think that's 
the source of the leak you saw though.

Other than that, I'd probably implement Graph and Vertex using 
std::vector and std::list respectively. The code would look something 
like this:

class Vertex { 
	std::list<int> adjacents;
public:
	void add(int x) { adjacents.push_back(x); }

	std::ostream &print(std::ostream &os) const { 
		std::copy(adjacents.begin(), adjacents.end(),
			std::ostream_iterator<int>(os, "\t"));
		return os;
	}
};

std::ostream &operator<<(std::ostream &os, Vertex const &v) { 
	return v.print(os);
}

class Graph { 
	std::vector<Vertex> vertices;
public:
	Graph(int num_vertices) : vertices(num_vertices) {}

	void add_arc(int v1, int v2) { vertices[v1].add(v2);	}

	void add_edge(int v1, int v2) { 
		add_arc(v1, v2);
		add_arc(v2, v1);
 	}

	std::ostream &print(std::ostream &os) const { 
		std::copy(vertices.begin(), vertices.end(),
			std::ostream_iterator<Vertex>(os, "\n"));
		return os;
	}				
};

std::ostream &operator<<(std::ostream &os, Graph const &g) {
	return g.print(os);
}

For the sake of simplicity, I left out the "Vertex" label on each line, 
but that wouldn't be terribly difficult to add if you really want it.

Incidentally, while I used std::list for Vertex since you'd used a 
linked list representation, you could just as well use a vector, deque, 
or just about any other ordered collection. Likewise, since you never 
resize it after creation, I believe you should be able to use 
std::tr1::array instead of std::vector to implement Graph. These changes 
wouldn't have any material effect on the basic function though -- at 
most they'd be rather minor optimizations.

Adding the last piece there (the operator<< for a Graph) allows us to 
write out a graph in the usual way, so main comes out something like 
this:

	Graph g(5);
	
	g.add_edge(1, 3);
	g.add_edge(1, 4);
	g.add_edge(2, 4);
	g.add_edge(3, 4);
	
	std::cout << g;

Oh, I almost forgot to mention: the source of your leak was pretty 
simple: in main you dynamically allocated your Graph object, but you 
never deleted it. Since you never deleted it, its destructor never ran 
at all and all its contents was leaked. Since it didn't need to be 
dynamic anyway, I just allocated it automatically so it would be 
destroyed automatically upon going out of scope. Since we used standard 
containers, we didn't have to write the code for the copy constructor, 
copy assignment or destructor at all, and about the only memory leaks we 
might have would be due to problems in the standard library.

-- 
    Later,
    Jerry.

The universe is a figment of its own imagination.

      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

Hi,

Rog�rio Brito wrote:
> The program implements a simple graph data structure with adjacency 
> lists and is quite incomplete at this point. The source code is 
> available at:
> <http://www.ime.usp.br/~rbrito/graphs.cpp>.

I've rewritten your program a little, you can download it here: 
<http://technika.junior.cz/~avakar/private/rbrito-graphs.cpp>.

Once I changed those raw arrays into std::vector the program became much 
shorter. The copy constructor and assignment operator are both 
unnecessary and the destructor is left there only to print a message.

Also, in C++, you avoid using void (pun not intended) to denote empty 
parameter lists. Empty parentheses will do just fine.

I've also written function 'print_graph2' for you to demonstrate the use 
of iterators.

> Unfortunately (and this is the reason why I'm writing here) is that when 
> I run it under valgrind (which is a tool to analyze memory leaks), I see 
> that I have lost 240 bytes and more may be wasted with bigger graphs. It 
> seems like the destructor is not performing all the actions that I 
> wanted to.

You're seeing memory leaks because you're not deleting your graph before 
you return from main. You could fix the leak by adding a delete 
statement right before return. There is however no need to create the 
graph dynamically. Instead of

     Graph * g = new Graph(5);

write

     Graph g(5);

The object will get destroyed automatically.

> I am *very* biased towards programming in C and programming with classes 
> is a new thing for me. I would be grateful if anybody could help me with 
> suggestions and comments on how to improve the program, so that I can 
> use the language efficiently.

As was pointed out elsethread, C++ is best used in combination with its 
standard library and with proper idioms in mind. If you start slowly by 
ditching linked lists and raw arrays in favor of standard containers, 
you'll be on the right track. Another good thing is to read this group's 
FAQ (see the link in the signature).

Good luck. :-)
-- 
Martin


      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

On Jan 3, 8:35 pm, Francis Glassborow
<francis.glassbo...@btinternet.com> wrote:

> Of course you source is just a jumble when read in Windows (different
> end of line code).

Francis,

There are better tools than Notepad to deal with this kind of problem.
Visual Studio, Wordpad (write.exe), DOS Edit to name a few.

Alex

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]

{ considered as discussion on the policy, and let through. -mod }

Alex wrote:
> On Jan 3, 8:35 pm, Francis Glassborow
> <francis.glassbo...@btinternet.com> wrote:
> 
>> Of course you source is just a jumble when read in Windows (different
>> end of line code).
> 
> Francis,
> 
> There are better tools than Notepad to deal with this kind of problem.
> Visual Studio, Wordpad (write.exe), DOS Edit to name a few.
> 
> Alex
> 

indeed but that is not the main point. Code requiring comment should be
posted. I should not need to go elsewhere.

-- 
      [ See http://www.gotw.ca/resources/clcm.htm for info about ]
      [ comp.lang.c++.moderated.    First time posters: Do this! ]