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