13 #ifndef LIMBO_ALGORITHMS_GRAPHSIMPLIFICATION_H
14 #define LIMBO_ALGORITHMS_GRAPHSIMPLIFICATION_H
25 #include <boost/graph/graph_concepts.hpp>
26 #include <boost/graph/graph_utility.hpp>
27 #include <boost/graph/adjacency_list.hpp>
28 #include <boost/graph/undirected_graph.hpp>
29 #include <boost/property_map/property_map.hpp>
44 namespace la = ::limbo::algorithms;
50 template <
typename GraphType>
55 typedef GraphType graph_type;
56 typedef typename boost::graph_traits<graph_type>::vertex_descriptor graph_vertex_type;
57 typedef typename boost::graph_traits<graph_type>::edge_descriptor graph_edge_type;
58 typedef typename boost::graph_traits<graph_type>::vertex_iterator vertex_iterator;
59 typedef typename boost::graph_traits<graph_type>::adjacency_iterator adjacency_iterator;
60 typedef typename boost::graph_traits<graph_type>::edge_iterator edge_iterator;
97 graph_vertex_type v = 0;
98 for (
typename std::vector<graph_vertex_type>::iterator it =
m_vParent.begin(), ite =
m_vParent.end(); it != ite; ++it, ++v)
101 for (
typename std::vector<std::vector<graph_vertex_type> >::iterator it =
m_vChildren.begin(), ite =
m_vChildren.end(); it != ite; ++it, ++v)
103 #ifdef DEBUG_GRAPHSIMPLIFICATION
115 template <
typename Iterator>
119 #ifdef DEBUG_GRAPHSIMPLIFICATION
134 std::pair<graph_type, std::map<graph_vertex_type, graph_vertex_type> >
simplified_graph()
const;
155 void recover(std::vector<int8_t>& vColorFlat, std::vector<std::vector<int8_t> >& mColor, std::vector<std::vector<graph_vertex_type> >
const& mSimpl2Orig)
const;
183 void recover_biconnected_component(std::vector<std::vector<int8_t> >& mColor, std::vector<std::vector<graph_vertex_type> >
const& mSimpl2Orig)
const;
208 std::vector<uint32_t>& vLow, std::vector<graph_vertex_type>& vParent, uint32_t& visit_time,
209 std::stack<std::pair<graph_vertex_type, graph_vertex_type> >& vEdge,
210 std::list<std::pair<graph_vertex_type, std::set<graph_vertex_type> > >& mCompVertex)
const;
216 graph_vertex_type
parent(graph_vertex_type v)
const
218 #ifdef DEBUG_GRAPHSIMPLIFICATION
229 graph_vertex_type
parent(uint32_t v, std::vector<uint32_t>
const& vParent)
const
231 while (v != vParent.at(v))
240 graph_vertex_type vp1 = this->
parent(v1);
241 graph_vertex_type vp2 = this->
parent(v2);
242 std::vector<graph_vertex_type>
const& vChildren1 =
m_vChildren.at(vp1);
243 std::vector<graph_vertex_type>
const& vChildren2 =
m_vChildren.at(vp2);
244 for (
typename std::vector<graph_vertex_type>::const_iterator vic1 = vChildren1.begin(); vic1 != vChildren1.end(); ++vic1)
245 for (
typename std::vector<graph_vertex_type>::const_iterator vic2 = vChildren2.begin(); vic2 != vChildren2.end(); ++vic2)
247 std::pair<graph_edge_type, bool> e12 = boost::edge(*vic1, *vic2,
m_graph);
249 if (e12.second && boost::get(boost::edge_weight,
m_graph, e12.first) >= 0)
return true;
258 graph_vertex_type vp1 = this->
parent(v1);
259 graph_vertex_type vp2 = this->
parent(v2);
260 std::vector<graph_vertex_type>
const& vChildren1 =
m_vChildren.at(vp1);
261 std::vector<graph_vertex_type>
const& vChildren2 =
m_vChildren.at(vp2);
262 for (
typename std::vector<graph_vertex_type>::const_iterator vic1 = vChildren1.begin(); vic1 != vChildren1.end(); ++vic1)
263 for (
typename std::vector<graph_vertex_type>::const_iterator vic2 = vChildren2.begin(); vic2 != vChildren2.end(); ++vic2)
265 std::pair<graph_edge_type, bool> e12 = boost::edge(*vic1, *vic2,
m_graph);
267 if (e12.second && boost::get(boost::edge_weight,
m_graph, e12.first) < 0)
return true;
274 std::pair<graph_edge_type, bool>
connected_edge(graph_vertex_type v1, graph_vertex_type v2)
const
276 graph_vertex_type vp1 = this->
parent(v1);
277 graph_vertex_type vp2 = this->
parent(v2);
278 std::vector<graph_vertex_type>
const& vChildren1 =
m_vChildren.at(vp1);
279 std::vector<graph_vertex_type>
const& vChildren2 =
m_vChildren.at(vp2);
280 for (
typename std::vector<graph_vertex_type>::const_iterator vic1 = vChildren1.begin(); vic1 != vChildren1.end(); ++vic1)
281 for (
typename std::vector<graph_vertex_type>::const_iterator vic2 = vChildren2.begin(); vic2 != vChildren2.end(); ++vic2)
283 std::pair<graph_edge_type, bool> e12 = boost::edge(*vic1, *vic2,
m_graph);
284 if (e12.second)
return e12;
286 return std::make_pair(graph_edge_type(),
false);
293 #ifdef DEBUG_GRAPHSIMPLIFICATION
295 if (!flag) assert(v1 ==
m_vParent.at(v1));
302 bool good(graph_vertex_type v1)
const
361 template <
typename GraphType>
362 std::pair<typename GraphSimplification<GraphType>::graph_type, std::map<typename GraphSimplification<GraphType>::graph_vertex_type,
typename GraphSimplification<GraphType>::graph_vertex_type> >
365 size_t vertex_cnt = 0;
366 std::map<graph_vertex_type, graph_vertex_type> mG2MG;
367 std::map<graph_vertex_type, graph_vertex_type> mMG2G;
368 vertex_iterator vi1, vie1;
369 for (boost::tie(vi1, vie1) = boost::vertices(m_graph); vi1 != vie1; ++vi1)
371 graph_vertex_type v1 = *vi1;
374 mG2MG[*vi1] = vertex_cnt;
375 mMG2G[vertex_cnt] = v1;
379 graph_type mg (vertex_cnt);
381 edge_iterator ei, eie;
382 for (boost::tie(ei, eie) = boost::edges(m_graph); ei != eie; ++ei)
384 graph_edge_type e = *ei;
385 graph_vertex_type s = boost::source(e, m_graph);
386 graph_vertex_type t = boost::target(e, m_graph);
388 if (this->hidden(s) || this->hidden(t))
continue;
390 graph_vertex_type sp = this->parent(s);
391 graph_vertex_type tp = this->parent(t);
393 #ifdef DEBUG_GRAPHSIMPLIFICATION
394 assert(mG2MG.count(sp));
395 assert(mG2MG.count(tp));
397 graph_vertex_type msp = mG2MG[sp];
398 graph_vertex_type mtp = mG2MG[tp];
399 std::pair<graph_edge_type, bool> emg = boost::edge(msp, mtp, mg);
402 emg = boost::add_edge(msp, mtp, mg);
404 boost::put(boost::edge_weight, mg, emg.first, boost::get(boost::edge_weight, m_graph, e));
412 boost::edge_weight, mg, emg.first,
413 boost::get(boost::edge_weight, mg, emg.first) + boost::get(boost::edge_weight, m_graph, e)
418 return std::make_pair(mg, mMG2G);
421 template <
typename GraphType>
423 std::vector<
typename GraphSimplification<GraphType>::graph_vertex_type>& vSimpl2Orig)
const
425 if (comp_id >= m_mCompVertex.size())
return false;
427 std::vector<graph_vertex_type>
const& vCompVertex = m_mCompVertex[comp_id];
429 graph_type sg (vCompVertex.size());
430 std::map<graph_vertex_type, graph_vertex_type> mOrig2Simpl;
431 vSimpl2Orig.assign(vCompVertex.begin(), vCompVertex.end());
432 for (uint32_t i = 0; i != vCompVertex.size(); ++i)
433 mOrig2Simpl[vCompVertex[i]] = i;
434 #ifdef DEBUG_GRAPHSIMPLIFICATION
435 std::cout <<
"Comp " << comp_id <<
": ";
436 for (uint32_t i = 0; i != vCompVertex.size(); ++i)
437 std::cout << vCompVertex[i] <<
" ";
438 std::cout << std::endl;
441 for (
typename std::vector<graph_vertex_type>::const_iterator vi = vCompVertex.begin(); vi != vCompVertex.end(); ++vi)
443 graph_vertex_type v = *vi;
444 graph_vertex_type vsg = mOrig2Simpl[v];
445 assert(this->good(v));
446 bool ap = this->articulation_point(v);
447 std::vector<graph_vertex_type>
const& vChildren = m_vChildren.at(v);
448 for (
typename std::vector<graph_vertex_type>::const_iterator vic = vChildren.begin(); vic != vChildren.end(); ++vic)
450 graph_vertex_type vc = *vic;
451 typename boost::graph_traits<graph_type>::adjacency_iterator ui, uie;
452 for (boost::tie(ui, uie) = boost::adjacent_vertices(vc, m_graph); ui != uie; ++ui)
454 graph_vertex_type uc = *ui;
456 if (this->hidden(uc))
continue;
457 graph_vertex_type u = this->parent(uc);
459 if (!this->good(u))
continue;
460 else if (v >= u)
continue;
461 else if (ap && !mOrig2Simpl.count(u))
continue;
465 std::pair<graph_edge_type, bool> e = boost::edge(vc, uc, m_graph);
469 graph_vertex_type usg = mOrig2Simpl[u];
470 assert_msg(usg != vsg, u <<
"==" << v <<
": " << usg <<
" == " << vsg);
472 std::pair<graph_edge_type, bool> esg = boost::edge(vsg, usg, sg);
475 esg = boost::add_edge(vsg, usg, sg);
477 boost::put(boost::edge_weight, sg, esg.first, boost::get(boost::edge_weight, m_graph, e.first));
485 boost::edge_weight, sg, esg.first,
486 boost::get(boost::edge_weight, sg, esg.first) + boost::get(boost::edge_weight, m_graph, e.first)
496 template <
typename GraphType>
500 if (this->has_precolored())
501 m_level = m_level & (~MERGE_SUBK4) & (~BICONNECTED_COMPONENT);
503 bool reconstruct =
true;
505 if (m_level & HIDE_SMALL_DEGREE)
507 this->hide_small_degree();
510 if (m_level & MERGE_SUBK4)
514 if (m_level & BICONNECTED_COMPONENT)
516 this->biconnected_component();
522 m_mCompVertex.assign(1, std::vector<graph_vertex_type>());
523 for (graph_vertex_type v = 0, ve = boost::num_vertices(m_graph); v != ve; ++v)
525 m_mCompVertex[0].push_back(v);
529 template <
typename GraphType>
533 if (m_level & BICONNECTED_COMPONENT)
534 this->recover_biconnected_component(mColor, mSimpl2Orig);
537 for (uint32_t sub_comp_id = 0; sub_comp_id < mColor.size(); ++sub_comp_id)
539 std::vector<int8_t>
const& vColor = mColor[sub_comp_id];
540 std::vector<graph_vertex_type>
const& vSimpl2Orig = mSimpl2Orig[sub_comp_id];
541 for (uint32_t subv = 0; subv < vColor.size(); ++subv)
543 graph_vertex_type v = vSimpl2Orig[subv];
544 if (vColorFlat[v] >= 0)
545 assert(vColorFlat[v] == vColor[subv]);
547 vColorFlat[v] = vColor[subv];
551 if (m_level & MERGE_SUBK4)
553 this->recover_merge_subK4(vColorFlat);
555 if (m_level & HIDE_SMALL_DEGREE)
568 template <
typename GraphType>
580 vertex_iterator vi1, vie1;
581 for (boost::tie(vi1, vie1) = boost::vertices(m_graph); vi1 != vie1; ++vi1)
583 graph_vertex_type v1 = *vi1;
585 if (!this->good(v1))
continue;
587 std::vector<graph_vertex_type>
const& vChildren1 = m_vChildren.at(v1);
588 for (
typename std::vector<graph_vertex_type>::const_iterator vic1 = vChildren1.begin(); vic1 != vChildren1.end(); ++vic1)
590 #ifdef DEBUG_GRAPHSIMPLIFICATION
591 assert(vic1-vChildren1.begin() >= 0);
593 graph_vertex_type vc1 = *vic1;
594 adjacency_iterator vi2, vie2;
595 for (boost::tie(vi2, vie2) = boost::adjacent_vertices(vc1, m_graph); vi2 != vie2; ++vi2)
598 if (this->hidden(*vi2))
continue;
600 std::pair<graph_edge_type, bool> e12 = boost::edge(vc1, *vi2, m_graph);
602 if (boost::get(boost::edge_weight, m_graph, e12.first) < 0)
continue;
604 graph_vertex_type v2 = this->parent(*vi2);
606 std::vector<graph_vertex_type>
const& vChildren2 = m_vChildren.at(v2);
607 for (
typename std::vector<graph_vertex_type>::const_iterator vic2 = vChildren2.begin(); vic2 != vChildren2.end(); ++vic2)
609 graph_vertex_type vc2 = *vic2;
610 adjacency_iterator vi3, vie3;
611 for (boost::tie(vi3, vie3) = boost::adjacent_vertices(vc2, m_graph); vi3 != vie3; ++vi3)
614 if (this->hidden(*vi3))
continue;
616 std::pair<graph_edge_type, bool> e23 = boost::edge(vc2, *vi3, m_graph);
618 if (boost::get(boost::edge_weight, m_graph, e23.first) < 0)
continue;
620 graph_vertex_type v3 = this->parent(*vi3);
622 if (v3 == v1)
continue;
624 if (!this->connected_conflict(v1, v3))
continue;
627 std::vector<graph_vertex_type>
const& vChildren3 = m_vChildren.at(v3);
628 for (
typename std::vector<graph_vertex_type>::const_iterator vic3 = vChildren3.begin(); vic3 != vChildren3.end(); ++vic3)
630 graph_vertex_type vc3 = *vic3;
631 adjacency_iterator vi4, vie4;
632 for (boost::tie(vi4, vie4) = boost::adjacent_vertices(vc3, m_graph); vi4 != vie4; ++vi4)
635 if (this->hidden(*vi4) || this->precolored(*vi4))
continue;
637 std::pair<graph_edge_type, bool> e34 = boost::edge(vc3, *vi4, m_graph);
639 if (boost::get(boost::edge_weight, m_graph, e34.first) < 0)
continue;
641 graph_vertex_type v4 = this->parent(*vi4);
643 if (v4 == v1 || v4 == v2 || this->precolored(v4))
continue;
646 if (!this->connected_conflict(v2, v4) || this->connected_conflict(v1, v4))
continue;
648 if (!this->check_max_merge_level(m_vChildren[v1].size()+m_vChildren[v4].size()))
continue;
650 m_vStatus[v4] = MERGED;
651 m_vChildren[v1].insert(m_vChildren[v1].end(), m_vChildren[v4].begin(), m_vChildren[v4].end());
652 m_vChildren[v4].resize(0);
655 #ifdef DEBUG_GRAPHSIMPLIFICATION
656 assert(m_vStatus[v1] == GOOD);
661 if (merge_flag)
break;
663 if (merge_flag)
break;
665 if (merge_flag)
break;
667 if (merge_flag)
break;
669 if (merge_flag)
break;
671 if (merge_flag)
break;
673 }
while (merge_flag);
677 template <
typename GraphType>
688 vertex_iterator vi1, vie1;
689 for (boost::tie(vi1, vie1) = boost::vertices(m_graph); vi1 != vie1; ++vi1)
691 graph_vertex_type v1 = *vi1;
693 if (!this->good(v1) || this->precolored(v1))
continue;
694 size_t conflict_degree = 0;
696 std::vector<graph_vertex_type>
const& vChildren1 = m_vChildren.at(v1);
697 for (
typename std::vector<graph_vertex_type>::const_iterator vic1 = vChildren1.begin(); vic1 != vChildren1.end(); ++vic1)
699 #ifdef DEBUG_GRAPHSIMPLIFICATION
700 assert(vic1-vChildren1.begin() >= 0);
702 graph_vertex_type vc1 = *vic1;
703 adjacency_iterator vi2, vie2;
704 for (boost::tie(vi2, vie2) = boost::adjacent_vertices(vc1, m_graph); vi2 != vie2; ++vi2)
707 if (this->hidden(*vi2))
continue;
709 std::pair<graph_edge_type, bool> e12 = boost::edge(vc1, *vi2, m_graph);
711 if (boost::get(boost::edge_weight, m_graph, e12.first) < 0)
continue;
713 conflict_degree += 1;
716 if (conflict_degree < m_color_num)
719 m_vHiddenVertex.push(v1);
724 std::vector<graph_vertex_type>
const& vChildren1 = m_vChildren.at(v1);
725 for (
typename std::vector<graph_vertex_type>::const_iterator vic1 = vChildren1.begin(); vic1 != vChildren1.end(); ++vic1)
726 m_vStatus[*vic1] = HIDDEN;
727 #ifdef DEBUG_GRAPHSIMPLIFICATION
728 std::cout <<
"std::stack +" << v1 << std::endl;
729 assert(m_vStatus[v1] == HIDDEN);
736 this->connected_component();
741 template <
typename GraphType>
744 uint32_t vertex_num = boost::num_vertices(m_graph);
745 std::stack<graph_vertex_type> vStack;
747 std::deque<bool> vVisited (vertex_num,
false);
748 std::vector<graph_vertex_type> vParent (vertex_num);
749 std::vector<uint32_t> vChildrenCnt (vertex_num, 0);
754 std::deque<bool> vArtiPoint (vertex_num,
false);
755 std::stack<std::pair<graph_vertex_type, graph_vertex_type> > vEdge;
756 std::list<std::pair<graph_vertex_type, std::set<graph_vertex_type> > > mCompVertex;
757 uint32_t visit_time = 0;
760 vertex_iterator vi, vie;
761 for (boost::tie(vi, vie) = boost::vertices(m_graph); vi != vie; ++vi)
764 for (boost::tie(vi, vie) = boost::vertices(m_graph); vi != vie; ++vi)
766 graph_vertex_type source = *vi;
767 if (!vVisited[source])
769 biconnected_component_recursion(source, vVisited, vDisc, vLow, vParent, visit_time, vEdge, mCompVertex);
777 mCompVertex.back().second.insert(vEdge.top().first);
778 mCompVertex.back().second.insert(vEdge.top().second);
780 }
while (!vEdge.empty());
784 uint32_t comp_id = 0;
786 m_mArtiPoint.clear();
787 m_mCompVertex.assign(mCompVertex.size(), std::vector<graph_vertex_type>());
788 for (
typename std::list<std::pair<graph_vertex_type, std::set<graph_vertex_type> > >::const_iterator it = mCompVertex.begin(); it != mCompVertex.end(); ++it, ++comp_id)
790 graph_vertex_type vap = it->first;
791 std::set<graph_vertex_type>
const& sComp = it->second;
793 m_mArtiPoint.insert(std::make_pair(vap, std::set<uint32_t>()));
794 m_mCompVertex[comp_id].assign(sComp.begin(), sComp.end());
797 for (
typename std::list<std::pair<graph_vertex_type, std::set<graph_vertex_type> > >::const_iterator it = mCompVertex.begin(); it != mCompVertex.end(); ++it, ++comp_id)
800 std::set<graph_vertex_type>
const& sComp = it->second;
801 for (
typename std::set<graph_vertex_type>::const_iterator itc = sComp.begin(); itc != sComp.end(); ++itc)
803 graph_vertex_type v = *itc;
804 if (this->articulation_point(v))
805 m_mArtiPoint[v].insert(comp_id);
808 #ifdef DEBUG_GRAPHSIMPLIFICATION
810 for (
typename std::list<std::pair<graph_vertex_type, std::set<graph_vertex_type> > >::const_iterator it = mCompVertex.begin(); it != mCompVertex.end(); ++it, ++comp_id)
812 graph_vertex_type vap = it->first;
813 std::set<graph_vertex_type>
const& sComp = it->second;
814 std::cout <<
"+ articulation point " << vap <<
" --> comp " << comp_id <<
": ";
815 for (
typename std::set<graph_vertex_type>::const_iterator itc = sComp.begin(); itc != sComp.end(); ++itc)
816 std::cout << *itc <<
" ";
817 std::cout << std::endl;
819 for (
typename std::map<graph_vertex_type, std::set<uint32_t> >::const_iterator it = m_mArtiPoint.begin(); it != m_mArtiPoint.end(); ++it)
821 graph_vertex_type vap = it->first;
822 std::set<uint32_t>
const& sComp = it->second;
823 std::cout <<
"ap " << vap <<
": ";
824 for (
typename std::set<uint32_t>::const_iterator itc = sComp.begin(); itc != sComp.end(); ++itc)
825 std::cout << *itc <<
" ";
826 std::cout << std::endl;
831 template <
typename GraphType>
833 std::vector<uint32_t>& vLow, std::vector<graph_vertex_type>& vParent, uint32_t& visit_time,
834 std::stack<std::pair<graph_vertex_type, graph_vertex_type> >& vEdge,
835 std::list<std::pair<graph_vertex_type, std::set<graph_vertex_type> > >& mCompVertex)
const
838 uint32_t children = 0;
844 vDisc[v] = vLow[v] = visit_time++;
847 if (!this->good(v))
return;
851 std::vector<graph_vertex_type>
const& vChildren = m_vChildren.at(v);
852 for (
typename std::vector<graph_vertex_type>::const_iterator vic = vChildren.begin(); vic != vChildren.end(); ++vic)
854 graph_vertex_type vc = *vic;
856 if (this->hidden(vc))
continue;
858 adjacency_iterator ui, uie;
859 for (boost::tie(ui, uie) = boost::adjacent_vertices(vc, m_graph); ui != uie; ++ui)
861 graph_vertex_type uc = *ui;
863 if (this->hidden(uc))
continue;
866 graph_vertex_type u = this->parent(uc);
867 assert(this->good(u));
876 biconnected_component_recursion(u, vVisited, vDisc, vLow, vParent, visit_time, vEdge, mCompVertex);
880 vLow[v] =
std::min(vLow[v], vLow[u]);
887 if ((vParent[v] == v && children > 1)
888 || (vParent[v] != v && vLow[u] >= vDisc[v]))
890 mCompVertex.push_back(std::make_pair(v, std::set<graph_vertex_type>()));
891 while (vEdge.top().first !=
std::min(v, u) || vEdge.top().second !=
std::max(v, u))
893 mCompVertex.back().second.insert(vEdge.top().first);
894 mCompVertex.back().second.insert(vEdge.top().second);
897 mCompVertex.back().second.insert(vEdge.top().first);
898 mCompVertex.back().second.insert(vEdge.top().second);
903 else if (u != vParent[v] && vDisc[u] < vLow[v])
905 vLow[v] =
std::min(vLow[v], vDisc[u]);
914 mCompVertex.back().second.insert(v);
918 template <
typename GraphType>
924 uint32_t vertex_num = boost::num_vertices(m_graph);
925 std::stack<graph_vertex_type> vStack;
927 std::deque<bool> vVisited (vertex_num,
false);
928 uint32_t comp_id = 0;
932 vertex_iterator vi, vie;
933 for (boost::tie(vi, vie) = boost::vertices(m_graph); vi != vie; ++vi)
935 graph_vertex_type source = *vi;
936 if (this->hidden(source))
continue;
937 if (this->articulation_point(source))
continue;
939 if (vVisited[source])
continue;
941 vVisited[source] =
true;
942 while (!vStack.empty())
944 graph_vertex_type v = vStack.top();
946 #ifdef DEBUG_GRAPHSIMPLIFICATION
947 std::cout << v <<
" ";
950 vComponent[v] = comp_id;
953 if (this->articulation_point(v))
955 m_mArtiPoint[v].insert(comp_id);
960 adjacency_iterator ui, uie;
961 for (boost::tie(ui, uie) = boost::adjacent_vertices(v, m_graph); ui != uie; ++ui)
963 graph_vertex_type u = *ui;
964 if (this->hidden(u))
continue;
966 #ifdef DEBUG_GRAPHSIMPLIFICATION
967 std::pair<graph_edge_type, bool> e = boost::edge(u, v, m_graph);
980 #ifdef DEBUG_GRAPHSIMPLIFICATION
981 std::cout << std::endl;
985 for (
typename std::map<graph_vertex_type, std::set<uint32_t> >::const_iterator vapi = m_mArtiPoint.begin(); vapi != m_mArtiPoint.end(); ++vapi)
987 graph_vertex_type v = vapi->first;
990 adjacency_iterator ui, uie;
991 for (boost::tie(ui, uie) = boost::adjacent_vertices(v, m_graph); ui != uie; ++ui)
993 graph_vertex_type u = *ui;
994 if (this->hidden(u))
continue;
995 if (!vVisited[u] && this->articulation_point(u))
997 m_mArtiPoint[v].insert(comp_id);
998 m_mArtiPoint[u].insert(comp_id);
1000 #ifdef DEBUG_GRAPHSIMPLIFICATION
1001 std::cout <<
"detect " << v <<
", " << u <<
" ==> comp " << comp_id << std::endl;
1012 m_mCompVertex.assign(comp_id, std::vector<graph_vertex_type>());
1013 for (boost::tie(vi, vie) = boost::vertices(m_graph); vi != vie; ++vi)
1015 graph_vertex_type v = *vi;
1018 if (this->good(v) && !this->articulation_point(v))
1019 m_mCompVertex[vComponent[v]].push_back(v);
1021 for (
typename std::map<graph_vertex_type, std::set<uint32_t> >::const_iterator vapi = m_mArtiPoint.begin(); vapi != m_mArtiPoint.end(); ++vapi)
1023 graph_vertex_type vap = vapi->first;
1024 std::set<uint32_t>
const& sComp = vapi->second;
1025 for (
typename std::set<uint32_t>::const_iterator itc = sComp.begin(); itc != sComp.end(); ++itc)
1026 m_mCompVertex[*itc].push_back(vap);
1032 template <
typename GraphType>
1035 vertex_iterator vi, vie;
1036 for (boost::tie(vi, vie) = boost::vertices(m_graph); vi != vie; ++vi)
1038 graph_vertex_type v = *vi;
1041 assert(vColor[v] >= 0 && vColor[v] < (int8_t)this->m_color_num);
1042 for (uint32_t j = 0; j != m_vChildren[v].size(); ++j)
1044 graph_vertex_type u = m_vChildren[v][j];
1046 vColor[u] = vColor[v];
1053 template <
typename GraphType>
1061 std::vector<std::map<graph_vertex_type, graph_vertex_type> > mApOrig2Simpl (mSimpl2Orig.size());
1062 for (uint32_t i = 0; i < mSimpl2Orig.size(); ++i)
1064 std::vector<graph_vertex_type>
const& vSimpl2Orig = mSimpl2Orig[i];
1065 std::map<graph_vertex_type, graph_vertex_type>& vApOrig2Simpl = mApOrig2Simpl[i];
1067 for (uint32_t j = 0; j < vSimpl2Orig.size(); ++j)
1069 if (m_mArtiPoint.count(vSimpl2Orig[j]))
1070 vApOrig2Simpl[vSimpl2Orig[j]] = j;
1074 std::vector<int32_t> vRotation (m_mCompVertex.size(), 0);
1075 std::deque<bool> vVisited (m_mCompVertex.size(),
false);
1076 std::vector<std::set<graph_vertex_type> > vCompAp (m_mCompVertex.size());
1078 for (
typename std::map<graph_vertex_type, std::set<uint32_t> >::const_iterator vapi = m_mArtiPoint.begin(); vapi != m_mArtiPoint.end(); ++vapi)
1080 graph_vertex_type vap = vapi->first;
1081 std::set<uint32_t>
const& sComp = vapi->second;
1082 for (
typename std::set<uint32_t>::const_iterator itc = sComp.begin(); itc != sComp.end(); ++itc)
1084 uint32_t comp = *itc;
1085 vCompAp[comp].insert(vap);
1091 for (uint32_t comp_id = 0; comp_id < vCompAp.size(); ++comp_id)
1093 if (!vVisited[comp_id])
1095 std::stack<uint32_t> vStack;
1096 vStack.push(comp_id);
1097 vVisited[comp_id] =
true;
1098 while (!vStack.empty())
1100 uint32_t c = vStack.top();
1103 for (
typename std::set<graph_vertex_type>::const_iterator vapi = vCompAp[c].begin(); vapi != vCompAp[c].end(); ++vapi)
1105 graph_vertex_type vap = *vapi;
1106 std::set<uint32_t>
const& sComp = m_mArtiPoint.at(vap);
1108 for (
typename std::set<uint32_t>::const_iterator itcc = sComp.begin(); itcc != sComp.end(); ++itcc)
1110 uint32_t cc = *itcc;
1114 vVisited[cc] =
true;
1115 int8_t color_c = mColor[c][mApOrig2Simpl[c][vap]];
1116 int8_t color_cc = mColor[cc][mApOrig2Simpl[cc][vap]];
1117 vRotation[cc] += vRotation[c] + color_c - color_cc;
1126 for (uint32_t comp_id = 0; comp_id < mColor.size(); ++comp_id)
1128 std::vector<int8_t>& vColor = mColor[comp_id];
1129 int32_t rotation = vRotation[comp_id];
1131 rotation += (
limbo::abs(rotation)/m_color_num+1)*m_color_num;
1132 assert(rotation >= 0);
1133 rotation %= (int32_t)m_color_num;
1134 for (uint32_t v = 0; v < vColor.size(); ++v)
1136 assert(vColor[v] >= 0);
1137 vColor[v] = (vColor[v] + rotation) % (int32_t)m_color_num;
1141 #ifdef DEBUG_GRAPHSIMPLIFICATION
1142 for (
typename std::map<graph_vertex_type, std::set<uint32_t> >::const_iterator vapi = m_mArtiPoint.begin(); vapi != m_mArtiPoint.end(); ++vapi)
1144 graph_vertex_type vap = vapi->first;
1145 std::set<uint32_t>
const& sComp = vapi->second;
1147 int8_t prev_color = -1;
1148 for (
typename std::set<uint32_t>::const_iterator itc = sComp.begin(); itc != sComp.end(); ++itc)
1150 uint32_t comp = *itc;
1151 int8_t color = mColor[comp][mApOrig2Simpl[comp][vap]];
1152 if (itc == sComp.begin())
1155 vap <<
": " <<
"comp " << comp <<
", c[" << mApOrig2Simpl[comp][vap] <<
"] = " << color <<
"; "
1156 <<
"prev_color = " << prev_color);
1162 template <
typename GraphType>
1165 while (!m_vHiddenVertex.empty())
1167 graph_vertex_type v = m_vHiddenVertex.top();
1168 m_vHiddenVertex.pop();
1171 std::vector<char> vUnusedColor (m_color_num,
true);
1172 typename boost::graph_traits<graph_type>::adjacency_iterator vi, vie;
1173 for (boost::tie(vi, vie) = boost::adjacent_vertices(v, this->m_graph); vi != vie; ++vi)
1175 graph_vertex_type u = *vi;
1177 vUnusedColor[vColor[u]] =
false;
1181 for (int8_t i = 0; i != (int8_t)m_color_num; ++i)
1183 if (vUnusedColor[i])
1189 assert(vColor[v] >= 0 && vColor[v] < (int8_t)m_color_num);
1193 template <
typename GraphType>
1196 std::ofstream out((filename+
".gv").c_str());
1197 out <<
"graph D { \n"
1199 <<
" size=\"4, 3\"\n"
1200 <<
" ratio=\"fill\"\n"
1201 <<
" edge[style=\"bold\",fontsize=200]\n"
1202 <<
" node[shape=\"circle\",fontsize=200]\n";
1205 vertex_iterator vi1, vie1;
1206 for (boost::tie(vi1, vie1) = boost::vertices(m_graph); vi1 != vie1; ++vi1)
1208 graph_vertex_type v1 = *vi1;
1209 if (!this->good(v1))
continue;
1211 out <<
" " << v1 <<
"[shape=\"circle\"";
1213 out <<
",label=\"" << v1 <<
":(";
1214 for (
typename std::vector<graph_vertex_type>::const_iterator it1 = m_vChildren[v1].begin(); it1 != m_vChildren[v1].end(); ++it1)
1216 if (it1 != m_vChildren[v1].begin())
1224 for (boost::tie(vi1, vie1) = boost::vertices(m_graph); vi1 != vie1; ++vi1)
1226 graph_vertex_type v1 = *vi1;
1227 if (!this->good(v1))
continue;
1229 vertex_iterator vi2, vie2;
1230 for (boost::tie(vi2, vie2) = boost::vertices(m_graph); vi2 != vie2; ++vi2)
1232 graph_vertex_type v2 = *vi2;
1233 if (!this->good(v2))
continue;
1234 if (v1 >= v2)
continue;
1236 std::pair<graph_edge_type, bool> e = this->connected_edge(v1, v2);
1241 if (this->connected_conflict(v1, v2))
1242 out <<
" " << v1 <<
"--" << v2 <<
"[color=\"black\",style=\"solid\",penwidth=3]\n";
1243 else if (this->connected_stitch(v1, v2))
1244 out <<
" " << v1 <<
"--" << v2 <<
"[color=\"black\",style=\"dashed\",penwidth=3]\n";
1246 out <<
" " << v1 <<
"--" << v2 <<
"[color=\"black\",style=\"dotted\",penwidth=1]\n";
1255 template <
typename GraphType>
1258 std::ofstream out((filename+
".gv").c_str());
1259 out <<
"graph D { \n"
1261 <<
" size=\"4, 3\"\n"
1262 <<
" ratio=\"fill\"\n"
1263 <<
" edge[style=\"bold\",fontsize=200]\n"
1264 <<
" node[shape=\"circle\",fontsize=200]\n";
1266 uint32_t offset = 0;
1268 for (uint32_t comp_id = 0; comp_id != m_mCompVertex.size(); ++comp_id)
1271 std::vector<graph_vertex_type> vSimpl2Orig;
1272 bool flag = this->simplified_graph_component(comp_id, sg, vSimpl2Orig);
1276 vertex_iterator vi1, vie1;
1277 for (boost::tie(vi1, vie1) = boost::vertices(sg); vi1 != vie1; ++vi1)
1279 graph_vertex_type mv1 = *vi1;
1280 graph_vertex_type v1 = vSimpl2Orig[mv1];
1281 if (m_vChildren[v1].empty())
continue;
1283 out <<
" " << offset+mv1 <<
"[shape=\"circle\"";
1285 out <<
",label=\"" << mv1 <<
":(";
1286 for (
typename std::vector<graph_vertex_type>::const_iterator it1 = m_vChildren[v1].begin(); it1 != m_vChildren[v1].end(); ++it1)
1288 if (it1 != m_vChildren[v1].begin())
1292 out <<
"):" << comp_id <<
"\"]\n";
1295 edge_iterator ei, eie;
1296 for (boost::tie(ei, eie) = boost::edges(sg); ei != eie; ++ei)
1298 graph_edge_type e = *ei;
1299 graph_vertex_type mv1 = boost::source(e, sg);
1300 graph_vertex_type mv2 = boost::target(e, sg);
1301 int32_t w = boost::get(boost::edge_weight, sg, e);
1302 assert_msg(mv1 != mv2, mv1 <<
" == " << mv2);
1306 sprintf(buf,
" %lu--%lu[label=%d,color=\"black\",style=\"solid\",penwidth=3]", offset+mv1, offset+mv2, w);
1308 sprintf(buf,
" %lu--%lu[label=%d,color=\"black\",style=\"dashed\",penwidth=3]", offset+mv1, offset+mv2, w);
1309 out << buf << std::endl;
1311 offset += boost::num_vertices(sg);
bool hidden(graph_vertex_type v1) const
void simplify(uint32_t level)
std::vector< std::vector< graph_vertex_type > > m_vChildren
children verices of current vertex, a vertex is the child of itself if it is not merged ...
uint32_t m_max_merge_level
in MERGE_SUBK4, any merge that results in the children number of a vertex larger than m_max_merge_lev...
std::map< graph_vertex_type, std::set< uint32_t > > m_mArtiPoint
map of (vertex of articulation point, set of components split by the vertex)
void biconnected_component()
find all articulation points and biconnected components
strategy_type
simplification strategies available. These strategies are order-sensitive. It is recommended to call ...
GraphSimplification(graph_type const &g, uint32_t color_num)
T abs(T const &t)
generalized api can handle both integer and floating points
void write_simplified_graph_dot(std::string const &filename) const
std::vector< std::vector< graph_vertex_type > > m_mCompVertex
group vertices by components
std::stack< graph_vertex_type > const & hidden_vertices() const
bool has_precolored() const
std::vector< graph_vertex_type > const & parents() const
graph_vertex_type parent(uint32_t v, std::vector< uint32_t > const &vParent) const
void recover_merge_subK4(std::vector< int8_t > &vColor) const
void recover(std::vector< int8_t > &vColorFlat, std::vector< std::vector< int8_t > > &mColor, std::vector< std::vector< graph_vertex_type > > const &mSimpl2Orig) const
std::vector< vertex_status_type > const & status() const
void connected_component()
compute connected components
bool merged(graph_vertex_type v1) const
void biconnected_component_recursion(graph_vertex_type v, std::deque< bool > &vVisited, std::vector< uint32_t > &vDisc, std::vector< uint32_t > &vLow, std::vector< graph_vertex_type > &vParent, uint32_t &visit_time, std::stack< std::pair< graph_vertex_type, graph_vertex_type > > &vEdge, std::list< std::pair< graph_vertex_type, std::set< graph_vertex_type > > > &mCompVertex) const
std::pair< graph_type, std::map< graph_vertex_type, graph_vertex_type > > simplified_graph() const
void hide_small_degree()
hide vertices whose degree is no larger than number of colors - 1
uint32_t m_level
simplification level
std::vector< vertex_status_type > m_vStatus
status of each vertex
void precolor(Iterator first, Iterator last)
some graph utilities such as compute complement graph and graphviz writer.
std::vector< graph_vertex_type > m_vParent
parent vertex of current vertex
graph_vertex_type parent(graph_vertex_type v) const
std::pair< graph_edge_type, bool > connected_edge(graph_vertex_type v1, graph_vertex_type v2) const
hide vertices whose degree is smaller than number of colors available
bool connected_conflict(graph_vertex_type v1, graph_vertex_type v2) const
vertex is hidden by simplification
bool check_max_merge_level(uint32_t l) const
mathematical utilities such as abs
graph_type const & m_graph
original graph
void recover_biconnected_component(std::vector< std::vector< int8_t > > &mColor, std::vector< std::vector< graph_vertex_type > > const &mSimpl2Orig) const
recover color for biconnected components
uint32_t m_color_num
number of colors
bool connected_stitch(graph_vertex_type v1, graph_vertex_type v2) const
bool articulation_point(graph_vertex_type v) const
void recover_hide_small_degree(std::vector< int8_t > &vColor)
std::iterator_traits< Iterator >::value_type max(Iterator first, Iterator last)
get max of an array
uint32_t num_component() const
bool good(graph_vertex_type v1) const
bool simplified_graph_component(uint32_t comp_id, graph_type &sg, std::vector< graph_vertex_type > &vSimpl2Orig) const
namespace for Limbo.algorithms
std::stack< graph_vertex_type > m_vHiddenVertex
a std::stack that keeps a reverse order of vertices hidden, useful for color recovery ...
vertex is merged to other vertex
void max_merge_level(int32_t l)
merge 4-clique structures, no longer optimal
std::vector< int8_t > m_vPrecolor
precolor information, if uncolored, std::set to -1
bool precolored(graph_vertex_type v1) const
void write_graph_dot(std::string const &filename) const
std::iterator_traits< Iterator >::value_type min(Iterator first, Iterator last)
get min of an array
void graphviz2pdf(std::string const &filename, const char *suffix=".gv")
convert graphviz format to pdf. The input filename should be filename+suffix
std::vector< std::vector< graph_vertex_type > > const & children() const
#define assert_msg(condition, message)
assertion with message
divide graph by biconnected components
vertex_status_type
status of vertex.