-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathGraph.cpp
143 lines (105 loc) · 3.24 KB
/
Graph.cpp
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
#include "Graph.h"
// Constructor
Graph::Graph(ifstream& ifs)
{
// read in the matrix from file
vector<int> matrix;
int matrix_element;
while (ifs >> matrix_element)
matrix.push_back(matrix_element);
// calculate the number of vertices
int v = static_cast<int>(sqrt(matrix.size()));
for (int i = 0; i < v; i++)
{
// create vertex object
Vertex vertex(this, i);
// add vertex to collection of the graph's vertices
vertices.push_back(vertex);
// build a connection between vertex and its neighbors
for (int j = 0; j < v; j++)
vertices[i].addEdge(j, matrix[i*v + j]);
}
}
// Label all vertices as unvisited
void Graph::resetVertices()
{
for (int i = 0; i < V(); i++)
vertices[i].reset();
}
// Print summary for the given graph
ostream& operator <<(ostream& os, Graph& g)
{
os << " Number of vertices \tV = " << g.V() << endl;
os << " Connected: \t\t" << (g.isConnected() ? "YES" : "NO") << endl;
os << " Euler Circuit: \t" << (g.isEulerianCircuit() ? "YES" : "NO") << endl;
os << " Euler Path: \t\t" << (g.isEulerianPath() ? "YES" : "NO") << endl;
if (g.isEulerian())
g.printEulerTrail(os);
return os;
}
// Determine the starting point for Euler trail (path or circuit)
// Print either the Euler Path or Circuit as a sequence of edges (e.g. a-b b-c c-a)
void Graph::printEulerTrail(ostream& os)
{
int startIndex = 0;
// start an Euler path from the first odd vertex
// otherwise, start an Euler circuit from the first even vertex
for (int i = 0; i < V(); i++)
{
if (vertices[i].isOddDegree())
{
startIndex = i;
break;
}
}
os << endl;
// print header
if(isEulerianPath())
os << " Euler Path:" << endl << endl;
if (isEulerianCircuit())
os << " Euler Circuit:" << endl << endl;
// print trail
vertexAt(startIndex).printEulerTrailEdge(os);
os << endl;
}
// Returns the number of odd vertices from the graph
// Iterates through the all vertices collection and count odd vertices
int Graph::oddVerticesCount() const
{
int odd = 0;
for (int i = 0; i < V(); i++)
if (vertices[i].isOddDegree())
odd++;
return odd;
}
// Determines whether the graph has Euler path (exactly two odd vertices)
bool Graph::isEulerianPath()
{
return isConnected() && oddVerticesCount() == 2;
}
// Determines whether the graph has Euler circuit (all vertices are even)
bool Graph::isEulerianCircuit()
{
return isConnected() && oddVerticesCount() == 0;
}
// Determines whether the graph is Euler or semi-Euler (has Euler circuit or path)
bool Graph::isEulerian()
{
return isEulerianCircuit() || isEulerianPath();
}
// Determines whether the graph contains all vertices with non-zero degree connected
bool Graph::isConnected()
{
resetVertices();
int i;
for (i = 0; i < V(); i++)
if (vertices[i].degree() > 0)
break;
if (i == V())
return false;
vertices[i].traverse();
for (i = 0; i < V(); i++)
if (!vertices[i].isVisited() && vertices[i].degree() > 0)
return false;
return true;
}