ADS/P4/main.cpp

#define CATCH_CONFIG_RUNNER
#include "catch.h"
#include <iostream>
#include "EdgeWeightedGraph.h"
#include "PrimMST.h"
#include "Graphsearch.h"
#include "KruskalMST.h"
#include "DijkstraSP.h"
using namespace std;

bool isInGrapf(EdgeWeightedGraph gr, int v) {
    if (v > gr.getV())
        return false;
    return true;
}

void PrintGrapf(EdgeWeightedGraph g) {
    vector<vector<Edge> > adj = g.getAdj();

    cout << endl;
    for (int i = 0; i < g.getV(); i++) {
        cout << i << " -> ";
        for (int j = 0; j < adj[i].size(); j++) {
            cout << adj[i][j].other(i) << "[" << adj[i][j].weight() << "]";
            if (j < adj[i].size() - 1) {
                cout << " -> ";
            }
        }
        cout << endl;
    }
}


void print_digraph(EdgeWeightedDigraph graph) {
    int prev = -1;
    for (DirectedEdge e: graph.edges()) {
        if (e.from() != prev)
            cout << endl << e.from();

        cout << " -> " << e.to() << " [" << e.weight() << "] ";
        prev = e.from();
    }

    cout << endl << endl;
}

void print_mst(vector<Edge> mst) {
    vector<int> v;
    cout << endl;
    for (Edge e: mst) {
        int vorhanden = 0;
        for (int i: v) {
            if (e.either() == i)
                vorhanden++;
        }
        if (vorhanden == 0) {
            cout << e.either();
            for (Edge z: mst) {
                if (z.either() == e.either()) {
                    cout << " -> " << z.other(z.either()) << " [" << z.weight() << "] ";
                }
            }
            cout << endl;
        }
        v.push_back(e.either());
    }
}

void search(EdgeWeightedGraph gra, int type) {
    int search;
    cout << endl << "Suche nach ?> ";
    cin >> search;
    vector<bool> marked;
    vector<int> edgeTo;
    bool zsm;

    if (!isInGrapf(gra, search))
        cout << search << " ist nicht im Graphen" << endl;

    if (type == 2) {
        cout << "Tiefensuche(Depth - First - Search(DFS)) - Startknoten: " << search << endl << "Besuchsreihenfolge :"
                << endl;
        zsm = Graphsearch::DFS(gra, search, marked, edgeTo);
    } else {
        cout << "Breitensuche(Breadth - First - Search(BFS)) - Startknoten: " << search << endl <<
                "Besuchsreihenfolge :"
                << endl;
        zsm = Graphsearch::BFS(gra, search, marked, edgeTo);
    }

    cout << endl << "Marked Array:";
    for (int i = 0; i < marked.size(); i++)
        cout << endl << i << " -> " << marked[i];

    cout << endl << "Edge To Array:";
    for (int i = 0; i < edgeTo.size(); i++)
        cout << endl << i << " -> " << edgeTo[i];

    if (zsm)
        cout << endl << "Graph ist zusammenhaengend" << endl;
    else
        cout << endl << "Graph ist nicht zusammenhaengend" << endl;
}

bool get_edge_values(EdgeWeightedGraph &gra, int &from, int &to) {
    cout << endl << "Start Knoten ?>";
    cin >> from;

    if (!isInGrapf(gra, from)) {
        cout << from << " ist nicht im Graphen" << endl;
        return false;
    }

    cout << endl << "Ziel Knoten ?>";
    cin >> to;

    if (!isInGrapf(gra, to)) {
        cout << to << " ist nicht im Graphen" << endl;
        return false;
    }
    return true;
}

int main() {
    // Starte Unit-Tests
    Catch::Session().run();
    int selection;
    string graph;
    EdgeWeightedGraph gra(graph);
    EdgeWeightedDigraph wgra(graph);

    while (true) {
        if (graph == "")
            cout << endl << "Graph nicht gefunden" << endl;

        cout << endl
                << "Praktikum 4: Graphenalgorithem:" << endl
                << "1) Graph einlesen" << endl
                << "2) Tiefensuche" << endl
                << "3) Breitensuche" << endl
                << "4) MST nach Prim" << endl
                << "5) MST nach Kruskal" << endl
                << "6) Kuerzeste Wege nach Dijkstra" << endl
                << "7) Ausgabe der Adjazenzliste" << endl
                << "8) Kante löschen" << endl
                << "9) Kante hinzufügen" << endl
                << "10) Programm beenden" << endl
                << "? > ";
        cin >> selection;

        switch (selection) {
            case 1: {
                int auswahl;
                cout << endl << "Graph einlesen" << endl
                        << "1) Graph1" << endl
                        << "2) Graph2" << endl
                        << "3) Graph3" << endl
                        << "?> ";
                cin >> auswahl;

                switch (auswahl) {
                    case 1:
                        graph = "graph1.txt";
                        break;
                    case 2:
                        graph = "graph2.txt";
                        break;
                    case 3:
                        graph = "graph3.txt";
                        break;
                }
                if (graph != "") {
                    gra = EdgeWeightedGraph(graph);
                    wgra = EdgeWeightedDigraph(graph);
                    cout << endl << "Graph " << auswahl << " wurde eingelesen" << endl;
                } else
                    cout << endl << "Graph nicht gefunden" << endl;

                break;
            }
            case 2: {
                search(gra, selection);
                break;
            }
            case 3: {
                search(gra, selection);
                break;
            }
            case 4: {
                int start = 0;
                cout << endl << "Start Knoten ?> ";
                cin >> start;


                if (!isInGrapf(gra, start)) {
                    cout << start << " ist nicht im Graphen" << endl;
                    break;
                }

                PrimMST test(gra, start);
                cout << "Minimaler Spannbaum(MST) nach Prim :" << endl;
                cout << "Gewicht: " << test.weight();
                vector<Edge> mst = test.edges();

                print_mst(mst);
                break;
            }
            case 5: {
                KruskalMST test(gra);

                cout << "Minimaler Spannbaum(MST) nach Kruskal :" << endl;
                cout << "Gewicht: " << test.weight();
                vector<Edge> mst = test.edges();

                print_mst(mst);
                break;
            }
            case 6: {
                int start, ziel = 0;

                cout << endl << "Start Knoten ?> ";
                cin >> start;

                if (!isInGrapf(gra, start)) {
                    cout << start << " ist nicht im Graphen" << endl;
                    continue;
                }
                cout << endl << "Ziel Knoten ?>";
                cin >> ziel;

                if (!isInGrapf(gra, ziel)) {
                    cout << ziel << " ist nicht im Graphen" << endl;
                    continue;
                }

                DijkstraSP dijkstra(wgra, start);
                vector<DirectedEdge> path = dijkstra.pathTo(ziel);
                print_digraph(wgra);
                double kosten = 0.0;
                string out = "";
                cout << "Pfad: ";
                for (DirectedEdge de: path) {
                    kosten += de.weight();
                    out += to_string(de.from()) + " [" + to_string(de.weight()) + "] " + " -> ";
                }

                if (kosten == 0.0) {
                    cout << "Kein Weg gefunden" << endl;
                    continue;
                }

                cout << out;
                cout << path[path.size() - 1].to() << endl;
                cout << "Kosten: " << kosten << endl;
                break;
            }
            case 7: {
                PrintGrapf(gra);
                break;
            }
            case 8: {
                int from, to;
                if (get_edge_values(gra, from, to)) {
                    Edge n(from, to, 0);
                    DirectedEdge m(from, to, 0);
                    gra.del_Edge(n);
                    wgra.del_Edge(m);
                    cout << "Die Kante (" << from << " ; " << to << ") wurde gelöscht." << endl;

                    break;
                }
                break;
            }
            case 9: {
                int from, to, weight;
                bool a = get_edge_values(gra, from, to);

                cout << endl << "Gewicht ?>";
                cin >> weight;

                if (a) {
                    Edge n(from, to, weight);
                    DirectedEdge m(from, to, weight);
                    gra.add(n);
                    wgra.add(m);

                    cout << "Die Kante (" << from << " ; " << to << " ; " << weight << ") wurde hinzugefügt." << endl;
                }
                break;
            }
            case 10: {
            }
        }
    }
    return 0;
}