main.cpp

#include <iostream>
#include <string>
using namespace std;

#include "graph.h"

// Knotentyp.
using V = string;

// Feld mit Testgraphen.
// (Für eigene Tests können beliebige weitere Graphen hinzugefügt werden.)
// Damit Graphen der Typen Graph<V> und WeightedGraph<V> im selben Feld
// gespeichert werden können, werden Zeiger auf den Basistyp Graph<V>
// gespeichert, die bei Bedarf in Zeiger auf WeightedGraph<V>
// umgewandelt werden.
Graph<V>* graphs [] = {
        // Beispiel eines ungewichteten Graphen.
        new Graph<string>({ //Beispiel
                                  { "A", { "B", "C" } },
                                  { "B", { } },
                                  { "C", { "D" } },
                                  { "D", { "E" } },
                                  { "E", {  } }
                          }),
        new Graph<string>({ //Aufgabe 9 b
                                  { "A", { "B", "H" } },
                                  { "B", {"C", "F"} },
                                  { "C", { "D", "G" } },
                                  { "D", { "E", "G", "H"} },
                                  { "E", {  } },
                                  { "F", { "A", "B", "G"} },
                                  { "G", { "H" } },
                                  { "H", { "C" } }
                          }),
        new Graph<string>({ //Aufgabe 9 a
                                  { "A", { "A", "B" } },
                                  { "B", {"A", "C", "D"} },
                                  { "C", { "B", "D" } },
                                  { "D", { "B"} },
                                  { "E", { "D", "F" } },
                                  { "F", { "E", "F"} }
                                  }),

        // Beispiel eines gewichteten Graphen.
        new WeightedGraph<string>({ //Beispiel
                                          { "A", { { "B", 2 }, { "C", 3 } } },
                                          { "B", { } },
                                          { "C", { { "C", 4 } } }
                                  }),
        new WeightedGraph<string>({ //Jonas Graph
                                          { "A", { { "B", 3 }, { "E", 1 }, { "F", 5 } } },
                                          { "B", { { "A", 3}, { "C",8}, { "D", 7 }, { "E", 2 }, { "F", 5 }} },
                                          { "C", { { "B", 8 }, { "D", 5 }, { "E", 7 } } },
                                          { "D", { { "B", 7 }, { "C", 5 }, { "E", 8 } } },
                                          { "E", { { "A", 1 }, { "B", 2 }, { "C", 7 }, { "D", 8 }, { "F", 4 } } },
                                          { "F", { { "A", 5 }, { "B", 5 }, { "E", 4 } } },
                                  }),
        new WeightedGraph<string>({ //Aufgabe 13 Djik
                                          { "A", { { "B", 10 }, { "E", 5 } } },
                                          { "B", { { "C", 1}, { "E",2} } },
                                          { "C", { { "D", 4 } } },
                                          { "D", { { "A", 7 }, { "C", 6 } } },
                                          { "E", { { "B", 3 }, { "C", 9 }, { "D", 2 } } },
                                  }),
        new WeightedGraph<string>({ //Aufgabe 12 Bellman
                                          { "A", { { "B", 6 }, { "E", 7 } } },
                                          { "B", { { "C", 5}, { "D",-4}, { "E",8} } },
                                          { "C", { { "B", -2 } } },
                                          { "D", { { "A", 2 }, { "C", 7 } } },
                                          { "E", {  { "C", -3 }, { "D", 9 } } },
                                  }),
        new WeightedGraph<string>({ //Aufgabe 11 Prim
                                          { "A", { { "A", 10 }, { "B", 4 }, {"H", 8} } },
                                          { "B", { { "A", 4}, { "C",8}, { "H",11} } },
                                          { "C", { { "B", 8 }, {"D", 7}, {"F", 4}, {"I", 2} } },
                                          { "D", { { "C", 7 }, { "E", 9 }, {"F", 14} } },
                                          { "E", {  { "D", 9 }, { "F", 10 } } },
                                          { "F", {  { "C", 4 }, { "D", 14 }, {"G", 2} } },
                                          { "G", {  { "F", 2 }, {"H", 1}, { "I", 6 } } },
                                          { "H", {  {"A", 8}, {"B", 11}, { "G", 1 }, { "I", 7 } } },
                                          { "I", {  { "C", 2 }, { "G", 6 }, {"H", 7} } },
                                  }),
        new WeightedGraph<string>({ //Aufgabe 12 Bellman mit cylce
                                          { "A", { { "B", 1 }, { "C", 1 } } },
                                          { "B", { { "C", -1} } },
                                          { "C", { { "B", -1 } } }
                                  }),
};

// Weg vom Startknoten s zum Knoten v anhand der Vorgängerinformation
// in res ausgeben.
void path (V s, V v, Pred<V>& res) {
    if (s != v && res.pred[v] != res.NIL) {
        path(s, res.pred[v], res);
        cout << " -> ";
    }
    cout << v;
}

// Hauptprogramm.
// Auswahl des Algorithmus durch das erste Kommandozeilenargument:
// bfs -> breadth first search
// dfs -> depth first search
// sort -> topological sort
// scc -> strongly connected components
// prim -> Prim
// bell -> Bellman-Ford
// dijk -> Dijkstra
// Auswahl des Testgraphen durch das zweite Kommandozeilenargument.
// (Bei den Algorithmen prim, bell und dijk muss ein gewichteter
// Graph ausgewählt werden.)
// Auswahl des Startknotens durch das optionale dritte
// Kommandozeilenargument (Standardwert ist "A").
int main (int argc, char* argv []) {
    // Kommandozeilenargumente.
    //string a = argv[1];				// Algorithmus.
    string a = argv[1];				// Algorithmus.
    Graph<V>* g = graphs[stoi( argv[2])];	// Graph.
    V s = argc > 3 ? argv[3] : "A";		// Startknoten.

    // Gewünschten Algorithmus ausführen und sein Ergebnis ausgeben.
    if (a == "bfs") {
        BFS<V> res;
        bfs(*g, s, res);
        for (V v : g->vertices()) {
            path(s, v, res);
            uint d = res.dist[v];
            if (d == res.INF) cout << " inf" << endl;
            else cout << " " << d << endl;
        }
    }
    else if (a == "dfs") {
        DFS<V> res;
        dfs(*g, res);
        for (V v : res.seq) {
            cout << v << " " << res.det[v] << " " << res.fin[v] << endl;
        }
    }
    else if (a == "sort") {
        list<V> res;
        if (topsort(*g, res)) {
            for (V v : res) cout << v << endl;
        }
        else {
            cout << "cycle" << endl;
        }
    }
    else if (a == "scc") {
        list<list<V>> res;
        scc(*g, res);
        for (list<V> c : res) {
            c.sort();
            for (V v : c) cout << v << " ";
            cout << endl;
        }
    }
    else if (a == "prim") {
        Pred<V> res;
        prim(*(WeightedGraph<V>*)g, s, res);
        for (V v : g->vertices()) {
            path(s, v, res);
            cout << endl;
        }
    }
    else if (a == "bell") {
        SP<V> res;
        if (bellmanFord(*(WeightedGraph<V>*)g, s, res)) {
            for (V v : g->vertices()) {
                path(s, v, res);
                cout << " " << res.dist[v] << endl;
            }
        }
        else {
            cout << "negative cycle" << endl;
        }
    }
    else if (a == "dijk") {
        SP<V> res;
        dijkstra(*(WeightedGraph<V>*)g, s, res);
        for (V v : g->vertices()) {
            path(s, v, res);
            cout << " " << res.dist[v] << endl;
        }
    }
    else {
        cout << "unknown algorithm: " << a << endl;
    }
}