sloan_ordering.hpp

support vector clustering for vc++

        if( (h_i > h_s) && (w_i < w_e) ) 
        {
          h_s = h_i;
          s = i;
          while(!degree_queue.empty()) degree_queue.pop();
          new_start = true;         
        }
        else if(w_i < w_e)
        { 
          w_e = w_i;
          e = i;
        }
      }
      //end 6
        
    }while(new_start);
    
    return e;
  }

  //////////////////////////////////////////////////////////////////////////
  // Sloan algorithm with a given starting Vertex.
  //
  // This algorithm requires user to provide a starting vertex to
  // compute Sloan ordering.
  //////////////////////////////////////////////////////////////////////////
  template <class Graph, class OutputIterator,
            class ColorMap, class DegreeMap,
            class PriorityMap, class Weight>
  OutputIterator
  sloan_ordering(Graph& g,
                 typename graph_traits<Graph>::vertex_descriptor s,
                 typename graph_traits<Graph>::vertex_descriptor e,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority, 
                 Weight W1, 
                 Weight W2)
  {
    //typedef typename property_traits<DegreeMap>::value_type Degree;
    typedef typename property_traits<PriorityMap>::value_type Degree;
    typedef typename property_traits<ColorMap>::value_type ColorValue;
    typedef color_traits<ColorValue> Color;
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename std::vector<typename graph_traits<Graph>::vertices_size_type>::iterator vec_iter;
    typedef typename graph_traits<Graph>::vertices_size_type size_type;

    typedef typename property_map<Graph, vertex_index_t>::const_type VertexID;

    
    //Creating a std-vector for storing the distance from the end vertex in it
    typename std::vector<typename graph_traits<Graph>::vertices_size_type> dist(num_vertices(g), 0);
    
    //Wrap a property_map_iterator around the std::iterator
    boost::iterator_property_map<vec_iter, VertexID, size_type, size_type&> dist_pmap(dist.begin(), get(vertex_index, g)); 
    
    breadth_first_search
      (g, e, visitor
       (
           make_bfs_visitor(record_distances(dist_pmap, on_tree_edge() ) )
        )
       );
    
    //Creating a property_map for the indices of a vertex
    typename property_map<Graph, vertex_index_t>::type index_map = get(vertex_index, g);
    
    //Sets the color and priority to their initial status
    unsigned cdeg;    
    typename graph_traits<Graph>::vertex_iterator ui, ui_end;
    for (tie(ui, ui_end) = vertices(g); ui != ui_end; ++ui)
    {
        put(color, *ui, Color::white());
        cdeg=get(degree, *ui)+1;
        put(priority, *ui, W1*dist[index_map[*ui]]-W2*cdeg );  
    }
    
    //Priority list
    typedef indirect_cmp<PriorityMap, std::greater<Degree> > Compare;
    Compare comp(priority);
    std::list<Vertex> priority_list;

    //Some more declarations
    typename graph_traits<Graph>::out_edge_iterator ei, ei_end, ei2, ei2_end;
    Vertex u, v, w;

    put(color, s, Color::green());      //Sets the color of the starting vertex to gray
    priority_list.push_front(s);                 //Puts s into the priority_list
    
    while ( !priority_list.empty() ) 
    {  
      priority_list.sort(comp);         //Orders the elements in the priority list in an ascending manner
      
      u = priority_list.front();           //Accesses the last element in the priority list
      priority_list.pop_front();               //Removes the last element in the priority list
      
      if(get(color, u) == Color::green() )
      {
        //for-loop over all out-edges of vertex u
        for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) 
        {
          v = target(*ei, g);
          
          put( priority, v, get(priority, v) + W2 ); //updates the priority
          
          if (get(color, v) == Color::white() )      //test if the vertex is inactive
          {
            put(color, v, Color::green() );        //giving the vertex a preactive status
            priority_list.push_front(v);                     //writing the vertex in the priority_queue
          }           
        }
      }
      
      //Here starts step 8
      *permutation++ = u;                      //Puts u to the first position in the permutation-vector
      put(color, u, Color::black() );          //Gives u an inactive status
      
      //for loop over all the adjacent vertices of u
      for (tie(ei, ei_end) = out_edges(u, g); ei != ei_end; ++ei) {
        
        v = target(*ei, g);     
        
        if (get(color, v) == Color::green() ) {      //tests if the vertex is inactive
          
          put(color, v, Color::red() );        //giving the vertex an active status
          put(priority, v, get(priority, v)+W2);  //updates the priority        
          
          //for loop over alll adjacent vertices of v
          for (tie(ei2, ei2_end) = out_edges(v, g); ei2 != ei2_end; ++ei2) {
            w = target(*ei2, g);
            
            if(get(color, w) != Color::black() ) {     //tests if vertex is postactive
              
              put(priority, w, get(priority, w)+W2);  //updates the priority
              
              if(get(color, w) == Color::white() ){
                
                put(color, w, Color::green() );   // gives the vertex a preactive status
                priority_list.push_front(w);           // puts the vertex into the priority queue
                
              } //end if
              
            } //end if
            
          } //end for
          
        } //end if
        
      } //end for
      
    } //end while
    
    
    return permutation;
  }  
  
  /////////////////////////////////////////////////////////////////////////////////////////
  // Same algorithm as before, but without the weights given (taking default weights
  template <class Graph, class OutputIterator,
            class ColorMap, class DegreeMap,
            class PriorityMap>
  OutputIterator
  sloan_ordering(Graph& g,
                 typename graph_traits<Graph>::vertex_descriptor s,
                 typename graph_traits<Graph>::vertex_descriptor e,
                 OutputIterator permutation, 
                 ColorMap color, 
                 DegreeMap degree, 
                 PriorityMap priority)
  {
    return sloan_ordering(g, s, e, permutation, color, degree, priority, WEIGHT1, WEIGHT2); 
  }


  //////////////////////////////////////////////////////////////////////////
  // Sloan algorithm without a given starting Vertex.
  //
  // This algorithm finds a good starting vertex itself to
  // compute Sloan-ordering.
  //////////////////////////////////////////////////////////////////////////
 


  template < class Graph, class OutputIterator, 
             class Color, class Degree,
             class Priority, class Weight>
  inline OutputIterator
  sloan_ordering(Graph& G, 
                 OutputIterator permutation, 
                 Color color, 
                 Degree degree, 
                 Priority priority, 
                 Weight W1, 
                 Weight W2 )
  {
    typedef typename boost::graph_traits<Graph>::vertex_descriptor Vertex;
    
    Vertex s, e;
    e = sloan_start_end_vertices(G, s, color, degree);
    
    return sloan_ordering(G, s, e, permutation, color, degree, priority, W1, W2);
  }

  /////////////////////////////////////////////////////////////////////////////////////////
  // Same as before, but without given weights (default weights are taken instead)
  template < class Graph, class OutputIterator, 
             class Color, class Degree,
             class Priority >
  inline OutputIterator
  sloan_ordering(Graph& G, 
                 OutputIterator permutation, 
                 Color color, 
                 Degree degree, 
                 Priority priority)
  { 
    return sloan_ordering(G, permutation, color, degree, priority, WEIGHT1, WEIGHT2);
  }
  
  
} // namespace boost


#endif // BOOST_GRAPH_SLOAN_HPP