## Chapter 7: Graph Algorithms II

### Activity 15: Greedy Robot

We can solve this activity using the exact algorithm from *Exercise 33*, *Implementing the Bellman-Ford Algorithm (Part II)*. The potential pitfalls here are related to correctly interpreting the required task and representing the graph within the context of the problem you are actually trying to solve. Let's get started:

- The first step will be identical to the exercise. We will include the same headers and define an
**Edge**struct and an**UNKNOWN**constant:#include <iostream>

#include <vector>

#include <climits>

using namespace std;

struct Edge

{

int start;

int end;

int weight;

Edge(int s, int e, int w) : start(s), end(e), weight(w) {}

};

const int UNKNOWN = INT_MAX;

vector<Edge*> edges;

- In
**main()**, we will declare an integer,**N**, which determines the height/width of the grid. We will then iterate from 0 to N * N - 1 in a**for**loop and read the adjacency data given in the input:int main()

{

int N;

cin >> N;

for(int i = 0; i < N * N - 1; i++)

{

string directions;

int power;

cin >> directions >> power;

……

}

return 0;

}

- Now, we must face the first potential problem – accurately representing the adjacencies. Typically, we would be inclined to think of a grid in two dimensions, and while it would certainly be possible to solve the problem this way, it would not be the optimal approach for this particular problem. To reinterpret the grid and adjacencies in one dimension, we must simply observe the following relationships between the one-dimensional index,
**i**, and the corresponding two-dimensional grid coordinates:CURRENT CELL: (x, y) —> i

NORTH: (x, y - 1) —> i - N

SOUTH: (x, y + 1) —> i + N

EAST: (x + 1, y) —> i + 1

WEST: (x - 1, y) —> i - 1

- We can handle these relationships by iterating through the characters of
**directions**and containing the logic within a**switch**statement:for(int i = 0; i < N * N - 1; i++)

{

string directions;

int power;

cin >> directions >> power;

int next;

for(auto d : directions)

{

switch(d)

{

case 'N': next = i - N; break;

case 'S': next = i + N; break;

case 'E': next = i + 1; break;

case 'W': next = i - 1; break;

}

……

}

}

- This leads to the second problematic aspect of this activity; that is, the interpretation of the
**power**values. These, of course, will be the values that define the edge weights between adjacent cells, but within the context of this problem, the inputs can be rather misleading. According to the problem's description, we want to find the path that reaches the end with the maximum amount of energy compared to the baseline. A careless reading of the problem statement may lead us to conclude that the**power**values correspond exactly to the edge weights, but this would actually produce the opposite of what we intend to achieve. "Maximizing energy" can be viewed as the equivalent to "minimizing energy loss," and since the negative values actually represent the energy expenditure for each cell and the positive values represent energy gained, we must reverse the sign of each**power**value:for(auto d : directions)

{

switch(d)

{

……

}

// Add edge with power variable's sign reversed

edges.push_back(new Edge(i, next, -power));

}

- Now, we can implement
**BellmanFord()**. This time, our function will take**N**and**edges**as arguments and return an integer equal to the maximum relative energy. To simplify our code, we will pass**N**as the total number of cells in the grid (that is,**N * N**):int BellmanFord(int N, vector<Edge*> edges)

{

vector<int> distance(N, UNKNOWN);

// Starting node is always index 0

distance[0] = 0;

for(int i = 0; i < N - 1; i++)

{

for(auto edge : edges)

{

if(distance[edge->start] == UNKNOWN)

{

continue;

}

if(distance[edge->start] + edge->weight < distance[edge->end])

{

distance[edge->end] = distance[edge->start] + edge->weight;

}

}

}

……

}

- As per the standard implementation, we will also perform a check for negative cycles to handle the condition related to the robot's greedy energy consumption. In the case that a negative cycle is found, we will return
**UNKNOWN**:// Check for negative cycles

for(auto edge : edges)

{

if(distance[edge->start] == UNKNOWN)

{

continue;

}

if(distance[edge->start] + edge->weight < distance[edge->end])

{

return UNKNOWN;

}

}

return distance[N];

- Now, we can perform a call to
**BellmanFord()**in**main()**and handle the output accordingly:int result = BellmanFord(N * N, edges);

(result == UNKNOWN) ? cout << "ABORT TRAVERSAL" << endl

: cout << -1 * result << endl;

return 0;

### Activity 16: Randomized Graph Statistics

In this activity, we will generate randomized graphs for interview tests as described in the activity brief. Follow these steps to complete the activity:

- Begin by including the following headers, as well as defining the
**UNKNOWN**constant and the**Edge**struct:#include <iostream>

#include <vector>

#include <iomanip>

#include <algorithm>

#include <queue>

#include <utility>

using namespace std;

const int UNKNOWN = 1e9;

struct Edge

{

int u;

int v;

int w;

Edge(int u, int v, int w)

: u(u), v(v), w(w) {}

};

- Our first task is to handle the generation of each graph. For this activity, we will encapsulate our graph data within a struct:
struct Graph

{

int V, E;

int maxWeight = -1e9;

vector<Edge> edges;

vector<vector<int>> adj;

vector<vector<int>> weight;

Graph(int v, int e) : V(v), E(e)

{

...

}

};

- To make sure that the generated edges and the resulting graph are valid, we will create an adjacency matrix and check it during every attempt to create another edge. If an edge between the same two nodes already exists, we will begin another iteration. To make sure that every node has at least one incoming or outgoing edge, we will also set the diagonal cells in the matrix to true for each node that is part of an edge. If any of the diagonal cells are false after
**E**edges are created, the graph will be invalid. We can indicate a graph as invalid by setting**V**to**-1**:Graph(int v, int e) : V(v), E(e)

{

vector<vector<bool>> used(V, vector<bool>(V, false));

adj.resize(V);

weight.resize(V, vector<int>(V, UNKNOWN));

while(e)

{

// Generate edge values

int u = rand() % V;

int v = rand() % V;

int w = rand() % 100;

if(rand() % 3 == 0)

{

w = -w;

}

// Check if the edge is valid

if(u == v || used[u][v])

{

continue;

}

// Add to edges and mark as used

edges.push_back(Edge(u, v, w));

adj[u].push_back(v);

weight[u][v] = w;

maxWeight = max(maxWeight, w);

used[u][u] = used[v][v] = used[u][v] = used[v][u] = true;

e--;

}

for(int i = 0; i < V; i++)

{

// Set V to -1 to indicate the graph is invalid

if(!used[i][i])

{

V = -1;

break;

}

}

}

- Let's also define an enum called
**RESULT**with the corresponding values for each type of graph we need to consider:enum RESULT

{

VALID,

INVALID,

INTERESTING

};

- In
**main()**, we will receive the input, as well as declare the counters for each type of graph. We will then loop through the given number of iterations, create a new graph, and call a**TestGraph()**function that takes a**Graph**object as input and returns**RESULT**. Depending on the value that's returned, we will increment each counter accordingly:int main()

{

unsigned int seed;

int iterations, V, E;

cin >> seed;

cin >> iterations;

cin >> V >> E;

int invalid = 0;

int valid = 0;

int interesting = 0;

srand(seed);

while(iterations--)

{

Graph G(V, E);

switch(TestGraph(G))

{

case INVALID: invalid++; break;

case VALID: valid++; break;

case INTERESTING:

{

valid++;

interesting++;

break;

}

}

}

return 0;

}

**TestGraph()**will first check whether the value of**V**for each graph is equal to**-1**and return**INVALID**if so. Otherwise, it will perform Johnson's algorithm to retrieve the shortest distances. The first step will be to retrieve the reweighting array using the Bellman-Ford algorithm:RESULT TestGraph(Graph G)

{

if(G.V == -1)

{

return INVALID;

}

vector<int> distance = BellmanFord(G);

……

}

- The implementation of Bellman-Ford that's used in this solution corresponds exactly to the one from the exercise, except that it receives a single
**Graph**structure as an argument:vector<int> BellmanFord(Graph G)

{

vector<int> distance(G.V + 1, UNKNOWN);

int s = G.V;

for(int i = 0; i < G.V; i++)

{

G.edges.push_back(Edge(s, i, 0));

}

distance[s] = 0;

for(int i = 0; i < G.V; i++)

{

for(auto edge : G.edges)

{

if(distance[edge.u] == UNKNOWN)

{

continue;

}

if(distance[edge.u] + edge.w < distance[edge.v])

{

distance[edge.v] = distance[edge.u] + edge.w;

}

}

}

for(auto edge : G.edges)

{

if(distance[edge.u] == UNKNOWN)

{

continue;

}

if(distance[edge.u] + edge.w < distance[edge.v])

{

return {};

}

}

return distance;

}

- As we did in the exercise, we will check whether the vector that's returned by
**BellmanFord()**is empty. If so, we return**VALID**(the graph is valid but uninteresting). Otherwise, we will follow through with the rest of Johnson's algorithm by reweighting the edges and performing a call to Dijkstra's algorithm for each vertex:RESULT TestGraph(Graph G)

{

if(G.V == -1)

{

return INVALID;

}

vector<int> distance = BellmanFord(G);

if(distance.empty())

{

return VALID;

}

for(auto edge : G.edges)

{

G.weight[edge.u][edge.v] += (distance[edge.u] – distance[edge.v]);

}

double result = 0;

for(int i = 0; i < G.V; i++)

{

vector<int> shortest = Dijkstra(i, G);

}

}

- For this solution, let's use a more efficient form of Dijkstra's algorithm, which uses a min-priority queue to determine traversal order. To do this, each value that's added to the queue must consist of two values: the node's index and its distance value. We will do this using
**std::pair<int, int>**, which has been redefined here as**State**. When pushing elements to the queue, the first value must correspond to the distance since this is going to be the first value that's considered by the priority queue's internal ordering logic. All of this can be handled by**std::priority_queue**, but we will need to provide three template parameters corresponding to the data type, container, and comparison predicate, respectively:vector<int> Dijkstra(int source, Graph G)

{

typedef pair<int, int> State;

priority_queue<State, vector<State>, greater<State>> Q;

vector<bool> visited(G.V, false);

vector<int> distance(G.V, UNKNOWN);

Q.push({0, source});

distance[source] = 0;

while(!Q.empty())

{

State top = Q.top();

Q.pop();

int node = top.second;

int dist = top.first;

visited[node] = true;

for(auto next : G.adj[node])

{

if(visited[next])

{

continue;

}

if(dist != UNKNOWN && distance[next] > dist + G.weight[node][next])

{

distance[next] = distance[node] + G.weight[node][next];

Q.push({distance[next], next});

}

}

}

return distance;

}

- Now, we will calculate the averages in
**TestGraph()**for each set of paths. We do this by iterating through the array returned by**Dijkstra()**and keeping a sum of distances for which the index is not equal to the starting node's index. The corresponding value is not equal to**UNKNOWN**. Every time a valid distance is found, a counter is also incremented so that we can get the final average by dividing the sum by the count. Each one of these averages is then added to the total result, which is divided by the total number of vertices in the graph. Remember that we must reweight the distances again to get the correct values:double result = 0;

for(int i = 0; i < G.V; i++)

{

vector<int> shortest = Dijkstra(i, G);

double average = 0;

int count = 0;

for(int j = 0; j < G.V; j++)

{

if(i == j || shortest[j] == UNKNOWN)

{

continue;

}

shortest[j] += (distance[j] – distance[i]);

average += shortest[j];

count++;

}

average = average / count;

result += average;

}

result = result / G.V;

- The last step is to calculate the ratio between the result and the maximum weight in the graph. If the value is less than
**0.5**, we return**INTERESTING**; otherwise, we return**VALID**:double ratio = result / G.maxWeight;

return (ratio < 0.5) ? INTERESTING : VALID;

- We can now return to
**main()**and print the output. The first line will be equal to the value of**invalid**. The second line will be equal to**interesting / valid**, multiplied by**100**, so that it will be displayed as a percentage. Depending on how you do this, you may have to cast your variables as floating points to prevent the value from being rounded to an integer. When printing the output, you can easily make sure it is rounded to two decimal places by using**cout << fixed << setprecision(2)**:double percentInteresting = (double)interesting / valid * 100;

cout << "INVALID GRAPHS: " << invalid << endl;

cout << "PERCENT INTERESTING: " << fixed << setprecision(2) << percentInteresting << endl;

return 0;

### Activity 17: Maze-Teleportation Game

The entire activity conforms fairly closely to the standard implementations of the algorithms we've discussed in this chapter, but with a few slight modifications.

The terms that were used in the problem description, that is, *maze*, *rooms*, *teleporters*, and *points* could, of course, just as easily have been called *graph*, *vertices*, *edges*, and *edge weights*. The condition in which a player is able to infinitely reduce their score can be redefined as a *negative weight cycle*. Follow these steps to complete the activity:

- Let's begin by including the necessary headers and setting up the variables and input for the activity:
#include <iostream>

#include <vector>

#include <stack>

#include <climits>

struct Edge

{

int start;

int end;

int weight;

Edge(int s, int e, int w) : start(s), end(e), weight(w) {}

}

const int UNKNOWN = INT_MAX;

vector<Edge*> edges; // Collection of edge pointers

- We will receive input in the same form as our original Bellman-Ford implementation, but we will also build an adjacency list for our graph (represented here as a vector of integer vectors,
**adj**):int main()

{

int V, E;

cin >> V >> E;

vector<Edge*> edges;

vector<vector<int>> adj(V + 1);

for(int i = 0; i < E; i++)

{

int u, v, w;

cin >> u >> v >> w;

edges.push_back(new Edge(u, v, w));

adj[u].push_back(v);

}

vector<int> results;

- The first portion of the problem can be solved by using Bellman-Ford in an identical fashion to what was outlined in
*Exercise 32*,*Implementing the Bellman-Ford Algorithm (Part I)*. However, instead of printing all the values in the distance array, we will set its return type to**int**and include a few extra lines of code so that it returns only the shortest distance from the source vertex (or**UNKNOWN**if a negative cycle is detected):int BellmanFord(int V, int start, vector<Edge*> edges)

{

// Standard Bellman-Ford implementation

vector<int> distance(V, UNKNOWN);

distance[start] = 0;

for(int i = 0; i < V - 1; i++)

{

for(auto edge : edges)

{

if(distance[edge->start] == UNKNOWN)

{

continue;

}

if(distance[edge->start] + edge->weight < distance[edge->end])

{

distance[edge->end] = distance[edge->start] + edge->weight;

}

}

}

// Return UNKNOWN if a negative cycle is found

if(HasNegativeCycle(distance, edges))

{

return UNKNOWN;

}

int result = UNKNOWN;

for(int i = 0; i < V; i++)

{

if(i == start) continue;

result = min(result, distance[i]);

}

return result;

}

- We can now call this function in
**main()**and populate a results vector for output. If**BellmanFord()**happens to return**UNKNOWN**, we output**INVALID MAZE**and terminate the program (as per the first condition). If a certain starting node has no outgoing edges, we can skip the call to**BellmanFord**entirely and simply append**UNKNOWN**to the vector. If we make it through every vertex, we can output the values in the results (or**DEAD END**if the value is**UNKNOWN**):vector<int> results;

for(int i = 0; i < V; i++)

{

if(adj[i].empty())

{

results.push_back(UNKNOWN);

continue;

}

int shortest = BellmanFord(V, i, edges);

if(shortest == UNKNOWN)

{

cout << "INVALID MAZE" << endl;

return 0;

}

results.push_back(shortest);

}

for(int i = 0; i < V; i++)

{

cout << i << ": ";

(results[i] == INVALID) ? cout << "DEAD END" << endl : cout << results[i] << endl;

}

- Now, we've come to the final condition – finding rooms in which players can get "stuck." Considering this case in terms of graph connectivity, we can redefine it as follows: find the strongly connected components that have no outgoing edges to other components. There are many simple ways to do this once all the strongly connected components have been acquired, but let's try to maximize our program's efficiency and add the necessary logic directly into our existing Kosaraju implementation.
To accomplish this, we will declare two new vectors: one of type

**bool**, named**isStuck**and another of type**int**, named**inComponent**.**inComponent**will store the index of the component each node belongs to, while**isStuck**will tell us whether or not the component with index**i**is cut off from the rest of the graph.For the sake of simplicity, let's declare the new variables globally:

vector<bool> isStuck;

vector<int> inComponent;

int componentIndex;

Here, we can really begin to appreciate the benefits of encapsulation and object-oriented implementations of graph structures. Having to pass such a large amount of data between our functions is not only difficult to keep track of mentally, but it greatly complicates any kind of modifications we may want to make in the future (to say nothing about the headache-inducing appearance of a function call such as

**GetComponent(node, adj, visited, component, isStuck, inComponent, componentIndex)**. For the sake of example and readability, we opt to declare this data globally, but this sort of approach is highly recommended against within the context of an actual full-scale application. - Within our
**Kosaraju**function, we initialize the new data as follows:isStuck.resize(V, true);

inComponent.resize(V, UNKNOWN);

componentIndex = 0;

- Now, we will begin our
**while**loop, incrementing**componentIndex**by following each DFS traversal that's performed on the stack:while(!stack.empty())

{

int node = stack.top();

stack.pop();

if(!visited[node])

{

vector<int> component;

GetComponent(node, transpose, visited, component);

components.push_back(component);

componentIndex++;

}

}

- Now, we can write the logic in
**GetComponent()**, which will handle this case. We will begin by setting the value of each node's index in**inComponent**to**componentIndex**. Now, as we iterate through each node's neighbors, we will include another condition that occurs when the nodes have already been visited:component.push_back(node);

visited[node] = true;

inComponent[node] = componentIndex;

for(auto next : adj[node])

{

if(!visited[next])

{

GetComponent(next, visited, adj, component);

}

else if(inComponent[node] != inComponent[next])

{

isStuck[inComponent[next]] = false;

}

}

Essentially, we are checking to see whether each previously visited neighbor's component matches the current node's component. If their respective component IDs are different, we can conclude that the neighbor's component has a path that extends to other parts of the graph.

You may be wondering why, in a directed graph, the existence of an edge from the current node indicates that the neighboring node has an outgoing path outside of its own component. The reason this logic seems 'backward' is because it is. Remember that we are traversing the transform of the original graph, so the directions between adjacencies are all reversed!

- Upon finishing the DFS traversals, we can now return the
**components**vector and print the results:auto components = Kosaraju(V, adj);

for(int i = 0; i < components.size(); i++)

{

if(isStuck[i])

{

for(auto node : components[i])

{

cout << node << " ";

}

cout << endl;

}

}

return 0;