Coloring.h

Go to the documentation of this file.

 
#ifndef LIMBO_ALGORITHMS_COLORING_COLORING
#define LIMBO_ALGORITHMS_COLORING_COLORING
 
#include <fstream>
#include <vector>
#include <boost/cstdint.hpp>
#include <boost/functional/hash.hpp>
#include <boost/graph/graph_concepts.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/property_map.hpp>
#include <limbo/preprocessor/AssertMsg.h>
#include <limbo/algorithms/GraphUtility.h>

namespace limbo 
{ 
namespace algorithms 
{ 
namespace coloring 
{
 
using boost::uint32_t;
using boost::int32_t;
using boost::int8_t;
 
namespace la = limbo::algorithms;

template <typename GraphType>
struct ColoringVertexLabelWriter : public la::VertexLabelWriter<GraphType>
{
    typedef GraphType graph_type;
    typedef la::VertexLabelWriter<graph_type> base_type;
    typedef typename base_type::vertex_descriptor vertex_descriptor;
    
    std::vector<int8_t> const& vColor; 

    ColoringVertexLabelWriter(graph_type const& g, std::vector<int8_t> const& vc) : base_type(g), vColor(vc) {}

    std::string label(vertex_descriptor v) const 
    {
        std::ostringstream oss; 
        oss << v << ":" << (int32_t)vColor[v];
        return oss.str();
    }
};

template <typename GraphType>
struct ColoringEdgeLabelWriter : public la::EdgeLabelWriter<GraphType>
{
    typedef GraphType graph_type;
    typedef la::EdgeLabelWriter<graph_type> base_type;
    typedef typename base_type::edge_descriptor edge_descriptor;
    typedef typename base_type::edge_weight_type edge_weight_type;
    typedef typename boost::graph_traits<graph_type>::vertex_descriptor vertex_descriptor;
 
    std::vector<int8_t> const& vColor; 

    ColoringEdgeLabelWriter(graph_type const& g, std::vector<int8_t> const& vc) : base_type(g), vColor(vc) {}

    edge_weight_type label(edge_descriptor e) const {return boost::get(boost::edge_weight, this->g, e);}
    std::string color(edge_descriptor e) const 
    {
        vertex_descriptor s = boost::source(e, this->g);
        vertex_descriptor t = boost::target(e, this->g);
        edge_weight_type w = boost::get(boost::edge_weight, this->g, e);
        bool conflict_flag = (vColor[s] >= 0 && vColor[s] == vColor[t]);
        if (w >= 0 && conflict_flag) // conflict 
            return "red";
        else return "black";
    }

    std::string style(edge_descriptor e) const {return (boost::get(boost::edge_weight, this->g, e) >= 0)? "solid" : "dashed";}
};

template <typename GraphType>
class Coloring 
{
    public:
        typedef GraphType graph_type;
        typedef typename boost::graph_traits<graph_type>::vertex_descriptor graph_vertex_type;
        typedef typename boost::graph_traits<graph_type>::edge_descriptor graph_edge_type;
        typedef typename boost::graph_traits<graph_type>::vertex_iterator vertex_iterator_type;
        typedef typename boost::graph_traits<graph_type>::edge_iterator edge_iterator_type;
        typedef typename boost::graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
        // value type for edge weight, integer or double...
        typedef typename boost::property_traits<typename boost::property_map<graph_type, boost::edge_weight_t>::const_type>::value_type edge_weight_type;
        // edge weight is used to differentiate conflict edge and stitch edge 
        // non-negative weight implies conflict edge 
        // negative weight implies stitch edge 
        typedef typename boost::property_traits<typename boost::property_map<graph_type, boost::edge_index_t>::const_type>::value_type edge_index_type;
        

        enum ColorNumType
        {
            TWO = 2,
            THREE = 3, 
            FOUR = 4
        };

        struct EdgeHashType : std::unary_function<graph_edge_type, std::size_t>
        {
            std::size_t operator()(graph_edge_type const& e) const 
            {
                std::size_t seed = 0;
                boost::hash_combine(seed, e.m_source);
                boost::hash_combine(seed, e.m_target);
                return seed;
            }
        };
 

        Coloring(graph_type const& g);
        virtual ~Coloring() {};
 
        // member functions
        virtual double operator()(); 

        virtual void color_num(ColorNumType cn) {m_color_num = cn;} 
        virtual void color_num(int8_t cn) {m_color_num = (cn == 3)? THREE : (cn == 2)? TWO : FOUR;}
        virtual ColorNumType color_num() const {return m_color_num;}

        virtual void precolor(graph_vertex_type v, int8_t c) {m_vColor[v] = c; m_has_precolored = true;}

        virtual bool has_precolored() const {return m_has_precolored;}

        virtual double stitch_weight() const {return m_stitch_weight;}
        virtual void stitch_weight(double w) {m_stitch_weight = w;}

        virtual void threads(int32_t t) {m_threads = t;}

        virtual int8_t color(graph_vertex_type v) const {return m_vColor[v];}
 
        // helper functions 
        inline virtual edge_weight_type edge_weight(graph_edge_type const& e) const {return boost::get(boost::edge_weight, m_graph, e);}

        virtual edge_weight_type calc_cost(std::vector<int8_t> const& vColor) const;

        void check_edge_weight(graph_type const& g, edge_weight_type lb, edge_weight_type ub) const;

        void print_edge_weight(graph_type const& g) const;
        
        // search vertexes in stitch relation
        // @param v vertex
        // @param stitch_relatiin_set recording for each vertex indicating the stitch relation
        // @param visited is visited in DFS
        // @param stitch_edge_num total stitch edge number in graph
        void depth_first_search_stitch(graph_vertex_type v, std::vector<int32_t>& stitch_relation_set,
            std::vector<bool>& visited,uint32_t& stitch_edge_num,int32_t stitch_index);
        // for debug 
        virtual void write_graph(std::string const& filename) const;
        virtual void write_graph(std::string const& filename, graph_type const& g, std::vector<int8_t> const& vColor) const;
    protected:
        virtual double coloring() = 0;
 
        graph_type const& m_graph; 
        std::vector<int8_t> m_vColor; 
 
    ColorNumType m_color_num; 
    double m_stitch_weight; 
    int32_t m_threads; 
    bool m_has_precolored; 
 
    // node num in big graph
    int32_t m_stitch_index;
    // edge num in big graph
    int32_t m_big_edge_num;
    std::vector<int32_t> m_stitch_relation_set;
    //a verctor of len(stitch_index*stitch_index) 
    std::vector<int32_t> m_edge_index_vector;
};
 
template <typename GraphType>
Coloring<GraphType>::Coloring(Coloring<GraphType>::graph_type const& g) 
    : m_graph(g)
    , m_vColor(boost::num_vertices(g), -1)
    , m_color_num(THREE)
    , m_stitch_weight(0.1)
    , m_threads(std::numeric_limits<int32_t>::max())
    , m_has_precolored(false)
    , m_stitch_index(0)
    , m_big_edge_num(0)
{}
 
template <typename GraphType>
double Coloring<GraphType>::operator()()
{
    double cost ;
    uint32_t stitch_edge_num = 0;
    //total wo-stitch node number
    
    //parent node in non-stitch graph index of each node in stitch graph
 
 
    //Step 1. Firstly, count the number of stitch edges and store all of the stitch relations
    vertex_iterator_type vi, vie,next;
    boost::tie(vi, vie) = vertices(m_graph);
    std::vector<bool> visited(boost::num_vertices(m_graph), false);
    m_stitch_relation_set.assign(boost::num_vertices(m_graph),-1);
    for (next = vi; vi != vie; vi = next)
    {
        ++next;
        graph_vertex_type v = *vi;
        if(visited[(int32_t)v]) continue;
        else{
            visited[(int32_t)v] = true;
            m_stitch_relation_set[(int32_t)v] = m_stitch_index;
            depth_first_search_stitch(v,m_stitch_relation_set,visited,stitch_edge_num,m_stitch_index);
            m_stitch_index ++;
        }
    }
 
 
    m_edge_index_vector.assign(m_stitch_index*m_stitch_index,-1);
    bool is_legal = true;
 
    //Step 2. Verify the feasibility of this method(no conflict should be introduced when inserting stitch)
    // Also, record the edge_index_vector
    boost::tie(vi, vie) = vertices(m_graph);
    for (next = vi; vi != vie; vi = next)
    {
        ++next;
        graph_vertex_type v = *vi;
        adjacency_iterator vi2, vie2,next2;
        boost::tie(vi2, vie2) = boost::adjacent_vertices(v, m_graph);
        for (next2 = vi2; vi2 != vie2; vi2 = next2){
            ++next2; 
            graph_vertex_type v2 = *vi2;
            std::pair<graph_edge_type, bool> e12 = boost::edge(v, v2, m_graph);
            limboAssert(e12.second);
            if(boost::get(boost::edge_weight, m_graph, e12.first) > 0){
                //if the big_edge is not considered, consider it and add 1
                if(m_edge_index_vector[m_stitch_relation_set[(int32_t)v]*m_stitch_index + m_stitch_relation_set[(int32_t)v2]] == -1){
                    m_edge_index_vector[m_stitch_relation_set[(int32_t)v]*m_stitch_index + m_stitch_relation_set[(int32_t)v2]] = m_big_edge_num;
                    m_big_edge_num++;
                }
            }
            if (boost::get(boost::edge_weight, m_graph, e12.first) > 0 && m_stitch_relation_set[(int32_t)v] == m_stitch_relation_set[(int32_t)v2])  is_legal = false;
        }
    }
    //Step 3. Assign the colors 
    std::vector<int32_t> stitch_relation_to_color(m_stitch_index,-1);
    std::vector<bool> unused_color(color_num(),true);
 
 
    if (boost::num_vertices(m_graph) <= color_num()+stitch_edge_num && is_legal) // if vertex number is no larger than color number, directly assign color
    {
        //Step 3.1: Assign pre-defined color firstly
        limboAssert(m_stitch_index <= color_num());
        for (int32_t i = 0, ie = m_vColor.size(); i != ie; ++i)
        {
            if (m_vColor[i] >= 0) // if not precolored, assign to an unused color
            {
                stitch_relation_to_color[m_stitch_relation_set[i]] = m_vColor[i];
                unused_color[m_vColor[i]] = false;
            }
        }
 
        //Step 3.2: Assign un-pre-defined color and keep colors of stitch vertexes same.
        for (int32_t i = 0, ie = m_vColor.size(); i != ie; ++i)
        {
            if (m_vColor[i] < 0) // if not precolored, assign to an unused color
            {
                if(stitch_relation_to_color[m_stitch_relation_set[i]] != -1){ 
                    m_vColor[i] = stitch_relation_to_color[m_stitch_relation_set[i]];
                    }
                else{
                    for(int32_t c= 0;c<color_num();c++){
                        if(unused_color[c]){
                            m_vColor[i] = c;
                            stitch_relation_to_color[m_stitch_relation_set[i]] = c;
                            unused_color[m_vColor[i]] = false;
                            break;
                        }
                    }
                }
                
            }
        }
        cost = calc_cost(m_vColor);
        std::cout<<"Heustical calcuted";
        limboAssert(cost == 0);
    }
    else // perform coloring algorithm 
        cost = this->coloring();
        std::cout<<"selected coloring solver calcuted"<<cost;
    // clock_t sub_comp_end = clock();
    return cost;
}
 
template <typename GraphType>
void Coloring<GraphType>::depth_first_search_stitch(graph_vertex_type v, std::vector<int32_t>& stitch_relation_set,\
std::vector<bool>& visited,uint32_t& stitch_edge_num, int32_t stitch_index)
{
    adjacency_iterator vi2, vie2,next2;
    boost::tie(vi2, vie2) = boost::adjacent_vertices(v, m_graph);
    for (next2 = vi2; vi2 != vie2; vi2 = next2){
        ++next2; 
        graph_vertex_type v2 = *vi2;
        if(visited[(int32_t)v2])    continue;
        std::pair<graph_edge_type, bool> e12 = boost::edge(v, v2, m_graph);
        limboAssert(e12.second);
        if (boost::get(boost::edge_weight, m_graph, e12.first) < 0) {
            visited[(int32_t)v2] = true;
            stitch_edge_num ++;
            stitch_relation_set[(int32_t)v2] = stitch_index;
            depth_first_search_stitch(v2,stitch_relation_set,visited,stitch_edge_num,stitch_index);
        }
    }
}
 
 
template <typename GraphType>
typename Coloring<GraphType>::edge_weight_type Coloring<GraphType>::calc_cost(std::vector<int8_t> const& vColor) const 
{
    limboAssert(vColor.size() == boost::num_vertices(this->m_graph));
    double cost = 0;
    edge_iterator_type ei, eie;
    for (boost::tie(ei, eie) = boost::edges(m_graph); ei != eie; ++ei)
    {
        edge_weight_type w = boost::get(boost::edge_weight, m_graph, *ei);
        graph_vertex_type s = boost::source(*ei, m_graph);
        graph_vertex_type t = boost::target(*ei, m_graph);
        if (s == t) // skip self edges 
            continue; 
        if (w >= 0) // conflict edge 
        {
            cost += (vColor[s] == vColor[t])*w;
        }
        else // stitch edge 
        {
            cost -= (vColor[s] != vColor[t])*w*this->stitch_weight();
        }
    }
    return cost;
}
 
template <typename GraphType>
void Coloring<GraphType>::check_edge_weight(typename Coloring<GraphType>::graph_type const& g, typename Coloring<GraphType>::edge_weight_type lb, typename Coloring<GraphType>::edge_weight_type ub) const 
{
    edge_iterator_type ei, eie;
    for (boost::tie(ei, eie) = boost::edges(g); ei != eie; ++ei)
    {
        edge_weight_type w = boost::get(boost::edge_weight, m_graph, *ei);
        limboAssertMsg(w >= lb && w <= ub, "edge weight out of range: " << w);
    }
}
 
template <typename GraphType>
void Coloring<GraphType>::print_edge_weight(typename Coloring<GraphType>::graph_type const& g) const 
{
    edge_iterator_type ei, eie;
    for (boost::tie(ei, eie) = boost::edges(g); ei != eie; ++ei)
    {
        edge_weight_type w = boost::get(boost::edge_weight, m_graph, *ei);
        limboPrint(kNONE, "%g ", (double)w);
    }
    limboPrint(kNONE, "\n");
}
 
// it seems doxygen cannot handle template functions with the same name correctly 
template <typename GraphType>
void Coloring<GraphType>::write_graph(std::string const& filename) const 
{
    write_graph(filename, m_graph, m_vColor);
}
 
template <typename GraphType>
void Coloring<GraphType>::write_graph(std::string const& filename, Coloring<GraphType>::graph_type const& g, std::vector<int8_t> const& vColor) const
{
    std::ofstream out ((filename+".gv").c_str());
    limboPrint(kINFO, "write_graph : %s\n", filename.c_str());
    la::write_graph(out, g, ColoringVertexLabelWriter<graph_type>(g, vColor), ColoringEdgeLabelWriter<graph_type>(g, vColor));
    out.close();
    la::graphviz2pdf(filename);
}
 
} // namespace coloring
} // namespace algorithms
} // namespace limbo
 
#endif