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
|
#include <iostream>
#include <unordered_set>//c++11
#include <vector>
using namespace std;
typedef int Vertex;
typedef pair<unordered_set<Vertex>::const_iterator,//stores the locations of the vertices within the set
unordered_set<Vertex>::const_iterator> Edge;//so I didn't have to make copies of the vertex
class Graph{
private:
unordered_set<Vertex>vertices;//bucket of vertices
vector<Edge>edges;
public:
void addVertex(Vertex);
void addEdge(Vertex,Vertex);
void DisplayVertices();
void DisplayEdges();
Vertex firstNeighbor(Vertex);
Vertex nextNeighbor(Vertex,Vertex);
void allNeighbors(Vertex);
void deleteEdge(Vertex,Vertex);
bool isEdge(Vertex,Vertex);
};
void Graph::addVertex(Vertex vertex){
vertices.emplace(vertex);//adds to set if value is unique
}
void Graph::addEdge(Vertex a,Vertex b){
if(a!=b){//don't think we can have a vertex with edge to itself?
unordered_set<Vertex>::const_iterator first=vertices.find(a);
unordered_set<Vertex>::const_iterator second=vertices.find(b);
edges.emplace_back(first,second);//put it at the back
}
}
void Graph::DisplayVertices(){
for(const Vertex& x: vertices){cout<<x<<" ";}
}
void Graph::DisplayEdges(){
cout<<endl<< "Edges:"<<endl;
for (auto& x: edges){
cout<<"("<<*x.first <<","<<*x.second<<")";
cout<<endl;
}
}
Vertex Graph::firstNeighbor(Vertex v){
for(unsigned i=0;i<edges.size();++i){
if(v==*edges[i].first)//if we find the first value
return *edges[i].second;//return the second value
if(v==*edges[i].second)//and vice versa
return *edges[i].first;
}
return edges.size();
}
Vertex Graph::nextNeighbor(Vertex a, Vertex b){//a to b (finds c)
for(unsigned i=0;i<edges.size();++i){
if((a==*edges[i].first)&&(b==*edges[i].second)){//if we find an exact match
for(unsigned j=i+1;j<edges.size();++j){//search the rest for a single matching vertex
if((a==*edges[j].first)||(b==*edges[j].first)){return *edges[j].second;}
if((a==*edges[j].second)||(b==*edges[j].second)){return *edges[j].first;}
}
}
}
return edges.size();
}
void Graph::allNeighbors(Vertex v){
for(unsigned i=0;i<edges.size();++i){
if(v==*edges[i].first){cout<<*edges[i].second<<" ";}
if(v==*edges[i].second){cout<<*edges[i].first<<" ";}
}
cout<<endl;
}
void Graph::deleteEdge(Vertex a,Vertex b){//order matters in pair
for(unsigned i=0;i<edges.size();++i){
if((a==*edges[i].first)&&(b==*edges[i].second)){
edges.erase(edges.begin()+i);
}
}
}
bool Graph::isEdge(Vertex a, Vertex b){//order doesn't matter
for(unsigned i=0;i<edges.size();++i){
if( ((a==*edges[i].first)&&(b==*edges[i].second))||((a==*edges[i].second)&&(b==*edges[i].first)) ){
return true;
}
}
return false;
}
int main()
{
Graph G;
G.addVertex(0);
G.addVertex(1);
G.addVertex(2);
G.addVertex(5);
G.addVertex(3);
G.addEdge(5,0);//first neighbor of 0 should be 5
G.addEdge(0,2);
G.addEdge(3,5);
G.addEdge(0,1);//first neighbor of 1 should be zero
G.addEdge(5,2);
G.addEdge(2,1);
G.DisplayVertices();
G.DisplayEdges();
cout<<"Is (5,3) an edge?: "<<G.isEdge(3,5)<<endl;
cout<<"Is (2,3) an edge?: "<<G.isEdge(3,2)<<endl;
cout<<"First neighbor of 0: "<<G.firstNeighbor(0)<<endl;
cout<<"First neighbor of 1: "<<G.firstNeighbor(1)<<endl;
cout<<"Next neighbor of (5,0): "<<G.nextNeighbor(5,0)<<endl;
cout<<"All neighbors of 5: ";
G.allNeighbors(5);//should be 0,3,2
G.deleteEdge(5,0);
cout<<"Is (0,5) an edge?: "<<G.isEdge(5,0)<<endl;
cout<<"All neighbors of 5 after (5,0) was erased: ";
G.allNeighbors(5);
return 0;
}
|
