Файл convert.срр

#include "SetGraph.h"

#include "MatrixGraph.h"

#include "ListGraph.h"

#include "ArcGraph.h"

 

// Функция преобразования представления из M-графа в S-граф

SetGraph * convert(const MatrixGraph & srcGraph) {

int n = srcGraph.vertexCoun();

SetGraph *destGraph = new SetGraph(n);

for (int i = 0; i < n; i++) {

// Представление строки исходного графа:

bool * srcRow = srcGraph.graph[i];

// Соответствующее множество результирующего графа:

Set & destRow = *destGraph->graph[i];

for (int j = 0; j < n; j++) {

// Новая дуга записывается с помощью операции

// добавления элемента к множеству

if (srcRow[j]) destRow |= j; } } return destGraph;

}

// Функция преобразования представления из S-графа в L-граф

ListGraph * convert(const SetGraph & srcGraph) {

int n = srcGraph.vertexCount();

ListGraph *destGraph = new ListGraph(n);

for (int i = 0; i < n; i++) {

// Представление строки исходного графа:

Set & srcRow = *srcGraph.graph[i];

// Соответствующий список дуг в результирующем графе:

List<int> & destRow = destGraph->graph[i];

for (int j = 0; j < n; j++) {

// Обе операции - проверка принадлежности множеству и добавления

// элемента в список выполняются за фиксированное время.

if (srcRow.has(j)) destRow.add(i);

}}

return destGraph;

}

 

// Функция преобразования представления из L-графа в А-граф.

// В этой функции используются только открытые операции А-графа,

// поэтому она может и не "дружить" с описанием класса ArcGraph

ArcGraph * convert(const ListGraph & srcGraph) {

 

int n = srcGraph.vertexCount0;

ArcGraph *destGraph = new ArcGraph(n);

for (int i = 0; i < n; i++) {

List<int>::ListItem *current = srcGraph.graph[i].first;

while (current) {

// Добавление дуги в список дуг с помощью операции addArc.

destGraph->addArc(i, current->item);

current = current->next; } } return destGraph;

}

 

// Функция преобразования представления из А-графа в M-граф.

MatrixGraph * convert(const ArcGraph & srcGraph) {

int n = srcGraph.vertexCount();

MatrixGraph *destGraph = new MatrixGraph(n);

// в цикле перебираются все дуги

for (ArcGraph::Arc * current = srcGraph.first; current; current = current->next) {

destGraph->graph[current->begin][current->end] = true;

}

return destGraph;

}