API-PROJECT-2020-2021

The development of this project is part of the algorithms and principles of informatics course at the Polytechnic University of Milan, and as a final examination, it is necessary for the bachelor's degree in computer engineering. The course was held by prof. Matteo Pradella, Davide Martinenghi and Alessandro Barenghi in the academic year 2020-2021 and the project was automatically evaluated by a proprietary platform of the DEIB (Department of Electronics, Information, Bioengineering) of the Polytechnic University of Milan.
Final score: 30/30 cum laude

Project specification

This project establishes a ranking of a set of weighted direct graphs provided as input. The score attributed to each graph is obtained from the sum of the shortest paths between the initial node and all the other nodes.

The program receives two parameters, from the command line, separated by a space:

1. d ⁓ number of nodes of the graphs
2. k ⁓ length of the ranking

Supported commands:

• AggiungiGrafo [adjacency_matrix]

  A graph is added to those considered to draw up the ranking. The command is followed by the adjacency matrix of the graph itself, inserted one row at a time, with elements separated by commas.

• TopK

  The program prints the integer indices of the k graphs having the smallest kvalues according to the previously described metric. If there are several graphs with the same score, the first to arrive have priority.

Example of execution

  >  3,2
  >  AggiungiGrafo
  >  0,4,3
  >  0,2,0
  >  2,0,0
  >  AggiungiGrafo
  >  0,0,2
  >  7,0,4
  >  0,1,0
  >  AggiungiGrafo
  >  3,1,8
  >  0,0,6
  >  0,9,0
  >  TopK
  >> 0 1
 

Compiling the program with GCC

1. Go to the folder where the source code file is stored
2. Compile the source code file typing: gcc [program_name].c -o [executable_file_name]
3. Run the newly compiled program typing: ./[executable_file_name]

Tools used

• GCC + Ubuntu - Development environment
• Memcheck, AddressSaniter - Memory error detector
• Massif (Massif-visualizer) - Allocated memory visualizer
• Callgrind (Kcachegrind) - Execution time controller