pk17r / minimum_spanning_tree Goto Github PK

Graph implementations of Minimum Spanning Tree using Prim's Algorithm and Dijkstra's Shortest Path Algorithm

Program made as part of Coursera C++ for C Programmers Part 1 Course Homework

Compile using g++ -Wall -g *.cpp *.cc -o main

Arguments accepted: test - to use test dataset.

Program output on Windows 10 machine:

•                                                                                    *
  

•            Prim's MST and Dijkstra's Shortest Path Graph Algorithms                *
  

•                                                                                    *
  

•                - Pass a single argument 'test' to run test data                    *
  

•                                                                                    *
  

•                         Program Author: Prashant Kumar                             *
  

•                                                                                    *
  

•                                                                                    *
  

• While making this program I learned how to / use / implement / learned about:      *
  

•                                                                                    *
  

•  - usage of new and delete to allocate heap memory                                 *
  

•  - when a copy constructor is called                                               *
  

•  - implementing a priority queue                                                   *
  

•  - lambda function usage                                                           *
  

•  - usage of functions from algorithm header file like insert, erase, copy          *
  

•  - how to separate header and source files                                         *
  

•  - how to separate program into separate files for every class and structure       *
  

•  - use of static functions and variables. how to initialize static variables       *
  

•  - useing static variables to note times each constructor is being called          *
  

•  - learned about string class                                                      *
  

•  - overloading cout/ostream operator with class objects                            *
  

•  - usage of friend class                                                           *
  

•  - how to disable automatic cout flush to terminal                                 *
  

•  - calling by value and reference                                                  *
  

•  - mapping processing time taken using chrono::high_resolution_clock               *
  

•  - how to initialize a vector in multiple ways, vector insertion                   *
  

•  - how to use snprintf to format numbers                                           *
  

•  - smartly formatting thousand separators to number strings                        *
  

•  - smartly creating one resizable print box and calling it with multiple ways      *
  

•  - reading a data file using ifstream_iterator                                     *
  

•  - abstracting functions and classes                                               *
  

•  - overloading a function arg with template type - FormatSmallNumber function      *
  

•  - how to neatly print stuff to represent data in understandable way               *
  

•  - how to follow Google C++ Code Style for naming conventions on filenames,        *
  

•    variables, classes, structs, functions include statements, not having           *
  

•    namespace in header files, making header files self-sufficient                  *
  

•  - usage of pseudo code to code algorithms easily and correctly                    *
  

•  - encapsulation by making class and structure members public and private          *
  

•  - how to correctly compile multiple files using g++                               *
  

•  - difference in print time of printf and cout                                     *
  

•  - choosing unambigous variable, function and class, structure names               *
  

•                                                                                    *
  

•                                                                                    *
  

•                          *
  

• Read Data from File      *
  

•                          *
  

Reading file: cplusplus4c_homeworks_Homework3_SampleTestData_mst_data.txt Graph Size: 20 Size of edge_list: 344 First Edge: (0, 1, 17) Last Edge: (19, 18, 11) Data read from input file efficiently and heap allocated memory cleared without memory leaks

•                                        *
  

• Connectivity and Distance Matrices     *
  

•                                        *
  

Connectivity Matrix:

Distance Matrix:

•                                                                    *
  

• Dijkstras Algorithm Nearest City Paths and Distance to Origin      *
  

•                                                                    *
  

1 (origin) 2 ( 2 | 2) -> (origin) 3 ( 9 | 3) -> ( 2 | 2) -> (origin) 4 (17 | 4) -> (origin) 5 (19 | 5) -> (origin) 6 ( 1 | 5) -> (17 | 4) -> (origin) 7 (12 | 5) -> (17 | 4) -> (origin) 8 (11 | 6) -> ( 2 | 2) -> (origin) 9 ( 8 | 6) -> ( 9 | 3) -> ( 2 | 2) -> (origin) 10 (13 | 6) -> ( 9 | 3) -> ( 2 | 2) -> (origin) 11 ( 6 | 6) -> ( 1 | 5) -> (17 | 4) -> (origin) 12 ( 3 | 6) -> (12 | 5) -> (17 | 4) -> (origin) 13 (15 | 7) -> ( 2 | 2) -> (origin) 14 (18 | 7) -> ( 2 | 2) -> (origin) 15 (14 | 7) -> (11 | 6) -> ( 2 | 2) -> (origin) 16 ( 4 | 7) -> ( 8 | 6) -> ( 9 | 3) -> ( 2 | 2) -> (origin) 17 ( 5 | 7) -> ( 6 | 6) -> ( 1 | 5) -> (17 | 4) -> (origin) 18 (10 | 8) -> (17 | 4) -> (origin) 19 ( 7 | 8) -> ( 4 | 7) -> ( 8 | 6) -> ( 9 | 3) -> ( 2 | 2) -> (origin) 20 (16 | 9) -> ( 5 | 7) -> ( 6 | 6) -> ( 1 | 5) -> (17 | 4) -> (origin)

connected cities 20 | avg city distance to origin city 6.00

•                                  *
  

• Prim's Minimum Spanning Tree     *
  

•                                  *
  

Branch # ( City # | Edge Lenth ) -> MST Branch

1 (16 | 2) -> ( 5 | 1) -> (18 | 1) -> (14 | 1) -> (11 | 1) -> (12 | 3) -> ( 9 | 1) -> ( 2 | 2) -> (origin) 2 (10 | 2) -> ( 7 | 1) -> ( 4 | 1) -> ( 8 | 3) -> ( 9 ) 3 ( 6 | 1) -> ( 1 | 1) -> (17 | 1) -> (12 ) 4 (19 | 2) -> (15 | 2) -> ( 4 ) 5 ( 3 | 1) -> (12 ) 6 (13 | 3) -> ( 9 )

connected cities 20 | total mst length 30

•                                                                                      *
  

•                                     RESULTS                                          *
  

•                                                                                      *
  

•   Input data file: cplusplus4c_homeworks_Homework3_SampleTestData_mst_data.txt       *
  

•                                                                                      *
  

•                     Prims's Minimum Spanning Tree Length: 30                         *
  

•                                                                                      *
  

•              Dijkstra's Algorithm Average Distance to Origin: 6.00                   *
  

•                                                                                      *
  

•                                                                                      *
  

•                                                                                      *
  

• Input file read time                              :         16,643 microseconds      *
  

•                                                                                      *
  

• Graph Algorithms with My Priority Queue time      :          1,704 microseconds      *
  

•                                                                                      *
  

• Print things to terminal time                     :         61,206 microseconds      *
  

•                                                                                      *
  

~CityGraph() Heap allocated memory of City Graph with graphSize 20 deleted.