Connectivity.h

Go to the documentation of this file.

// ----------------------------------------------------------------------------
//
// $Id$
//
// Copyright 2008, 2009, 2010, 2011, 2012  Antonio Franchi and Paolo Stegagno    
//
// This file is part of MIP.
//
// MIP is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// MIP is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with MIP. If not, see <http://www.gnu.org/licenses/>.
//
// Contact info: antonio.franchi@tuebingen.mpg.de stegagno@diag.uniroma1.it
//
// ----------------------------------------------------------------------------




/* @{ */

#ifndef __CONNECTIVITY_H_
#define __CONNECTIVITY_H_

#ifdef MIP_HOST_APPLE
#include <applePatch.h>
#endif

#include <stdio.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>
#include <stdlib.h>
#include <signal.h>
#include <assert.h>
#include <vector>

#include <iostream> // std::cout
#include <utility> // std::pair

#include <Types.h>
#include <Time.h>
#include <Spaces.h>


class TarjanVar{
 public:
  vector< int > indexes;
  vector< unsigned int > lowlinks;
  vector< unsigned int > stack; 
  unsigned int  index;  
  
  bool undefined(unsigned int index){
   assert(index<indexes.size());
   return (indexes[index]==-1);
  }
  
  void clear(){
   indexes.clear();
   lowlinks.clear();
   stack.clear();
  }
  
  void resize(unsigned int dim){
   indexes.resize(dim,-1);
   lowlinks.resize(dim,0);
   /*note, the stack must not be resized*/
  }
  
};


class Connectivity{
 private:
  static const unsigned int CONN_DEFAULT_ROB_NUM = 20;  
  static const unsigned int CONN_MAX_ROB_NUM   = 200; 
  static const Decimal CONN_DEFAULT_RADIUS = 1.0; 

  PosiFeatures      _posiFeatures; 
  vector< vector<bool> > _connMatrix;  
  
  Decimal _radius; 
  
  TarjanVar _tarjanVar; 
  
  void resize(unsigned int dim){
   _posiFeatures.resize(dim,PosiFeature());
   _connMatrix.resize(dim,vector<bool>());
   for(unsigned int i=0;i<dim;i++){
    _connMatrix[i].resize(dim,false);
   }
  }
  void reset(){
   unsigned int dim = size();
   clear();
   resize(dim);
  }
  void update(unsigned int row){
   /*size retrival and checks*/
   unsigned int dim = size();
   assert(row < dim);
   assert(_posiFeatures[row].associated());
   assert(row == _posiFeatures[row].getId());
   /*matrix update*/
   Position rowPosition = _posiFeatures[row].getPosition();
   for(unsigned int i=0;i<dim;i++){
    if(i==row){
     _connMatrix[row][row] = true; /*intersection of row and column*/
    }else{
     if(_posiFeatures[i].associated()){/*if this position exists*/
      if(rowPosition.dist(_posiFeatures[i].getPosition()) <_radius){/*iand is near enough*/
       _connMatrix[row][i] = true;
       _connMatrix[i][row] = true;
      }else{
       _connMatrix[row][i] = false;
       _connMatrix[i][row] = false;// An empty stack of nodes
      }
     }else{
      _connMatrix[row][i] = false;
      _connMatrix[i][row] = false;
     }
    }
   }
  }
  
  void tarjan(unsigned int vertex,unsigned int dim){
   _tarjanVar.indexes[vertex] = _tarjanVar.index; // Set the depth index for vertex
   _tarjanVar.lowlinks[vertex] = _tarjanVar.index;
   _tarjanVar.index += 1;
   _tarjanVar.stack.push_back(vertex); // Push vertex on the stack
   /*adjacent controls*/
   for(unsigned int adjaVertex=0;adjaVertex<dim;adjaVertex++){// Consider successors of vertex 
    if((_connMatrix[vertex][adjaVertex]==true)&&(vertex!=adjaVertex)){/*è adicente*/
     if(_tarjanVar.undefined(adjaVertex)){// Was successor adjaVertex visited?
      tarjan(adjaVertex,dim);// Recurse
      _tarjanVar.lowlinks[vertex]=
        min(_tarjanVar.lowlinks[vertex],_tarjanVar.lowlinks[adjaVertex]);
     }else if(inVector(adjaVertex,_tarjanVar.stack)){// Is adjaVertex on the stack?
      _tarjanVar.lowlinks[vertex]=
        min(_tarjanVar.lowlinks[vertex],_tarjanVar.lowlinks[adjaVertex]);
     }    
    }
   }
//    if(_tarjanVar.lowlinks[vertex] == _tarjanVar.indexes[vertex]){
//     cout << "SCC:";
//     do{     
//      cout << _tarjanVar.stack.back();
//      _tarjanVar.stack.pop_back();
//     }while(_tarjanVar.stack.size() > 0);
//    }
  }
  
  void merge(vector<unsigned int>& destination,const vector<unsigned int>& source){
   unsigned int dimDest = destination.size();
   unsigned int dimSource = source.size();
   for(unsigned int i=0;i<dimSource;i++){
    bool different = true;
    for(unsigned int j=0;j<dimDest;j++){
     if(source[i] == destination[j]){
      different = false;
      break;
     }
    }
    if(different){
     destination.push_back(source[i]);
    }
   }
  }
  
  bool inVector(unsigned int value,const vector<unsigned int>& vect){
   unsigned int vectSize = vect.size();
   for(unsigned int i=0;i<vectSize;i++){
    if(vect[i]==value){
     return true;
    }
   }
   return false;
  }

 public:
  Connectivity(){
   resize(CONN_DEFAULT_ROB_NUM);
   reset();
   _radius = CONN_DEFAULT_RADIUS;
  }
  ~Connectivity(){
   _connMatrix.clear();
  }
  void setRadius(Decimal value){
   _radius = value;
  }
  unsigned int size(){
   unsigned int dim = _posiFeatures.size();
   assert( dim == _connMatrix.size() );
   for(unsigned int i=0;i<dim;i++){
    assert( dim == _connMatrix[i].size() );
   }
   return dim;
  }
  void add(PosiFeature& pf){
   /* some preliminary checks */
   assert(pf.associated());
   unsigned int id = (unsigned int) pf.getId(); /*positivity is automatically checked*/
   assert(id < CONN_MAX_ROB_NUM);
   /*if needed resize*/
   if((id+1) > _posiFeatures.size()){
    resize(id+1);
   }
   /*update vector*/
   _posiFeatures[id] = pf;
   /*update matrix*/
   update(id);
  }

  void subnet(vector<unsigned int>& connComp,unsigned int id){
   /*checks and itializations*/
   unsigned int dim = size();
   assert(id<dim);
   connComp.clear();/*connected component*/
   connComp.reserve(dim);
   connComp.push_back(id);
   /*tarjan algorithm initialization*/
   _tarjanVar.clear();
   _tarjanVar.index = 0;
   _tarjanVar.resize(dim);
   /*tarjan algorithm (recursive)*/
   tarjan(id,dim);
   connComp = _tarjanVar.stack;
  }
  
  void subnets(vector<unsigned int>& group){
   /* some preliminary checks */
   unsigned int groupSize = group.size();
   assert(groupSize < size());
   vector<unsigned int> newGroup;
   for(unsigned int i = 0;i<groupSize;i++){
    if(!inVector(group[i],newGroup)){
     vector<unsigned int> connComp;
     subnet(connComp,group[i]);
     merge(newGroup,connComp);
    }
   }
   group.clear();
   group = newGroup;
  }
  
  
  void clear(){
   unsigned int dim = size(); 
   for(unsigned int i=0;i<dim;i++){
    _connMatrix[i].clear();
   } 
   _connMatrix.clear();
   _posiFeatures.clear();
  }
};





#endif