2
\$\begingroup\$

I've made a little implementation of an undirected graph, using FIFO lists, for one of my homeworks. Never really knew how to write a proper FIFO data structure, so I would be glad to see some opinion of yours.

#include <iostream>
#include <fstream>

using namespace std;

class Graph
{
    class Node
    {
        struct adj
        {
            int data;
            adj* next;
        };

        adj* head;
        adj* tail;
        int num;
    public:
        Node();
        Node(const Node&);
        Node& operator=(const Node&);
        bool is_empty();
        bool is_leaf();
        void push(int);
        int pop();
        void print();
        ~Node();
    };

    int num_nodes;
    Node* nodes;
public:
    Graph(int);
    Graph(ifstream&);
    Graph(const Graph&);
    void add_edge(int, int);
    Node& operator[](int);
    void print();
    ~Graph();
};

Graph::Node::Node()
{
    head=NULL;
    tail=NULL;
    num=0;
}

Graph::Node::Node(const Node& F)
{
    head=NULL;
    tail=NULL;
    num=0;

    adj* tmp=F.head;

    while(tmp)
    {
        push(tmp->data);
        tmp=tmp->next;
    }
}

Graph::Node& Graph::Node::operator=(const Node& F)
{
    if(this!=&F)
    {
        head=NULL;
        tail=NULL;
        num=0;

        adj* tmp=F.head;

        while(tmp)
        {
            push(tmp->data);
            tmp=tmp->next;
        }
    }

    return *this;
}

bool Graph::Node::is_empty()
{
    return head==NULL;
}

bool Graph::Node::is_leaf()
{
    return num==1;
}

void Graph::Node::push(int value)
{
    adj* tmp=new adj;

    tmp->data=value;
    tmp->next=NULL;

    if(is_empty())
    {
        head=tmp;
    }
    else
    {
        tail->next=tmp;
    }

    tail=tmp;

    num++;
}

int Graph::Node::pop()
{
    if(!is_empty())
    {
        adj* tmp=head;

        head=head->next;

        int value=tmp->data;

        delete tmp;

        num--;

        return value;
    }
    else
    {
        return -1;
    }
}

void Graph::Node::print()
{
    adj*tmp=head;

    while(tmp)
    {
        cout<<tmp->data<<" ";
        tmp=tmp->next;
    }
    cout<<endl;
}

Graph::Node::~Node()
{
    while(!is_empty())
    {
        pop();
    }
}

Graph::Graph(int num_nodes)
{
    this->num_nodes=num_nodes;
    nodes=new Node[num_nodes+1];
}

Graph::Graph(ifstream& f)
{
    f>>num_nodes;

    nodes=new Node[num_nodes+1];

    int start, end;

    while(f>>start>>end)
    {
        add_edge(start, end);
    }
}

Graph::Graph(const Graph& G)
{
    num_nodes=G.num_nodes;

    nodes=new Node[num_nodes+1];

    for(int i=1; i<=num_nodes; i++)
    {
        nodes[i]=G.nodes[i];
    }
}

void Graph::add_edge(int start, int end)
{
    nodes[start].push(end);
    if(start!=end)
    {
        nodes[end].push(start);
    }
}

Graph::Node& Graph::operator[](int i)
{
    return nodes[i];
}

void Graph::print()
{
    for(int i=1; i<=num_nodes; i++)
    {
        nodes[i].print();
    }

    cout<<endl;
}

Graph::~Graph()
{
    delete[] nodes;
}

int main()
{
    ifstream f("graph.txt");

    Graph G(f);

    G.print();

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ You seem to be correct with that guess :) \$\endgroup\$ – Vogel612 Apr 25 at 20:23
  • \$\begingroup\$ Welcome to Code Review. I have rolled back your last edit. Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Heslacher Apr 26 at 12:54
  • \$\begingroup\$ Oh, understood. \$\endgroup\$ – Balog Szilárd Apr 26 at 13:03
2
\$\begingroup\$

Add spaces to improve readability:

head = NULL;
while (tmp)
if (this != &F)

Member functions that do not change any of the class members should be declared with the const specifier:

bool is_empty() const;
bool is_leaf() const;

Some of your while loops could be rewritten as for loops. For example, the loop in the Node copy constructor could be rewritten as

for (adj* tmp = F.head; tmp != NULL; tmp = tmp->next)
    push(tmp->data);

Should a pop with an empty list be tolerated? Currently you silently ignore the problem by returning a -1. Would throwing an exception (to report the error) be better? Or at least a std::assert(false); before the return, so you can detect the problem in a debug build. Also, you don't need the else there, since the body of the if will return.

You have no error checking. In particular, add_edge will happily try to add an edge to a node that doesn't exist, resulting in Undefined Behavior and (if you're lucky) a crash. (The same applies to Graph::operator[]. You could add an assert check, or an at method that would check the bounds, similar to how std::vector operates.)

Your Graph copy constructor does not copy nodes[0].

Why are you using raw memory for Graph's nodes? You should use std::vector or some form of smart pointer.

\$\endgroup\$
  • \$\begingroup\$ I'm very thankful for your comment. Now I have added spaces, rewritten the while loops. I initially used exception handling but then removed it. Now I re-added it. There is still something I really don't understand. First, I start my indexes by 1, so that's why I'm not copying nodes[0], since it doesn't store any valuable data, just an empty list. The other thing, I thought the ~Node destructor frees up the allocated memory. Also, why should I delete the this object if I want to copy it? PS: I haven't learnt to use the STLs so that's why I didn't included them in my code. \$\endgroup\$ – Balog Szilárd Apr 26 at 12:05
  • \$\begingroup\$ @BalogSzilárd I completely missed ~Node since it isn't near the constructors. It would probably make sense to locate the destructor next to the constructors, since what they do is related. The assignment operator sets head to NULL, and doesn't free up any of the adj objects that are currently stored in this. \$\endgroup\$ – 1201ProgramAlarm Apr 26 at 13:56
  • \$\begingroup\$ OMG now I completely understand . Should I explicitly call the destructor as this->~Node() or just simply type the right code to do it? I'm completely grateful for your time and for your help. I thought it would be a good idea to write the destructors at the end of that list since it is the last thing a function executes, but it seems its not the case. Anyways, big thanks! Have a great day! \$\endgroup\$ – Balog Szilárd Apr 26 at 15:09
  • \$\begingroup\$ @BalogSzilárd Don't call the destructor. Since duplicating code is not a good idea, you can put what the destructor does into a (private) function (cleanup or something like that), then call that from the destructor and the copy assignment operator. Then maybe just do the memory handling that pop does, without having to track or return a value (or have multiple redundant checks for empty). \$\endgroup\$ – 1201ProgramAlarm Apr 26 at 19:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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