The 2nd-shortest Path

The 2nd-shortest Path

October 21, 2021

Date:11.19.2021

Update Log 11.25.2021:

Comptability:

Known issue has been included in README.md

Recommend to compile with clang++,or Visual Studio 2019 CE.
Lab Files has been compiled and reviewed under MacOS 12.0.1,and Windows 10 + CMake 3.19 + Visual Studio Community 2019.

Set CMake minimum requirement to 3.14

Performance Improvement:

Using C++ 11 rvalue reference/move semantics to mitigate the copy construction overhead, 5% speed improvement under large case
Using C++11 std::future, std::async for async function calls, with 5% improvement in speed.

1
#define __THREADING__ 

Chapter 1: Introduction

Given M vertices, indexed from 1 to M, and N edges to represent a Directional Graph.

(In my implementation, both directional and undirectional graph works fine.)

To simplify the problem, the starting point is vertex 1 and the destination is vertex M.

Task: Find Out the Second Shortest Path

  • Allow Backtracking: means each vertex can be presented in the path more than once.
    • e.g. Path: 1->2->1->3 is valid
  • Multiple Shortest Path: if multiple shortest path exists, the second shortest path is the one whose length is longer than those but no longer than any other path.
    • e.g. The length of all possible paths are 100,100,105,110. The second shortest path length is 105.
    • If two or more second shortest paths exist, any second shortest path would be accepted.

Input Specification:

In the first line specifies the number of vertices M and number of edges N of a digraph.

Then the rest N lines, each line is consisted of a edge, given by:

1
sourceVertex destVertex pathLength
  • Vertex is numbered from 1 to M
  • Only positive path length are considered

Constraints:

  • $1\le M\le1000$
  • $1\le N\le5000$
  • $1\le pathLength\le1000$

Hint:

  • If(InputSize = 1000~10^6), a tolerable upper bound of an algorithm would be $O(nlog(n))$
  • If(InputSize = 10^7), a tolerable upper bound of an algorithm would be $O(n)$
  • For this problem, if the input size is roughly $10^6<$M*N $<10^7$, the algorithm should be at least bounded by
  • $O(MN log(MN))$ .

Output Specification:

Output the second shortest path in the form below:

1
2
Cost: cost
Path: 1 ... m (exactly one space between each vertex, but no extra space at last)

If there’s no second shortest path exist:

  • Print a prompt to indicate there’s no second shortest path
  • Print the shortest path in the form below:
1
2
3
"But, the shortest path is"
Cost: cost
Path: 1 ... m (exactly one space between each vertex, but no extra space at last)

Sample:

  • Input
1
2
3
4
5
6
7
5 6
1 2 50
2 3 100
2 4 150
3 4 130
3 5 70
4 5 40
  • Output
1
240 1 2 4 5

In general, this is an specialization of single source K Shortest Path Problem , where K=2.

Many different methods have been proposed to solve this problem, and there are two main variants of this problem:

For DiGraph with M edges and N vertices:

This problem, is the Loopy variant, which means an optimal time complexity can be achieved at $O(n*log (n))$, which has a desirable run time with given constraints.

Build Environment & To Run:

Building Environment:

  • MacOS 12.0.1
  • VSCode
  • Compiler: Clang ++ 13.0
  • C++ Standard = C++ 11
  • ARM64 Platform (Apple Silicon)

Using cmake for crossplatform compile

Step1:

Download and install cmake

Step2:

The Cmake instructions (CMakeLists.txt) has been provided. You can modify it yourself.

Step3:

Open terminal/Powershell

Type in command as below

1
2
3
4
5
mkdir build
cd build
cmake ..
make
./main #under macOS or Unix-like OS

Now you’re running the program.

The program will output result carries out by each algorithm and their total runtime, in order of decreasing time complexity.

Approach 2

Using VSCode C/C++ Extensions

1.Modify tasks.json file:

1
2
3
4
5
6
7
8
"args": [
"-fdiagnostics-color=always",
"-g",
"${file}",
"-std=c++11",
"-o",
"${fileDirname}/${fileBasenameNoExtension}"
],

2.Click the button on Run and Debug panel

Other IDE:

Import the source files, and set the C++ standard to C++11, better compile with Visual Studio 2019, or using Clang++.

Known Issue:

  • GCC doesn’t support some C++ 11 features as of on Clang++, so if possible using clang++ instead.
  • When using Visual Studio 2019 for compiling, a largest case of 5000 edges would throw error of std::vector memory limit. However, this won’t happen when compile with clang++.

INPUT MODE:

By default we set to __FILE_INPUT_ And Looptime to 1.

1
2
3
4
5
6
7
8
9
#define __FILE__INPUT__

/*
change your loopTime here
*/
namespace loop
{
int loopTime = 1;
}

USAGE ON MACROS:

  • _SAMPLE_CASE_: The sample given by OJ.
  • FILE_INPUT_: Get input from files.
    • 1 file case is provided to test the largest possible input.
    • of size M=1000, N=5000
  • _USER_INPUT_: Get input from command line
  • Available Cases:
    • _SAMPLE_CASE_1~6
  • Available Graph Type:
    • class DiGraph for directional graph
    • class UGraph for undirectional graph

Chapter 2: Algorithm Specification Description

Graph Representation:

We use the multiList representation of graph, meaning the multiList[i] indicates all the edges which starts from vertex i.

  • Vertices on user interface level are numbered from 1 to n

  • Vertices in the multiList are numbered from 0 to n-1

  • Since variable sized array is available in C++, we don’t need linked list for the multiList implementation, using vector<vector<std::pair<int,int>>> instead.

  • In the std::pair, the first one indicates the destination vertex and the second indicates the path length (or cost).

  • Type of the elements in the multiList:

    1
    2
    3
    4
    5
    type(multiList) == vector<vector<std::pair<int,int>>> # this full multiList
    type(multiList[0]) == vector<std::pair<int,int>> # this is all edges starting from a certain vertex
    type(multiList[0][0]) == std::pair<int,int> # this is the single edge
    pair.first # this is edge's destination
    pair.second # this is edge's path length
  • We implemented two types of graph, undirected graph and directed graph.

    • They differs quite little in this implementation. A undirected graph, in this case, is a specialization of the directed graph.
  • An API insertEdge() is implemented for edge insertion.

Check Connection:

Before we start to find the second shortest path, we have to firstly check if there’s a possible path from vertex 1 to vertex m. We implemented this by Breadth-First-Search.

1
2
3
4
5
6
7
8
9
10
11
12
13
//keep a queue to store the vertices to be visited
queue<vertexNum> adjVertices
//keep a array to represent each vertices is visted or not
visited<bool> isVisited

enqueue the first vertex

while(queue is not empty)
currentNode = dequeue()
if(currentNode is visited)
continue;
mark the currentNode as visited;
enqueue the adjacent nodes of currentNode;

After above process, we check if vertex m has been visited, if not, means there’s no possible path from vertex 1 to vertex m, abort.

If vertex m has been visited, means there’s at least one path from vertex 1 to vertex m.

In this case, ShortestPath from 1 to m must exist.

Second Shortest Path:

In the Dijkstra’s algorithm, we find the shortest path by steps below:

  • We keep an table, keeps track of each vertex’s shortest Path Length from Start and its direct predecessor of in shortest path.

    • Each vertex is initialized as cost to infinity and predecessor to -1 as “Unmarked”

    • Each time visit the Unvisited Vertex Which Has The Shortest Path Length from Start

    • Compute its neighbors’ cumulative Path Length,

      check if it’s shorter than the table’s records
      if it's shorter, update table with the **path length and predecessor**
      
    • After compute, Mark the Vertex as visited.

  • Dijkstra’s algorithm is an Greedy Algorithm, using local minimum to get global minimum.

    • It’s possible to only record the direct predecessor of each vertex and be able to get the path from the table.
      • The shortest path from vertex 1 to m is the global minimum, and each edge along this path is also the global minimum from vertex 1 to that vertex.
    • An table may look like this
    image-20211120011014800

Note that each step we have to find the Unvisited Vertex Which Has The Shortest Path Length from Start, If we do linear scan, the time complexity would be O(V^2). But if we keep a min heap, the time complexity would be O((V+E)log(E)).

Make Some Extension

To find the second shortest path, we simply keep another table, record the second shortest path from vertex 1 to vertex i. And we have to keep track of all of its predecessors (in implementation, a string), instead of a single direct predecessor, since a second shortest path isn’t necessarily made up by multiple second shortest sub-paths.

We made some modification in the update part of the Dijkstra’s algorithm.

1
2
3
4
5
6
for v in adj(u):
if shortest[u] + cost(u, v) < shortest[v]:
second_shortest[v] = shortest[v]
shortest[v] = shortest[u] + cost(u, v)
else if shortest[u] + cost(u, v) < sec_shortest[v] and shortest[u]+cost(u,v)!=shortest[v]: //in case there are multiple shortest paths.
second_shortest[v] = shortest[u] + cost(u, v)

Also, to allow backtracking, each node can be pushed on to min heap multiple times. But for the second shortest path, the node in such path can appear at most twice.

This is obvious, if a path 1->3->1->2->1->4 contains a node appears more than twice (1 appears 3 times), there must exist 2 shorter paths where vertex 1 appear 1 and 2 times and reach 4, and thus it’s not a second shortest path.

The overall pseudocode looks like below:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
minHeap.push(vertex1)

//break the loop if the heap is empty or the second shortest path has been calculated
while(minHeap!=empty and second_shortest[vertexLast].cost == infinity)
{
for v in adj(u):
if(v has been visited twice)
continue;
if shortest[u] + cost(u, v) < shortest[v]:
second_shortest[v] = shortest[v]
shortest[v] = shortest[u] + cost(u, v)
else if shortest[u] + cost(u, v) < sec_shortest[v] and shortest[u]+cost(u,v)!=shortest[v]: //in case there are multiple shortest paths.
second_shortest[v] = shortest[u] + cost(u, v)
}

If the second_shortest[vertexLast].cost=infinity, means there’s no second shortest path from vertex 1 to last vertex. In this case, we output the shortest path. A shortest path is ensured since we’ve done the BFS in advance.

Chapter 3: Testing Results

Case 1: Sample Case

1
2
3
4
5
6
7
DiGraph graph(5, 6);
graph.insertEdge(1, 2, 50);
graph.insertEdge(2, 3, 100);
graph.insertEdge(2, 4, 150);
graph.insertEdge(3, 4, 130);
graph.insertEdge(3, 5, 70);
graph.insertEdge(4, 5, 40);

Result: Correct

image-20211120014336249

Case 2: An Undirectional Graph

image-20211120014537752
1
2
3
4
5
6
7
8
9
10
11
12
UGraph graph(10, 11);
graph.insertEdge(1, 2, 4);
graph.insertEdge(1, 3, 2);
graph.insertEdge(1, 7, 7);
graph.insertEdge(2, 4, 2);
graph.insertEdge(3, 6, 8);
graph.insertEdge(3, 7, 3);
graph.insertEdge(4, 7, 5);
graph.insertEdge(4, 8, 6);
graph.insertEdge(6, 10, 3);
graph.insertEdge(7, 10, 4);
graph.insertEdge(8, 10, 2);

Result: Correct

image-20211120014515770

Case 3: Two shortest paths exists, second shortest path requires backtracking

1
2
3
4
UGraph graph(3, 3);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 4);
graph.insertEdge(2, 3, 3);

Result: Correct

image-20211120014753271

Case 4: No second shortest path, but exist two shortest path of same length.

1
2
3
4
DiGraph graph(3, 3);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 4);
graph.insertEdge(2, 3, 3);

Result: Correct

image-20211120014957572

Case 5: No valid path from 1 to m

1
2
3
4
DiGraph graph(4, 3);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 4);
graph.insertEdge(2, 3, 3);

Result: Correct

image-20211120015142150

Case 6: Minimum Case

1
2
3
4
5
/*
Minimum case, 2 vertices and 1 edge (since self loop is not allowed)
*/
DiGraph graph(2, 1);
graph.insertEdge(1, 2, 1);

Result: Correct

image-20211120132214734

Case 7: Maximum Case

1
2
3
4
5
/*
Get input from largestCase.in
Use macro __FILE__INPUT__
m=1000,n=5000
*/
image-20211120015529523

Conclusion:

  • The result seems acceptable so far, need some complex test cases for validation.

Chapter 4: Analysis and Comments

  • M = number of Vertices
  • N = number of Edges

1.Build Graph:

We keep an multiList by inserting all edges into the vector<vector<pair<int,int>>>

  • Each insertion takes $O(1)$, the overall time complexity would be $O(N)$

Overall Time Complexity: $O(N)$

We keep an multiList, each element is consist of destination and cost, which is $O(1)$

the overall time complexity would be $O(N)$

Overall Space Complexity: $O(N)$

For Undirectional Graph, the only difference is that the insertion time and space taken by undirectional graph is twice as the directional one. But both are O(N) after all.

2.Check Connection:

  1. In this step each edge is visited at most once, each node is visited at most once.
  2. The enqueue and dequeue takes $O(1)$ time.

the overall time complexity would be $O(N)$

Overall Time Complexity: $O(M+N)$

Space Complexity :

A queue of $O(N)$ (at most contains all edges) is needed in this step.

Overall Space Complexity: $O(N)$

3.Second Shortest Path

  • We push each node to min heap at most twice (2M)

    • Each time a edge is popped

      • We update table, which takes $O(1)$ time
    • Each pop or push takes $O(log(M))$ time

Overall Time Complexity: $O(Mlog(M))$

  • We keep two tables, each tables takes M elements, each elements contains a string (contains all predecessors, at most length O(N)) and a int (cumulative cost).

    • Two tables occupies $O(2M*N)$ Space.
  • We also keeps an heap of max size $O(N)$, each node occupies $O(1)$ Space.

Overall Space Complexity: $O(M*N)$

OVERALL:

Overall Time Complexity: $O(N+Mlog(M))$

Overall Space Complexity: $O(M*N)$

Comments:

In the actual implementation of the constraint “each node is visited at most twice”, we use a slightly different approach based on the cumulative length, but they should have the same effect.

Although no hacking cases founded now, if things go wrong in some cases, the logic there needs a rewrite to be more accurate.

Extra: K-Shortest Path

If we extend the same technique to the K shortest path, we have to keep K table, which takes up $O(KMN)$ Space.

Each node can be pushed to heap at most K times, Which takes overall $O(N + KMlog (M))$ time.

Overall Time Complexity: $O(N+K*Mlog(M))$

Overall Space Complexity: $$O(KMN)$$

Appendix: Source Code (in C++11)

Djikstra.hpp

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
#pragma once
#include "Graph.hpp"
#include <queue>

/*
anscestors are numbered from 0~n-1
*/
struct CostTable
{
int cost;
string ancestors;
};

/*
heap node is numbered from 1~n
*/
struct HeapNode
{
string ancestors;
int src;
int dst;
int cost;

HeapNode(string&& ancestors, int src, int dst, int cost)
{
this->ancestors = ancestors;
this->src = src;
this->dst = dst;
this->cost = cost;
};
};

/*
Order minHeap by cost
*/
struct compare
{
bool operator()(const HeapNode &a, const HeapNode &b) const
{
return a.cost > b.cost;
}
};

/*
Allowing for both digraph and undirectional graphs.
finding the second shortest path using extended dijkstra algorithm
graph: the graph to be searched
verbose: print out result, by default set to true
*/
template <typename T>
void dijkstra(T &graph, bool verbose = true)
{
/*
type check
*/
bool isGraph = std::is_same<T, UGraph>::value || std::is_same<T, DiGraph>::value;
if (!isGraph)
throw std::runtime_error("Input is not compatible graph");

/*
initialize the table,
with the total path cost to inifinity,
parent to - 1 as null
*/

/*
record the shortest path cost
*/
vector<CostTable> costTable(graph.getVertexNum(), {INT32_MAX, {"-1"}});

/*
record the second shortest path cost
*/
vector<CostTable> secondCostTable(graph.getVertexNum(), {INT32_MAX, {"-1"}});

//initialize priority_queue as minHeap. STL implementation by default is maxHeap
priority_queue<HeapNode, vector<HeapNode>, compare> minHeap;

//set starting point
costTable[0].ancestors = "-2";
costTable[0].cost = 0;

/*
priority_queue doesn't offer a iterator
each node contains source, destination and cumulative cost
order by cumulative cost
*/

//push the adjacent nodes of the starting node
for (auto &edge : graph.multiList[0])
{
auto tmpNode = HeapNode("1 " + to_string(edge.first + 1), 1, edge.first + 1, edge.second);
minHeap.push(tmpNode);
}

/*
while the second shortest path of the given vertex is not determined
*/
while (!minHeap.empty() && secondCostTable.back().cost == INT32_MAX)
{

auto node = minHeap.top();
minHeap.pop();

int totalCost = node.cost;
int srcIndex = node.src;
int destIndex = node.dst;

/*
if the current node's total cost is less than the cost in shortest table
update the shortest path, and the second shortest path
*/
if (totalCost < costTable[destIndex - 1].cost)
{
secondCostTable[destIndex - 1].cost = costTable[destIndex - 1].cost;
secondCostTable[destIndex - 1].ancestors = costTable[destIndex - 1].ancestors;
costTable[destIndex - 1].cost = totalCost;
costTable[destIndex - 1].ancestors = node.ancestors;
}

/*
if the current node's total cost is larger than the shortest
and less than the cost in second shortest
update the second shortest path
*/
else if (totalCost < secondCostTable[destIndex - 1].cost && totalCost != costTable[destIndex - 1].cost)
{
secondCostTable[destIndex - 1].cost = totalCost;
secondCostTable[destIndex - 1].ancestors = node.ancestors;
}

else
{ //to find the 2nd shortest path
// there's no need to push the child of 3rd or 4th shortest path to heap
continue;
}

/*
push the adjacent nodes, we don't check if the node is visited or not
since we allow backtracking
*/
for (auto &edge : graph.multiList[destIndex - 1])
{
/*
each node is ensured to be visited twice at most
*/
if (secondCostTable[edge.first].cost < totalCost + edge.second)
continue;

//push the node to the priority queue
auto tmpNode = HeapNode(node.ancestors + " " + to_string(edge.first + 1), destIndex, edge.first + 1, totalCost + edge.second);
minHeap.push(tmpNode);
};
}

/*
if the ancestors is "-1", means the second cost table of the last vertex
haven't been visited yet, Which means there's no second shortest path, but at least one path
from start to end is ensured through previous checkConnection().
*/
if (secondCostTable.back().ancestors == "-1")
{
if (verbose)
{
cout << "Doesn't exist second shortest path." << endl;
cout << "But, the shortest path is" << endl;
}

int cost = costTable.back().cost;
auto path = costTable.back().ancestors;

if (verbose)
{
cout << "Cost: " << cost << endl;
cout << "Path: ";
cout << path << endl;
}
return;
}

/*
return the second shortest path with given cost table
*/
if (verbose)
cout << "The second shortest path is" << endl;

int cost = secondCostTable.back().cost;
auto path = secondCostTable.back().ancestors;

if (verbose)
{
cout << "Cost: " << cost << endl;
cout << "Path: ";
cout << path << endl;
}

return;
};

Graph.hpp

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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#pragma once
#include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

/*
Base Class
*/
class Graph
{
public:
//multiList Representation, using vector
//each element contains destination and cost
vector<vector<pair<int, int>>> multiList;

Graph(){};

//initialize
Graph(int vertexNum, int edgeNum)
{
vNum = vertexNum;
eNum = edgeNum;
multiList.resize(vertexNum);
inDegree.resize(vertexNum);
}

//get number of vertices
int getVertexNum() const
{
return vNum;
}

//get number of vertices
int getEdgeNum() const
{
return eNum;
}

/*
insert an edge from src to dst
*/
virtual void insertEdge(int srcVertex, int dstVertex, int cost) = 0;

bool containsEdge(int srcVertex, int dstVertex)
{
// make it easier to index
int src = srcVertex - 1;
int dst = dstVertex - 1;

//check if the graph contains a certain edge, using lambda expression
if (find_if(multiList[src].begin(), multiList[src].end(), [&](const pair<int, int> &elem)
{ return elem.first == dst; }) != multiList[src].end())

return true;

return false;
};

void print()
{
for (int i = 0; i < multiList.size(); i++)
{
cout << i + 1 << ": ";
for (int j = 0; j < multiList[i].size(); j++)
{
cout << multiList[i][j].first + 1 << ' ' << multiList[i][j].second << ' ';
}
cout << endl;
}
}

protected:
vector<int> inDegree;
//number of edges and vertices
int vNum;
int eNum;
};

/*
a class for undirectional graphs
*/
class UGraph : public Graph
{
public:
UGraph(int vNum, int eNum) : Graph(vNum, eNum){};
//insert an edge from src to dst
void insertEdge(int srcVertex, int dstVertex, int cost) override
{
// minus one, make it easier to index
int src = srcVertex - 1;
int dst = dstVertex - 1;

//update parameters
multiList[src].push_back(make_pair(dst, cost));
multiList[dst].push_back(make_pair(src, cost));
inDegree[dst]++;
inDegree[src]++;
};
};

/*
a class for Directional graphs
*/
class DiGraph : public Graph
{
public:
DiGraph(int vNum, int eNum) : Graph(vNum, eNum){};

//insert an edge from src to dst
void insertEdge(int srcVertex, int dstVertex, int cost) override
{
// minus one, make it easier to index
int src = srcVertex - 1;
int dst = dstVertex - 1;

//update parameters
multiList[src].push_back(make_pair(dst, cost));
inDegree[dst]++;
};
};

/*
BFS algorithm to check if there's a path from the first node to the last node
*/
template <typename T>
bool checkConnection(T &graph)
{
/*
type check
*/
bool isGraph = std::is_same<T, UGraph>::value || std::is_same<T, DiGraph>::value;
if (!isGraph)
throw std::runtime_error("Input is not compatible graph");

vector<bool> isVisited(graph.getVertexNum(), false);
queue<int> q;

/*
push in the first node
*/
q.push(0);

/*
each round:
1.currentNode = dequeue(), if(currentNode is visited) continue;
2.mark the currentNode as visited.
3.enqueue the adjacent nodes of currentNode
*/
int currentNode;
while (!q.empty())
{
currentNode = q.front();
q.pop();

if (isVisited[currentNode])
continue;

isVisited[currentNode] = true;

for (const auto &adjNode : graph.multiList[currentNode])
{
q.push(adjNode.first);
}
}

/*
if there's no path from the first node to the last node
means there's no possible second shortest path
*/
if (!isVisited[graph.getVertexNum() - 1])
{
cout << "ERROR: No Path to Destination" << endl;
return false;
}

return true;
}

lab3.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
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include "Graph.hpp"
#include "Dijkstra.hpp"
#include <fstream>
#include <thread>
#include <future>
// #define __SAMPLE__CASE__
#define __CASE__2__
// #define __USER__INPUT__
// #define __FILE__INPUT__
#define __THREADING__
using namespace std;

/*
change your loopTime here
*/
namespace loop
{
int loopTime = 10000;
}

int main()
{

#ifdef __SAMPLE__CASE__
DiGraph graph(5, 6);
graph.insertEdge(1, 2, 50);
graph.insertEdge(2, 3, 100);
graph.insertEdge(2, 4, 150);
graph.insertEdge(3, 4, 130);
graph.insertEdge(3, 5, 70);
graph.insertEdge(4, 5, 40);
#endif

/*
a bidirectional (undirected graph) case
*/
#ifdef __CASE__1__
UGraph graph(10, 11);
graph.insertEdge(1, 2, 4);
graph.insertEdge(1, 3, 2);
graph.insertEdge(1, 7, 7);
graph.insertEdge(2, 4, 2);
graph.insertEdge(3, 6, 8);
graph.insertEdge(3, 7, 3);
graph.insertEdge(4, 7, 5);
graph.insertEdge(4, 8, 6);
graph.insertEdge(6, 10, 3);
graph.insertEdge(7, 10, 4);
graph.insertEdge(8, 10, 2);
#endif

/*
there exist two shortest path between 1-3
*/
#ifdef __CASE__2__
UGraph graph(3, 3);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 4);
graph.insertEdge(2, 3, 3);
#endif

/*
Only one shortest path between 1 and 3
*/
#ifdef __CASE__3__
DiGraph graph(3, 3);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 4);
graph.insertEdge(2, 3, 3);
#endif

/*
Vertex 4 is isolated, no valid path
*/
#ifdef __CASE__4__
DiGraph graph(4, 3);
graph.insertEdge(1, 2, 1);
graph.insertEdge(1, 3, 4);
graph.insertEdge(2, 3, 3);
#endif

/*
Minimum case, 2 vertices and 1 edge (since self loop is not allowed)
*/
#ifdef __CASE__5__
DiGraph graph(2, 1);
graph.insertEdge(1, 2, 1);
#endif

/*
DiGraph with cycle
*/
#ifdef __CASE__6__
DiGraph graph(5, 5);
graph.insertEdge(1, 2, 100);
graph.insertEdge(2, 3, 100);
graph.insertEdge(3, 4, 100);
graph.insertEdge(3, 5, 1);
graph.insertEdge(5, 2, 1);
#endif

#ifdef __FILE__INPUT__
/*
a large input case
*/
std::ifstream inputFile("largestCase.in");

int vNum, eNum;
inputFile >> vNum >> eNum;
DiGraph graph(vNum, eNum);

int src, dst, cost;
while (eNum > 0)
{
inputFile >> src >> dst >> cost;
graph.insertEdge(src, dst, cost);
eNum--;
}
#endif
/*
get input from user, by default directional graph
*/
#ifdef __USER__INPUT__
int vNum, eNum;
cin >> vNum >> eNum;
DiGraph graph(vNum, eNum);

int src, dst, cost;
for (int i = 0; i < graph.getEdgeNum(); i++)
{
cin >> src >> dst >> cost;
graph.insertEdge(src, dst, cost);
}
#endif

std::chrono::time_point<std::chrono::system_clock> start, end;
start = std::chrono::system_clock::now();

for (int i = 0; i < loop::loopTime; i++)
{
//using async function
#ifdef __THREADING__
std::future<bool> fp = async(
launch::async, checkConnection<decltype(graph)>,
std::ref(graph));
#endif

#ifndef __THREADING__
if (!checkConnection(graph))
return 0;
#endif

dijkstra(graph, false);

#ifdef __THREADING__
try
{
bool isConnected = fp.get();
if (!isConnected)
return 0;
}
catch (std::exception &e)
{
cout << "Error: threading failed:" << e.what() << endl;
return 0;
}
#endif
}

std::chrono::duration<double> duration;
end = std::chrono::system_clock::now();
duration = end - start;
//print time it takes
std::cout << "Program Completed in: " << duration.count() << " seconds" << std::endl;

/*
test code for graph functionality
*/
// cout << graph.containsEdge(1, 2) << endl;
// graph.print();
}