#include <LEDA/graphics/graphwin.h>
#include <LEDA/graph/graph.h>
#include <LEDA/core/queue.h>
#include <LEDA/core/stack.h>
#include <LEDA/core/list.h>

using namespace leda;

// Teste, ob an einer Koordinate schon ein Knoten gesetzt wurde
node position_empty(GraphWin& gw, double x, double y){
    const graph& G = gw.get_graph();
    node v;
    forall_nodes(v, G){
        point pos = gw.get_position(v);
        if (pos.xcoord() == x && pos.ycoord() == y){
            return v;
        }
    }
    return nil;
}


// Benutze anstatt level "färbung" -1 ungefärbt, 1 und 0 Färbung
bool bipartit(const graph& G, node_array<int>& color){
    node w;
    forall_nodes(w, G){
        if (color[w] == -1){
            queue<node> q;
            q.append(w);
            color[w] = 0;
            while (!q.empty()){
                node u = q.pop();
                edge e;
                // Überprüfe alle ausgehenden Kanten
                forall_out_edges(e,u){
                    node v = G.target(e);
                    if (color[v] == -1){//Nachbar noch nicht gefärbt
                        color[v] = 1 - color[u];//mit anderen Farbe färben
                        q.append(v);
                    } else if (color[v] == color[u]){
                        //Nachbar gleiche Farbe
                        return false;
                    }
                }
                // Überprüfe alle eingehenden Kanten
                forall_in_edges(e,u){
                    node v = G.source(e);
                    if (color[v] == -1){
                        color[v] = 1 - color[u];
                        q.append(v);
                    } else if (color[v] == color[u]){
                        return false;
                    }
                }   
            }
        }
    }
    return true;
}


void draw_bipartite(GraphWin& gw, node_array<int>& color){
    const graph& G = gw.get_graph();
    bool flush0 = gw.set_flush(false);
    node u;
    double x = 50;
    double y =10;
    double z = 0;
    forall_nodes(u,G){
        if (color[u] == 0){
            gw.set_color(u,blue);
        } else{
            gw.set_color(u,red);
        }
        z = x + color[u]* 200;
        while (position_empty(gw, z, y) != nil){// Knoten an leere Position setzen
            y+=40.0;
        }
        gw.set_position(u,point(z,y));
        y = 10;
    }
    gw.redraw();
    gw.set_flush(flush0);
}


// angepasste Tiefensuche um ungeraden Zyklus zu finden
// 0 unvisited, 1 visiting, 2 visited in status
void DFS(const graph& G, node s, node_array<int>& status, list<edge>& odd_cycle_edges){
    // Fall, dass ungerader Kreis gefunden wurde
    if (!odd_cycle_edges.empty()) status[s] = 2;
    if (status[s] == 2) return;
    status[s] = 1;
    edge e;
    forall_out_edges(e, s){
        node v = G.target(e);
        if ( status[v] == 0){
            DFS(G, v, status, odd_cycle_edges);
        } else if ( status[v] == 1){
            //Rückwärtskante gefunden
            odd_cycle_edges.append(e);
            node next_node = v;
            edge f;
            while (next_node != s){
                // Kreiskanten finden
                forall_out_edges(f,next_node){
                    node w = G.target(f);
                    if (status[w] == 1){
                        next_node = w;
                        odd_cycle_edges.append(f);
                        break;
                    }
                }
            }
        }
        if (!odd_cycle_edges.empty()){
            int odd = odd_cycle_edges.length() % 2;
            // Zyklus hat gerade Laenge
            if (odd == 0){
                odd_cycle_edges.clear();
            } else{
            return;
            }
        }
    }
    status[s] = 2;
}


list<edge> findOddLengthCycle(const graph& G) {
    node_array<int> status(G, 0);
    list<edge> odd_cycle_edges;
    node s;
    forall_nodes(s, G){
        if (status[s] == 0){
            DFS(G, s, status, odd_cycle_edges);
            if (!odd_cycle_edges.empty()){
                return odd_cycle_edges;
            }
        }
    }
    return list<edge>();
}


void draw_oddCycle(GraphWin& gw){
    const graph& G = gw.get_graph();
    bool flush0 = gw.set_flush(false);
    list<edge> odd_edges = findOddLengthCycle(G);
    edge e;
    forall(e, odd_edges){
        gw.set_color(e,red);
    }
    gw.redraw();
    gw.set_flush(flush0); 
}


int main() 
{
    GraphWin gw;
    graph& G = gw.get_graph();
    gw.display(window::center,window::center);
    
    while (gw.edit()){
        node_array<int> color(G,-1);
        if (bipartit(G, color)){
            gw.save_all_attributes();
            draw_bipartite(gw, color);
            gw.wait("This Graph is bipartit, Look.");
            gw.restore_all_attributes();
        }
        else{
            gw.save_all_attributes();
            draw_oddCycle(gw);
            gw.wait("This Graph is not bipartit, Look a odd cycle.");
            gw.restore_all_attributes();
        }
        
    }    
   return 0;
}