pap2023v2

Programmazione Avanzata e Parallela 2023, 2° tentativo.
Progetto di Programmazione Avanzata e Parallela, UniTS, AIDA, 2023: realizzazione di una classe template per la creazione di grafi ed implementazione degli algoritmi di ottimizzazione per la ricerca del percorso di costo minimo "Dijkstra" e "Bellman-Ford".

Autori: Leo Peinkhofer, Lorenzo Di Bernardo

Documentazione:

• Graph -> Includendo Graph.hpp si includono automaticamente le librerie: "queue", "vector", "forward_list", "pair", "limits", "algorithm", "iterator"
• Graph è una classe template che accetta qualsiasi tipo primitivo come T. T rappresenta il tipo di pesi degli archi del grafo.

Attributi

(Graph non espone attributi pubblici)

• (private) std::vector < std::forward_list < std::pair < int, T > > > adj_list;
  • È la lista di adiacenza che contiene tutti gli archi che compongono il grafo.
  • Ogni vertice è univocamente identificato dall'indice del "std::vector" in cui si trova.
  • Ogni "forward_list" rappresenta gli archi in partenza dal nodo

• (private) std::vector < std::forward_list < std::pair < int, T > > > getAdjList(): Restituisce il vector di liste di archi.

Metodi pubblici:

• void addEdge(int src, int dst, T weight): Aggiunge un arco da srt a dst di peso weight alla adj_list.
• VertexIterator begin(): Restituisce un iteratore al primo elemento del vettore
• VertexIterator end(): Restituisce un iteratore all'ultimo elemento del vettore
• EdgeIterator begin(int v): Restituisce un iteratore al primo elemento della lista di adiacenza in posizione [v] del vettore
• EdgeIterator end(int v): Restituisce un iteratore dopo l'ultimo elemento della lista in posizione [v] del vettore
• int getNumVertex(): Restituisce la quantità di vertici da cui parte almeno un arco.
• T getEdgeWeight(int src, int dst) Restituisce il peso dell'arco da "src" a "dst" (se esistente)

Metodi della classe:

• Graph<T> dijkstra(Graph g, int src):
  • Esegue l'algoritmo di Dijkstra sul grafo g specificato, a partire dal nodo src.
  • Restituisce un sottografo di "g" avente soltanto i percorsi minimi da "src" a tutti i nodi da esso raggiungibili.

• Graph<T> bellmanFord(Graph g, int src):

  • Esegue l'algoritmo di Bellman-Ford sul grafo g specificato, a partire dal nodo src.
  • Restituisce un sottografo di "g" avente soltanto i percorsi minimi da "src" a tutti i nodi da esso raggiungibili.

• Varie:

  • Main.cpp: Questo file sorgente contiene, oltre ad un main(), un metodo menu() pre-configurato, al fine di verificare facilmente il funzionamento della libreria tramite CLI.

  Demo images

  • "Demo images.jpg" contiene la rappresentazione grafica dei grafi pre-impostati nel menu per facilitare il test della libreria.

CMakeLists.txt

• "CMakeLists.txt" contiene le direttive per CMake, per generare i file progetto indipendentemente dalla piattaforma. E' necessario creare una cartella "build" in cui chiamare tramite terminale il comando "cmake .." per la creazione del progetto.