#include "graph.h"
#include "set.h" // Определение класса для работы с множествами
class SetGraph : public Graph {
Set **graph; // Массив множеств дуг
int vertexNumber; // Число вершин
public:
// Конструктор графа с n вершинами создает массив из пустых множеств
SetGraph(int n) : vertexNumber(n), graph(new Set*[n])
{ for (int i = 0; i < n; i++) { graph[i] = new Set(0,n); }
}
// Деструктор уничтожает массив множеств
~SetGraph();
// Функция подсчета числа вершин просто выдает
// ранее сохраненное значение
int vertexCount () const { return vertexNumber; }
// Основные методы работы с графом
void addArc(int from, int to);
bool hasArc(int from, int to) const;
};
Все виртуальные функции легко реализуются с помощью соответствующих операций над множествами. Так, принадлежность дуги (и, v) графу может быть легко реализована следующим образом:
bool SetGraph::hasArc(int u, int v) const {
if (u < 0 || u >= vertexNumber || v < 0 || v >= vertexNumber)
return false; // Неправильно задана дуга
return graph[u]->has(v); }
Аналогично, добавление дуги к графу реализуется так:
void SetGraph::addArc(int u, int v) {
if (u < 0 || u >= vertexNumber || v < 0 || v >= vertexNumber)
return; // Неправильно задана дуга
*graph[u] |= v; }
В данной реализации при попытке задать номера вершин, которых заведомо нет в графе, функции просто ничего не делают. Возможно, более правильной моделью поведения было бы возбуждение исключительной ситуации.
В данном представлении также легко и эффективно реализуется метод, позволяющий удалить дугу с заданными номерами инцидентных ей вершин. Несколько сложнее решается задача перебора дуг, инцидентных данной вершине. Например, для того чтобы определить количество дуг, выходящих из вершины с заданным номером, нужно иметь возможность определять количество элементов в множестве. Если считать, что класс set содержит метод card для подсчета числа элементов множества (мощности множества), то число выходящих из заданной вершины u дуг легко получить с помощью выражения graph[u] .card(), однако число входящих в заданную вершину дуг может быть получено только путем перебора всех вершин графа.