#include "stdafx.h"
using namespace std;
#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include "Graph.h"
#include "Task.h"
void main(int argc, char **argv){
setlocale(0, "rus");
int action, vertexCount = 10, edgesCount = 20, from = 0, to = 0;
float weight = 0.0;
char data;
Graph<float, char> *graph = new Graph<float, char>;
Task<float, char> *task = new Task<float, char>;
while (true) {
printf("1. Создатьорграф\n");
printf("2. Вставить ребро\n");
printf("3. Добавить точку\n");
printf("4. Удалить ребро\n");
printf("5. Проверить ребро на существование\n");
printf("6. Установить параметры ребра\n");
printf("7. Вывести орграф\n");
printf("8. Установить данные для точки\n");
printf("9. Алгоритм определения вершин, удаленных от заданной вершины в пределах заданного по весу расстояния\n");
printf("0. Выход\n\n");
printf("Выберите операцию: ");
cin>> action;
switch (action) {
case 0: {
return;
}
case 1: {
system("CLS");
if (graph) delete graph;
Graph<float, char> *graph = new Graph<float, char>;
for (int i = 0; i<vertexCount; i++) {
graph->addVertex('a' + i);
}
for (int i = 0; i<edgesCount; i++) {
unsigned int from = rand() % vertexCount, to = rand() % edgesCount;
float w = (rand() % 99 + 1) / 100.0;
graph->insertEdge(from, to, w);
}
cout<< "Орграфсоздан.\n";
break;
}
case 2: {
system("CLS");
cout<< "Введите начальный индекс вершины (число): ";
cin>>from;
cout<< "Введите конечный индекс вершины (число): ";
cin>>to;
cout<< "Вес ребра (с плавающей запятой): ";
cin>> weight;
if(graph->insertEdge(from, to, weight)){
cout<< "Вставлено ребро от " <<from<< " к " <<to<< " с весом " <<weight<< "\n";
} else {
cout<< "Невозможно вставить ребро. Начальный или конечный индекс не существуют, либо такое ребро было создано ранее.\n";
}
break;
}
case 3: {
system("CLS");
if(graph){
cout<< "Введите данные для новой вершины: ";
cin>> data;
graph->addVertex(data);
cout<< "Новая вершина с данными " <<data<< " создана.\n";
} else {
cout<< "Орграф пуст.\n";
}
break;
}
case 4: {
system("CLS");
if(graph){
cout<< "Введите начальный индекс вершины (число): ";
cin>>from;
cout<< "Введите конечный индекс вершины (число): ";
cin>> to;
if(graph->delEdge(from, to)){
cout<< "Удалено ребро от " <<from<< " к " <<to<< "\n";
} else {
cout<< "Невозможно удалить ребро, т.к. оно не существует.\n";
}
} else {
cout<< "Орграф пуст.\n";
}
break;
}
case 5: {
system("CLS");
if(graph){
cout<< "Введите начальный индекс вершины (число): ";
cin>>from;
cout<< "Введите конечный индекс вершины (число): ";
cin>> to;
if (graph->hasEdge(from, to)) {
cout<< "Ребро существует.\n";
} else {
cout<< "Ребро не существует.\n";
}
} else {
cout<< "Орграф пуст.\n";
}
break;
}
case 6: {
system("CLS");
if(graph){
cout<< "Введите начальный индекс вершины (число): ";
cin>>from;
cout<< "Введите конечный индекс вершины (число): ";
cin>>to;
cout<< "Вес ребра (с плавающей запятой): ";
cin>> weight;
if(graph->setEdge(from, to, weight)){
cout<< "Ребро от " <<from<< " к " <<to<< " получило новый вес " <<weight<< "\n";
} else {
cout<< "Ребро не существует.\n";
}
} else {
cout<< "Орграф пуст.\n";
}
break;
}
case 7: {
system("CLS");
if(graph){
graph->print();
cout<< "\n";
} else {
cout<< "Орграфпуст.\n";
}
break;
}
case 8: {
system("CLS");
if(graph){
cout<< "Введите индекс вершины (число): ";
cin>>from;
cout<< "Введите новые данные: ";
cin>> data;
if(graph->setVertexData(from, data)){
cout<< "Данные вершины изменены.\n";
} else {
cout<< "Такого индекса не существует.\n";
}
} else {
cout<< "Орграф пуст.\n";
}
break;
}
case 9: {
system("CLS");
if(graph){
task->graph = graph;
cout<< "Алгоритм определения вершин, удаленных от заданной вершины в пределах заданного по весу расстояния.\n";
cout<< "Введите индекс вершины: ";
cin>>task->graph->from;
cout<< "Введитевес: ";
cin>> task->graph->weight;
task->visited.assign(task->graph->vertexCount(), false);
task->showPath(task->graph->from, task->graph->weight);
cout<<endl;
} else {
cout<< "Орграфпуст.\n";
}
break;
}
}
}
}
Алгоритмопределения вершин, удаленных от заданной вершины в пределах заданного по весу расстояния
Task.h
#ifndef TASK_H
#define TASK_H
template <typename Weight, typenameVert>
class Task {
public:
void showPath(unsigned int from, Weight weight);
Graph<Weight, Vert> *graph;
vector<bool> visited;
};
template <typename Weight, typenameVert>
void Task<Weight, Vert>::showPath(unsigned int from, Weight weight){
float localWeight = weight;
if(this->graph->vertices[from] && visited[from]!= true){
visited[from] = true;
Vertex<Weight, Vert> *vertex = this->graph->vertices[from];
if(vertex->edges){
for (Edge<Weight> *it = vertex->edges; it; it = it->next) {
if(it->weight <= weight && visited[it->to]!= true){
cout<< it->to << " ";
this->showPath(it->to, localWeight - it->weight);
}
}
}
} else {
cout<< "Такой вершины не существует.\n";
}
};
#endif