Implementation of the Navigator project.
Within this task, all graphs must meet the following requirements:
- Edge weights are only natural numbers
- There may be loops
- Weights may differ on all edges
- Only a nonzero connected graph
Implementation of the s21_graph.h library:
- The library must be developed in C++ language of C++17 standard
- The library code must be located in the src folder in the develop branch
- When writing code it is necessary to follow the Google style
- Make it as a static library (with the s21_graph.h header file)
- The library must be represented as a
Graphclass that stores information about the graph using an adjacency matrix. The dimensionality of the adjacency matrix should be set dynamically when initializing the graph (when loading it from a file) - The program must be built with Makefile which contains standard set of targets for GNU-programs: all, clean, test, s21_graph.a
*Prepare full coverage of the
Graphclass methods with unit-tests - The class
Graphmust contain at least the following public methods:LoadGraphFromFile(string filename)- loading a graph from a file in the adjacency matrix formatExportGraphToDot(string filename)- exporting a graph to a dot file (see materials)
Implementation of the s21_graph_algorithms.h library:
- The library must be developed in C++ language of C++17 standard
- The library code must be located in the src folder in the develop branch
- Make it as a static library (with the s21_graph_algorithms.h header file)
- The library must be represented as a
GraphAlgorithmsclass that stores the implementation of algorithms on graphs. The classGraphAlgorithmsitself must not know anything about the internal representation of the graph from the classGraph. To interact with graph data, the classGraphAlgorithmscan only use the public methods and properties provided by theGraphclass. - Add to the Makefile s21_graph_algorithms.a target
*Prepare full coverage of the
GraphAlgorithmsclass methods with unit-tests - The class
GraphAlgorithmsmust contain at least the following public methods:DepthFirstSearch(Graph &graph, int start_vertex)- a non-recursive depth-first search in the graph from a given vertex. The function should return an array that contains the traversed vertices in the order they were traversed. When implementing this function, you must use the self-written data structure stack, which should be previously made as a separate static libraryBreadthFirstSearch(Graph &graph, int start_vertex)- breadth-first search in the graph from a given vertex. The function should return an array that contains the traversed vertices in the order they were traversed. When implementing this function, you must use the self-written data structure queue, which should be previously made as a separate static libraryGetShortestPathBetweenVertices(Graph &graph, int vertex1, int vertex2)- searching for the shortest path between two vertices in a graph using Dijkstra's algorithm. The function accepts as input the numbers of two vertices and returns a numerical result equal to the smallest distance between themGetShortestPathsBetweenAllVertices(Graph &graph)- searching for the shortest paths between all pairs of vertices in a graph using the Floyd-Warshall algorithm. As a result, the function returns the matrix of the shortest paths between all vertices of the graphGetLeastSpanningTree(Graph &graph)- searching for the minimal spanning tree in a graph using Prim's algorithm. As a result, the function should return the adjacency matrix for the minimal spanning treeSolveTravelingSalesmanProblem(Graph &graph)- solving the traveling salesman's problem using the ant colony algorithm. You need to find the shortest path that goes through all vertices of the graph at least once, followed by a return to the original vertex. As a result, the function should return theTsmResultstructure.
In this and the following tasks, consider that the vertex numbers start from 1
Console interface
- You need to write the main program, which is a console application for testing the functionality of the implemented s21_graph.h and s21_graph_algorithms.h libraries
- The console interface must provide the following functionality:
- loading the original graph from a file
- graph traversal in breadth with output of the result to the console
- graph traversal in depth with output of the result to the console
- searching for the shortest path between any two vertices and displaying the result to the console
- searching for the shortest paths between all pairs of vertices in the graph with the output of the resulting matrix to the console
- searching for the minimal spanning tree in the graph with the output of the resulting adjacency matrix to the console
- solving the salesman problem with the output of the resulting route and its length to the console