1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
| //Prufer.cpp
#include <vector>
#include <algorithm>//Использование стандартных алгоритмов
#include <iostream>
#include <functional>//Использование функторов
#include <stdexcept>//Использование стандартных классов исключений
#include "Prufer.h"
AbstractMatr::AbstractMatr(size_t n, size_t m)
{
Matrix.resize(n);//Установка размера исходной матрицы
for(int i=0; i!=GetRow(); ++i)
{
Matrix[i].resize(m);//Установка размера строки исходной матрицы
}
}
void AbstractMatr::SetSize(size_t n, size_t m)
{
if(GetRow()!=0&&GetCol()!=0)//Если столбцы/строки не равны нулю
Matrix.clear();//Чистим вектор
Matrix.resize(n);
for(int i=0; i!=GetRow(); ++i)
{
Matrix[i].resize(m);
}
}
void AbstractMatr::swap(AbstractMatr& Ob)
{
Matrix.swap(Ob.Matrix);//Меняем местами значения вектора
}
void Prufer::Code()
{
for(int i=0; i!=GetRow(); ++i)
Nodes.push_back(i+1);//Записываем в вершины элемент i+1
for(int i=0; i!=GetRow(); ++i)
Degrees.push_back(Degree(Nodes[i]-1));//Записываем в степени степень i элемента вектора Nodes - 1
for(int t=0; t!=GetRow()-2; ++t)//От 0 до N-2
{
//Проверка на то, что наличие листьев
if(std::count_if(Degrees.begin(), Degrees.end(), std::bind2nd(std::equal_to<int>(), 1))==0)
{
std::cout<<"On "<< t+1 <<" step\n";//Пишем на каком шаге
//Кидаем исключение, которое будет обработано в main(). Используем стандартный класс
//std::invalid_argument
throw std::invalid_argument("Can`t code this graph (tree). There are no nodes with degree 1\n");
}
for(int i=0; i!=Nodes.size(); ++i)//От 0 до размера вектора вершин
{
if(Degrees[i]==1)//Если i-ая вершина - лист
{
if(IsMin(Nodes[i]))//Если i-ая вершина минимальна
{
int Adj=Adjacent(Nodes[i]-1);//Возвращаем смежную с i-1 вершиной вершину
Pruf.push_back(Adj+1);//Добавляем в вектор кода Прюфера, смежную вершину+1
DeleteEdge(Nodes[i]-1, Adj);//Удаляем ребро Nodes[i]-1, Adj
//Удаляем из вектора вершин i-тую вершину
Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
Degrees.clear();//Очищаем вектор степеней
for(int i=0; i!=Nodes.size(); ++i)
{
Degrees.push_back(Degree(Nodes[i]-1));//Заполняем вектор степеней
}
break;//Брякаем цикл
}
}
}
}
Edges.push_back(std::make_pair<int, int>(Nodes[0], Nodes[1]));//Записываем ребро Nodes[0]->Nodes[1] в вектор ребер
std::cout<<"Prufer`s code\n";//Вывод в консоль строки
std::copy(Pruf.begin(), Pruf.end(), std::ostream_iterator<int>(std::cout, " "));//Вывод в консоль вектора
std::cout<<std::endl;//Перевод каретки+очистка буфера
}
void Prufer::Decode()
{
std::pair<int, int> Temp;//Создаем временный элемент типа пары двух интовых значений
Temp=Edges.front();//Записываем первый элемент из вектора ребер во временный элемент
Edges.clear();//Чистим вектор ребер
Nodes.clear();//Чистим вектор вершин
for(int i=0; i!=Matrix.size(); ++i)
Nodes.push_back(i+1);//Записываем i+1 вершину (дабы начиналось с 1)
for(int t=0; t!=GetRow()-2; ++t)//До N-2
{
for(int i=0; i!=Nodes.size(); ++i)
{
if(!IsInPruf(Nodes[i]))//Если не i-тая вершина не выходит в код прюфера
{
if(IsMinNode(Nodes[i], i))//И если она минимальная среди вершин
{
//Делаем пару интовых значений. Первый элемент вектора Прюфера и i-тую вершину.
//Записываем ее в вектор ребер
Edges.push_back(std::make_pair<int, int>(Pruf[0], Nodes[i]));
//Удаляем i-тую вершину
Nodes.erase(std::remove(Nodes.begin(), Nodes.end(), Nodes[i]), Nodes.end());
Pruf.erase(std::find(Pruf.begin(), Pruf.end(), Pruf[0]));//Удаляем первый элемент из в. Прюфера
break;//Брякаем
}
}
}
}
Edges.push_back(Temp);//Записываем в конец вектора значение, записанное во временной переменной
std::cout<<"Decode from Prufers`s code\nDefault tree\n";//Вывод строки
//Цикл по итератору. От начала вектора ребер, до конца.
for(std::vector<std::pair<int, int> >::const_iterator Iter=Edges.begin(); Iter!=Edges.end(); ++Iter)
{
std::cout<<"<"<<Iter->first<<','<<Iter->second<<'>'<<'\n';//Выводим в консоль <вершина из прюфера, вершина из nodes>
}
}
int Prufer::Degree(int row)
{
int cnt=0;//Счетчик
for(int j=0; j!=GetCol(); ++j)//До кол-ва столбцов
{
if(Matrix[row][j]==1)//Если j-ый элемент строки row равен 1
cnt++;//Плюсуем счетчик
}
return cnt;
}
int Prufer::Adjacent(int row)
{
int i;
for(i=0; i!=GetCol(); ++i)
if(Matrix[row][i]==1)//Если i-ый элемент строки row равен 1
break;//Брякаем
return i;//Вернули i
}
bool Prufer::IsMin(int elem)
{
int min=elem;//min=elem
for(int i=0; i!=Degrees.size(); ++i)
{
if(Degrees[i]==1)//Если i-ая степень=1
{
if(Nodes[i]<min)//Если i-ая вершина меньше минимума
min=Nodes[i];//Минимум становится равен i-ой вершине
}
}
return (min==elem);//Если min==elem возвращаем true, иначе false
}
void Prufer::DeleteEdge(int row, int col)
{
Matrix[row][col]=0;//col-тый элемент в row-той строке равен 0
Matrix[col][row]=0;//наоборот
}
std::ostream& operator <<(std::ostream& os, const Prufer& Ob)
{
for(int i=0; i!=Ob.GetRow(); ++i)
{
//Вывод на экран. Стандартный алгоритм copy
std::copy(Ob.Matrix[i].begin(), Ob.Matrix[i].end(), std::ostream_iterator<int>(os, " "));
os<<'\n';
}
return os;
}
std::istream& operator >>(std::istream& is, Prufer& Ob)
{
for(int i=0; i!=Ob.GetRow(); ++i)
{
for(int j=0; j!=Ob.GetCol(); ++j)
{
if(i>=j)//Если i>=j переходим к след итерации
continue;
std::cout<<"Enter 1 for connect "<< i+1 <<" and "<< j+1 <<" nodes, and 0 for not\n";
is>>Ob.Matrix[i][j];
if(i!=j)//Если i!=j
Ob.Matrix[j][i]=Ob.Matrix[i][j];//
}
}
return is;
}
bool Prufer::IsInPruf(int elem)
{
for(int i=0; i!=Pruf.size(); ++i)
{
if(elem==Pruf[i])//Если элемент = Pruf[i]
{
return true;//Вернули true. То есть элемент присутствует в Прюфере
}
}
return false;//Вернули false. Элемента нет. Все гуд
}
bool Prufer::IsMinNode(int elem, int row)
{
int min=elem;//Минимум = элемент
for(int i=row; i!=Nodes.size(); ++i)//От номера элемента в массиве до конца
{
if(Nodes[i]<min)
min=Nodes[i];
}
return (min==elem);
} |