-
Notifications
You must be signed in to change notification settings - Fork 0
/
bbfs.cpp
61 lines (54 loc) · 1.58 KB
/
bbfs.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
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <string>
#include <string.h>
#include <vector>
#include <math.h>
#include "TemporalGraph.h"
void TemporalGraph::addEdgeToIndex(int src, int dst, int startTime){
}
void TemporalGraph::removeEdgeFromIndex(int src, int dst, int startTime, int endTime){
}
int TemporalGraph::isReachable(int src, int dst, int startTime, int endTime, int c, bool fractional){
/*reset all Nodes*/
int *earliestArrival = new int[numNodes];
bool *isInQueue = new bool[numNodes];
std::vector<int> queue;
for (int i = 0; i < numNodes; i++){
earliestArrival[i] = -1;
isInQueue[i] = false;
}
int u = src;
earliestArrival[u] = startTime;
queue.push_back(u);
isInQueue[u] = true;
Interval *query = new Interval(startTime, endTime);
while (queue.size() > 0){
u = queue[0];
queue.erase(queue.begin());
isInQueue[u] = false;
//for each edge from u
TemporalNode *n = nodes[u];
for (int i = 0; i < n->getNumEdges(true); i++){
TemporalEdge *e = n->getEdgeAt(i,true);
int v = e->getDestId();
if ((e->getEndTime() != -2) //no point in taking perpetual edges, temporarily changed -1 to -2
&& (e->getStartTime() >= earliestArrival[u])
&& ((earliestArrival[v] > e->getEndTime()) || (earliestArrival[v] == -1))
&& (e->getEndTime() <= endTime)){
earliestArrival [v] = e->getEndTime();
if (isInQueue[v] == false){
queue.push_back(v);
isInQueue[v] = true;
}
}
}
}
free(query);
int answer = 0;
if (earliestArrival[dst] != -1) answer = 1;
delete[] earliestArrival;
delete[] isInQueue;
return answer;
}