Search Strategy Pattern

Overview: In this lab you will extend Lab 1 to include a Search class that extends from the Strategy Design pattern single interface for implementing and analyzing the performance of the following search algorithms: BFS, DFS, Dijkstra, A*.

Code Requirements:

• Use same Strategy Class from Lab 1 with same functionality of member methods (including output stats and timing functionality)
• Create the following search algorithms
  • DFS (both iterative and recursive implementations)
  • BFS (both iterative and recursive implementations)
  • Dijkstra
  • A*
• Each Algorithm should:
  • Accept two int values as input, representing source and destination nodes
  • Return the path from source to destination, with total cost of path
  • Perform search over both adjacency list and adjacency matrix forms of loaded graphs
• Graph sets provided have the following format.
  • Graph.txt = Connectivity of directed graph
    Each row is a csv, where first value is node and remaining values are children
    1,3,5,9 => Node 1 connects to Nodes 3,5,9
    
    Weights.txt = edge weights for directed graph
    Each row is a csv, where first two values are nodes and remaining value is weight
    1,2,3.78 => Cost of moving from Node 1 to 2 is 3.78
    
    Positions.txt = position information for each node
    Each row is a csv, where first value is node ID and reaming values are x,y, z position
    1, 3.78, -43.0,0 => Node 1 is located at position (3.78, -43.0, 0)
  • Sample graphs will be provided but will also be tested on graphs not provided during grading.
• Program should also accept command line arguments for source and destination node as ints, this feature will be used during grading to test on private data set.
  • Example: ~> Myprogram.exe src dest
• Algorithm::Stats should now output the following information in an easy to read format
  • Algorithm Name
  • Returned Path
  • Number of nodes in returned path
  • Total Cost and/or distance of path
  • Number of nodes explored
  • Execution time to find path
• In main.cpp, loop through all algorithms and data sets to collect the performance timing. Your main.cpp should look similar to

Algorithm src = new Search();
for (all Algo Search Types) src->Select(ALGOTYPE); for(all Graphs)
src->Load(input file type); src->Execute(); src->Stats();