Добавил:
Studfiles2
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Лабораторная работа 3 / lab3 / Sketcher / container / Graph
.h// Copyright (C) 1991 - 1999 Rational Software Corporation
#if defined (_MSC_VER) && (_MSC_VER >= 1000)
#pragma once
#endif
#ifndef _INC_GRAPH_46F8FA7D014A_INCLUDED
#define _INC_GRAPH_46F8FA7D014A_INCLUDED
//////////////////////////////////////////////////////////////////////////
#include <ostream>
#include <string>
#include <list>
#include "container/Ribble.h"
#include "container/Iterator.h"
#include "container/ExternalGraphIterator.h"
#include "exceptions/GraphException.h"
#include "exceptions/RibbleExistsException.h"
#include "exceptions/RibbleNotFoundException.h"
#include "exceptions/VertexNotFoundException.h"
//////////////////////////////////////////////////////////////////////////
template<class T> class Ribble;
template<class T> class Iterator;
template<class T> class ExternalGraphIterator;
//////////////////////////////////////////////////////////////////////////
//граф на базе списка ребер
template<class T> class Graph
{
private:
//список ребер
list< Ribble<T> *>* _ribbleList;
//внутрениий итератор
template<class T>
class GraphIterator : public Iterator<T>
{
private:
// локальная копия указателя на список
list< Ribble <T>* >* _innerList;
// итератор обхода списка рёбер
list< Ribble <T>* >::iterator _iter;
public:
//перейти к первому эл-ту
virtual Ribble<T>* first()
{
if (_innerList->size() == 0)
{
return NULL;
}
else
{
_iter = _innerList->begin();
return *_iter;
}
}
//перейти к последнему эл-ту
virtual Ribble<T>* last()
{
if (_innerList->size() == 0)
{
return NULL;
}
else
{
first();
Ribble<T>* res = NULL;
while (hasNext())
{
res = next();
}
return res;
}
}
//перейти к следующему эл-ту
virtual Ribble<T>* next()
{
Ribble<T>* res = *_iter;
_iter++;
return res;
}
//перейти к предыдущему эл-ту
virtual Ribble<T>* previous()
{
_iter--;
Ribble<T>* res = *_iter;
return res;
}
virtual bool hasPrevious()
{
return
_innerList->size() > 0 &&
_iter != _innerList->begin();
}
virtual bool hasNext()
{
return
_innerList->size() > 0 &&
_iter != _innerList->end();
}
GraphIterator(list< Ribble<T>* >* innerList)
{
_innerList = innerList;
_iter = _innerList->begin();
cout<<"[graph_iterator] graph iterator created\n";
}
};
public:
// количество ребер в графе
int getRibbleCount() const
{
return _ribbleList->size();
}
//итератор по списку инцидентных ребер
ExternalGraphIterator<T>* getNearestRibbles(T* vertex)
{
if (vertex == NULL)
{
throw new GraphException("Nillable vertices are not allowed!");
}
Graph<T>* res = new Graph<T>();
Iterator<T>* iter = getIterator();
while (iter->hasNext())
{
Ribble<T>* current = iter->next();
if (!current->isLoop() && current->contains(vertex))
{
res->addRibble(current);
}
}
return new ExternalGraphIterator<T>(res);
}
// связать две вершины графа ребром
void linkVertices(T* vertex1, T* vertex2)
{
if (vertex1 == NULL || vertex2 == NULL)
{
throw new GraphException("Nillable vertices are not allowed!");
}
Iterator<T>* iter = getIterator();
// удостоверяемся, что такие вершины есть
bool v1Present = false;
bool v2Present = false;
Ribble<T>* firstRibble = NULL;
Ribble<T>* secondRibble = NULL;
while ( iter->hasNext() && !(v1Present && v2Present) )
{
Ribble<T>* current = iter->next();
if (!v1Present && current->contains(vertex1))
{
v1Present = true;
// запоминаем ребро
firstRibble = current;
}
if (!v2Present && current->contains(vertex2))
{
v2Present = true;
// запоминаем ребро
secondRibble = current;
}
}
if ( !v1Present || !v2Present)
{
throw new VertexNotFoundException("no vertex to link");
}
else if (v1Present && v2Present)
{ // вершины найдены
// дуги не храним, избавляемся от них
if (firstRibble->isLoop())
{
removeRibble(firstRibble);
}
if (secondRibble->isLoop())
{
removeRibble(secondRibble);
}
// добавляем ребро
addRibble(vertex1, vertex2);
}
}
//очистить граф. очистка объектов по указателям не производится
void clear()
{
cout<<"\n[graph] clearing graph\n";
Iterator<T>* iter = getIterator();
while (iter->hasNext())
{
Ribble<T>* current = iter->next();
delete current;
}
_ribbleList->clear();
cout<<"[graph] graph cleared\n";
}
//добавить ребро по двум вершинам
void addRibble(T* vertex1, T* vertex2)
{
if (vertex1 == NULL || vertex2 == NULL)
{
throw new GraphException("Nillable vertices are not allowed!");
}
cout<<"\n[graph] adding ribble, checking if it already exists\n";
Ribble<T>* ribble = new Ribble<T>(vertex1, vertex2);
addRibble(ribble);
};
//добавить готовое ребро
void addRibble(Ribble<T>* ribble)
{
// проверяем, нет ли уже такого ребра
Iterator<T>* iter = getIterator();
bool isPresent = false;
while (iter->hasNext() && !isPresent)
{
Ribble<T>* current = iter->next();
if ( current->equals(ribble) )
{
isPresent = true;
throw new RibbleExistsException("cannot add: ribble already exists in graph");
}
}
// если нет - добавляем
if (!isPresent)
{
_ribbleList->push_back(ribble);
cout<<"[graph] ribble added successfully\n";
}
};
//добавить вершину в граф, на выходе - вершина, к которой присоединена новая
T* addVertex(T* vertex)
{
if (vertex == NULL)
{
throw new GraphException("Nillable vertices are not allowed!");
}
// проверяем, нет ли ребра c одной и той же вершиной
Iterator<T>* iter = getIterator();
Ribble<T>* current = NULL;
while (iter->hasNext())
{
current = iter->next();
if ( *(current->get__vertex1()) == *(current->get__vertex2()) )
{ // вершины одинаковы - заменяем одну вершину и выходим
current->set__vertex2(vertex);
return current->get__vertex1();
}
}
if (current!=NULL)
{ // такого ребра нет - присоединяем к вершине последнего ребра
_ribbleList->push_back(new Ribble<T>(current->get__vertex2(), vertex));
return current->get__vertex2();
}
else
{ // ребер еще вообще нет
_ribbleList->push_back(new Ribble<T>(vertex, vertex));
return vertex;
}
};
// удалить ребро
void removeRibble(Ribble<T>* ribble)
{
// проверяем, есть ли такое ребро
// проверка не обязательна, но нужна, чтобы продемонстрировать экспешен =)
Iterator<T> *iter = getIterator();
bool isPresent = false;
while (iter->hasNext() && !isPresent)
{
Ribble<T>* current = iter->next();
if ( current->equals(ribble) )
{ // если есть - удаляем
isPresent = true;
_ribbleList->remove(current);
current->~Ribble();
cout<<"[graph] ribble removed successfully\n";
}
}
// если нет - бросаем эксепшен
if (!isPresent)
{
throw new RibbleNotFoundException("cannot remove: ribble not found");
}
}
//удалить ребро по его вершинам
void removeRibble(T* vertex1, T* vertex2)
{
cout<<"\n[graph] removing ribble\n";
Ribble<T>* ribble = new Ribble<T>(vertex1, vertex2);
removeRibble(ribble);
}
// удалить вершину
void removeVertex(T* vertex)
{
// проверяем, есть ли такая вершина
Iterator<T>* iter = getIterator();
bool isPresent = false;
while (iter->hasNext())
{
Ribble<T>* current = iter->next();
// запоминаем вершину, ставшую висячей
T* hangVertex = NULL;
if (*current->get__vertex1() == *vertex)
{
hangVertex = current->get__vertex2();
}
else if (*current->get__vertex2() == *vertex)
{
hangVertex = current->get__vertex1();
}
if (hangVertex != NULL)
{
if (!(*current->get__vertex1() == *current->get__vertex2()))
{ // это не та же самая вершина, что удаляем
addVertex(hangVertex);
}
_ribbleList->remove(current);
current->~Ribble();
isPresent = true;
cout<<"\t[graph] ribble containig vertex removed\n";
}
}
if (!isPresent)
{
throw new VertexNotFoundException("cannot remove: vertex not found");
}
else
{
cout<<"[graph] vertex removed successfully\n";
}
};
// получить итератор для обхода графа
GraphIterator<T>* getIterator() const
{
return new GraphIterator<T>(_ribbleList);
}
Graph()
{
_ribbleList = new list< Ribble<T>* >;
cout<<"[graph] graph created\n";
};
~Graph()
{
delete _ribbleList;
}
friend std::ostream& operator<<(std::ostream& o, const Graph<T>& rhs);
};
//////////////////////////////////////////////////////////////////////////
template <class T>
std::ostream& operator<<( std::ostream& o, const Graph<T>& rhs )
{
Iterator<T>* iter = new ExternalGraphIterator<T>(&rhs);
int i = 0;
while (iter->hasNext())
{
o<<"ribble #"<<++i<<endl;
Ribble<T>* current = iter->next();
o<<"===vertex 1===\n"<<*(current->get__vertex1())
<<"===vertex 2===\n"<<*(current->get__vertex2())
<<endl;
}
if (i == 0)
{
o<<"[graph] graph is empty"<<endl;
}
return o;
}
//////////////////////////////////////////////////////////////////////////
#endif /* _INC_GRAPH_46F8FA7D014A_INCLUDED */