minimum_degree_ordering.hpp

support vector clustering for vc++

        // stack) at location 0.  Since these don't affect any other
        // nodes, we can eliminate them without doing degree updates.
        typename DegreeLists::stack list_isolated = degreelists[0];
        while (!list_isolated.empty()) {
          vertex_t node = list_isolated.top();
          marker.mark_done(node);
          numbering(node);
          numbering.increment();
          list_isolated.pop();
        }
        size_type min_degree = 1;
        typename DegreeLists::stack list_min_degree = degreelists[min_degree];

        while (list_min_degree.empty()) {
          ++min_degree;
          list_min_degree = degreelists[min_degree];
        }

        // check if the whole eliminating process is done
        while (!numbering.all_done()) {

          size_type min_degree_limit = min_degree + delta; // WARNING
          typename Workspace::stack llist = work_space.make_stack();

          // multiple elimination
          while (delta >= 0) {

            // Find the next non-empty degree
            for (list_min_degree = degreelists[min_degree]; 
                 list_min_degree.empty() && min_degree <= min_degree_limit; 
                 ++min_degree, list_min_degree = degreelists[min_degree])
              ;
            if (min_degree > min_degree_limit)
              break;

            const vertex_t node = list_min_degree.top();
            const size_type node_id = get(vertex_index_map, node);
            list_min_degree.pop();
            numbering(node);

            // check if node is the last one
            if (numbering.all_done(supernode_size[node])) {
              numbering.increment(supernode_size[node]);
              break;
            }
            marker.increment_tag();
            marker.mark_tagged(node);

            this->eliminate(node);

            numbering.increment(supernode_size[node]);
            llist.push(node_id);
          } // multiple elimination

          if (numbering.all_done()) 
            break;

          this->update( llist, min_degree);
        }

      } // do_mmd()

      void eliminate(vertex_t node)
      {
        typename Workspace::stack element_neighbor = work_space.make_stack();

        // Create two function objects for edge removal
        typedef typename Workspace::stack WorkStack;
        predicateRemoveEdge1<Graph, MarkerP, NumberingD, 
                             WorkStack, VertexIndexMap>
          p(G, marker, numbering, element_neighbor, vertex_index_map);

        predicate_remove_tagged_edges<Graph, MarkerP> p2(G, marker);

        // Reconstruct the adjacent node list, push element neighbor in a List.
        remove_out_edge_if(node, p, G);
        //during removal element neighbors are collected.

        while (!element_neighbor.empty()) {
          // element absorb
          size_type e_id = element_neighbor.top();
          vertex_t element = get(index_vertex_map, e_id);
          adj_iter i, i_end;
          for (tie(i, i_end) = adjacent_vertices(element, G); i != i_end; ++i){
            vertex_t i_node = *i;
            if (!marker.is_tagged(i_node) && !numbering.is_numbered(i_node)) {
              marker.mark_tagged(i_node);
              add_edge(node, i_node, G);
            }
          }
          element_neighbor.pop();
        }
        adj_iter v, ve;
        for (tie(v, ve) = adjacent_vertices(node, G); v != ve; ++v) {
          vertex_t v_node = *v;
          if (!degree_lists_marker.need_update(v_node) 
              && !degree_lists_marker.outmatched_or_done(v_node)) {
            degreelists.remove(v_node);
          }
          //update out edges of v_node
          remove_out_edge_if(v_node, p2, G);

          if ( out_degree(v_node, G) == 0 ) { // indistinguishable nodes
            supernode_size[node] += supernode_size[v_node];
            supernode_size[v_node] = 0;
            numbering.indistinguishable(v_node, node);
            marker.mark_done(v_node);
            degree_lists_marker.mark(v_node);
          } else {                           // not indistinguishable nodes
            add_edge(v_node, node, G);
            degree_lists_marker.mark_need_update(v_node);
          }
        }
      } // eliminate()


      template <class Stack>
      void update(Stack llist, size_type& min_degree)
      {
        size_type min_degree0 = min_degree + delta + 1;

        while (! llist.empty()) {
          size_type deg, deg0 = 0;

          marker.set_multiple_tag(min_degree0);
          typename Workspace::stack q2list = work_space.make_stack();
          typename Workspace::stack qxlist = work_space.make_stack();

          vertex_t current = get(index_vertex_map, llist.top());
          adj_iter i, ie;
          for (tie(i,ie) = adjacent_vertices(current, G); i != ie; ++i) {
            vertex_t i_node = *i;
            const size_type i_id = get(vertex_index_map, i_node);
            if (supernode_size[i_node] != 0) {
              deg0 += supernode_size[i_node];
              marker.mark_multiple_tagged(i_node);
              if (degree_lists_marker.need_update(i_node)) {
                if (out_degree(i_node, G) == 2)
                  q2list.push(i_id);
                else
                  qxlist.push(i_id);
              }
            }
          }

          while (!q2list.empty()) {
            const size_type u_id = q2list.top();
            vertex_t u_node = get(index_vertex_map, u_id);
            // if u_id is outmatched by others, no need to update degree
            if (degree_lists_marker.outmatched_or_done(u_node)) {
              q2list.pop();
              continue;
            }
            marker.increment_tag();
            deg = deg0;

            adj_iter nu = adjacent_vertices(u_node, G).first;
            vertex_t neighbor = *nu;
            if (neighbor == u_node) {
              ++nu;
              neighbor = *nu;
            }
            if (numbering.is_numbered(neighbor)) {
              adj_iter i, ie;
              for (tie(i,ie) = adjacent_vertices(neighbor, G);
                   i != ie; ++i) {
                const vertex_t i_node = *i;
                if (i_node == u_node || supernode_size[i_node] == 0)
                  continue;
                if (marker.is_tagged(i_node)) {
                  if (degree_lists_marker.need_update(i_node)) {
                    if ( out_degree(i_node, G) == 2 ) { // is indistinguishable
                      supernode_size[u_node] += supernode_size[i_node];
                      supernode_size[i_node] = 0;
                      numbering.indistinguishable(i_node, u_node);
                      marker.mark_done(i_node);
                      degree_lists_marker.mark(i_node);
                    } else                        // is outmatched
                      degree_lists_marker.mark(i_node);
                  }
                } else {
                  marker.mark_tagged(i_node);
                  deg += supernode_size[i_node];
                }
              }
            } else
              deg += supernode_size[neighbor];

            deg -= supernode_size[u_node];
            degree[u_node] = deg; //update degree
            degreelists[deg].push(u_node);
            //u_id has been pushed back into degreelists
            degree_lists_marker.unmark(u_node);
            if (min_degree > deg) 
              min_degree = deg;
            q2list.pop();
          } // while (!q2list.empty())

          while (!qxlist.empty()) {
            const size_type u_id = qxlist.top();
            const vertex_t u_node = get(index_vertex_map, u_id);

            // if u_id is outmatched by others, no need to update degree
            if (degree_lists_marker.outmatched_or_done(u_node)) {
              qxlist.pop();
              continue;
            }
            marker.increment_tag();
            deg = deg0;
            adj_iter i, ie;
            for (tie(i, ie) = adjacent_vertices(u_node, G); i != ie; ++i) {
              vertex_t i_node = *i;
              if (marker.is_tagged(i_node)) 
                continue;
              marker.mark_tagged(i_node);

              if (numbering.is_numbered(i_node)) {
                adj_iter j, je;
                for (tie(j, je) = adjacent_vertices(i_node, G); j != je; ++j) {
                  const vertex_t j_node = *j;
                  if (marker.is_not_tagged(j_node)) {
                    marker.mark_tagged(j_node);
                    deg += supernode_size[j_node];
                  }
                }
              } else
                deg += supernode_size[i_node];
            } // for adjacent vertices of u_node
            deg -= supernode_size[u_node];
            degree[u_node] = deg;
            degreelists[deg].push(u_node);
            // u_id has been pushed back into degreelists
            degree_lists_marker.unmark(u_node); 
            if (min_degree > deg)
              min_degree = deg;
            qxlist.pop();
          } // while (!qxlist.empty()) {

          marker.set_tag_as_multiple_tag();
          llist.pop();
        } // while (! llist.empty())

      } // update()


      void build_permutation(InversePermutationMap next,
                             PermutationMap prev) 
      {
        // collect the permutation info
        size_type i;
        for (i = 0; i < n; ++i) {
          diff_t size = supernode_size[get(index_vertex_map, i)];
          if ( size <= 0 ) {
            prev[i] = next[i];
            supernode_size[get(index_vertex_map, i)]
              = next[i] + 1;  // record the supernode info
          } else
            prev[i] = - next[i];
        }
        for (i = 1; i < n + 1; ++i) {
          if ( prev[i-1] > 0 )
            continue;
          diff_t parent = i;
          while ( prev[parent - 1] < 0 ) {
            parent = - prev[parent - 1];
          }

          diff_t root = parent;
          diff_t num = prev[root - 1] + 1;
          next[i-1] = - num;
          prev[root-1] = num;

          parent = i;
          diff_t next_node = - prev[parent - 1];
          while (next_node > 0) {
            prev[parent-1] = - root;
            parent = next_node;
            next_node = - prev[parent - 1];
          }
        }
        for (i = 0; i < n; i++) {
          diff_t num = - next[i] - 1;
          next[i] = num;
          prev[num] = i;
        }
      } // build_permutation()
    };

  } //namespace detail


  // MMD algorithm
  // 
  //The implementation presently includes the enhancements for mass
  //elimination, incomplete degree update, multiple elimination, and
  //external degree.
  //
  //Important Note: This implementation requires the BGL graph to be
  //directed.  Therefore, nonzero entry (i, j) in a symmetrical matrix
  //A coresponds to two directed edges (i->j and j->i).
  //
  //see Alan George and Joseph W. H. Liu, The Evolution of the Minimum
  //Degree Ordering Algorithm, SIAM Review, 31, 1989, Page 1-19
  template<class Graph, class DegreeMap, 
           class InversePermutationMap, 
           class PermutationMap,
           class SuperNodeMap, class VertexIndexMap>
  void minimum_degree_ordering
    (Graph& G, 
     DegreeMap degree, 
     InversePermutationMap inverse_perm, 
     PermutationMap perm, 
     SuperNodeMap supernode_size, 
     int delta, 
     VertexIndexMap vertex_index_map)
  {
    detail::mmd_impl<Graph,DegreeMap,InversePermutationMap,
      PermutationMap, SuperNodeMap, VertexIndexMap> 
      impl(G, num_vertices(G), delta, degree, inverse_perm, 
           perm, supernode_size, vertex_index_map);
    impl.do_mmd();
    impl.build_permutation(inverse_perm, perm);
  }

} // namespace boost

#endif // MINIMUM_DEGREE_ORDERING_HPP