Graph.h
#ifndef GRAPH_H
#define GRAPH_H
template <typename Weight>
class Edge {
public:
Weight weight;
unsigned int from, to;
Edge<Weight> *next;
Edge(int, int, Weight);
~Edge();
};
template <typename Weight, typenameVert>
class Vertex {
public:
Vert data;
Edge<Weight> *edges;
Vertex(Vert);
~Vertex();
};
template <typename Weight, typenameVert>
class Graph {
protected:
static constsize_t _defaultCount = 2;
size_t _vertexCount, _maxVertexCount;
public:
Graph();
~Graph();
bool insertEdge(unsigned int, unsigned int, Weight);
void addVertex(Vert);
void print();
size_tvertexCount();
bool hasEdge(unsigned int, unsigned int);
bool setEdge(unsigned int, unsigned int, Weight);
bool delEdge(unsigned int, unsigned int);
bool setVertexData(unsigned int, Vert);
unsigned int from;
Weight weight;
Vertex<Weight, Vert> **vertices;
Vertex<Weight, Vert>* getVertex(unsigned int);
Edge<Weight>* getEdge(unsigned int, unsigned int);
};
template<typename Weight, typenameVert>
Vertex<Weight, Vert>::Vertex(Vert data){
this->edges = 0;
this->data = data;
}
template<typename Weight, typenameVert>
Vertex<Weight, Vert>::~Vertex(){
if(edges) delete edges;
}
template<typename Weight>
Edge<Weight>::Edge(int from, int to, Weight weight): next(0){
this->from = from;
this->to = to;
this->weight = weight;
}
template<typename Weight>
Edge<Weight>::~Edge(){
if(next) delete next;
}
template<typename Weight, typenameVert>
Graph<Weight, Vert>::Graph(): _vertexCount(0){
_maxVertexCount = _defaultCount;
vertices = new Vertex<Weight, Vert>*[_maxVertexCount];
}
template<typename Weight, typenameVert>
Graph<Weight, Vert>::~Graph(){
if(vertices) delete [] vertices;
}
template<typename Weight, typenameVert>
Vertex<Weight, Vert>* Graph<Weight, Vert>::getVertex(unsigned int index) {
if(index >= this->_vertexCount) return 0;
return this->vertices[index];
}
template<typename Weight, typenameVert>
bool Graph<Weight, Vert>::insertEdge(unsigned int from, unsigned int to, Weight weight) {
if(from >= this->_vertexCount || to >= this->_vertexCount)
return false;
if(from == to)
return false;
if(this->hasEdge(from, to))
return false;
Edge<Weight> *new_edge = new Edge<Weight>(from, to, weight);
Vertex<Weight, Vert> *v_start = vertices[from];
Edge<Weight> *it_start = v_start->edges;
if(!it_start){
v_start->edges = new_edge;
} else {
while (it_start->next) it_start = it_start->next;
it_start->next = new_edge;
}
return true;
}
template<typename Weight, typenameVert>
void Graph<Weight, Vert>::addVertex(Vert data) {
if(this->_vertexCount == this->_maxVertexCount){
Vertex<Weight, Vert> **new_vertices = new Vertex<Weight, Vert>*[_maxVertexCount*2];
unsigned int i;
for (i = 0; i<_maxVertexCount; i++) {
new_vertices[i] = this->vertices[i];
}
new_vertices[i] = new Vertex<Weight, Vert>(data);
this->_maxVertexCount *= 2;
delete this->vertices;
this->vertices = new_vertices;
} else {
this->vertices[this->_vertexCount] = new Vertex<Weight, Vert>(data);
}
this->_vertexCount++;
}
template<typename Weight, typenameVert>
void Graph<Weight, Vert>::print() {
unsigned int i;
for (i = 0; i<this->_vertexCount; i++) {
Vertex<Weight, Vert> *v = this->vertices[i];
cout<<i<< "(" << v->data << "):\t";
if (v->edges) {
for (Edge<Weight> *it = v->edges; it; it = it->next) {
cout<< it->from << "->" << it->to << "(" << it->weight << ") ";
}
}
cout<<endl;
}
}
template<typename Weight, typenameVert>
size_t Graph<Weight, Vert>::vertexCount() {
return this->_vertexCount;
}
template<typename Weight, typenameVert>
bool Graph<Weight, Vert>::hasEdge(unsigned int from, unsigned int to) {
return!!(this->getEdge(from, to));
}
template<typename Weight, typenameVert>
Edge<Weight>* Graph<Weight, Vert>::getEdge(unsigned int from, unsigned int to) {
if(from >= this->_vertexCount || to >= this->_vertexCount)
return 0;
Edge<Weight> *it = this->vertices[from]->edges;
while(it){
if (it->from == from && it->to == to) return it;
it = it->next;
}
return 0;
}
template<typename Weight, typenameVert>
bool Graph<Weight, Vert>::setEdge(unsigned int from, unsigned int to, Weight weight) {
if (from > this->_vertexCount || to > this->_vertexCount) {
return false;
}
Edge<Weight> *edge = this->getEdge(from, to);
if (edge) {
edge->weight = weight;
return true;
} else return false;
}
template<typename Weight, typenameVert>
bool Graph<Weight, Vert>::delEdge(unsigned int from, unsigned int to) {
if(from >= this->_vertexCount || to >= this->_vertexCount)
return false;
Edge<Weight> *prev = vertices[from]->edges;
if(!prev)
return false;
if(prev->from == from &&prev->to == to){
Edge<Weight> *it = prev->next;
this->vertices[from]->edges = it;
delete prev;
return true;
} else {
Edge<Weight> *it = prev->next;
while (it) {
if (it->from == from && it->to == to) {
prev->next = it->next;
it->next = NULL;
delete it;
return true;
}
prev = it;
it = it->next;
}
}
return false;
}
template<typename Weight, typenameVert>
bool Graph<Weight, Vert>::setVertexData(unsigned int key, Vert data) {
if(key > this->_vertexCount)
return false;
this->vertices[key]->data = data;
returntrue;
}
#endif // GRAPH_H
Исходныйкодпрограммы