4
\$\begingroup\$

I've created this adjacency list, but I don't like the design of the graph. The issue is that there is one pointer in the node to its adjacency list and there is a pointer in an adj_list node to the actual node. I am also using next pointers to traverse the graph in the order in which nodes were added and the list to get the adjacency list of a node.

Any suggestions?

#include <queue>


enum color{
    WHITE,
    GREY,
    BLACK
};

struct adj_list;

struct node{
    int id;
    int weight;
    color visited;
    adj_list* adj;
    node(int n){
        id = n;
        weight = _I32_MAX;
        visited = WHITE;
    }

};


    struct adj_list{
        adj_list* next;  //This next pointer for visiting each node one after another in the order in which the nodes were added to the graph
        adj_list* list;
        node* n;
        adj_list(node& _n){
            n = &(_n);
            next = NULL;
            list = NULL;
        }
    };

node* add_node(int id,std::queue<int> q , node* root)
{
    node* n = new node(id);
    adj_list* adj = new adj_list(*n);
    n->adj = adj;

    if(root == NULL){
      return n;
    }
    std::queue<adj_list*> q1;

    while(1){
        adj_list* iter = root->adj;
        if(q.empty())break;
        int k = q.front();
        q.pop();
        while(iter){    
            if(iter->n->id == k){
                q1.push(iter);
                adj_list*  temp = iter->list;
                iter->list = new adj_list(*n);
                iter->list->list = temp;
                break;
            }
            iter = iter->next;
        }
    }

    adj_list* iter = root->adj;
    while(iter->next){
        iter = iter->next;
    }

    iter->next = adj;

    while(!q1.empty()){
        adj_list* temp = q1.front();
        q1.pop();
        adj_list* new_adj = new adj_list(* temp->n);
        adj->list = new_adj;
        adj = new_adj;
    }
    return root;
}

Adding a new node to the graph:

std::queue<int> q;
q.push(4);
q.push(9);

add_node(20,q , &root);

Update:

I have made some changes here to make it more C++, but an issue here I don't like is that driver has to know about the other vertexes to add to their adjacency list. I'm not sure how to get rid of that if we have to create the graph incrementally.

Another is to provide the graph with a matrix, but that just beats the idea behind adjacency matrix.

#include "iostream"
#include "vector"
#include "list"

struct edge{



int destination_vertex;

    edge(int ver){
        destination_vertex = ver;
    }
    };

struct vertex{
    int id;
    std::list<edge>  list;
    vertex(int _id){
        id = _id;
    }
};


class graph
{
private:
    std::vector<vertex*> vertexes;
    int next;

public:
    graph(void){
        next = 0;
    }

    ~graph(void){}

    void add_node(std::vector<int> edges ){

        vertex* v = new vertex(next++);
        vertexes.push_back(v);

        for(unsigned int i=0;i<edges.size();i++){

            vertex* existing_vertex = vertexes[edges[i]];
            existing_vertex->list.push_back(*(new edge (v->id)));

            edge* e = new edge(edges[i]);
            v->list.push_back(*e);
        }
    }

    void print(){
        for(unsigned int i = 0 ; i < vertexes.size();i++){
            vertex* v =  vertexes[i]; 
            std::cout << v->id <<"->";
            for(std::list<edge>::iterator iter = v->list.begin() ; iter != (v->list).end();iter++)
            {
                std::cout << iter->destination_vertex <<",";
            }
            std::cout << std::endl;
        }
    }
};
\$\endgroup\$

1 Answer 1

5
\$\begingroup\$

e.g. of adding a new node to the graph

Well for starters I don't see the graph:

I would expect the code to be:

 Graph    graph;
 graph.add_node(20,q); // Add nodes to graph.

Stop passing pointers around.

node* add_node(int id,std::queue<int> q , node* root)

Pointers have no associated ownership semantics. This is normal in C. But if you are writing C++ you should never do this. Ownership symantis defines who owns and thus who is responsible for calling delete on dynamically allocated objects. If it is an automatic variable you should probably be passing a reference (or in the case more likely making add_node() a member of the graph object.

Also you manipulate node and adj_list directly from add_node. Again fine from a C perspective but not from a C++ one. You should ask the object to manipulate itself by asking it to perform some operation (ie method). Since your code is so intertwined without methods it makes it real hard to read and understand. So that's about all I have.

Update:

Comment on update section

For every call to new there MUST be a call to delete. Without this the code will leak memory. In your case here we don't actually need any calls to new so we can remove all the leaks by just using normal automatic variables.

// might be a bit overkill
// For just holding a destination vertex.
struct edge
{
    // This should really be private
    // Once created you don't really want it changing.
    // So make it hard to change accidentally by making it private.
    // Alternatively you can make it const (but this makes copying hard
    // so I would make it private and private an accessor)
    private: int destination_vertex;
    public:  int getDest() const {return destination_vertex;}

    // Prefer to use initializer lists.
    edge(int ver){
        destination_vertex = ver;
    }

    // i.e. Prefer to write like this
    edge(int ver)
        : destination_vertex(ver)
    {}

    // A friend for printing.
    friend std::ostream& operator<<(std::ostream& s, edge const& e)
    {
        return s << e.destination_vertex;
    }
};


struct vertex
{
    int id;                 // This should probably be const
                            // as it never changes.
                            // But because this makes copying hard
                            // prefer to make it private and provide
                            // an accessor.
    std::list<edge>  list;

    // Prefer initializer lists.
    // Also prefer not to put '_' on the front of your identifers.
    // The rules are non trivial and most people don't know the actual
    // rules so its is easy to get wrong (in this case you got it correct)
    //
    vertex(int id)
        : id(id)    // The compiler can easily distinguish between these too.
    {}

    friend std::ostream& operator<<(std::ostream& s, vertex const& v)
    {
          s << v.id << "->";
          std::copy(v.list.begin(), v.list.end(),
                    std::ostream_iterator<edge>(s, ","));
          return s;
    }
};

Lets fix some memory leaks.

class graph
{
    private:
        // No need for this to be vertex*
        std::vector<vertex*> vertexes;


        // If you just make it a vector of `vetrtex` then everything works
        // as expected and you don't need to call new anywhere.
        std::vector<vertex>   vertexes;
        int                   next;

    public:
        // Prefer initializer list
        // Don't put void as the parameter list.
        graph(void)
            : next(0)
        {}

        // You should have written this so it cleaned up all the
        // allocated memory. If your destructor does nothing then
        // don't write one, let the compiler generate one do the work
        //
        // Since we are not going to have any dynamic allocation just
        // delete it now.
        //
        // ~graph(void){}

        // Comment code that is non trivial it took me a while to
        // figure this out!
        //
        // Add a new node node 'n'
        // The vector of edges defines what node(s) 'n' connects too.
        //      add an edge from 'n' to each node in `edges'
        //      add an edge from each node in `edges' to 'n'
        //
        // Note It is assumed that `edges` does not contain any nodes
        //      larger than (n-1)

        // When passing non trivial objects pass by reference
        // If your code is not supposed to change the code make it const
        // as well. Thus the compiler warns you if you try and modify it
        // accidentally.
        void add_node(std::vector<int> const  & edges)
                                   /// ^^^^^  ^
        {
            // no need for dynamic allocation.
            // vector is already doing most of the work
            // vertex* v = new vertex(next++);
            // vertexes.push_back(v);

            // Rather just add a new element to vector
            // Then grab a reference to it for convenience.
            vertexes.push_back(vertex());
            vertex&  v = vertexes.back();  // a reference to the element you
                                           // just added.



            for(unsigned int i=0;i<edges.size();i++)
            {
                // Added comment to the beginning about this
                // assumption.
                vertex& existing_vertex = vertexes[edges[i]];

                // This:    *(new edge (v->id))
                // Dynamically allocates an edge then de-references
                // so it can be copied into a list. You lost all
                // information about the pointer you created with new
                // so the memory is leaked and lost.
                // There is no need to create dynamically allocated object
                // just use the int automatic value.

                existing_vertex.list.push_back(v.id);

                // This has the same problem as the last line.
                // apart from you are doing it in two steps so keep
                // the pointer (which you should have deleted after use)        
                // edge* e = new edge(edges[i]);
                // v->list.push_back(*e);


                // This can be replaced with
                v.push_back(edges[i]);




               // In fact I would get rid of all the above lines and
               // replace with code that looks symmetrical so that you
               // can see that you are adding edges in both directions.

               vertexes[edges[i]].list.push_back(v.id);
               vertexes[v.id].list.push_back(edges[i]);

            }
        }

        // Methods that do not change the state of the object should
        // be marked const. 

        void print()  const
        {       ///   ^^^^^

            // Sure you can iterate by index.
            // But you could just as easily have used an iterator.
            // Also prefer to use ++i rather than i++
            // It makes no difference for integers but if you change
            // changed the way you iterate then you don't need to think
            // am I using the correct increment style.
            for(unsigned int i = 0 ; i < vertexes.size();i++){

                // Get a reference for ease of use
                vertex& v =  vertexes[i]; 
                std::cout << v.id << "->";

                // Nice use of iterator.
                // But prefer const_iterator if you are not going
                // to modify the container.

                for(std::list<edge>::const_ iterator iter = v.list.begin() ; iter != v.list.end();iter++)
                {
                    std::cout << iter->destination_vertex <<",";
                }

                // Prefer '\n' over std::endl
                // The difference is that std::endl() outputs a '\n'
                // then calls flush on the stream. This makes it very
                // efficient (as the whole pointer of the buffer is
                // so we only flush to the physical stream rarely).
                std::cout << '\n';
            }
        }

        // Since we have defined output operators for edge and vertex
        // We can do the same for graph:
        friend std::ostream& operator<<(std::ostream& s, graph const& g)
        {
             std::copy(v.vertexes.begin(), v.vertexes.end(),
                       std::ostream_iterator<vertex>(s, "\n"));
             return s;
        }
        // Now you can print a graph like this:
        //    std::cout << g;

};

After cleaning up all the comments.
It looks like this:

Headers

#include <iostream>
#include <list>
#include <vector>
#include <iterator>

Edge

class edge
{   
    int destination_vertex;
    public:
        int getDest() const {return destination_vertex;}

        edge(int ver)
            : destination_vertex(ver)
        {}  

    friend std::ostream& operator<<(std::ostream& s, edge const& e)
    {   
        return s << e.destination_vertex;
    }   
};  

Vertex

class graph;
class vertex
{   
    friend class graph;
    int id; 
    std::list<edge>  list;

    public:
        vertex(int id) 
            : id(id)
        {}  

    friend std::ostream& operator<<(std::ostream& s, vertex const& v)
    {   
          s << v.id << "->";
          std::copy(v.list.begin(), v.list.end(),
                    std::ostream_iterator<edge>(s, ","));
          return s;
    }   
};  

Graph

class graph
{   
    private:
        std::vector<vertex>   vertexes;
        int                   next;

    public:
        graph()
            : next(0)
        {}  

        //
        // Add a new node node 'n'
        // The vector of edges defines what node(s) 'n' connects too.
        //      add an edge from 'n' to each node in `edges'
        //      add an edge from each node in `edges' to 'n'
        //
        // Note It is assumed that `edges` does not contain any nodes
        //      larger than (n-1)
        void add_node(std::vector<int> const  & edges)
        {   
            vertexes.push_back(vertex(next));

            for(unsigned int i=0;i<edges.size();++i)
            {   
               vertexes[edges[i]].list.push_back(next);
               vertexes[next].list.push_back(edges[i]);
            }   
            ++next;
        }   

        friend std::ostream& operator<<(std::ostream& s, graph const& g)
        {   
             std::copy(g.vertexes.begin(), g.vertexes.end(),
                       std::ostream_iterator<vertex>(s, "\n"));
             return s;
        }   
};  

Main

int main()
{
    graph   g;

    std::vector<int>    v;
    g.add_node(v);

    v.push_back(0);
    g.add_node(v);

    std::cout << g << "\n";
}
\$\endgroup\$
5
  • \$\begingroup\$ For there is no graph i thought i will use add_node(id,empty_q , NULL) to create the first node which will be set to root.. \$\endgroup\$
    – sethi
    Jun 11, 2013 at 14:07
  • \$\begingroup\$ @bapusethi: That's my point. There should be a graph object. Dynamically creating nodes (like the root) enherently leads to issues of ownership and thus to memory management and from their to memory leaks. You need a graph object to encapsulate this and handle ownership concerns. \$\endgroup\$ Jun 11, 2013 at 15:08
  • \$\begingroup\$ Yes looks much better and cleaner now.. \$\endgroup\$
    – sethi
    Jun 11, 2013 at 17:38
  • \$\begingroup\$ And if anything, if you want to use pointers, use std::{unique,shared}_ptr<...>. \$\endgroup\$ Nov 26, 2014 at 18:02
  • \$\begingroup\$ @Ryan: Though true a vast simplification. \$\endgroup\$ Nov 26, 2014 at 19:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.