Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Vertex Cover FPT Implementation

By: a guest on Jul 24th, 2012  |  syntax: C++  |  size: 3.59 KB  |  hits: 17  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. #include<iostream>
  2. #include<cmath>
  3. #include<vector>
  4. #include <algorithm>
  5. #include <utility>
  6. #include <boost/graph/graph_traits.hpp>
  7. #include <boost/graph/adjacency_list.hpp>
  8. #include <boost/graph/subgraph.hpp>
  9. #define k 2
  10.  
  11. using namespace std;
  12. using namespace boost;
  13.  
  14. typedef adjacency_list_traits<vecS, vecS, directedS> Traits;
  15. typedef subgraph< adjacency_list<vecS, vecS, directedS,
  16.     property<vertex_color_t, int>, property<edge_index_t, int> > > Graph;
  17.  
  18. typedef graph_traits<Graph>::vertex_iterator vertex_iter;
  19. typedef pair<int, int> Edge;
  20. typedef property_map<Graph, vertex_index_t>::type IndexMap;
  21.  
  22. vector<int> compress(vector <int>, Graph, int);
  23.  
  24. int main()
  25. {
  26.  
  27.     enum{u,v,w,x,y,z,n};
  28.  
  29.     const int num_vertices= n;
  30.     Graph g(num_vertices),gcopy;
  31.     int i;
  32.     Edge edge_array[]= { Edge(u,w), Edge(v,w), Edge(v,z), Edge(z,y), Edge(w,x) }; //array of edges
  33.     const int num_edges= sizeof (edge_array)/sizeof(edge_array[0]);
  34.  
  35.     for (int i = 0; i < num_edges; ++i)
  36.       add_edge(edge_array[i].first, edge_array[i].second, g); //adding the edges to the main graph
  37.  
  38.     IndexMap index = get(vertex_index, g);
  39.     pair<vertex_iter, vertex_iter> vp;
  40.  
  41.     vector<int> vccopy,vc;
  42.     vp=vertices(g);
  43.     vertex_iter first= vp.first;
  44.     gcopy= g.create_subgraph( ); // create a subgraph
  45.  
  46.     for (vp = vertices(g),i=0; vp.first != vp.second; i++, ++vp.first)// iterates as many times as the vertics.
  47.     {
  48.         add_vertex(i, gcopy);                                   //add thevertices one by one to G[i]
  49.         vc=compress( vccopy, gcopy, i);                         //k size vc foundfor  G[i], if it exists.
  50.         vccopy= vc;
  51.         vccopy.push_back(index[*vp.first]);                     // add the i+1th vertex to the make it the k+1 size vc of G[i+1]
  52.     }
  53.     if(vc.empty())
  54.     {
  55.         cout<<"No vertex cover exists.";
  56.     }
  57.     else
  58.     {
  59.         cout<<"Vertex cover is:";
  60.         for(i=0 ; i<vc.size(); i++)
  61.         {
  62.             cout<<vc[i];
  63.         }
  64.     }
  65. }
  66.  
  67. bool contains(vector<int> a, int item)
  68. {
  69.     if(find(a.begin(), a.end(), item)!=a.end())
  70.         return true;
  71.     else
  72.         return false;
  73. }
  74.  
  75. vector<int> compress( vector <int> vccopy, Graph gcopy, int j)
  76. {
  77.     vector<int> cdd, cd0,cd1, null;
  78.     IndexMap index = get(vertex_index, gcopy);
  79.  
  80.     for(int i=1; i<pow(2, j+1); i++)
  81.     {
  82.         int shift= j, icopy=i;
  83.         pair<vertex_iter, vertex_iter> vp;
  84.         graph_traits<Graph>::edge_iterator ei, ei_end;
  85.  
  86.         for ( vp = vertices(gcopy); vp.first != vp.second; ++vp.first)
  87.         {
  88.             if(icopy%2==0)
  89.             {
  90.                 cd0.push_back(index[*vp.first]);
  91.             }
  92.  
  93.             else
  94.             {
  95.                 cd1.push_back(index[*vp.first]);
  96.             }
  97.  
  98.             icopy/=2; //shift right operation.
  99.  
  100.         }
  101.  
  102.  
  103.         for (tie(ei, ei_end) = edges(gcopy); ei != ei_end; ++ei)
  104.         { Construction of the  Graph
  105.             if(contains(cd0,index[source(*ei, gcopy)]) || contains(cd0,index[target(*ei, gcopy)]))
  106.             {
  107.                 break;
  108.             }
  109.             else if(contains(cd0,index[source(*ei, gcopy)]))
  110.             {
  111.                 cdd.push_back(index[target(*ei, gcopy)]);
  112.             }
  113.             else if(contains(cd0,index[target(*ei, gcopy)]))
  114.             {
  115.                 cdd.push_back(index[source(*ei, gcopy)]);
  116.  
  117.             }
  118.         }
  119.  
  120.         if ((cdd.size()+cd1.size())<=k)
  121.         {
  122.             cdd.insert(cdd.end(), cd1.begin(), cd1.end());
  123.             return cdd;
  124.         }
  125.         else
  126.             return null;
  127.     }
  128. }
create a new version of this paste RAW Paste Data