qbfdag.cpp

来自「算断裂的」· C++ 代码 · 共 113 行

// ------------------------------------------------------------------
// qbfdag.cpp
//
// This file contains member functions qbfdag.h.  This is a class
// for maintain a directed acyclic graph (DAG) of box faces.
// ------------------------------------------------------------------
// Author: Stephen A. Vavasis
// Copyright (c) 1999 by Cornell University.  All rights reserved.
// 
// See the accompanying file 'Copyright' for authorship information,
// the terms of the license governing this software, and disclaimers
// concerning this software.
// ------------------------------------------------------------------
// This file is part of the QMG software.  
// Version 2.0 of QMG, release date September 3, 1999.
// ------------------------------------------------------------------

#include "qbfdag.h"
#include "qboxstack.h"



namespace {

  using namespace QMG;


  // ------------------------------------------------------------------
  // permutation_sign
  // Compute the sign (+1 or -1) of a permutation
  // ------------------------------------------------------------------

  int permutation_sign(const vector<int>& permut,
    vector<int>& wksp) {
    

    int l = permut.size();
    wksp.resize(l);
   
#ifdef DEBUGGING
    for (int i1 = 0; i1 < l; ++i1)
      wksp[i1] = 0;
    for (int i2 = 0; i2 < l; ++i2) {
      if (permut[i2] < 0 || permut[i2] >= l ||
          wksp[permut[i2]] == 1) {
        throw_error("Illegal permutation");
        return 1;
      }
      wksp[permut[i2]] = 1;
    }
#endif
    int swapcount = 0;
    wksp = permut;
    for (int j = 0; j < l; ++j)
      while (wksp[j] != j) {
        int tmp = wksp[j];
        wksp[j] = wksp[tmp];
        wksp[tmp] = tmp;
        ++swapcount;
      }
    if (swapcount % 2)
      return -1;
    else
      return 1;
  }
}

void
QMG::MG::BoxFaceDag::trace_path_to_root(Index starting_link,
                                        vector<SimpComplex::VertexOrdinalIndex>& volist,
                                        int& permut_sgn,
                                        int& surf_ori) const {
  volist.resize(0);
  side_.resize(0);
  permut_.resize(0);
  Index p = starting_link;
  surf_ori = (linkstack_[p].is_leaf())? linkstack_[p].is_front() : 2;
  while (p >= 0) {
    Index parent = linkstack_[p].parent1();
    volist.push_back(linkstack_[p].vertex_index());
    if (parent >= 0) {
      permut_.push_back(linkstack_[p].dim1());
      side_.push_back(linkstack_[p].side1());
    }
    p = parent;
    if (volist.size() > 2 * MAXDIM)
      throw_error("Loop in dag");
  }
  if (volist.size() == di_ + 1) {
    permut_sgn = permutation_sign(permut_,wksp_);
    for (int j = 0; j < di_; ++j)
      if (side_[j]) 
        permut_sgn *= -1;
  }
  else 
    permut_sgn = 1;
}





QMG::MG::BoxFaceDag::Index 
QMG::MG::BoxFaceDag::add_protected_box(const ActiveBox& b,
                                       SimpComplex::VertexOrdinalIndex vnum_o) {
  Index sz = linkstack_.size();
  linkstack_.resize(sz + 1, BoxFaceDag::DagNode());
  linkstack_.back().initialize_node(b.link_parent(), b.link_parent_side(),
    b.link_parent_dim(), vnum_o, (b.dim() == 0), b.is_front_surface());
  return sz;
}