Пример 3. Анализ временной сложности:

Исходный граф:

 

Граф после удаления:

Анализ временной сложности:

Воспользовавшись формулой 1, рассчитаем временную сложность программы для данного примера (количество дуг M = 181, , N = 77):

7601 проход по циклам.

Анализ ёмкостной сложности:

В данном примере количество дуг M = 181, количество вершин N = 77. Исходя из этого, вычислим ёмкостную сложность программы для данного примера по формуле 2:

3309 байт памяти.

Результаты работы программы:

 

 

 

 

 

7. Исходный код программы:

#include "stdafx.h"

#include <iostream>

#include <fstream>

#include <string>

#include <Windows.h>

 

using namespace std;

 

struct ArcGraph {

int outVertexId;

int inVertexId;

};

 

struct DirectedGraph {

ArcGraph oneArc;

DirectedGraph *previousArc;

DirectedGraph *nextArc;

};

 

void _input(int &var) {

int BAD_STATE = 2;

 

do {

cin.clear();

cin.sync();

 

cin >> var;

} while(cin.rdstate() == BAD_STATE);

}

 

void _input(char &output, char mode = 'b') {

const char OUTPUT_MODE = 'o', ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's';

bool successfulInput;

 

do {

cin.sync();

 

cin >> output;

if(output == 'e') exit(0);

 

switch(mode) {

case OUTPUT_MODE: successfulInput = (output == 'f' || output == 's'); break;

case ASK_MODE: successfulInput = (output == 'y' || output == 'n'); break;

case MAIN_MODE: successfulInput = (output == 'p' || output == 'm' || output == 'd' || output == 'r'); break;

case SOME_ACTIONS_MODE: successfulInput = (output == 'p' || output == 'm' || output == 's' || output == 'r'); break;

}

} while(!successfulInput);

}

 

void _input(string &var) {

cin.sync();

 

getline(cin, var);

}

 

bool fileExists(string fileName) {

return (ifstream(fileName)!= NULL);

}

 

void main() {

setlocale(LC_ALL, "Russian");

system("cls");

 

static DirectedGraph *firstArc, *sideNode;

 

static ostream *out;

static fstream fileForOutput;

static string fileForOutputName;

 

static short CURRENT_STAGE = 0;

static int vertexWithMaxLevel, maxLevel, NUM_VERTEX = 0;

static bool **adjacencyMatrix, fileOutput;

static char action;

 

const static short START_EXECUTION = 0, INPUT_DATA = 1, THE_MAIN_PART = 2, SOME_ACTIONS_PERFORMED = 3;

const static char ASK_MODE = 'b', MAIN_MODE = 'm', SOME_ACTIONS_MODE = 's',

YES = 'y', NO = 'n',

ON_THE_SCREEN = 's', INTO_A_FILE = 'f',

FOR_INPUT = 'i', FOR_OUTPUT = 'o', FOR_APPEND = 'a',

PRINT_NEIBORHOODS = 'p', MAKE_ADJACENCY_MATRIX = 'm', DELETE_VERTEX = 'd', RESTART_PROGRAM = 'r', SAVE_NEW_GRAPH = 's', EXIT = 'e';

 

DirectedGraph *assembleGraph(int &NUM_VERTEX, ostream *stream);

fstream openFile(string fileName, char mode);

int findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevel, ostream *stream);

bool **completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX);

bool saveGraph(string fileName, DirectedGraph *firstNode, int NUM_VERTEX);

void removeAdjacentVertex(DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel);

void removeNode(DirectedGraph *node, DirectedGraph *&firstNode);

void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "");

void printMatrix(bool **matrix, int dimension, ostream *stream, string title = "");

void clearMatrix(bool **matrix, int dimention);

 

switch(CURRENT_STAGE) {

case START_EXECUTION:

cout << "Режим ввода данных (f - в файл, s - на экран, e - выход): ";

_input(action, FOR_OUTPUT);

switch(action) {

case ON_THE_SCREEN:

out = &cout;

fileOutput = false;

break;

case INTO_A_FILE:

cout << "Имя файла для записи (расширение не требуется): ";

_input(fileForOutputName);

 

if(fileExists("output/"+fileForOutputName+".txt"))

fileForOutput = openFile("output/"+fileForOutputName+".txt", FOR_APPEND);

else

fileForOutput = openFile("output/"+fileForOutputName+".txt", FOR_OUTPUT);

 

out = &fileForOutput;

fileOutput = true;

break;

}

CURRENT_STAGE = INPUT_DATA;

break;

case INPUT_DATA:

firstArc = assembleGraph(NUM_VERTEX, out);

CURRENT_STAGE = THE_MAIN_PART;

break;

case THE_MAIN_PART:

cout << "Список доступных действий:" << endl;

cout << PRINT_NEIBORHOODS << " - вывести список окрестностей" << endl;

cout << MAKE_ADJACENCY_MATRIX << " - составить и вывести матрицу смежности" << endl;

cout << DELETE_VERTEX << " - удалить смежные с вершиной, имеющей наибольшую степень исхода, вершины" << endl;

cout << RESTART_PROGRAM << " - начать выполнение программы сначала" << endl;

cout << EXIT << " - выход" << endl;

_input(action, MAIN_MODE);

switch(action) {

case PRINT_NEIBORHOODS:

printNeiborhoodsList(firstArc, out, NUM_VERTEX, false, "Граф задан следующим списком окрестностей:");

*out << endl << endl;

if(fileOutput)

cout << "Список окрестностей исходного графа записан в файл." << endl;

break;

case MAKE_ADJACENCY_MATRIX:

adjacencyMatrix = completeAdjacencyMatrix(firstArc, NUM_VERTEX);

printMatrix(adjacencyMatrix, NUM_VERTEX, out, "Матрица смежности исходного графа: ");

clearMatrix(adjacencyMatrix, NUM_VERTEX);

*out << endl << endl;

if(fileOutput)

cout << "Матрица смежности исходного графа записана в файл." << endl;

break;

case DELETE_VERTEX:

vertexWithMaxLevel = findVertexAndPrintNewList(firstArc, NUM_VERTEX, maxLevel, out);

*out << endl;

NUM_VERTEX -= maxLevel;

removeAdjacentVertex(firstArc, NUM_VERTEX, vertexWithMaxLevel, maxLevel);

if(fileOutput)

cout << "Вершины, смежные с вершиной, имеющей максимальную степень исхода, удалены," << endl

<< "Степени исхода всех вершин записаны в файл." << endl;

CURRENT_STAGE = SOME_ACTIONS_PERFORMED;

break;

case RESTART_PROGRAM:

while(firstArc!= NULL) {

sideNode = firstArc;

firstArc = firstArc->nextArc;

delete sideNode;

}

 

if(fileOutput) {

fileForOutput.close();

*out << endl << endl;

cout << "Запись в файл успешно завершена!" << endl;

}

CURRENT_STAGE = START_EXECUTION;

break;

}

break;

case SOME_ACTIONS_PERFORMED:

cout << "Список доступных действий:" << endl;

cout << PRINT_NEIBORHOODS << " - вывести список окрестностей" << endl;

cout << MAKE_ADJACENCY_MATRIX << " - соствить и вывести матрицу смежности" << endl;

cout << SAVE_NEW_GRAPH << " - сохранить новый граф" << endl;

cout << RESTART_PROGRAM << " - начать выполнение программы сначала" << endl;

cout << EXIT << " - выход" << endl;

_input(action, SOME_ACTIONS_MODE);

switch(action) {

case PRINT_NEIBORHOODS:

printNeiborhoodsList(firstArc, out, NUM_VERTEX, false, "Список окрестностей графа после удаления вершин, смежных с вершиной, имеющей максимальную степень исхода:");

*out << endl << endl;

if(fileOutput)

cout << "Список окрестностей нового графа записан в файл." << endl;

break;

case MAKE_ADJACENCY_MATRIX:

adjacencyMatrix = completeAdjacencyMatrix(firstArc, NUM_VERTEX);

printMatrix(adjacencyMatrix, NUM_VERTEX, out, "Матрица смежности нового графа: ");

clearMatrix(adjacencyMatrix, NUM_VERTEX);

*out << endl << endl;

if(fileOutput)

cout << "Матрица смежности нового графа записана в файл." << endl;

break;

case SAVE_NEW_GRAPH:

cout << "Введите имя нового графа: ";

_input(fileForOutputName);

if(!saveGraph(fileForOutputName, firstArc, NUM_VERTEX))

cout << "Граф с таким именем " << fileForOutputName << " уже существует!" << endl;

else

cout << "Сохранение графа произведено успешно." << endl;

break;

case RESTART_PROGRAM:

while(firstArc!= NULL) {

sideNode = firstArc;

firstArc = firstArc->nextArc;

delete sideNode;

}

 

if(fileOutput) {

fileForOutput.close();

*out << endl << endl;

cout << "Запись в файл успешно завершена!" << endl;

}

CURRENT_STAGE = START_EXECUTION;

break;

}

}

 

system("pause");

main();

}

 

DirectedGraph *assembleGraph(int &NUM_VERTEX, ostream *stream) {

DirectedGraph *firstNode = NULL, *lastNode = NULL, *currentNode;

 

bool getArcData(string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout);

 

string graphName;

 

cout << "Имя графа: ";

_input(graphName);

 

if(getArcData(graphName, NUM_VERTEX, firstNode, stream)) {

currentNode = firstNode;

 

while(getArcData(graphName, NUM_VERTEX, lastNode)) {

lastNode->previousArc = currentNode;

lastNode->nextArc = NULL;

 

currentNode->nextArc = lastNode;

currentNode = lastNode;

}

}

 

return firstNode;

}

 

bool getArcData(string graphName, int &NUM_VERTEX, DirectedGraph *&lastNode, ostream *stream = &cout) {

static fstream fileForReadGraph;

string filePath = "graphs/";

 

int inVertexId;

static int counter = 0;

char sideChar;

static bool firstIn = true;

 

bool fileExists(string fileName);

fstream openFile(string fileName, char mode);

 

if(firstIn) {

if(!fileExists(filePath+graphName+".txt")) {

cout << "Графа с таким именем не существует!" << endl << "Будет загружен стандартный файл..." << endl;

graphName = "default";

}

fileForReadGraph = openFile(filePath+graphName+".txt", 'i');

 

*stream << "Граф " << graphName << endl;

 

firstIn = false;

counter++;

}

if(fileForReadGraph.eof()) {

firstIn = true;

NUM_VERTEX = counter;

counter = 0;

fileForReadGraph.close();

return false;

}

 

lastNode = (DirectedGraph*) new (DirectedGraph);

lastNode->previousArc = NULL;

lastNode->nextArc = NULL;

if(lastNode == NULL) {

cout << "Память не выделилась!" << endl << "Выполнение программы завершено...";

Sleep(1000);

exit(1);

}

 

fileForReadGraph >> inVertexId;

 

lastNode->oneArc.inVertexId = inVertexId;

lastNode->oneArc.outVertexId = counter;

 

sideChar = fileForReadGraph.get();

 

if(sideChar == '\n')

counter++;

 

return true;

}

 

int findVertexAndPrintNewList(DirectedGraph *firstNode, int NUM_VERTEX, int &maxLevelOfVertex, ostream *stream) {

int counter, inVertexCounter, vertexWithMaxLevel = 0;

 

maxLevelOfVertex = 0;

for(counter = 1; counter <= NUM_VERTEX; counter++) {

inVertexCounter = 0;

while((firstNode!= NULL) && (firstNode->oneArc.outVertexId == counter)) {

inVertexCounter++;

firstNode = firstNode->nextArc;

}

*stream << "Степень исхода вершины " << counter << ": " << inVertexCounter << endl;

 

if(inVertexCounter > maxLevelOfVertex) {

maxLevelOfVertex = inVertexCounter;

vertexWithMaxLevel = counter;

}

}

 

*stream << "Вершина с максимальной степенью исхода: " << vertexWithMaxLevel << endl;

 

return vertexWithMaxLevel;

}

 

int foundInArray(int value, int *arr, int rightBound) {

int counter, middle, leftBound = 0;

 

if((value > arr[rightBound]) || (value < arr[leftBound]))

return -1;

 

counter = 0;

while((rightBound-leftBound) > 1) {

middle = (rightBound+leftBound)/2;

 

if(arr[middle] < value)

leftBound = middle;

else

rightBound = middle;

}

 

for(counter = 0; counter <= rightBound; counter++) {

if(arr[counter] == value)

return counter;

}

 

return -1;

}

 

fstream openFile(string fileName, char mode) {

fstream filePointer;

 

switch(mode) {

case 'i': filePointer.open(fileName, ios_base::in); break;

case 'o': filePointer.open(fileName, ios_base::out); break;

case 'a': filePointer.open(fileName, ios_base::app); break;

}

 

return filePointer;

}

 

void removeNode(DirectedGraph *node, DirectedGraph *&firstNode) {

if((node->previousArc!= NULL) && (node->nextArc!= NULL)) {

node->previousArc->nextArc = node->nextArc;

node->nextArc->previousArc = node->previousArc;

} else if((node->previousArc == NULL) && (node->nextArc!= NULL)) {

node->nextArc->previousArc = NULL;

firstNode = node->nextArc;

} else if((node->previousArc!= NULL) && (node->nextArc == NULL)) {

node->previousArc->nextArc = NULL;

} else if((node->previousArc == NULL) && (node->nextArc == NULL)) {

firstNode = NULL;

}

 

delete node;

}

 

bool saveGraph(string fileName, DirectedGraph *firstNode, int NUM_VERTEX) {

bool fileExists(string fileName);

void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "");

fstream openFile(string fileName, char mode);

 

if(fileExists("graphs/"+fileName+".txt")) return false;

 

fstream file;

file = openFile("graphs/"+fileName+".txt", 'o');

printNeiborhoodsList(firstNode, &file, NUM_VERTEX, true);

return true;

}

 

void removeAdjacentVertex(DirectedGraph *&firstArc, int NUM_VERTEX, int vertexId, int vertexLevel) {

DirectedGraph *currentNode, *nodePointer, *sidePointer;

int counter, currentId, *adjacentVertex, *newVertexId, NOT_FOUND = -1;

bool noOneBefore;

 

void removeNode(DirectedGraph *node, DirectedGraph *&firstNode);

int foundInArray(int value, int *arr, int rightBound);

 

currentNode = firstArc;

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId!= vertexId))

currentNode = currentNode->nextArc;

 

counter = 1;

adjacentVertex = new int [vertexLevel];

adjacentVertex[0] = currentNode->oneArc.inVertexId;

currentNode->oneArc.inVertexId = 0;

currentNode = currentNode->nextArc;

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == vertexId)) {

adjacentVertex[counter] = currentNode->oneArc.inVertexId;

nodePointer = currentNode;

currentNode = currentNode->nextArc;

removeNode(nodePointer, firstArc);

counter++;

}

 

currentNode = firstArc;

while(currentNode!= NULL) {

currentId = currentNode->oneArc.outVertexId;

if(foundInArray(currentId, adjacentVertex, vertexLevel-1)!= NOT_FOUND) {

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentId)) {

nodePointer = currentNode;

currentNode = currentNode->nextArc;

removeNode(nodePointer, firstArc);

}

continue;

}

 

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentId))

currentNode = currentNode->nextArc;

}

 

currentNode = firstArc;

newVertexId = new int [NUM_VERTEX];

counter = 0;

while(currentNode!= NULL) {

newVertexId[counter] = currentNode->oneArc.outVertexId;

 

if(currentNode->oneArc.inVertexId!= 0) {

noOneBefore = true;

sidePointer = NULL;

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == newVertexId[counter])) {

currentNode->oneArc.outVertexId = counter+1;

if(sidePointer!= NULL) {

removeNode(sidePointer, firstArc);

sidePointer = NULL;

}

 

if(foundInArray(currentNode->oneArc.inVertexId, adjacentVertex, vertexLevel-1)!= NOT_FOUND) {

if(noOneBefore) {

currentNode->oneArc.inVertexId = 0;

sidePointer = currentNode;

currentNode = currentNode->nextArc;

} else {

nodePointer = currentNode;

currentNode = currentNode->nextArc;

removeNode(nodePointer, firstArc);

}

 

continue;

}

 

if(noOneBefore)

noOneBefore = false;

currentNode = currentNode->nextArc;

}

} else {

currentNode->oneArc.outVertexId = counter+1;

currentNode = currentNode->nextArc;

}

 

counter++;

}

 

currentNode = firstArc;

while(currentNode!= NULL) {

if(currentNode->oneArc.inVertexId == 0) {

currentNode = currentNode->nextArc;

continue;

}

 

currentId = currentNode->oneArc.outVertexId;

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentId)) {

currentNode->oneArc.inVertexId = foundInArray(currentNode->oneArc.inVertexId, newVertexId, NUM_VERTEX-1)+1;

currentNode = currentNode->nextArc;

}

}

}

 

void printNeiborhoodsList(DirectedGraph *firstNode, ostream *stream, int NUM_VERTEX, bool saveMode, string title = "") {

DirectedGraph *currentNode = firstNode;

int currentVertex;

 

if(!title.empty())

*stream << title;

 

if(saveMode) {

while(currentNode!= NULL) {

currentVertex = currentNode->oneArc.outVertexId;

*stream << endl << currentNode->oneArc.inVertexId;

currentNode = currentNode->nextArc;

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentVertex)) {

*stream << ' ' << currentNode->oneArc.inVertexId;

currentNode = currentNode->nextArc;

}

}

 

} else {

while(currentNode!= NULL) {

*stream << endl << (currentVertex = currentNode->oneArc.outVertexId) << ": ";

 

*stream << currentNode->oneArc.inVertexId;

currentNode = currentNode->nextArc;

while((currentNode!= NULL) && (currentNode->oneArc.outVertexId == currentVertex)) {

*stream << ' ' << currentNode->oneArc.inVertexId;

currentNode = currentNode->nextArc;

}

}

}

}

 

bool **completeAdjacencyMatrix(DirectedGraph *firstNode, int NUM_VERTEX) {

DirectedGraph *currentNode = firstNode;

int currentId, rowCounter, colCounter;

bool **adjacencyMatrix = new bool* [NUM_VERTEX];

 

for(rowCounter = 0; rowCounter < NUM_VERTEX; rowCounter++) {

adjacencyMatrix[rowCounter] = new bool [NUM_VERTEX];

for(colCounter = 0; colCounter < NUM_VERTEX; colCounter++)

adjacencyMatrix[rowCounter][colCounter] = false;

}

currentNode = firstNode;

 

while(currentNode!= NULL) {

if(currentNode->oneArc.inVertexId!= 0)

adjacencyMatrix[currentNode->oneArc.outVertexId-1][currentNode->oneArc.inVertexId-1] = true;

 

currentNode = currentNode->nextArc;

}

 

return adjacencyMatrix;

}

 

void printMatrix(bool **matrix, int dimension, ostream *stream, string title = "") {

int rowCounter, colCounter;

 

if(!title.empty())

*stream << title;

 

for(rowCounter = 0; rowCounter < dimension; rowCounter++) {

*stream << endl << ' ' << matrix[rowCounter][0];

for(colCounter = 1; colCounter < dimension; colCounter++) {

*stream << ' ' << matrix[rowCounter][colCounter];

}

}

}

 

void clearMatrix(bool **matrix, int dimention) {

for(int counter = 0; counter < dimention; counter++)

delete [] matrix[counter];

 

delete [] matrix;

}