rtsGraph.h
2.67 KB
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
#ifndef RTS_GRAPH_H
#define RTS_GRAPH_H
#include <list>
#include <algorithm>
using namespace std;
template<typename T>
class rtsGraph
{
unsigned int current_id;
public:
class rtsGraphNode;
typedef typename list<rtsGraphNode>::iterator rtsGraphNodePtr;
class rtsGraphNode
{
public:
list<rtsGraphNodePtr> ConnectionList;
unsigned int ID;
T Data;
};
list<rtsGraphNode> NodeList;
rtsGraphNodePtr addNode(T data)
{
//Adds a node to the graph. This node is unconnected by default.
//create the new node
rtsGraphNode new_node;
//set the data to the data provided
new_node.Data = data;
//set the id
new_node.ID = current_id++;
//add the node to the node list
NodeList.push_back(new_node);
rtsGraphNodePtr result = NodeList.end();
result--;
return result;
}
bool cmpPtr(const rtsGraphNodePtr a, const rtsGraphNodePtr b)
{
return (*a).ID < (*b).ID;
}
void addConnection(rtsGraphNodePtr n0, rtsGraphNodePtr n1)
{
//adds a connection between two nodes
//connect n0 to n1
(*n0).ConnectionList.push_back(n1);
(*n1).ConnectionList.push_back(n0);
}
void removeNode(rtsGraphNodePtr n)
{
typename list<rtsGraphNodePtr>::iterator i;
typename list<rtsGraphNodePtr>::iterator j;
typename list<rtsGraphNodePtr>::iterator temp;
rtsGraphNodePtr m;
rtsGraphNodePtr k;
/*Remove all of the connections TO n*/
//for each node m connected to n
for(i = (*n).ConnectionList.begin(); i != (*n).ConnectionList.end(); i++)
{
m = (*i);
//for each node k connected to m
j = (*m).ConnectionList.begin();
while(j != (*m).ConnectionList.end())
{
k = (*j);
//if k is the same as n, remove it
if(k == n)
{
temp = j;
j++;
(*m).ConnectionList.erase(temp);
}
else
j++;
}
}
/*Add all connections to neighboring nodes*/
//for each node m connected to n
for(i = (*n).ConnectionList.begin(); i != (*n).ConnectionList.end(); i++)
{
m = (*i);
//for each node k connected to n
for(j = (*n).ConnectionList.begin(); j != (*n).ConnectionList.end(); j++)
{
k = (*j);
if(k != m)
(*m).ConnectionList.push_back(k);
}
//(*m).ConnectionList.sort(&rtsGraph<T>::cmpPtr);
//sort((*m).ConnectionList.begin(), (*m).ConnectionList.end(), rtsGraph<T>::cmpPtr);
(*m).ConnectionList.unique();
}
}
void PrintGraph()
{
rtsGraphNodePtr i;
typename list<rtsGraphNodePtr>::iterator c;
for(i = NodeList.begin(); i != NodeList.end(); i++)
{
cout<<(*i).Data<<": ";
for(c = (*i).ConnectionList.begin(); c != (*i).ConnectionList.end(); c++)
{
if(c != (*i).ConnectionList.begin())
cout<<"--";
cout<<(*(*c)).Data;
}
cout<<endl;
}
}
};
#endif