Algorithm15/color_graph at master · Wilson1211/Algorithm15 · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include "user_cmd.h"
#include "graph.h"
#include <iostream>
#include <fstream>
#include <stdio.h>
#include "../lib/tm_usage.h"
#include <string>
#include <sstream>
using namespace std;
using namespace CommonNs;
char G[30];
extern Graph *ag;
/////////////////////////////////////////////////////////////

size_t
myStrGetTok(const string& str, string& tok, size_t pos = 0,
            const char del = ' ')
{
   size_t begin = str.find_first_not_of(del, pos);
   if (begin == string::npos) { tok = ""; return begin; }
   size_t end = str.find_first_of(del, begin);
   tok = str.substr(begin, end - begin);
   return end;
}

 Color_Graph::Color_Graph(const char * const name) : Cmd(name) {
        optMgr_.setShortDes("Color Graph");
        optMgr_.setDes("Color Graph");

        Opt *opt = new Opt(Opt::BOOL, "print usage", "");
        opt->addFlag("h");
        opt->addFlag("help");
        optMgr_.regOpt(opt);


    }
    Color_Graph::~Color_Graph(){}
    void encolor(Node* u){
        vector<Edge* >::iterator it;
        Node* node;
        int flag = 1;
        it = u->edge.begin();
        while(it!= u->edge.end()){

            node = (*it)->getNeighbor(u);
            if(flag == node->color){
                flag++;
                it = u->edge.begin();
            }else{
                it++;
            }
        }
        u->color = flag;
    }
    void Colorvisit(Node* u){
        vector<Edge*>::iterator it;
        it = (u->edge).begin();
        Node* node;
        while(it != (u->edge).end()){
            node = (*it)->getNeighbor(u);
            if(node->edge.size() == u->edge.size()){
                if(node->color == 0){
                    encolor(node);
                    Colorvisit(node);
                }
            }
            it++;
        }
        return;
    }

    bool Color_Graph::exec(int argc, char **argv){

        ag->sortNodesByDegree();
        CommonNs::TmUsage tmusg;
        CommonNs::TmStat stat;
        vector<Node *>::iterator it1;
        vector<Edge *>::iterator it2;
        int flag = 1;
        int max_color = 1;
        Node * node ;

        it1 = (ag->nodes).begin();
        while(it1 != (ag->nodes).end()){
            (*it1)->color = 0;
            it1++;
        }

        it1 = (ag->nodes).begin();
        int edgemax = (*it1)->edge.size();
        tmusg.periodStart();
        while(it1!=(ag->nodes).end()){//first check all max edges degree vertices, and color them
            //if((*it1)->edge.size() < edgemax){break;}
            if((*it1)->color != 0){it1++;continue;}
            encolor(*it1);
            Colorvisit(*it1);
            it1++;
        }
        /*flag = 1;
        it1 = (ag->nodes).begin();
        while(it1 != (ag->nodes).end()){
            if((*it1)->color ==0){
                it2 = (*it1)->edge.begin();
                while(it2 != (*it1)->edge.end()){
                    node = (*it2)->getNeighbor(*it1);

                    if(flag == node->color){
                        flag++;
                        it2 = (*it1)->edge.begin();
                    }else{
                        it2++;
                    }
                }
                if(max_color < flag){max_color = flag;}
                (*it1)->color = flag;
                flag = 1;
            }
            it1++;
        }*/
    }