forked from freekdotcom/Snacs
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Landmarks.cpp
164 lines (142 loc) · 4.77 KB
/
Landmarks.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
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include "Landmarks.h"
/// Created By
/// E. Janssen & F. v.d. Meulen
///--------------------------------------
/// Project : Landmark System
/// Course : Social Network Analysis
/// Date : 10/12/2018
/// Classe : Landmarks
///---------------------------------------
// Function : Constructor
// Description :
// @Param : const Graph * G
// @Param : std::list<Node*>* nodes
// @Param : int _landmarks
// @Pre :
// @Post :
Landmarks::Landmarks(const Graph* G, std::vector<Node*>* nodes, Delegate _strategy, int _landmarks)
{
strategy = _strategy;
if(G == NULL)
throw "No valid input - Landmarks::Landmarks";
nmbrLandmarks = _landmarks;
landmarks = NULL;
graph = NULL;
std::cout << "Converting Graph to Landmark System" << std::endl
<< "Status: Starting" << std::endl;
if (ConvertGraph(G, nodes) == false)
throw "Converting Graph Error - Landmarks::Landmarks";
else
std::cout << "Status: Completed" << std::endl << std::endl;
}
// Function : Destructor
// Description :
// @Pre :
// @Post :
Landmarks::~Landmarks()
{
delete landmarks;
graph = NULL;
}
// Function : Distance Landmarks
// Description :
// @Param : const Node* s
// @Param : const Node* t
// @Pre :
// @Post : Tuple with the Lowerbound, Upperbound, the middle point and the geometric mean
boost::tuple<int,int,int,int> Landmarks::DistanceLandmarks(Node* s, Node* t)
{
int LowerBound = 0;
int UpperBound = INT_MAX;
for(int i = 0; i < nmbrLandmarks;i++)
{
std::map<Node*,int>* landmark = graph->at(i);
int si = landmark->find(s)->second;
int ti = landmark->find(t)->second;
if(si != INT_MAX || ti != INT_MAX)
{
//Calculate lower bound from this landmark.
int L = abs(ti - si);
if (L > LowerBound)
LowerBound = L;
//Calculate upper bound from this landmark.
int U = si + ti;
if (U != 0 && U < UpperBound)
UpperBound = U;
}
}
//Calculate middle point and geometric mean.
int mPoint = floor((UpperBound + LowerBound) / 2);
int gMean = floor(sqrt(UpperBound * LowerBound));
return boost::make_tuple(UpperBound, LowerBound, mPoint, gMean);
}
// Function : Convert Graph
// Description :
// @Param : const Graph * G
// @Param : std::list<Node*>* nodes
// @Pre :
// @Post :
bool Landmarks::ConvertGraph(const Graph* G, std::vector<Node*>* nodes)
{
if (nodes == NULL || nodes->size() == 0)
throw "Invallid node structure - Landmark::ConvertGraph";
std::cout << "Finding Landmarks" << std::endl;
landmarks = PickLandmarks(G,nodes);
if (landmarks == NULL || landmarks->size() == 0)
return false;
std::cout << "Found Landmarks" << std::endl;
//Create Graph Representation
std::vector<std::map<Node*,int>*>* newGraph = new std::vector<std::map<Node*,int>*>();
for (std::vector<Node *>::iterator source = landmarks->begin(); source != landmarks->end(); ++source)
{
newGraph->push_back(DijkstraDistance(G,*source,nodes));
}
graph = newGraph;
return true;
}
// Function : Pick Landmarks
// Description :
// @Param : const Graph * G
// @Param : std::vector<Node*>* nodes
// @Pre :
// @Post :
std::vector<Node*>* Landmarks::PickLandmarks(const Graph* G, std::vector<Node*>* nodes)
{
std::vector<Node*>* newLandmarks = new std::vector<Node*>();
std::vector<int>* nmbrs = strategy(G,nmbrLandmarks,nodes);
//Node Selection By Index
int loopsize = nmbrs->size();
for (int i = 0; i < loopsize; i++)
{
newLandmarks->push_back(nodes->at(nmbrs->at(i)));
}
int currentLandmarks = newLandmarks->size();
if(currentLandmarks != nmbrLandmarks)
throw "Not enough Landmarks selected - Landmark::PickLandmarks";
else
return newLandmarks;
}
// Function : Dijkstra Distance Landmarks
// Description :
// @Param : const Graph * G
// @Param : Node * s
// @Param : std::vector<Node*>* nodes
// @Pre :
// @Post :
std::map<Node*, int>* Landmarks::DijkstraDistance(const Graph* G, Node * s, std::vector<Node*>* nodes)
{
// Create things for Dijkstra
std::vector<Vertex> parents(boost::num_vertices(*G)); // To store parents
std::vector<int> distances(boost::num_vertices(*G)); // To store distances
Vertex begin = vertex(s->GetInfo(), *G);
// Compute shortest paths from begin to all vertices, and store the output in parents and distances
boost::dijkstra_shortest_paths(*G, begin, boost::predecessor_map(&parents[0]).distance_map(&distances[0]));
std::map<Node*, int>* returnValue = new std::map<Node*, int>();
boost::graph_traits < Graph >::vertex_iterator vertexIterator, vend;
for (boost::tie(vertexIterator, vend) = boost::vertices(*G); vertexIterator != vend; ++vertexIterator)
{
Node* target = nodes->at(*vertexIterator);
returnValue->insert(std::pair<Node*, int>(target, distances[*vertexIterator]));
}
return returnValue;
}