//--------------------------------------------------

//CPPfile: breitensuche.cpp

//Beschreibung: Breitensuche auf einem Graphen mit der STL

//Autor: Tobias Schwalb & Michael Tansella, ITIV

//Erstellt: 13.07.2011

//Version: 1.0

//--------------------------------------------------



#include <iostream>

#include <stdlib.h>

#include <vector>

#include <list>

#include <queue>



using namespace std;



//Zur Speicherung der Einfährbung der Konten im Graph

enum farben{ weiss, grau, schwarz };



//Klasse zur Speicherung eines einzelnen Graphelements

//Beinhaltet den Namen und die Nachfolger (Vektor) des Elements

//Auch werden die Attribute (Farbe, Abstand, Vater) von der

//Breitensuche in der Klasse gespeichert

//Die Methoden sind zum Setzen und Lesen der privaten Attribute

//und der Konstruktor zum Initialisieren der Werte (entsprechend

//den Vorgaben der Breitensuche)

class GraphElement {

private:

    char name;

    vector<GraphElement*> nachfolger;



    farben farbe;

    int abstand;

    GraphElement* vater;



public:

    char getName() { return name; }

    void setName( char name ) { this->name = name; }

    farben getFarbe() { return farbe; }

    void setFarbe(  farben farbe ) { this->farbe = farbe; }

    int getAbstand() { return abstand; }

    void setAbstand( char abstand ) { this->abstand = abstand; }

    GraphElement* getVater() { return vater; }

    void setVater( GraphElement* vater ) { this->vater = vater; }

    void addNachfolger( GraphElement* nachfolger ) { this->nachfolger.push_back( nachfolger ); }

    vector<GraphElement*>* getNachfolger() { return &nachfolger; }

    GraphElement();

};



//Konstruktor zum Initialisieren der Werte eines Elements im Graphen

//(entsprechend den Vorgaben der Breitensuche)

GraphElement::GraphElement() {

    name = ' ';

    farbe = weiss;

    abstand = 9999;

    vater = NULL;

}



//Klasse zur Verwaltung des Graph

class Graph {

private:

    list<GraphElement*> graph;

    GraphElement* elementSuchen( char name );

public:

    void graphInitialisieren();

    GraphElement* erstesElement();

    void breitensuche( GraphElement* startelement );

    void ausgabe();

};



//Methode zum Aufbau eines Beispielgraph

//entspricht dem Graph in Übung 7 - Folie 13 mit zusätzlicher Kante E-D

void Graph::graphInitialisieren() {



    for( int i = 0; i < 8; i++ ) {

        GraphElement* neuesElement = new GraphElement;

        neuesElement->setName( 'A' + i );

        graph.push_back( neuesElement );

    }



    elementSuchen( 'A' )->addNachfolger( elementSuchen( 'B' ) );

    elementSuchen( 'A' )->addNachfolger( elementSuchen( 'C' ) );



    elementSuchen( 'C' )->addNachfolger( elementSuchen( 'B' ) );

    elementSuchen( 'C' )->addNachfolger( elementSuchen( 'E' ) );



    elementSuchen( 'D' )->addNachfolger( elementSuchen( 'A' ) );

    elementSuchen( 'D' )->addNachfolger( elementSuchen( 'C' ) );

    elementSuchen( 'D' )->addNachfolger( elementSuchen( 'G' ) );



    elementSuchen( 'E' )->addNachfolger( elementSuchen( 'D' ) );



    elementSuchen( 'F' )->addNachfolger( elementSuchen( 'B' ) );

    elementSuchen( 'F' )->addNachfolger( elementSuchen( 'G' ) );



    elementSuchen( 'G' )->addNachfolger( elementSuchen( 'E' ) );

    elementSuchen( 'G' )->addNachfolger( elementSuchen( 'F' ) );

    elementSuchen( 'G' )->addNachfolger( elementSuchen( 'H' ) );



    elementSuchen( 'H' )->addNachfolger( elementSuchen( 'E' ) );



}



//Methode zum Finden eines Graphelements entsprechend dem Namen

//wird zur einfacheren Initialisierung des Graph verwendet

GraphElement* Graph::elementSuchen( char name ) {

    for ( list<GraphElement*>::iterator iter = graph.begin(); iter != graph.end(); iter++ ) {

        if( (*iter)->getName() == name ) {

            GraphElement* test = *iter;

            return test;

        }

    }

    return NULL;

}



//Methode gibt das erste Element im Graph zurück

GraphElement* Graph::erstesElement() {

    return graph.front();

}



//Methode der Breitensuche

//--> siehe Vorlesung 10 - ab Folie 10-14

//Implementierung der Scheife einmal unter Zugriff auf die Nachfolger

//und einmal unter Verwendung eines Iterators zum Zugriff auf den Vektor

void Graph::breitensuche( GraphElement* start ) {

    queue<GraphElement*> warteschlange;



    start->setFarbe( grau );

    start->setAbstand( 0 );

    warteschlange.push( start );



    while( warteschlange.empty() != true ) {

        GraphElement* u = warteschlange.front();

        warteschlange.pop();



        // Die zwei folgenden for-Schleifen sind in der Ausführung identisch

        for( unsigned int i = 0; i < u->getNachfolger()->size(); i++ ) {

            if( u->getNachfolger()->at( i )->getFarbe() == weiss ) {

                u->getNachfolger()->at( i )->setFarbe( grau );

                u->getNachfolger()->at( i )->setAbstand( u->getAbstand() + 1 );

                u->getNachfolger()->at( i )->setVater( u );

                warteschlange.push(u->getNachfolger()->at( i ));

            }

        }



        //for(vector<GraphElement*>::iterator iter( u->getNachfolger()->begin() ); iter != u->getNachfolger()->end(); iter++ ) {

        //  if( (*iter)->getFarbe() == weiss ) {

        //    (*iter)->setFarbe( grau );

        //    (*iter)->setAbstand( u->getAbstand() );

        //    (*iter)->setVater( u );

        //    warteschlange.push( *iter );

        //  }

        //}



        u->setFarbe( schwarz );

    }

}



//Methode zur Ausgabe aller GraphElemente und deren Attribute

//Ausgabe des Namens des Element, dessen Abstand zum Startkonten und des Vaters

void Graph::ausgabe( ) {

    for( list<GraphElement*>::iterator iter = graph.begin(); iter != graph.end(); iter++ ) {

        cout << "Element " << (*iter)->getName()

             << " -> Abstand: " << (*iter)->getAbstand();

        if ((*iter)->getVater() == NULL) {

            cout << ", Vater: keiner" << endl;

        } else {

            cout << ", Vater: " << (*iter)->getVater()->getName() << endl;

        }

    }

}



//Hauptfunktion

//bilden einer Instanz des Graph und Ausführung der implementierten Methoden

int main() {

    Graph myGraph;

    myGraph.graphInitialisieren();

    myGraph.breitensuche( myGraph.erstesElement() );

    myGraph.ausgabe();

    system( "pause" );

}