PROBLEM STATEMENT

To implement Graph Data Structure. Complete the unfilled methods in the graph class of the given template.

• To Total number of paths in given digraph from given source to destination having exactly m edges. Which returns the number of paths existing between source and destination with m edges.
• Find all friends of Friends. Output should not print your direct friend. Which returns a list of Friends of friends
• DFS -BFS

Input:

• First line contains integer V, is the number of vertices in the graph
• Second line contains integer E, is the number of Edges in the graph
• Next E lines is the description of edges which contains three information from vertex, to vertex and edge cost which are space separated in the format from to weight
• Next line contains integer N, is the number of operations in the test case.
• Next N line will include the series of operations of the following type Character, value,
• Where character indicates the graph operation F- returns a list of Friends of Friends, if there is no Friends for your friend then returns an empty list and print “No FoF”, P - returns an integer that is the number of paths between source and destination with m edges.
• For Friends of friends function, F is followed by a value which is the person for which you need to find friends of friends.
• For P, it is followed by three values, first is the source vertex and second is the destination vertex, third is m - which is the path length
• For D, do the DFS traversal and classify the edges
• For B, do the BFS traversal and classify the edges

Output:

• It prints the connection details and also prints the Adjacency Matrix, followed by the output for each of the test cases
• For each testcase, output the result of each operation separated by a newline.The output of Friends of friends is a list.
• Path count returns number of path exists between source and destination with specified path length.
• DFS prints the Forward edges and Back edges
• BFS prints the forward edges and Cross edges

Sample Input

  11
  19
  1 2 19
  5 0 10
  4 6 11
  6 10 23
  10 9 33
  9 8 7
  6 7 6
  8 7 1
  9 6 9
  7 10 14
  0 4 15
  0 3 16
  0 2 5
  0 1 2
  2 3 4
  3 4 30
  4 5 18
  5 2 22
  3 1 17
  4
  F  4
  P  0  4  2
  D  0
  B  0

Sample Output

  ( 0 , 4 )
  ( 0 , 3 )
  ( 0 , 2 )
  ( 0 , 1 )
  ( 1 , 2 )
  ( 2 , 3 )
  ( 3 , 4 )
  ( 3 , 1 )
  ( 4 , 6 )
  ( 4 , 5 )
  ( 5 , 0 )
  ( 5 , 2 )
  ( 6 , 10 )
  ( 6 , 7 )
  ( 7 , 10 )
  ( 8 , 7 )
  ( 9 , 8 )
  ( 9 , 6 )
  ( 10 , 9 )
  Adjacent matrix:
  0 2 5 16 15 0 0 0 0 0 0 
  0 0 19 0 0 0 0 0 0 0 0 
  0 0 0 4 0 0 0 0 0 0 0 
  0 17 0 0 30 0 0 0 0 0 0 
  0 0 0 0 0 18 11 0 0 0 0 
  10 0 22 0 0 0 0 0 0 0 0 
  0 0 0 0 0 0 0 6 0 0 23 
  0 0 0 0 0 0 0 0 0 0 14 
  0 0 0 0 0 0 0 1 0 0 0 
  0 0 0 0 0 0 9 0 7 0 0 
  0 0 0 0 0 0 0 0 0 33 0 
  [10, 7, 0, 2]
  1
  Depth first Traversal
  Front edges: [[0, 4], [4, 6], [6, 10], [10, 9], [9, 8], [8, 7], [4, 5], [5, 2], [2, 3], [3, 1]]
  Back edges: [[7, 10], [9, 6], [6, 7], [5, 0], [3, 4], [1, 2], [0, 3], [0, 2], [0, 1]]
  dfs: [0, 4, 6, 10, 9, 8, 7, 5, 2, 3, 1]
  Breadth first Traversal
  Bfs: [0, 4, 3, 2, 1, 6, 5, 10, 7, 9, 8]
  Cross edge: [[3, 4], [3, 1], [2, 3], [1, 2], [5, 0], [5, 2], [7, 10], [9, 6], [8, 7]]