Kruskal

gistfile1.cpp

/*
 * kruskal.cpp
 *
 *  Created on: Nov 28, 2010
 *      Author: blabos
 */
#include <iostream>
#include <set>
#include <queue>
#include <stack>
#include <string>


using namespace std;


const int ord   = 25;


typedef int adj_mat_t[ord][ord];


class edge {
public:
    edge(int u, int v, int w) {
        this->u = u;
        this->v = v;
        this->w = w;
    }
    
    int u;
    int v;
    int w;
};

class edge_order {
    bool lower;
public:
    edge_order(bool lower = true) { this->lower = lower; }
    
    bool operator() (const edge& left, const edge& right) {
        
        return lower ? left.w > right.w : left.w < right.w;
    } 
};

typedef priority_queue< edge, vector<edge>, edge_order > edge_priority_queue;


#define A 0
#define B 1
#define C 2
#define D 3
#define E 4
#define F 5
#define G 6
#define H 7
#define I 8
#define J 9
#define K 10
#define L 11
#define M 12
#define N 13
#define O 14
#define P 15
#define Q 16
#define R 17
#define S 18
#define T 19
#define U 20
#define V 21
#define X 22


void print_vector(int* v, int len) {
    cout << "cores:    ";
    for (int i = 0; i < len; i++) {
        cout  << v[i] << " ";
    }
    cout << endl;
}

void print_stack(stack<int> s) {
    cout << "pilha:    ";
    while (!s.empty()) {
        cout << s.top() << " ";
        s.pop();
    }
    cout << endl;
}

void print_queue(queue<int> q) {
    cout << "fila:     ";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    cout << endl;
}

bool dfs(adj_mat_t graph, int start, int target) {
    const int white = 0;
    const int gray  = 1;
    const int black = 2;
    
    int color[ord];
    stack<int> aux_stack;
    
    for (int i = 0; i < ord; i++) {
        color[i] = white;
    }
    
    color[start] = gray;
    aux_stack.push(start);
    
    while (!aux_stack.empty()) {
        int u = aux_stack.top();
        aux_stack.pop();
        
        if (u == target) return true;
        
        for (int v = 0; v < ord; v++) {
            if (graph[u][v] > 0 && color[v] == white) {
                color[v] = gray;
                aux_stack.push(v);
            }
        }
        
        color[u] = black;
    }
    return false;
}


void clear_matrix(adj_mat_t m) {
    for (int i = 0; i < ord; i++) {
        for (int j = 0; j < ord; j++) {
            m[i][j] = 0;
        }
    }
}

void print_matrix(adj_mat_t m) {
    cout << "matriz de adjacencia:" << endl;
    
    cout.flags(ios::internal);
    cout.width(4);
    cout << " ";
    for (int i = 0; i < ord; i++) {
        cout.flags(ios::internal);
        cout.width(4);
        cout << char('A' + i);
    }
    cout << endl;
        
    for (int i = 0; i < ord; i++) {
        cout.flags(ios::internal);
        cout.width(4);
        cout << char('A' + i);
        for (int j = 0; j < ord; j++) {
            cout.flags(ios::internal);
            cout.width(4);
            cout << m[i][j];
        }
        cout << endl;
    }
    cout << endl;
}

void print_edge_queue(edge_priority_queue q) {
    cout << "Lista de Arestas:" << endl;
    while (!q.empty()) {
        cout << "[" << char(q.top().u + 'A') << "-"
                << char(q.top().v + 'A') << ": "
                << q.top().w << "]" << endl;
        q.pop();
    }
}


void init_graph(adj_mat_t graph) {
    clear_matrix(graph);
    
    graph[A][B] = 15;
    
    graph[B][A] = 15;
    graph[B][C] = 15;
    
    graph[C][B] = 15;
    graph[C][D] = 18;
    graph[C][O] = 19;
    
    graph[D][C] = 18;
    graph[D][E] = 20;
    graph[D][O] = 15;
    
    graph[E][D] = 20;
    graph[E][F] = 120;
    graph[E][G] = 70;
    graph[E][N] = 70;
    graph[E][O] = 19;
    
    graph[F][E] = 120;
    graph[F][G] = 100;
    graph[F][K] = 90;
    
    graph[G][E] = 70;
    graph[G][F] = 100;
    graph[G][H] = 95;
    
    graph[H][G] = 95;
    graph[H][I] = 120;
    graph[H][K] = 200;
    graph[H][L] = 200;
    graph[H][M] = 170;
    graph[H][N] = 150;
    
    graph[I][H] = 120;
    graph[I][J] = 60;
    
    graph[J][I] = 60;
    graph[J][K] = 250;
    
    graph[K][F] = 90;
    graph[K][H] = 200;
    graph[K][J] = 250;
    
    graph[L][H] = 200;
    graph[L][M] = 15;
    graph[L][S] = 17;
    graph[L][U] = 100;
    
    graph[M][H] = 170;
    graph[M][L] = 15;
    graph[M][N] = 10;
    graph[M][P] = 19;
    graph[M][S] = 18;
    
    graph[N][E] = 70;
    graph[N][H] = 150;
    graph[N][M] = 10;
    graph[N][O] = 17;
    graph[N][P] = 16;
    
    graph[O][C] = 19;
    graph[O][D] = 15;
    graph[O][E] = 19;
    graph[O][N] = 17;
    graph[O][P] = 16;
    graph[O][Q] = 18;
    
    graph[P][M] = 19;
    graph[P][N] = 16;
    graph[P][O] = 16;
    graph[P][Q] = 17;
    graph[P][S] = 20;
    graph[P][T] = 30;
    
    graph[Q][O] = 18;
    graph[Q][P] = 17;
    graph[Q][R] = 8;
    
    graph[R][Q] = 8;
    graph[R][T] = 10;
    
    graph[S][L] = 17;
    graph[S][M] = 18;
    graph[S][P] = 20;
    graph[S][T] = 20;
    
    graph[T][P] = 30;
    graph[T][R] = 10;
    graph[T][S] = 20;
    graph[T][U] = 8;
    
    graph[U][L] = 100;
    graph[U][T] = 8;
    graph[U][V] = 15;
    
    graph[V][U] = 15;
    graph[V][X] = 250;
    
    graph[X][V] = 250;
}


void make_priority_queue(edge_priority_queue& q, adj_mat_t graph) {
    for (int i = A; i <= X; i++) {
        for (int j = i; j <= X; j++) {
            if (i == j || graph[i][j] <= 0) continue;
            
            q.push(edge(i, j, graph[i][j]));
        }
    }
}


void kruskal(adj_mat_t graph, adj_mat_t tree) {
    set<edge, edge_order>   a;
    set<int>                c;
    edge_priority_queue     q;
    string foo;
    
    make_priority_queue(q, graph);
    
    for (int i = A; i <= X; i++) {
        c.insert(i);
    }
    
    while ((a.size() < c.size() - 1) && !q.empty()) {
        cin.get();
        
        print_edge_queue(q);
        edge e = q.top();
        q.pop();
        
        if (!dfs(tree, e.u, e.v)) {
            cout << "nao tem caminho entre "
                    << char('A' + e.u) << " e "
                    << char('A' + e.v) << ". Faz parte da solucao"
                    << endl;
            
            tree[e.u][e.v] = e.w;
            tree[e.v][e.u] = e.w;
            a.insert(e);
        }
        else {
            cout << "ja tem caminho entre "
                    << char('A' + e.u) << " e "
                    << char('A' + e.v) << ". Descartar"
                    << endl;
        }
        
        print_matrix(tree);
    }
}


int main(int argc, char** argv) {
    adj_mat_t graph, tree;
    
    
    clear_matrix(tree);
    init_graph(graph);
    print_matrix(graph);
    kruskal(graph, tree);
    print_matrix(tree);
    
    return 0;
}