Question

ADJACENCY LIST ( use Breadth-First Search algorithm)

How to get the total number of paths of fixed length from vector of vector adjacency LIST. REMEMBER: the fixed length has to be the shortest length.

So, const std::vector< std::vector<unsigned> > & adjList;

and I'm supposed to get the number of paths for a given shortest path from the adjList.

What I want:

1. To define the function countingGraphPathWays(const vector< vector > &adjVertex, unsigned source, vector & thPathLen, vector & numOfTheShortestPaths)

2. For the TESTED CODE to run (see attached code below) (this tested code help defining the function countingGraphPathWays)

THIS IS THE TESTED CODE (the bold are the code, and the italicswords are the information of what each function does):

TRY(GraphingTester, GraphingTesterA)
{
vector< vector > gA = {
  {1, 2, 4}, {0,3}, {0,3}, {1,2,5, 7}, {0, 5, 6}, {3, 4}, {4, 7}, {3, 6},
   }; //adjacency list
  

vector pathLengths(8);

vector numShortestPaths(8);
  
countingGraphPathWays(gA, 0,thePathLen, numOfTheShortestPaths);

/**

The function: countingGraphPathWays(const vector< vector > &adjVertex, unsigned source, vector & thPathLen, vector & numOfTheShortestPaths)

**/

//thePathLen = path lengths is basically the shortest length to reach from the source vertex to the destination vertex

vector expectedOfThePathLen = {0, 1, 1, 2, 1, 2, 2, 3}; //source vertex is 0 , and this is shortest length
vector expectedOfNumberShortestPath = {1, 1, 1, 2, 1, 1, 1, 3}; //source vertex is 0, how many ways to get to shortest length

EXPECT_TRUE(thePathLen ==expectedOfThePathLen && expectedOfNumberShortestPath ==numOfTheShortestPaths);

}

Answer 1

By using Breadth-First Search algorithm

void countingGraphPathWays(vector<vector<int>> &adj, int src, vector<int> &thePathLen, vector<int> &numOfTheShortestPaths )
{  
   int n = adj.size();
   bool visited[n];
for (int i = 0; i < n; i++)
{
       visited[i] = false;
thePathLen.push_back(INT_MAX);
       numOfTheShortestPaths .push_back(0);
   }
thePathLen[src] = 0;
numOfTheShortestPaths [src] = 1;
queue <int> q;
q.push(src);
visited[src] = true;
while (!q.empty())
{
int curr = q.front();
q.pop();
  

for (auto x : adj[curr])
{

if (visited[x] == false)
{
q.push(x);
visited[x] = true;
}
  
if (thePathLen[x] > thePathLen[curr] + 1)
{
thePathLen[x] = thePathLen[curr] + 1;
numOfTheShortestPaths [x] = numOfTheShortestPaths [curr];
}
  
else if (thePathLen[x] == thePathLen[curr] + 1)
numOfTheShortestPaths [x] += numOfTheShortestPaths [curr];
}
}  
}