SkelGIS  3.0
/home/helene/Documents/These/SkelGIS/SkelGIS_Library/SkelGIS_V3/skelgis/data_structures/DDAG/ddag_impl.hpp
Go to the documentation of this file.
00001 /*! \file ddag_impl.hpp
00002  *  \brief Definitions of the object DDAG_impl used by the user. Three template specializations are available.
00003  *  DDAG_impl is the structure of the tree, not data. data are stored in DProperty objects.
00004  */
00005 #ifndef DDAG_IMPL_H
00006 #define DDAG_IMPL_H
00007 
00008 #include "../../util/mpi_.hpp"
00009 #include "../../iterators/DDAG/iterator.hpp"
00010 #include <math.h>
00011 #include<vector>
00012 
00013 namespace skelgis{
00014   
00015   //-------------------------------------------------------------------------------
00016   //!  base template class of Distributed DAG
00017   /*!
00018     This template class defines the base distributed dag
00019     This basic template does not have an implementation, only specializations have
00020     direction of the DAG is not usefull the input file of the user precise the direction
00021     no parameter on the physical border because roots and leafs nodes are always managed in a different way than standard elements (different neighborhood etc.)
00022     \tparam node is a boolean parameter to indicate if computations on nodes are needed for this DDAG_impl
00023     \tparam edge is a boolean parameter to indicate if computations on edges are needed for this DDAG_impl
00024   */
00025   //-------------------------------------------------------------------------------
00026   template<bool node, bool edge> struct DDAG_impl;
00027   //-------------------------------------------------------------------------------
00028 
00029   //-------------------------------------------------------------------------------
00030   //!  First specialization of the DDAG_impl class
00031   /*!
00032     This is the more complex case where both nodes and edges have to be computed
00033   */
00034   //-------------------------------------------------------------------------------
00035   template<> struct DDAG_impl<true,true>
00036   //-------------------------------------------------------------------------------
00037   {
00038   protected:
00039 
00040     /*!< to manage physical border
00041       physical border in DDAG_impl for scientific simulations are leafs and roots of the global DDAG_impl */
00042     unsigned int dim_roots; //! number of roots elements in the local DDAG_impl (global notion of roots)
00043     unsigned int dim_leafs; //! number of leafs elements int the local DDAG_impl (global notion of leafs)
00044     /*!< As distribution is not perfect, especially for huge DDAG_impl, it is important to make an overlap of communications by local computations
00045       For this reason pure local elements (except roots and leafs) are distinguished from elements that need communications */
00046     unsigned int dim_loc; //! number of internal nodes without any communication
00047     unsigned int dim_comm; //! number of internal nodes with communications
00048     
00049     //DATA STRUCTURE
00050     //nodes
00051     unsigned int dim_node; //! number of nodes
00052     /*!< cumulative degrees for inside neighbors nodes and edges
00053       foreach node you can get the number of inside nodes and inside edges (same) neighbors */
00054     unsigned int *degcum_in;
00055     /*!< cumulative degrees for outside neighbors nodes and edges
00056       foreach node you can get the number of outside nodes and inside edges (same) neighbors */
00057     unsigned int *degcum_out;
00058     /*!< associated table to degcum_in
00059       This table is the list of input neighbors nodes indexes for each node of the local DDAG_impl */
00060     unsigned int *neigh_in;
00061     /*!< associated table to degcum_out
00062       This table is the list of output neighbors nodes indexes for each node of the local DDAG_impl */
00063     unsigned int *neigh_out;
00064     /*!< associated table to degcum_in
00065       This table is the list of input neighbors edges indexes for each node of the local DDAG_impl */
00066     unsigned int *edges_out;
00067     /*!< associated table to degcum_out
00068       This table is the list of output neighbors edges indexes for each node of the local DDAG_impl */
00069     unsigned int *edges_in;
00070     
00071     //DATA STRUCTURE
00072     //edges
00073     unsigned int dim_edge; //! number of edges
00074     unsigned int *src_nodes; //! source node of each edge
00075     unsigned int *dst_nodes; //! destination node of each edge
00076 
00077     //DATA STRUCTURE
00078     //indexation
00079     unsigned int dim_ind_ed,dim_ind_no; //! number of indexes for nodes and edges (with additionnal communication indexes)
00080     /*!< Associations between new local nodes indexes values and nodes indexes of the global DAG
00081       Order of the new nodes indexes are very important for a transparent iteration on local elements
00082       All local nodes tables use those new indexes (neighborhood etc)
00083       indexes are stored this way :
00084       ******************************************************************************************************************************************
00085       ||  pure local elements  |  elements with communications  |  leafs  |  roots  |  comunicated elements from other processors IN then OUT ||
00086       ******************************************************************************************************************************************
00087      */
00088     unsigned int *indexes_nodes;
00089     /*!< Associations between new local edges indexes values and edges indexes of the global DAG 
00090       Edges are indexed following the nodes indexes
00091       output edges of Node 0 are indexed from 0 to degcum_out[0]
00092       output edges of Node k are indexed from degcum_out[k-1] to degcum_out[k]
00093     */
00094     unsigned int *indexes_edges;
00095 
00096     //DATA STRUCTURE
00097     //parallelization
00098     /*!< Number of elements to receive : outputs and inputs elements */
00099     unsigned int dim_tor_out,dim_tor_in;
00100     /*!< Number of elements to send : outputs and inputs elements */
00101     unsigned int dim_tos_out,dim_tos_in;
00102     /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output and input elements to send */
00103     unsigned int *degcum_tos;
00104     /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of  input elements to send  
00105      for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types */
00106     unsigned int * degcum_tos_in;
00107     /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output elements to send 
00108      for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types */
00109     unsigned int * degcum_tos_out;
00110     /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output and input elements to receive */
00111     unsigned int *degcum_tor;
00112     /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of input elements to receive 
00113      for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types*/
00114     unsigned int *degcum_tor_in;
00115     /*!< For each processor of the current MPI execution, it represents the cumulative degrees of the number of output elements to receive 
00116      for now difference between input and output is made for edges only. It is needed for DPMap_edges on pointers types*/
00117     unsigned int *degcum_tor_out;
00118     /*!< associated table to degcum_tos for edges
00119       This table is the list of edges local indexes to send to each other processor 
00120       */
00121     //unsigned int *edges_tos;
00122     /*!< associated table to degcum_tos_in for edges
00123       This table is the list of edges to send that goes in another processor, local indexes to send to each other processor */
00124     unsigned int *edges_tos_in;
00125     /*!< associated table to degcum_tos_out for edges
00126       This table is the list of edges to send that goes out of another processor, local indexes to send to each other processor */
00127     unsigned int *edges_tos_out;
00128     /*!< associated table to degcum_tos for nodes
00129       This table is the list of nodes local indexes to send to each other processor */
00130     unsigned int *nodes_tos;
00131     /*!< associated table to degcum_tor for edges
00132       This table is the list of edges local indexes to receive to each other processor  */
00133     //unsigned int *edges_tor;
00134     /*!< associated table to degcum_tor_in for edges
00135       This table is the list of edges local indexes to receive in from each other processor  */
00136     unsigned int *edges_tor_in;
00137     /*!< associated table to degcum_tor_out for edges
00138       This table is the list of edges local indexes to receive out from each other processor  */
00139     unsigned int *edges_tor_out;
00140     /*!< associated table to degcum_tos for nodes
00141       This table is the list of nodes local indexes to receive to each other processor  */
00142     unsigned int *nodes_tor;
00143 
00144     //-------------------------------------------------------------------------------
00145     //! find position tool
00146     /*!
00147       Find the position of element in table
00148       \param table is the pointer table in which the element has to be searched
00149       \param size is the size of the table
00150       \param element is the element value to search
00151       \param position is a reference to the position found
00152       \return true if the position has been found, false otherwise
00153     */
00154     //-------------------------------------------------------------------------------
00155     bool find_position(unsigned int * table,unsigned int size,unsigned int element,unsigned int &position)
00156     //-------------------------------------------------------------------------------
00157     {
00158       for(unsigned int i=0;i<size;i++)
00159         {
00160           if(table[i]==element)
00161             {
00162               position=i;
00163               return true;
00164             }
00165         }
00166       return false;
00167     }
00168     //-------------------------------------------------------------------------------
00169     //! find position tool
00170     /*!
00171       Find the position of element in table but do not get the position value
00172       \param table is the pointer table in which the element has to be searched
00173       \param size is the size of the table
00174       \param element is the element value to search
00175       \return true if the position has been found, false otherwise
00176     */
00177     //-------------------------------------------------------------------------------
00178     bool find_position(unsigned int * table,unsigned int size,unsigned int element)
00179     //-------------------------------------------------------------------------------
00180     {
00181       for(unsigned int i=0;i<size;i++)
00182         {
00183           if(table[i]==element)
00184               return true;
00185         }
00186       return false;
00187     }
00188     //-------------------------------------------------------------------------------
00189     //! find from tool
00190     /*!
00191       Search an element in a table with two positions between which to search
00192       \param table is the pointer table in which the element has to be searched
00193       \param position1 is the index value in the table where to start the search
00194       \param position2 is the index value in the table where to end the search (included)
00195       \param element is the element value to search in table
00196       \return true if the position has been found, false otherwise
00197     */
00198     //-------------------------------------------------------------------------------
00199     bool find_from(unsigned int * table,unsigned int position1,unsigned int position2,unsigned int element)
00200     //-------------------------------------------------------------------------------
00201     {
00202       for(unsigned int i=position1;i<position2+1;i++)
00203         {
00204           if(table[i]==element)
00205               return true;
00206         }
00207       return false;
00208     }
00209     //-------------------------------------------------------------------------------
00210     //! get maximum value tool
00211     /*!
00212       search the minimum value between three values
00213       \param a is the first value
00214       \param b is the second value
00215       \param c is the third value
00216       \return the minimum value between a, b and c
00217     */
00218     //-------------------------------------------------------------------------------
00219     unsigned int max(unsigned a,unsigned b,unsigned c)
00220     //-------------------------------------------------------------------------------
00221     {
00222       a=(a>b) ? a : b;
00223       return (a>c) ? a : c;
00224     }
00225     //-------------------------------------------------------------------------------
00226     //! recursively increment the number of time a subtree has been visited
00227     /*!
00228       Is used to count the number of total edges under a subtree
00229       \param index is the index of the root element of the subtree
00230       \param visited is the table to increment for the subtree
00231       \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks)
00232       \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks
00233     */
00234     //-------------------------------------------------------------------------------
00235     void is_visited(unsigned int index, unsigned int * visited, unsigned int * degcum_block, unsigned int *linked_blocks)
00236     //-------------------------------------------------------------------------------
00237     {
00238       unsigned int nb = degcum_block[index+1]-degcum_block[index];
00239       for(unsigned int i=0;i<nb;i++)
00240           is_visited(linked_blocks[degcum_block[index]+i],visited,degcum_block,linked_blocks);
00241       visited[index]+=1;
00242     }
00243     //-------------------------------------------------------------------------------
00244     //! recursively count the number of edges in a subtree
00245     /*!
00246       Is used to modify is_visited error
00247       \param index is the index of the root element of the subtree
00248       \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks)
00249       \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks
00250       \param edge_block is the cumulative degrees for the number of edges in each block of sister edges
00251       \return The number of edges in the subtree
00252     */
00253     //-------------------------------------------------------------------------------
00254     unsigned int all_edges_under(unsigned int index, unsigned int * degcum_block, unsigned int *linked_blocks, unsigned int * edge_block)
00255     //-------------------------------------------------------------------------------
00256     {
00257       unsigned int nb = degcum_block[index+1]-degcum_block[index];
00258       unsigned int res = edge_block[index+1] - edge_block[index];
00259       for(unsigned int i=0;i<nb;i++)
00260         res+=all_edges_under(linked_blocks[degcum_block[index]+i],degcum_block,linked_blocks,edge_block);
00261 
00262       return res;
00263     }
00264     //-------------------------------------------------------------------------------
00265     //! Take all the subtree for the same processor
00266     /*!
00267       Used in the distribution of the DDAG_impl, if the number of edges in the subtree < ideal take it entirely
00268       \param index is the index of the root element of the subtree
00269       \param edge_block is the cumulative degrees for the number of edges in each block of sister edges
00270       \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks)
00271       \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks
00272       \param taken is the table to note to which processor is assigned each block
00273       \param count is the reference to the count of edges for the current processor
00274       \param cur_proc is the current processor index
00275     */
00276     //-------------------------------------------------------------------------------
00277     void takeall(unsigned int index,unsigned int *edge_block,unsigned int *degcum_block,unsigned int *linked_blocks,unsigned int *taken,unsigned int &count, unsigned int cur_proc)
00278       //-------------------------------------------------------------------------------
00279     {
00280       //std::cout<<"index="<<index<<std::endl;
00281       if(taken[index]==0)
00282         {
00283           count += edge_block[index+1]-edge_block[index];
00284           taken[index] = cur_proc+1;
00285         }
00286       for(unsigned int i=0;i<degcum_block[index+1]-degcum_block[index];i++)
00287         takeall(linked_blocks[degcum_block[index]+i],edge_block,degcum_block,linked_blocks,taken,count,cur_proc);
00288     }
00289     //-------------------------------------------------------------------------------
00290     //! to verify that no isolated edges are stuck
00291     /*!
00292       When the ideal number of edges is reached, verify that no isolated edges are stuck in the subtree taken by the processor
00293       \param index is the index of the root element of the subtree
00294       \param edge_b_loc 
00295       \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks)
00296       \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks
00297       \param taken is the table to note to which processor is assigned each block
00298       \param count is the reference to the count of edges for the current processor
00299     */
00300     //-------------------------------------------------------------------------------
00301     void verif(unsigned int *index,unsigned int *edge_b_loc, unsigned int size, unsigned int * degcum_block, unsigned int *linked_blocks, 
00302                unsigned int *taken, unsigned int &count)
00303     //-------------------------------------------------------------------------------
00304     {
00305       for(unsigned int i=0;i<size;i++)
00306         {
00307           if(taken[index[i]]==0 && degcum_block[index[i]+1]-degcum_block[index[i]]==1 && taken[linked_blocks[degcum_block[index[i]]]]>0)
00308             {
00309               count+=edge_b_loc[i];
00310               taken[index[i]] = taken[linked_blocks[degcum_block[index[i]]]];
00311             }
00312         }
00313     }
00314     //-------------------------------------------------------------------------------
00315     //! recursive function for distribution when a root has been chosen or when a leaf has been reached (so an additionnal root is chosen)
00316     /*!
00317       \param mean_edges is the mean of the number of edges in blocks, it is used for an error on the ideal number of edges
00318       \param edges_r
00319       \param index is the index where to start the recursive distribution
00320       \param edge_b_loc
00321       \param size
00322       \param ideal is the ideal number of edges per processor
00323       \param taken is the table to note which block is assigned to which processor
00324       \param edges_subtree
00325       \param count is the number of edges taken by the current processor
00326       \pram cur_proc is the current processor
00327       \return false if the ideal number of edges is reached
00328     */
00329     //-------------------------------------------------------------------------------
00330     bool dist(unsigned int mean_edges, unsigned int & edges_r,unsigned int *index,unsigned int *edge_b_loc, unsigned int size, unsigned int ideal, 
00331                       unsigned int *edge_block, unsigned int * degcum_block, unsigned int *linked_blocks, 
00332                       unsigned int *taken, unsigned int * edges_subtree,unsigned int &count,int &cur_proc)
00333     //-------------------------------------------------------------------------------
00334     {
00335       /*
00336         1) try to take output blocks in edge_b_loc
00337         2) first search for subtrees (with roots in edge_b_loc) that can be get entirely without reaching ideal
00338         3) then enter the recrusive call of dist(...) itself for biger subtree
00339         This way isolated branches are avoided
00340        */
00341 
00342       if(size>0)
00343         {
00344           //first take the blocks that we can entirely take (<ideal)
00345           unsigned int bigger=0;
00346           for(unsigned int i=0;i<size;i++)
00347             {
00348               if(taken[index[i]]==0)
00349                 {
00350                   if(edges_subtree[index[i]]>edges_subtree[index[bigger]])
00351                     bigger = i;
00352 
00353                   if(count<ideal)
00354                     {
00355                       //if we can directly add the block and its subtree
00356                       //if(count+edges_subtree[index[i]]<=ideal+mean_edges+floor(ideal*0.1))
00357                       if(count+edges_subtree[index[i]]<=ideal+mean_edges)
00358                         takeall(index[i],edge_block,degcum_block,linked_blocks,taken,count,cur_proc);
00359                     }
00360                   else if(count>=ideal)
00361                     {
00362                       verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count);
00363                       //free(index);
00364                       //free(edge_b_loc);
00365                       return false;
00366                     }
00367                 }
00368             }
00369           //bigger case
00370           if(taken[index[bigger]]==0 && count<ideal)
00371             {
00372               //if(count<ideal && count+edge_b_loc[bigger]<=ideal+mean_edges+floor(ideal*0.1))
00373               if(count<ideal && count+edge_b_loc[bigger]<=ideal+mean_edges)
00374                 {
00375                   count+=edge_b_loc[bigger];
00376                   taken[index[bigger]] = cur_proc+1;
00377                   //recursive call
00378                   if(count<ideal)
00379                     {
00380                       unsigned int new_size=degcum_block[index[bigger]+1]-degcum_block[index[bigger]];
00381                       unsigned int *edge_block_loc = (unsigned int *)calloc(new_size,sizeof(unsigned int));
00382                       unsigned int *index_loc = (unsigned int *)calloc(new_size,sizeof(unsigned int));
00383                       if(new_size>0)
00384                         {
00385                           for(unsigned int j=0;j<degcum_block[index[bigger]+1]-degcum_block[index[bigger]];j++)
00386                             {
00387                               index_loc[j] = linked_blocks[degcum_block[index[bigger]]+j];
00388                               edge_block_loc[j] = edge_block[index_loc[j]+1]-edge_block[index_loc[j]];
00389                             }
00390                         }
00391 
00392                       //appel récursif
00393                       bool ret = dist(mean_edges,edges_r,index_loc,edge_block_loc,new_size,ideal,
00394                                               edge_block,degcum_block,linked_blocks,taken,edges_subtree,count,cur_proc);
00395                       verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count);
00396                       
00397                       free(index_loc);
00398                       free(edge_block_loc);
00399                       if(ret==false)
00400                         return ret;
00401                     }
00402                   else if(count>=ideal)
00403                     {
00404                       verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count);
00405                       //free(index);
00406                       //free(edge_b_loc);
00407                       return false;
00408                     }
00409                 }
00410               else if(count>=ideal)
00411                 {
00412                   verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count);
00413                   //free(index);
00414                   //free(edge_b_loc);
00415                   return false;
00416                 }
00417             }
00418         }
00419     }
00420     //-------------------------------------------------------------------------------
00421     //! Read the input DAG file .dot
00422     /*!
00423       \param file is the path to the file to read
00424       \param dim_node_g is the number of nodes in the global DDAG_impl
00425       \param dim_edge_g is the number of edges in the global DDAG_impl
00426       \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl
00427       \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl
00428     */
00429     //-------------------------------------------------------------------------------
00430     void read(const char * file,unsigned int &dim_node_g,unsigned int &dim_edge_g,unsigned int *&src_nodes_g,unsigned int *&dst_nodes_g)
00431     //-------------------------------------------------------------------------------
00432     {
00433       FILE *dotfile=fopen(file,"r");
00434       
00435       int read = fscanf(dotfile,"%u -> %u ;", &src_nodes_g[dim_edge_g], &dst_nodes_g[dim_edge_g]);
00436       while(!feof(dotfile)) 
00437       {
00438         dim_node_g=max(dim_node_g,src_nodes_g[dim_edge_g],dst_nodes_g[dim_edge_g]);
00439         dim_edge_g++;
00440         src_nodes_g=(unsigned int *)realloc(src_nodes_g,(dim_edge_g+1)*sizeof(unsigned int));
00441         dst_nodes_g=(unsigned int *)realloc(dst_nodes_g,(dim_edge_g+1)*sizeof(unsigned int));
00442         read = fscanf(dotfile,"%u -> %u ;", &src_nodes_g[dim_edge_g], &dst_nodes_g[dim_edge_g]);
00443       }
00444 
00445       fclose(dotfile);
00446     }
00447     //-------------------------------------------------------------------------------
00448     //! Find roots and leafs of the global DDAG_impl
00449     /*!
00450       \param dim_node_g is the number of nodes in the global DDAG_impl
00451       \param dim_edge_g is the number of edges in the global DDAG_impl
00452       \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl
00453       \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl
00454       \param dim_roots_g is the reference to the global number of roots elements in the global DDAG_impl
00455       \param dim_leafs_g is the reference to the global number of leafs elements in the global DDAG_impl
00456     */
00457     //-------------------------------------------------------------------------------
00458     void findRootsLeafs(unsigned int dim_node_g, unsigned int dim_edge_g, unsigned int * src_nodes_g, unsigned int * dst_nodes_g, 
00459                         unsigned int &dim_roots_g, unsigned int &dim_leafs_g, unsigned int *&roots_g, unsigned int *&leafs_g)
00460     //-------------------------------------------------------------------------------
00461     {
00462       for(unsigned int j=0;j<dim_node_g;j++)
00463         {
00464           int found_src=0;
00465           int found_dst=0;
00466           for(unsigned int i=0;i<dim_edge_g;i++)
00467             {
00468               if(src_nodes_g[i]==j)
00469                 found_src++;
00470               if(dst_nodes_g[i]==j)
00471                 found_dst++;
00472             }
00473           if(found_src>0 && found_dst==0)
00474             {
00475               dim_roots_g++;
00476               roots_g = (unsigned int *)realloc(roots_g,(dim_roots_g)*sizeof(unsigned int));
00477               roots_g[dim_roots_g-1]=j;
00478             }
00479           if(found_src==0 && found_dst>0)
00480             {
00481               dim_leafs_g++;
00482               leafs_g = (unsigned int *)realloc(leafs_g,(dim_leafs_g)*sizeof(unsigned int));
00483               leafs_g[dim_leafs_g-1]=j;
00484             }
00485         }
00486     }
00487     //-------------------------------------------------------------------------------
00488     //! Construction of the global DAG data structure
00489     /*!
00490       \param dim_edge_g is the number of edges in the global DDAG_impl
00491       \param dim_node_g is the number of nodes in the global DDAG_impl
00492       \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl
00493       \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl
00494       \param degcum_in_g equivalent of degcum_in for the global DAG_impl
00495       \param degcum_out_g equivalent of degcum_out for the global DAG_impl
00496       \param neigh_out_g equivalent of the neigh_out for the global DAG_impl
00497       \param neigh_in_g equivalent of the neigh_in for the global DAG_impl
00498       \param edges_g equivalent of edges_out and edges_in for the global DAG_impl (no distinction needed)
00499       \param edge_block cumulative degrees of the number of edges per block
00500     */
00501     //-------------------------------------------------------------------------------
00502     void globalDS(unsigned int dim_edge_g,unsigned int dim_node_g,unsigned int *src_nodes_g,unsigned int *dst_nodes_g,
00503                   unsigned int *&degcum_in_g,unsigned int *&degcum_out_g,unsigned int *&neigh_out_g,unsigned int *&neigh_in_g,unsigned int *&edges_g, unsigned int *&edge_block,
00504                   unsigned int &mean_edges, unsigned int &max_edges, unsigned int &b)
00505     //-------------------------------------------------------------------------------
00506     {
00507       //--------------------------------------------------------------------------------
00508       //construction of degcum_out_g and degcum_in_g :
00509       //represent the cumulative number of inputs and outputs nodes and edges of a node
00510       //construction of edge_block :
00511       //represent the number of edges in each group of sister edges
00512       //--------------------------------------------------------------------------------
00513       unsigned int *deg_in=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int));
00514       unsigned int *deg_out=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int));
00515       for(unsigned int i=0;i<dim_edge_g;i++)
00516         {
00517           deg_out[src_nodes_g[i]]++;
00518           deg_in[dst_nodes_g[i]]++;
00519         }
00520 
00521       degcum_in_g=(unsigned int *)calloc(dim_node_g+1,sizeof(unsigned int));
00522       degcum_out_g=(unsigned int *)calloc(dim_node_g+1,sizeof(unsigned int));
00523       edge_block=(unsigned int *)realloc(edge_block,1*sizeof(unsigned int));
00524       edge_block[0] = degcum_out_g[0];
00525       for (int i=1;i<dim_node_g+1;i++)
00526         {
00527           degcum_out_g[i]=degcum_out_g[i-1]+deg_out[i-1];
00528           degcum_in_g[i]=degcum_in_g[i-1]+deg_in[i-1];
00529           if(i<dim_node_g && degcum_out_g[i]>degcum_out_g[i-1])
00530             {
00531               b++;
00532               edge_block=(unsigned int *)realloc(edge_block,(b+1)*sizeof(unsigned int));
00533               edge_block[b] = degcum_out_g[i];
00534               if(edge_block[b]-edge_block[b-1]>max_edges)
00535                 max_edges = edge_block[b]-edge_block[b-1];
00536 
00537               mean_edges += edge_block[b]-edge_block[b-1];
00538             }
00539           
00540         }
00541       free(deg_in),free(deg_out);
00542       mean_edges = static_cast<unsigned int>(floor(mean_edges/b));
00543       //--------------------------------------------------------------------------------
00544       //construction of neigh_out_g, neigh_in_g and edges
00545       //represent the associated neighbour nodes and edges of a node with use of degcum tables
00546       //--------------------------------------------------------------------------------
00547       unsigned int *t_in=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int));
00548       unsigned int *t_out=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int));
00549       unsigned int *t=(unsigned int *)calloc(dim_node_g,sizeof(unsigned int));
00550 
00551       neigh_in_g=(unsigned int *)calloc(dim_edge_g,sizeof(unsigned int));
00552       neigh_out_g=(unsigned int *)calloc(dim_edge_g,sizeof(unsigned int));
00553       edges_g=(unsigned int *)calloc(dim_edge_g,sizeof(unsigned int));
00554 
00555       for (int i=0;i<dim_edge_g;i++) 
00556         {
00557           neigh_out_g[ degcum_out_g[src_nodes_g[i]] + t_out[ src_nodes_g[i] ]++ ]=dst_nodes_g[i];
00558           neigh_in_g[ degcum_in_g[dst_nodes_g[i]] + t_in[ dst_nodes_g[i] ]++ ]=src_nodes_g[i];
00559           edges_g[ degcum_out_g[src_nodes_g[i]] + t[ src_nodes_g[i] ]++ ]=i;
00560         }
00561       free(t_out),free(t_in),free(t);
00562     }
00563     //-------------------------------------------------------------------------------
00564     //! Prepare data for distribution
00565     /*!
00566       \param b is the number of blocks in the global DAG
00567       \param edges_g equivalent of edges_out and edges_in for the global DAG (no distinction)
00568       \param edge_block cumulative degrees of the number of edges per block
00569       \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl
00570       \param degcum_out_g equivalent of degcum_out for the global DAG_impl
00571       \param degcum_block is the cumulative degrees for links between blocks of sister edges (equivalent of degcum_out for blocks)
00572       \param linked_blocks is the associated table to degcum_block, it is the list of neighbor blocks
00573       \param edges_subtree
00574     */
00575     //-------------------------------------------------------------------------------
00576     void dataDistr(unsigned int b,unsigned int *edges_g,unsigned int *edge_block,unsigned int *dst_nodes_g,unsigned int *degcum_out_g,
00577                    unsigned int *&degcum_block,unsigned int *&linked_blocks,unsigned int *&edges_subtree)
00578     //-------------------------------------------------------------------------------
00579     {
00580       //--------------------------------------------------------------------------------
00581       //construction of degcum_block and linked_block
00582       //represent the equivalent of degcum_out and neigh_out of nodes, but for blocks of sister edges
00583       //--------------------------------------------------------------------------------
00584       for(unsigned int i=0;i<b;i++)
00585         {
00586           //initialization of degcum_block i+1 with the previous value
00587           degcum_block[i+1] = degcum_block[i];
00588 
00589           //with edge_block and edges we know which edges are in each block
00590           unsigned int end = edge_block[i+1] - edge_block[i];
00591           unsigned int * cur_edges = (unsigned int *)calloc(end,sizeof(unsigned int));
00592           for(unsigned int j=0;j<end;j++)
00593             cur_edges[j] = edges_g[edge_block[i]+j];
00594 
00595           for(unsigned int j=0;j<end;j++)
00596             {
00597               //with dst_nodes we know the destination node the edges is connected to
00598               unsigned int node_dst = dst_nodes_g[cur_edges[j]];
00599               //with degcum_out and edges we know the out edges of the destination node
00600               unsigned int en = degcum_out_g[node_dst+1] - degcum_out_g[node_dst];
00601               unsigned int *out_ed = (unsigned int *)calloc(en,sizeof(unsigned int));
00602               for(unsigned int k=0;k<en;k++)
00603                 out_ed[k] = edges_g[degcum_out_g[node_dst]+k];
00604 
00605               //now we identify which edges block has these output edges
00606               if(en>0)
00607                 {
00608                   for(unsigned int l=0;l<b;l++)
00609                     {
00610                       if(en >0 && edge_block[l+1]==out_ed[0])
00611                         {
00612                           degcum_block[i+1]++;
00613                           linked_blocks = (unsigned int *)realloc(linked_blocks,degcum_block[i+1]*sizeof(unsigned int));
00614                           linked_blocks[degcum_block[i+1]-1]=l+1;
00615                         }
00616                     }
00617                 }
00618               free(out_ed);
00619             }
00620           free(cur_edges);
00621         }
00622       //--------------------------------------------------------------------------------
00623       //construction of the last table edges_subtree
00624       //represent the total number of edges under a block if this block is the root of the subtree (we count its own edges too)
00625       //--------------------------------------------------------------------------------
00626       for(unsigned int i=0;i<b;i++)
00627         {
00628           //naive calculation of edges_subtree
00629           edges_subtree[i] = all_edges_under(i,degcum_block,linked_blocks,edge_block);
00630           //error correction
00631           unsigned int * visited = (unsigned int *)calloc(b,sizeof(unsigned int));
00632           is_visited(i,visited,degcum_block,linked_blocks);
00633           for(unsigned int j=0;j<b;j++)
00634             {
00635               if(visited[j]>1)
00636                 edges_subtree[i] -= (visited[j]-1)*(edge_block[j+1]-edge_block[j]);
00637             }
00638           free(visited);
00639         }
00640     }
00641     //-------------------------------------------------------------------------------
00642     //! Fill src_nodes and dst_nodes and construct temporary pure local indexes
00643     /*!
00644       \param b is the number of blocks in the global DAG
00645       \param taken is the table to note which block is assigned to which processor
00646       \param edge_block is the cumulative degrees for the number of edges in each block of sister edges
00647       \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl
00648       \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl
00649       \param edges_g equivalent of edges_out and edges_in for the global DAG (no distinction)
00650       \param dim_roots_g is the number of roots in the global DAG_impl
00651       \param dim_leafs_g is the number of leafs in the global DAG_impl
00652       \param roots_g is the list of roots in the global DAG_impl
00653       \param leafs_g is the list of leafs in the global DAG_impl
00654     */
00655     //-------------------------------------------------------------------------------
00656     void localSrcDstNodes(unsigned int b,unsigned int *taken,unsigned int *edge_block,unsigned int *src_nodes_g,unsigned int *dst_nodes_g,unsigned int *edges_g,
00657                           unsigned int dim_roots_g,unsigned int dim_leafs_g,unsigned int *roots_g,unsigned int *leafs_g)
00658     //-------------------------------------------------------------------------------
00659     {
00660       /*
00661         src_nodes and dst_nodes are taken from globals src_nodes_g and dst_nodes_g and the table taken
00662         indexes of edges are also taken from this
00663         BUT indexation are modified three time during the construction of the data structure
00664         1) at the beginning (in this method) to take into acount local elements that are global roots and leafs 
00665         (these elements do not need communications and in addition to this they have to be managed differently than other elements)
00666         2) later communications are calculated and indexation of new elements received from other processors are calculated
00667         3) finally in the same code different indexation are made between local elements that do not need any communication to be computed and elements that need communications
00668         Indexation for nodes is finally made this way :
00669         ******************************************************************************************************************************************
00670         ||  pure local elements  |  elements with communications  |  leafs  |  roots  |  comunicated elements from other processors IN then OUT ||
00671         ******************************************************************************************************************************************
00672 
00673         Indexation for edges depends on indexation of nodes and are modify too
00674         output edges of Node 0 are indexed from 0 to degcum_out[0]
00675         output edges of Node k are indexed from degcum_out[k-1] to degcum_out[k]
00676        */
00677 
00678       //get src_nodes, dst_nodes and basic indexes_edges from src_nodes_g dst_nodes_g and taken
00679       unsigned int ind=0;
00680       for(unsigned int i=0;i<b;i++)
00681         {
00682           if(taken[i]==Mpi_::mpi_rank+1)
00683             {
00684               for(unsigned int j=0;j<edge_block[i+1]-edge_block[i];j++)
00685                 {
00686                   src_nodes[ind+j] = src_nodes_g[edges_g[edge_block[i]+j]];
00687                   dst_nodes[ind+j] = dst_nodes_g[edges_g[edge_block[i]+j]];
00688                   indexes_edges[ind+j] = edges_g[edge_block[i]+j];
00689                 }
00690               ind += edge_block[i+1]-edge_block[i];
00691             }
00692         }
00693       
00694       //sort the node indexes (src and dst) without double values
00695       //it represents the new basic indexes
00696       unsigned int * temp = (unsigned int*)calloc(2*dim_edge,sizeof(unsigned int));
00697       indexes_nodes = (unsigned int*)calloc(1,sizeof(unsigned int));
00698       for(unsigned int i=0;i<dim_edge;i++)
00699         temp[i] = src_nodes[i];
00700       for(unsigned int i=dim_edge;i<2*dim_edge;i++)
00701         temp[i] = dst_nodes[i-dim_edge];
00702       //sort temp
00703       bool mod=true;
00704       while(mod)
00705         {
00706           mod=false;
00707           for(unsigned int i=1;i<2*dim_edge;i++)
00708             {
00709               if(temp[i]<temp[i-1])
00710                 {
00711                   unsigned int t = temp[i];
00712                   temp[i] = temp[i-1];
00713                   temp[i-1] = t;
00714                   mod=true;
00715                 }
00716             }
00717         }
00718       //fill sort
00719       unsigned int * s_indexes_nodes = (unsigned int*)calloc(1,sizeof(unsigned int));
00720       s_indexes_nodes[0] = temp[0];
00721       dim_node=1;
00722       for(unsigned int i=1;i<2*dim_edge;i++)
00723         {
00724           //erase double values
00725           if(temp[i]!=temp[i-1])
00726             {
00727               dim_node++;
00728               indexes_nodes = (unsigned int*)realloc(indexes_nodes,dim_node*sizeof(unsigned int));
00729               s_indexes_nodes = (unsigned int*)realloc(s_indexes_nodes,dim_node*sizeof(unsigned int));
00730               s_indexes_nodes[dim_node-1]=temp[i];
00731               indexes_nodes[dim_node-1]=temp[i];
00732             }
00733         }
00734       free(temp);
00735       
00736       //change those new indexes, taking care of roots and leafs elements
00737       unsigned int rev = dim_node-1;
00738       unsigned int in=0;
00739       for(unsigned int i=0;i<dim_node;i++)
00740         {
00741           bool l=false;
00742           for(unsigned int j=0;j<dim_leafs_g;j++)
00743             {
00744               if(leafs_g[j]==s_indexes_nodes[i])
00745                 {
00746                   dim_leafs++;
00747                   indexes_nodes[rev]=s_indexes_nodes[i];
00748                   rev--;
00749                   l=true;
00750                 }
00751             }
00752           bool r = false;
00753           for(unsigned int j=0;j<dim_roots_g;j++)
00754             {
00755               if(roots_g[j]==s_indexes_nodes[i])
00756                 {
00757                   dim_roots++;
00758                   indexes_nodes[rev]=s_indexes_nodes[i];
00759                   rev--;
00760                   r=true;
00761                 }
00762             }
00763           if(!r && !l)
00764             {
00765               indexes_nodes[in] = s_indexes_nodes[i];
00766               in++;
00767             }
00768         }
00769       free(s_indexes_nodes);
00770 
00771       //modification of src_nodes and dst_nodes with local indexes
00772       for(unsigned int i=0;i<dim_edge;i++)
00773         {
00774           bool f_src=false;
00775           bool f_dst=false;
00776           for(unsigned int j=0;j<dim_node;j++)
00777             {
00778               if(!f_src && src_nodes[i]==indexes_nodes[j])
00779                 {
00780                   src_nodes[i] = j;
00781                   f_src=true;
00782                 }
00783               if(!f_dst && dst_nodes[i]==indexes_nodes[j])
00784                 {
00785                   dst_nodes[i] = j;
00786                   f_dst=true;
00787                 }
00788             }
00789         }
00790       //re-order src_nodes and dst_nodes to get growing src_nodes
00791       //usefull to get the local data structure with good output edges values
00792       unsigned int * old_src_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int));
00793       unsigned int * old_dst_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int));
00794       for(unsigned int i=0;i<dim_edge;i++)
00795         {
00796           old_src_nodes[i]=src_nodes[i];
00797           old_dst_nodes[i]=dst_nodes[i];
00798         }
00799       bool modif=true;
00800       while(modif)
00801         {
00802           modif=false;
00803           for(unsigned int i=1;i<dim_edge;i++)
00804             {
00805               if(src_nodes[i]<src_nodes[i-1])
00806                 {
00807                   unsigned int s = src_nodes[i];
00808                   unsigned int d = dst_nodes[i];
00809                   src_nodes[i] = src_nodes[i-1];
00810                   src_nodes[i-1] = s;
00811                   dst_nodes[i] = dst_nodes[i-1];
00812                   dst_nodes[i-1] = d;
00813                   modif=true;
00814                 }
00815             }
00816         }
00817       //change indexes_edges with this new order of src_nodes and dst_nodes
00818       unsigned int * new_indexes_edges = (unsigned int *)calloc(dim_edge,sizeof(unsigned int));
00819       for(unsigned int i=0;i<dim_edge;i++)
00820         {
00821           for(unsigned int j=0;j<dim_edge;j++)
00822             {
00823               if(src_nodes[i]==old_src_nodes[j] && dst_nodes[i]==old_dst_nodes[j])
00824                 {
00825                   new_indexes_edges[i] = indexes_edges[j];
00826                 }
00827             }
00828         }
00829 
00830       free(old_src_nodes);free(old_dst_nodes);
00831       free(indexes_edges);
00832       indexes_edges=new_indexes_edges;
00833 
00834     }
00835     //-------------------------------------------------------------------------------
00836     //! Fill the local data structure DDAG_impl
00837     /*!
00838       \param b is the number of blocks in the global DAG_impl
00839       \param dim_edge_g number of edges in the global DAG_impl
00840       \param dst_nodes_g is the list of destination nodes for each edge in the global DDAG_impl
00841       \param src_nodes_g is the list of source nodes for each edge in the global DDAG_impl
00842       \param edge_block is the cumulative degrees for the number of edges in each block of sister edges
00843       \param taken is the table to note which block is assigned to which processor
00844       \param degcum_out_t is a temporary equivalent of degcum_out to keep the pure local version
00845       \param degcum_in_t is a temporary equivalent of degcum_in to keep the pure local version
00846       \param edges_t_out is a temporary equivalent of edges_out to keep the pure local version
00847       \param edges_t_in is a temporary equivalent of edges_in to keep the pure local version
00848       \param neigh_out_t is a temporary equivalent of neigh_out to keep the pure local version
00849       \param neigh_in_t is a temporary equivalent of neigh_in to keep the pure local version
00850       \param roots_g is the list of roots in the global DAG_impl
00851       \param leafs_g is the list of leafs in the global DAG_impl
00852       \param dim_roots_g is the number of roots in the global DAG_impl
00853       \param dim_leafs_g is the number of leafs in the global DAG_impl
00854     */
00855     //-------------------------------------------------------------------------------
00856     void fillLocalDS(unsigned int b, unsigned int dim_edge_g,unsigned int *dst_nodes_g,unsigned int *src_nodes_g,unsigned int *edge_block,unsigned int *taken,
00857                      unsigned int *degcum_out_t,unsigned int *degcum_in_t,unsigned int *edges_t_out,unsigned int *edges_t_in,unsigned int *neigh_out_t,unsigned int *neigh_in_t,
00858                      unsigned int *roots_g,unsigned int *leafs_g,unsigned int dim_roots_g,unsigned int dim_leafs_g)
00859     //-------------------------------------------------------------------------------
00860     {
00861       /*
00862         for each node of the local data structure an analysis of communications needed is made
00863 
00864         1) search in all the global edges that are not taken by the currant processor if the node is found. In this case it represents an edge and a node to receive from another processor.
00865              a) fill degcum_tor edges_tor and nodes_tor with in and out communications to receive
00866              b) remember those communications in tor_out and tor_in and stor_out stor_in to modify local data structures
00867              c) remember the processors connected to complete the point 2)
00868         2) search in the local edges if the node is found. In this case it represents an edge and a node to send to another processor.
00869              a) fill degcum_tos edges_tos and nodes_tos helping with 1-c
00870              b) distinguish communication nodes from pure local nodes
00871         3) get the good order of edges for input edges
00872         4) modify local data structure degcum_out,degcum_in,neigh_out,neigh_in,edges_out and edges_in with communications
00873         5) change indexation taking into acount communication and pure local nodes of 2-b
00874 
00875         After that the new indexation can be applied to all local data structure
00876        */
00877 
00878       //indexes_nodes and indexes_edges has been filled for local elements
00879       //from dim_edge and dim_node to get new indexes for communicated elements
00880       dim_ind_ed=dim_edge;
00881       dim_ind_no=dim_node;
00882       //to note the nodes with comunication in order to change indexation after
00883       unsigned int * comm_nodes = (unsigned int *)calloc(dim_comm,sizeof(unsigned int));
00884       unsigned int * loc_nodes = (unsigned int *)calloc(dim_loc,sizeof(unsigned int));
00885       
00886       //foreach node of the local structure
00887       for(unsigned int i=0;i<dim_node;i++)
00888         {
00889           //tables to receive out and in (edges)
00890           unsigned int stor_out=0;
00891           unsigned int * tor_out = (unsigned int *)calloc(stor_out,sizeof(unsigned int));
00892           unsigned int stor_in=0;
00893           unsigned int * tor_in = (unsigned int *)calloc(stor_in,sizeof(unsigned int));
00894           //tables to send out and in (edges)
00895           unsigned int stos_out=0;
00896           unsigned int stos_in=0;
00897           unsigned int nb_proc=0;
00898           //unsigned int nb_proc_out=0;
00899           unsigned int * procs = (unsigned int *)calloc(nb_proc,sizeof(unsigned int));
00900           //unsigned int * procs_out = (unsigned int *)calloc(nb_proc_out,sizeof(unsigned int));
00901           //look at all edges in the global structure
00902           for(unsigned int j=0;j<dim_edge_g;j++)
00903             {
00904               unsigned int block = 0;
00905               //if the node is found in an edges
00906               if(indexes_nodes[i]==dst_nodes_g[j] || indexes_nodes[i]==src_nodes_g[j])
00907                 {
00908                   //which block is associated to this edge
00909                   for(unsigned int k=1;k<b+1;k++)
00910                     {
00911                       if(j>=edge_block[k-1] && j<edge_block[k])
00912                         {
00913                           block=k-1;
00914                           k=b+1;
00915                         }
00916                     }
00917                   //if the edge is not one of the current node then communications modifications are needed
00918                   //to receive informations
00919                   if(taken[block]-1!=Mpi_::mpi_rank)
00920                     {
00921                       //if the proc has not been noticed before in procs, add it
00922                       unsigned int t;
00923                       if(!find_position(procs,nb_proc,taken[block]-1,t))
00924                         {
00925                           nb_proc++;
00926                           procs = (unsigned int *)realloc(procs,nb_proc*sizeof(unsigned int));
00927                           procs[nb_proc-1]=taken[block]-1;
00928                         }
00929 
00930                       //receive an element that goes out of this node
00931                       if(indexes_nodes[i]==src_nodes_g[j])
00932                         {
00933                           //to receive
00934                           stor_out++;
00935                           tor_out = (unsigned int *)realloc(tor_out,stor_out*sizeof(unsigned int));
00936                           tor_out[stor_out-1] = j;
00937                           
00938                           //construction of degcum_tor,degcum_tos (simple modification of values)
00939                           for(unsigned int k=taken[block];k<Mpi_::mpi_nb+1;k++)
00940                             {
00941                               degcum_tor[k]++;
00942                               degcum_tor_out[k]++;
00943                             }
00944                           //construction of edges_tor,edges_tos,nodes_tor,nodes_tos (reallocation of new tables)
00945                           //unsigned int *edges_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int));
00946                           unsigned int *edges_tor_out_new = (unsigned int *)calloc(degcum_tor_out[Mpi_::mpi_nb],sizeof(unsigned int));
00947                           unsigned int *nodes_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int));
00948                           //values
00949                           //for processors before this one simply make a copy of values
00950                           for(unsigned int k=0;k<taken[block]-1;k++)
00951                             {
00952                               for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++)
00953                                 nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l];
00954                               for(unsigned int l=0;l<degcum_tor_out[k+1]-degcum_tor_out[k];l++)
00955                                 edges_tor_out_new[degcum_tor_out[k]+l] = edges_tor_out[degcum_tor_out[k]+l];
00956                             }
00957                           //for this processor add the new value
00958                           for(unsigned int l=0;l<degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1;l++)
00959                             nodes_tor_new[degcum_tor[taken[block]-1]+l] = nodes_tor[degcum_tor[taken[block]-1]+l];
00960                           for(unsigned int l=0;l<degcum_tor_out[taken[block]]-degcum_tor_out[taken[block]-1]-1;l++)
00961                               edges_tor_out_new[degcum_tor_out[taken[block]-1]+l] = edges_tor_out[degcum_tor_out[taken[block]-1]+l];
00962                           //add the new value
00963                           unsigned int last_tor = degcum_tor[taken[block]-1]+degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1;
00964                           nodes_tor_new[last_tor] = dst_nodes_g[j];
00965                           last_tor = degcum_tor_out[taken[block]-1]+degcum_tor_out[taken[block]]-degcum_tor_out[taken[block]-1]-1;
00966                           edges_tor_out_new[last_tor] = j;
00967                           //for the next processors copy values at a position +1
00968                           for(unsigned int k=taken[block];k<Mpi_::mpi_nb;k++)
00969                             {
00970                               for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++)
00971                                 {
00972                                   //edges_tor_new[degcum_tor[k]+l] = edges_tor[degcum_tor[k]+l-1];
00973                                   nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l-1];
00974                                 }
00975                               for(unsigned int l=0;l<degcum_tor_out[k+1]-degcum_tor_out[k];l++)
00976                                 edges_tor_out_new[degcum_tor_out[k]+l] = edges_tor_out[degcum_tor_out[k]+l-1];
00977                             }
00978 
00979                           /*free(edges_tor);*/free(nodes_tor);
00980                           /*edges_tor = edges_tor_new;*/ nodes_tor = nodes_tor_new;
00981                           free(edges_tor_out);
00982                           edges_tor_out = edges_tor_out_new;
00983                         }
00984                       //receive an element that goes in of this node
00985                       if(indexes_nodes[i]==dst_nodes_g[j])
00986                         {
00987                           //to receive
00988                           stor_in++;
00989                           tor_in = (unsigned int *)realloc(tor_in,stor_in*sizeof(unsigned int));
00990                           tor_in[stor_in-1] = j;
00991 
00992                           //construction of degcum_tor,degcum_tos (simple modification of values)
00993                           for(unsigned int k=taken[block];k<Mpi_::mpi_nb+1;k++)
00994                             {
00995                               degcum_tor[k]++;
00996                               degcum_tor_in[k]++;
00997                             }
00998                           //construction of edges_tor,edges_tos,nodes_tor,nodes_tos (reallocation of new tables)
00999                           //unsigned int *edges_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int));
01000                           unsigned int *edges_tor_in_new = (unsigned int *)calloc(degcum_tor_in[Mpi_::mpi_nb],sizeof(unsigned int));
01001                           unsigned int *nodes_tor_new = (unsigned int *)calloc(degcum_tor[Mpi_::mpi_nb],sizeof(unsigned int));
01002                           //values
01003                           //for processors before this one simply make a copy of values
01004                           for(unsigned int k=0;k<taken[block]-1;k++)
01005                             {
01006                               for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++)
01007                                 {
01008                                   //edges_tor_new[degcum_tor[k]+l] = edges_tor[degcum_tor[k]+l];
01009                                   nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l];
01010                                 }
01011                               for(unsigned int l=0;l<degcum_tor_in[k+1]-degcum_tor_in[k];l++)
01012                                 edges_tor_in_new[degcum_tor_in[k]+l] = edges_tor_in[degcum_tor_in[k]+l];
01013                             }
01014                           //for this processor add the new value
01015                           for(unsigned int l=0;l<degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1;l++)
01016                             {
01017                               //edges_tor_new[degcum_tor[taken[block]-1]+l] = edges_tor[degcum_tor[taken[block]-1]+l];
01018                               nodes_tor_new[degcum_tor[taken[block]-1]+l] = nodes_tor[degcum_tor[taken[block]-1]+l];
01019                             }
01020                           for(unsigned int l=0;l<degcum_tor_in[taken[block]]-degcum_tor_in[taken[block]-1]-1;l++)
01021                             edges_tor_in_new[degcum_tor_in[taken[block]-1]+l] = edges_tor_in[degcum_tor_in[taken[block]-1]+l];
01022                           //add the new value
01023                           unsigned int last_tor = degcum_tor[taken[block]-1]+degcum_tor[taken[block]]-degcum_tor[taken[block]-1]-1;
01024                           nodes_tor_new[last_tor] = src_nodes_g[j];
01025                           last_tor = degcum_tor_in[taken[block]-1]+degcum_tor_in[taken[block]]-degcum_tor_in[taken[block]-1]-1;
01026                           edges_tor_in_new[last_tor] = j;
01027                           //for the next processors copy values at a position +1
01028                           for(unsigned int k=taken[block];k<Mpi_::mpi_nb;k++)
01029                             {
01030                               for(unsigned int l=0;l<degcum_tor[k+1]-degcum_tor[k];l++)
01031                                 {
01032                                   //edges_tor_new[degcum_tor[k]+l] = edges_tor[degcum_tor[k]+l-1];
01033                                   nodes_tor_new[degcum_tor[k]+l] = nodes_tor[degcum_tor[k]+l-1];
01034                                 }
01035                               for(unsigned int l=0;l<degcum_tor_in[k+1]-degcum_tor_in[k];l++)
01036                                 edges_tor_in_new[degcum_tor_in[k]+l] = edges_tor_in[degcum_tor_in[k]+l-1];
01037                             }
01038 
01039                           /*free(edges_tor);*/free(nodes_tor);
01040                           /*edges_tor = edges_tor_new;*/ nodes_tor = nodes_tor_new;
01041                           free(edges_tor_in);
01042                           edges_tor_in = edges_tor_in_new;
01043                         }
01044                     }
01045                 }
01046             }
01047           //sending informations
01048           if(nb_proc>0)
01049             {
01050               bool ro = find_position(roots_g,dim_roots_g,indexes_nodes[i]);
01051               bool le = find_position(leafs_g,dim_leafs_g,indexes_nodes[i]);
01052               if(!ro && !le)
01053                 {
01054                   //communication node
01055                   dim_comm++;
01056                   comm_nodes = (unsigned int *)realloc(comm_nodes,dim_comm*sizeof(unsigned int));
01057                   //current local indexation noted
01058                   comm_nodes[dim_comm-1] = i;
01059                 }
01060               
01061               //sort procs
01062               bool mod=true;
01063               while(mod)
01064                 {
01065                   mod=false;
01066                   for(unsigned int j=1;j<nb_proc;j++)
01067                     {
01068                       if(procs[j]<procs[j-1])
01069                         {
01070                           unsigned int t = procs[j];
01071                           procs[j] = procs[j-1];
01072                           procs[j-1] = t;
01073                           mod=true;
01074                         }
01075                     }
01076                 }
01077               for(unsigned int j=0;j<dim_edge;j++)
01078                 {
01079                   //send an element that is out of another processor
01080                   if(i==dst_nodes[j] || i==src_nodes[j])
01081                     {
01082                       //Needed for communications in advanced DPMap with pointers
01083                       if(i==dst_nodes[j])
01084                         stos_out+=nb_proc;
01085                       else if(i==src_nodes[j])
01086                         stos_in+=nb_proc;
01087 
01088                       //construction of degcum_tor,degcum_tos (simple modification of values)
01089                       for(unsigned int p=0;p<nb_proc;p++)
01090                         {
01091                           for(unsigned int k=procs[p]+1;k<Mpi_::mpi_nb+1;k++)
01092                             {
01093                               degcum_tos[k]++;
01094                               if(i==dst_nodes[j])
01095                                 degcum_tos_out[k]++;
01096                               else if(i==src_nodes[j])
01097                                 degcum_tos_in[k]++;
01098                             }
01099                     
01100                           //construction of edges_tor,edges_tos,nodes_tor,nodes_tos (reallocation of new tables)
01101                           //unsigned int *edges_tos_new = (unsigned int *)calloc(degcum_tos[Mpi_::mpi_nb],sizeof(unsigned int));
01102                           unsigned int *edges_tos_in_new; unsigned int *edges_tos_out_new;
01103                           if(i==src_nodes[j])
01104                             edges_tos_in_new = (unsigned int *)calloc(degcum_tos_in[Mpi_::mpi_nb],sizeof(unsigned int));
01105                           else if(i==dst_nodes[j])
01106                             edges_tos_out_new = (unsigned int *)calloc(degcum_tos_out[Mpi_::mpi_nb],sizeof(unsigned int));
01107                           unsigned int *nodes_tos_new = (unsigned int *)calloc(degcum_tos[Mpi_::mpi_nb],sizeof(unsigned int));
01108                           //values
01109                           //for processors before this one simply make a copy of values
01110                           for(unsigned int k=0;k<procs[p];k++)
01111                             {
01112                               for(unsigned int l=0;l<degcum_tos[k+1]-degcum_tos[k];l++)
01113                                 nodes_tos_new[degcum_tos[k]+l] = nodes_tos[degcum_tos[k]+l];
01114                               if(i==src_nodes[j])
01115                                 {
01116                                   for(unsigned int l=0;l<degcum_tos_in[k+1]-degcum_tos_in[k];l++)
01117                                     edges_tos_in_new[degcum_tos_in[k]+l] = edges_tos_in[degcum_tos_in[k]+l];
01118                                 }
01119                               else if(i==dst_nodes[j])
01120                                 {
01121                                   for(unsigned int l=0;l<degcum_tos_out[k+1]-degcum_tos_out[k];l++)
01122                                     edges_tos_out_new[degcum_tos_out[k]+l] = edges_tos_out[degcum_tos_out[k]+l];
01123                                 }
01124                             }
01125                           //for this processor add the precedent values and the new value
01126                           for(unsigned int l=0;l<degcum_tos[procs[p]+1]-degcum_tos[procs[p]]-1;l++)
01127                             nodes_tos_new[degcum_tos[procs[p]]+l] = nodes_tos[degcum_tos[procs[p]]+l];
01128                           if(i==src_nodes[j])
01129                             {
01130                               for(unsigned int l=0;l<degcum_tos_in[procs[p]+1]-degcum_tos_in[procs[p]]-1;l++)
01131                                 edges_tos_in_new[degcum_tos_in[procs[p]]+l] = edges_tos_in[degcum_tos_in[procs[p]]+l];
01132                             }
01133                           else if(i==dst_nodes[j])
01134                             {
01135                               for(unsigned int l=0;l<degcum_tos_out[procs[p]+1]-degcum_tos_out[procs[p]]-1;l++)
01136                                 edges_tos_out_new[degcum_tos_out[procs[p]]+l] = edges_tos_out[degcum_tos_out[procs[p]]+l];
01137                             }
01138                           //add the new value
01139                           unsigned int last_tos = degcum_tos[procs[p]+1]-1;
01140                           if(i==dst_nodes[j])
01141                             nodes_tos_new[last_tos] = src_nodes[j];
01142                           else if(i==src_nodes[j])
01143                             nodes_tos_new[last_tos] = dst_nodes[j];
01144                           //edges_tos_new[last_tos] = j;
01145                           if(i==src_nodes[j])
01146                             {
01147                               last_tos = degcum_tos_in[procs[p]+1]-1;
01148                               edges_tos_in_new[last_tos] = j;
01149                             }
01150                           else if(i==dst_nodes[j])
01151                             {
01152                               last_tos = degcum_tos_out[procs[p]+1]-1;
01153                               edges_tos_out_new[last_tos] = j;
01154                             }
01155 
01156                           //for the next processors copy values at a position +1
01157                           for(unsigned int k=procs[p]+1;k<Mpi_::mpi_nb;k++)
01158                             {
01159                               for(unsigned int l=0;l<degcum_tos[k+1]-degcum_tos[k];l++)
01160                                 {
01161                                   //edges_tos_new[degcum_tos[k]+l] = edges_tos[degcum_tos[k]+l-1];
01162                                   nodes_tos_new[degcum_tos[k]+l] = nodes_tos[degcum_tos[k]+l-1];
01163                                 }
01164                               if(i==src_nodes[j])
01165                                 {
01166                                   for(unsigned int l=0;l<degcum_tos_in[k+1]-degcum_tos_in[k];l++)
01167                                     edges_tos_in_new[degcum_tos_in[k]+l] = edges_tos_in[degcum_tos_in[k]+l-1];
01168                                 }
01169                               else if(i==dst_nodes[j])
01170                                 {
01171                                   for(unsigned int l=0;l<degcum_tos_out[k+1]-degcum_tos_out[k];l++)
01172                                     edges_tos_out_new[degcum_tos_out[k]+l] = edges_tos_out[degcum_tos_out[k]+l-1];
01173                                 }
01174                             }
01175                           
01176                           /*free(edges_tos);*/free(nodes_tos);
01177                           /*edges_tos = edges_tos_new;*/ nodes_tos = nodes_tos_new;
01178                           if(i==src_nodes[j])
01179                             {
01180                               free(edges_tos_in);
01181                               edges_tos_in = edges_tos_in_new;
01182                             }
01183                           else if(i==dst_nodes[j])
01184                             {
01185                               free(edges_tos_out);
01186                               edges_tos_out = edges_tos_out_new;
01187                             }
01188                         }
01189                     }
01190                 }
01191             }
01192           else
01193             {
01194               bool ro = find_position(roots_g,dim_roots_g,indexes_nodes[i]);
01195               bool le = find_position(leafs_g,dim_leafs_g,indexes_nodes[i]);
01196               if(!ro && !le)
01197                 {
01198                   dim_loc++;
01199                   loc_nodes = (unsigned int *)realloc(loc_nodes,dim_loc*sizeof(unsigned int));
01200                   //current local indexation noted
01201                   loc_nodes[dim_loc-1] = i;
01202                 }
01203             }
01204           free(procs);
01205 
01206           //edges_t_in
01207           //edges_t_out is from 0 to dim_edge but with new indexation edges_t_in can't be so simple and has to be changed
01208           //for each node find in all local edges the node as destination
01209           unsigned int pl=0;
01210           for(unsigned int j=0;j<dim_edge;j++)
01211             {
01212               if(i==dst_nodes[j])
01213                 {
01214                   edges_t_in[degcum_in_t[i]+pl]=j;
01215                   pl++;
01216                 }
01217             }
01218                   
01219           //for this node modify degcum_out,degcum_in,neigh_out,neigh_in,edges_out and edges_in
01220           for(unsigned int j=i+1;j<dim_node+1;j++)
01221             {
01222               degcum_out[j]+=stor_out;
01223               degcum_in[j]+=stor_in;
01224             }
01225 
01226           dim_tor_out+=stor_out;
01227           dim_tor_in+=stor_in;
01228           dim_tos_out+=stos_out;
01229           dim_tos_in+=stos_in;
01230           
01231           //for the current node, modify neigh_out/neigh_in/edges_out/edges_in and indexes_nodes/indexes_edges
01232           neigh_out = (unsigned int *)realloc(neigh_out,degcum_out[i+1]*sizeof(unsigned int));
01233           neigh_in = (unsigned int *)realloc(neigh_in,degcum_in[i+1]*sizeof(unsigned int));
01234           edges_out = (unsigned int *)realloc(edges_out,degcum_out[i+1]*sizeof(unsigned int));
01235           edges_in = (unsigned int *)realloc(edges_in,degcum_in[i+1]*sizeof(unsigned int));
01236 
01237           //these varaibles are used to not hav multiple times the same value in indexes tables and to count the number of elements to add in indexes
01238           unsigned int ind_ed=0;
01239           unsigned int ind_no=0;
01240           //add new elements first for the current node
01241           //in elements to receive
01242           for(unsigned int j=0;j<stor_in;j++)
01243             {
01244               //change the size of indexes tables
01245               indexes_nodes = (unsigned int *)realloc(indexes_nodes,(dim_ind_no+ind_no+1)*sizeof(unsigned int));
01246               indexes_edges = (unsigned int *)realloc(indexes_edges,(dim_ind_ed+ind_ed+1)*sizeof(unsigned int));
01247 
01248               //for edges
01249               //if the index is not already stored add it to indexes when modifying neigh and edges
01250               unsigned int position;
01251               bool found = find_position(indexes_edges,dim_ind_ed+ind_ed,tor_in[j],position);
01252               if(!found)
01253                 {
01254                   //edges_in[degcum_in[i]+j]=dim_ind_ed+ind_ed;
01255                   edges_in[degcum_in[i]+j]=dim_ind_ed+ind_ed;
01256                   indexes_edges[dim_ind_ed+ind_ed]=tor_in[j];
01257                   ind_ed++;
01258                 }
01259               //else use the existing position value
01260               else
01261                 edges_in[degcum_in[i]+j]=position;
01262               //same for nodes
01263               found = find_position(indexes_nodes,dim_ind_no+ind_no,src_nodes_g[tor_in[j]],position);
01264               if(!found)
01265                 {
01266                   neigh_in[degcum_in[i]+j]=dim_ind_no+ind_no;
01267                   indexes_nodes[dim_ind_no+ind_no]=src_nodes_g[tor_in[j]];
01268                   ind_no++;
01269                 }
01270               else
01271                 neigh_in[degcum_in[i]+j]=position;
01272             }
01273           //out elements to receive
01274           dim_ind_no+=ind_no;
01275           dim_ind_ed+=ind_ed;
01276           ind_no=0;
01277           ind_ed=0;
01278           for(unsigned int j=0;j<stor_out;j++)
01279             {
01280               //change the size of indexes tables
01281               indexes_nodes = (unsigned int *)realloc(indexes_nodes,(dim_ind_no+ind_no+1)*sizeof(unsigned int));
01282               indexes_edges = (unsigned int *)realloc(indexes_edges,(dim_ind_ed+ind_ed+1)*sizeof(unsigned int));
01283 
01284               //for edges
01285               //if the index is not already stored add it to indexes when modifying neigh and edges
01286               unsigned int position;
01287               bool found = find_position(indexes_edges,dim_ind_ed+ind_ed,tor_out[j],position);
01288               if(!found)
01289                 {
01290                   edges_out[degcum_out[i]+j]=dim_ind_ed+ind_ed;
01291                   indexes_edges[dim_ind_ed+ind_ed]=tor_out[j];
01292                   ind_ed++;
01293                 }
01294               //else use existing position
01295               else
01296                 edges_out[degcum_out[i]+j]=position;
01297               //for nodes
01298               found = find_position(indexes_nodes,dim_ind_no+ind_no,dst_nodes_g[tor_out[j]],position);
01299               if(!found)
01300                 {
01301                   neigh_out[degcum_out[i]+j]=dim_ind_no+ind_no;
01302                   indexes_nodes[dim_ind_no+ind_no]=dst_nodes_g[tor_out[j]];
01303                   ind_no++;
01304                 }
01305               else
01306                 neigh_out[degcum_out[i]+j]=position;
01307             }
01308           dim_ind_no+=ind_no;
01309           dim_ind_ed+=ind_ed;
01310           //then add local elements for the current node in neigh and edges
01311           for(unsigned int j=0;j<degcum_out_t[i+1]-degcum_out_t[i];j++)
01312             {
01313               edges_out[degcum_out[i]+stor_out+j]=edges_t_out[degcum_out_t[i]+j];
01314               neigh_out[degcum_out[i]+stor_out+j]=neigh_out_t[degcum_out_t[i]+j];
01315             }
01316           for(unsigned int j=0;j<degcum_in_t[i+1]-degcum_in_t[i];j++)
01317             {
01318               edges_in[degcum_in[i]+stor_in+j]=edges_t_in[degcum_in_t[i]+j];
01319               neigh_in[degcum_in[i]+stor_in+j]=neigh_in_t[degcum_in_t[i]+j];
01320             }
01321 
01322           free(tor_out);free(tor_in);
01323         }
01324 
01325       //change indexation of nodes with communication and local nodes
01326       //this is very usefull for a communication/computation time overlap
01327       unsigned int * new_indexes_nodes = (unsigned int *)calloc(dim_ind_no,sizeof(unsigned int));
01328       unsigned int * old_new = (unsigned int *)calloc(dim_ind_no,sizeof(unsigned int));
01329       unsigned int * new_old = (unsigned int *)calloc(dim_ind_no,sizeof(unsigned int));
01330       //foreach old indexation value
01331       unsigned int count = dim_ind_no-1;
01332       for(unsigned int i=0;i<dim_ind_no-dim_node;i++)
01333         {
01334           new_indexes_nodes[count]=indexes_nodes[count];
01335           old_new[count]=count;
01336           new_old[count]=count;
01337           count--;
01338         }
01339       for(unsigned int i=0;i<dim_leafs;i++)
01340         {
01341           new_indexes_nodes[count]=indexes_nodes[count];
01342           old_new[count]=count;
01343           new_old[count]=count;
01344           count--;
01345         }
01346       for(unsigned int i=0;i<dim_roots;i++)
01347         {
01348           new_indexes_nodes[count]=indexes_nodes[count];
01349           old_new[count]=count;
01350           new_old[count]=count;
01351           count--;
01352         }
01353       unsigned int ind=dim_comm-1;
01354       for(unsigned int i=0;i<dim_comm;i++)
01355         {
01356           new_indexes_nodes[count]=indexes_nodes[comm_nodes[ind]];
01357           old_new[comm_nodes[ind]]=count;
01358           new_old[count]=comm_nodes[ind];
01359           ind--;
01360           count--;
01361         }
01362       ind = dim_loc-1;
01363       for(unsigned int i=0;i<dim_loc;i++)
01364         {
01365           new_indexes_nodes[count]=indexes_nodes[loc_nodes[ind]];
01366           old_new[loc_nodes[ind]]=count;
01367           new_old[count]=loc_nodes[ind];
01368           ind--;
01369           count--;
01370         }
01371       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" rcv = "<<dim_ind_no-dim_node<<std::endl;
01372       std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_leafs = "<<dim_leafs<<std::endl;
01373       std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_roots = "<<dim_roots<<std::endl;
01374       std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_comm = "<<dim_comm<<std::endl;
01375       std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_loc = "<<dim_loc<<std::endl;*/
01376 
01377       //delete old indexation
01378       free(indexes_nodes);
01379       indexes_nodes = new_indexes_nodes;
01380 
01381       //change values in data structures using old_new (only nodes concerned to to send values)
01382       for (int i=0;i<dim_edge;i++)
01383         src_nodes[i]=old_new[src_nodes[i]];
01384       for (int i=0;i<dim_edge;i++)
01385         dst_nodes[i]=old_new[dst_nodes[i]];
01386       for (int i=0;i<dim_tos_out+dim_tos_in;i++)
01387         nodes_tos[i]=old_new[nodes_tos[i]];
01388       //for degcum_out/degcum_in/neigh_out/neigh_in/edges_out/edges_in a little more dificult as it is cumulative
01389       unsigned int *new_degcum_out = (unsigned int *)calloc(dim_node+1,sizeof(unsigned int));
01390       unsigned int *new_degcum_in = (unsigned int *)calloc(dim_node+1,sizeof(unsigned int));
01391       unsigned int *new_neigh_out = (unsigned int *)calloc(dim_edge+dim_tor_out,sizeof(unsigned int));
01392       unsigned int *new_neigh_in = (unsigned int *)calloc(dim_edge+dim_tor_in,sizeof(unsigned int));
01393       unsigned int *new_edges_out = (unsigned int *)calloc(dim_edge+dim_tor_out,sizeof(unsigned int));
01394       unsigned int *new_edges_in = (unsigned int *)calloc(dim_edge+dim_tor_in,sizeof(unsigned int));
01395       for(unsigned int i=1;i<dim_node+1;i++)
01396         {
01397           new_degcum_out[i]=new_degcum_out[i-1]+(degcum_out[new_old[i-1]+1]-degcum_out[new_old[i-1]]);
01398           new_degcum_in[i]=new_degcum_in[i-1]+(degcum_in[new_old[i-1]+1]-degcum_in[new_old[i-1]]);
01399 
01400           unsigned int new_st = new_degcum_out[i-1];
01401           unsigned int st = degcum_out[new_old[i-1]];
01402           for(unsigned int j=0;j<new_degcum_out[i]-new_degcum_out[i-1];j++)
01403             {
01404               new_neigh_out[new_st+j]=old_new[neigh_out[st+j]];
01405               new_edges_out[new_st+j]=edges_out[st+j];
01406             }
01407           new_st = new_degcum_in[i-1];
01408           st = degcum_in[new_old[i-1]];
01409           for(unsigned int j=0;j<new_degcum_in[i]-new_degcum_in[i-1];j++)
01410             {
01411               new_neigh_in[new_st+j]=old_new[neigh_in[st+j]];
01412               new_edges_in[new_st+j]=edges_in[st+j];
01413             }
01414         }
01415 
01416       //put local indexes in nodes_tor and edges_tor (global values)
01417       for(unsigned int i=0;i<dim_tor_out;i++)
01418         {
01419           for(unsigned int j=0;j<dim_ind_no;j++)
01420             {
01421               if(indexes_nodes[j]==nodes_tor[i])
01422                 {
01423                   nodes_tor[i] = j;
01424                   break;
01425                 }
01426             }
01427           for(unsigned int j=0;j<dim_ind_ed;j++)
01428             {
01429               if(indexes_edges[j]==edges_tor_out[i])
01430                 {
01431                   edges_tor_out[i] = j;
01432                   break;
01433                 }
01434             }
01435         }
01436       for(unsigned int i=0;i<dim_tor_in;i++)
01437         {
01438           for(unsigned int j=0;j<dim_ind_no;j++)
01439             {
01440               if(indexes_nodes[j]==nodes_tor[dim_tor_out+i])
01441                 {
01442                   nodes_tor[dim_tor_out+i] = j;
01443                   break;
01444                 }
01445             }
01446           for(unsigned int j=0;j<dim_ind_ed;j++)
01447             {
01448               if(indexes_edges[j]==edges_tor_in[i])
01449                 {
01450                   edges_tor_in[i] = j;
01451                   break;
01452                 }
01453             }
01454         }
01455       
01456       
01457 
01458       free(degcum_out);free(degcum_in);free(neigh_out);free(neigh_in);free(edges_out);free(edges_in);
01459       degcum_out=new_degcum_out; degcum_in = new_degcum_in;
01460       neigh_out = new_neigh_out; neigh_in=new_neigh_in;
01461       edges_out=new_edges_out; edges_in=new_edges_in;
01462 
01463       free(old_new);free(new_old);
01464       free(loc_nodes);free(comm_nodes);
01465     }
01466     //-------------------------------------------------------------------------------
01467     //! Distribution
01468     /*!
01469       Read the input file, construct the global data structure, make the distribution and fill the local data structure
01470       \param file is the path to the .dot input file
01471     */
01472     //-------------------------------------------------------------------------------
01473     void distribute(const char * file)
01474     //-------------------------------------------------------------------------------
01475     {
01476       unsigned int dim_node_g,dim_edge_g;
01477       unsigned int *src_nodes_g, *dst_nodes_g;
01478       unsigned int *degcum_out_g, *degcum_in_g;
01479       unsigned int *neigh_out_g, *neigh_in_g;
01480       unsigned int * edges_g;
01481       unsigned int b=0;//number of blocks
01482       unsigned int * edge_block, *degcum_block, *linked_blocks, *edges_subtree;
01483       
01484       //--------------------------------------------------------------------------------
01485       //construction of src_nodes, dst_nodes, dim_node, dim_edge from dot file
01486       //for each line of type "unsigned int -> unsigned int ;" it is an edge of the DAG.
01487       //incrementation of dim_edge and of dim_node
01488       //--------------------------------------------------------------------------------
01489       dim_edge_g=0;
01490       dim_node_g=0;
01491       src_nodes_g=(unsigned int *)calloc(1,sizeof(unsigned int));
01492       dst_nodes_g=(unsigned int *)calloc(1,sizeof(unsigned int));
01493       read(file,dim_node_g,dim_edge_g,src_nodes_g,dst_nodes_g);
01494       dim_node_g++;
01495       //--------------------------------------------------------------------------------
01496       //Identify roots and leafs of the DAG
01497       //--------------------------------------------------------------------------------
01498       unsigned int * roots_g = (unsigned int *)calloc(0,sizeof(unsigned int));
01499       unsigned int * leafs_g = (unsigned int *)calloc(0,sizeof(unsigned int));
01500       unsigned int dim_roots_g=0;
01501       unsigned int dim_leafs_g=0;
01502       findRootsLeafs(dim_node_g, dim_edge_g, src_nodes_g, dst_nodes_g, dim_roots_g, dim_leafs_g, roots_g, leafs_g);
01503       //--------------------------------------------------------------------------------
01504       //Global data structure creation + edge_block
01505       //--------------------------------------------------------------------------------
01506       unsigned int mean_edges = 0;
01507       unsigned int max_edges = 0;
01508       edge_block = (unsigned int *)calloc(0,sizeof(unsigned int));
01509       globalDS(dim_edge_g,dim_node_g,src_nodes_g,dst_nodes_g,degcum_in_g,degcum_out_g,neigh_out_g,neigh_in_g,edges_g,edge_block,mean_edges,max_edges,b);
01510       //--------------------------------------------------------------------------------
01511       //Prepare data for distribution : degcum_block and linked_blocks and edges_subtree
01512       //--------------------------------------------------------------------------------
01513       degcum_block = (unsigned int *)calloc(b+1,sizeof(unsigned int));
01514       linked_blocks = (unsigned int *)calloc(1,sizeof(unsigned int));
01515       edges_subtree = (unsigned int *)calloc(b,sizeof(unsigned int));
01516       dataDistr(b,edges_g,edge_block,dst_nodes_g,degcum_out_g,degcum_block,linked_blocks,edges_subtree);
01517       //--------------------------------------------------------------------------------
01518       //DISTRIBUTION
01519       //--------------------------------------------------------------------------------
01520       /*
01521         The algorithm works this way :
01522         =TODO= ideal is the ideal number of edges needed per each processor for a perfect distribution
01523         =TODO= edges of the DAG can be ponderate by a weight, the ideal number take into acount this weight
01524         Edges are not managed independently. All sister edges are together in a block, and each is gonna be distribute amoung processors (table taken)
01525         All edges of a block are taken by a same processor
01526         1) foreach block (this is a sort of queue of blocks to deal with) - each time we reach this point the end of a subtree has been reached or we make the distribution for another processor
01527         2) try to get the new block
01528         3) if the new block is the first one, check if a brother block is not isolated or take it
01529         4) construct the list of outpt blocks and enter the recursive distribution call dist(...)
01530         5) When you get out of this recursive call it is because the ideal number has been reached for the processor or because the end of the subtree has been reached for this block
01531        */
01532       //table to know if a block is taken by a processor
01533       unsigned int *taken = (unsigned int *)calloc(b,sizeof(unsigned int));
01534       //to count the current number of edges taken
01535       unsigned int count=0;
01536       //the ideal number of edges to take
01537       unsigned int ideal = static_cast<unsigned int>(floor(dim_edge_g/Mpi_::mpi_nb)) +1;
01538       //std::cout<<"\nideal = "<<ideal<<"\n";
01539       //total number of edges that are not taken
01540       unsigned int edges_r = dim_edge_g;
01541       //current processor
01542       int cur_proc=0;
01543 
01544       for(unsigned int i=0;i<b;i++)
01545         {
01546           if(count<ideal)
01547             {
01548               if(taken[i]==0)
01549                 {
01550                   //new ideal value si calculated at each knew processor to manage
01551                   if(count==0)
01552                     ideal = static_cast<unsigned int>(floor(edges_r/(Mpi_::mpi_nb-cur_proc)));
01553 
01554                   if(count+edge_block[i+1]-edge_block[i]<=ideal)
01555                     {
01556                       count+=edge_block[i+1]-edge_block[i];
01557                       taken[i] = cur_proc+1;
01558 
01559                       if(count-(edge_block[i+1]-edge_block[i])==0)
01560                         {
01561                           //particular case only if count==0 before this node
01562                           if(count<ideal && count+edge_block[i+2]-edge_block[i+1]<=ideal+mean_edges)
01563                             {
01564                               //we verify if the next block is not getting out of the current one
01565                               bool found=false;
01566                               for(unsigned int j=0;j<degcum_block[i+1]-degcum_block[i];j++)
01567                                 {
01568                                   if(linked_blocks[degcum_block[i]+j]==1)
01569                                     {found=true;break;}
01570                                 }
01571                               //if the next block is not already taken and that it does not have any output block, we take it to not isolate it
01572                               if(taken[i+1]==0 && found==false && degcum_block[i+2]==degcum_block[i+1])
01573                                 {
01574                                   count+=edge_block[i+2]-edge_block[i+1];
01575                                   taken[i+1]=cur_proc+1;
01576                                 }
01577                               //if the next block is not already taken and that it does have a single output block
01578                               else if(taken[i+1]==0 && found==false && degcum_block[i+2]==degcum_block[i+1]+1 && edges_subtree[linked_blocks[i+2]]==edge_block[i+2]-edge_block[i+1])
01579                                 {
01580                                   count+=edge_block[i+2]-edge_block[i+1];
01581                                   taken[i+1]=cur_proc+1;
01582                                 }
01583                             }
01584                         }
01585                       if(count<ideal)
01586                         {
01587                           unsigned int size = degcum_block[i+1]-degcum_block[i];
01588                           unsigned int *edge_b_loc = (unsigned int *)calloc(size,sizeof(unsigned int));
01589                           unsigned int *index = (unsigned int *)calloc(size,sizeof(unsigned int));
01590 
01591                           for(unsigned int j=0;j<size;j++)
01592                             {
01593                               index[j] = linked_blocks[degcum_block[i]+j];
01594                               edge_b_loc[j] = edge_block[index[j]+1]-edge_block[index[j]];
01595                             }
01596                           //recursive call
01597                           dist(mean_edges, edges_r,index,edge_b_loc,size,ideal,edge_block,degcum_block,linked_blocks,taken,edges_subtree,count,cur_proc);
01598                           verif(index,edge_b_loc,size,degcum_block,linked_blocks,taken,count);
01599                           free(index);
01600                           free(edge_b_loc);
01601                           if(count>=ideal)
01602                             {
01603                               //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n";
01604                               if(cur_proc==Mpi_::mpi_rank)
01605                                 dim_edge = count;
01606                               edges_r -= count;
01607                               count = 0;
01608                               cur_proc++;
01609                             }
01610                         }
01611                       else
01612                         {
01613                           //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n";
01614                           if(cur_proc==Mpi_::mpi_rank)
01615                             dim_edge = count;
01616                           edges_r -= count;
01617                           count = 0;
01618                           cur_proc++;
01619                         }
01620                     }
01621                   else
01622                     {
01623                       //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n";
01624                       if(cur_proc==Mpi_::mpi_rank)
01625                         dim_edge = count;
01626                       edges_r -= count;
01627                       count = 0;
01628                       cur_proc++;
01629                       i=i-1;
01630                     }
01631                 }
01632             }
01633           else
01634             {
01635               //std::cout<<"Number of edges for proc "<<cur_proc<<" is "<<count<<"\n";
01636               if(cur_proc==Mpi_::mpi_rank)
01637                 dim_edge = count;
01638               edges_r -= count;
01639               count = 0;
01640               cur_proc++;
01641             }
01642         }
01643       /*std::cout<<std::endl;
01644       std::cout<<"Proc "<<Mpi_::mpi_rank<<" taken = ";
01645       for (int i=0;i<b;i++)
01646         std::cout<<taken[i]<<" ";
01647         std::cout<<std::endl;*/
01648 
01649       //--------------------------------------------------------------------------------
01650       //FILL Parallel data structure
01651       //--------------------------------------------------------------------------------
01652       //with taken, edge_block & edges_g we can construct the local data structure has done before for the global one
01653       //with degcum_block & linked_blocks we can get where communications are needed in the local data structure
01654       //--------------------------------------------------------------------------------
01655       //local src_nodes & dst_nodes
01656       //--------------------------------------------------------------------------------
01657       src_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01658       dst_nodes = (unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01659       indexes_edges = (unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01660       unsigned int * edges_t_out=(unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01661       unsigned int * edges_t_in=(unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01662       localSrcDstNodes(b,taken,edge_block,src_nodes_g,dst_nodes_g,edges_g,dim_roots_g,dim_leafs_g,roots_g,leafs_g/*,src_nodes,dst_nodes,indexes_edges,indexes_nodes,dim_edge,dim_node*/);
01663       //std::cout<<"Proc "<<Mpi_::mpi_rank<<" dim_node="<<dim_node<<std::endl;
01664       //--------------------------------------------------------------------------------
01665       //free global and distribution tables
01666       //--------------------------------------------------------------------------------
01667       free(degcum_out_g);free(degcum_in_g);
01668       free(neigh_out_g);free(neigh_in_g);
01669       free(edges_g);
01670       free(degcum_block);free(linked_blocks);free(edges_subtree);
01671       //--------------------------------------------------------------------------------
01672       //construction of local degcum_out and degcum_in :
01673       //represents the cumulative number of inputs and outputs nodes and edges of a node
01674       //--------------------------------------------------------------------------------
01675       unsigned int *deg_in2=(unsigned int *)calloc(dim_node,sizeof(unsigned int));
01676       unsigned int *deg_out2=(unsigned int *)calloc(dim_node,sizeof(unsigned int));
01677       for(unsigned int i=0;i<dim_edge;i++)
01678         {
01679           deg_out2[src_nodes[i]]++;
01680           deg_in2[dst_nodes[i]]++;
01681         }
01682       degcum_in=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int));
01683       degcum_out=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int));
01684       for(unsigned int i=1;i<dim_node+1;i++)
01685         {
01686           degcum_out[i]=degcum_out[i-1]+deg_out2[i-1];
01687           degcum_in[i]=degcum_in[i-1]+deg_in2[i-1];
01688         }
01689       free(deg_in2),free(deg_out2);
01690       //--------------------------------------------------------------------------------
01691       //--------------------------------------------------------------------------------
01692       //TEMPORARY DATA
01693       //--------------------------------------------------------------------------------
01694       //degcum_in_t and degcum_out_t = degcum_in and degcum_out to keep the pure local values (without communications problems)
01695       //--------------------------------------------------------------------------------
01696       unsigned int *degcum_in_t=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int));
01697       unsigned int *degcum_out_t=(unsigned int *)calloc(dim_node+1,sizeof(unsigned int));
01698       for(unsigned int i=0;i<dim_node+1;i++)
01699         {
01700           degcum_in_t[i] = degcum_in[i];
01701           degcum_out_t[i] = degcum_out[i];
01702         }
01703 
01704       //--------------------------------------------------------------------------------
01705       //neigh_out_t and neigh_in_t and edges_t to keep the pure local values (without communications problems)
01706       //--------------------------------------------------------------------------------
01707       unsigned int * t_in=(unsigned int *)calloc(dim_node,sizeof(unsigned int));
01708       unsigned int * t_out=(unsigned int *)calloc(dim_node,sizeof(unsigned int));
01709 
01710       unsigned int * neigh_in_t=(unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01711       unsigned int * neigh_out_t=(unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01712       //unsigned int * edges_t_out=(unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01713       //unsigned int * edges_t_in=(unsigned int *)calloc(dim_edge,sizeof(unsigned int));
01714 
01715       for (int i=0;i<dim_edge;i++) 
01716         {
01717           neigh_out_t[ degcum_out[src_nodes[i]] + t_out[ src_nodes[i] ]++ ]=dst_nodes[i];
01718           neigh_in_t[ degcum_in[dst_nodes[i]] + t_in[ dst_nodes[i] ]++ ]=src_nodes[i];
01719           edges_t_out[i]=i;
01720           //edges_t_in[i]=;
01721         }
01722       free(t_out),free(t_in);
01723       //--------------------------------------------------------------------------------
01724       //--------------------------------------------------------------------------------
01725 
01726       //--------------------------------------------------------------------------------
01727       //we have to add edges and nodes for parallelization and communications
01728       //to do that search root and leaf nodes of the local structure
01729       //found their direct (distance 1) neighbors in the global data structure
01730       //construct degcum_tos and degcum_tor and associated edges_tos, edges_tor, nodes_tos, nodes_tor
01731       //indexes of new elements have to be higher than local elements (at the end of every local data structure)
01732       //--------------------------------------------------------------------------------
01733       neigh_out = (unsigned int *)calloc(0,sizeof(unsigned int));
01734       neigh_in = (unsigned int *)calloc(0,sizeof(unsigned int));
01735       edges_out = (unsigned int *)calloc(0,sizeof(unsigned int));
01736       edges_in = (unsigned int *)calloc(0,sizeof(unsigned int));
01737       //edges_tor = (unsigned int *)calloc(0,sizeof(unsigned int));
01738       edges_tor_in = (unsigned int *)calloc(0,sizeof(unsigned int));
01739       edges_tor_out = (unsigned int *)calloc(0,sizeof(unsigned int));
01740       //edges_tos = (unsigned int *)calloc(0,sizeof(unsigned int));
01741       edges_tos_in = (unsigned int *)calloc(0,sizeof(unsigned int));
01742       edges_tos_out = (unsigned int *)calloc(0,sizeof(unsigned int));
01743       nodes_tor = (unsigned int *)calloc(0,sizeof(unsigned int));
01744       nodes_tos = (unsigned int *)calloc(0,sizeof(unsigned int));
01745       fillLocalDS(b,dim_edge_g,dst_nodes_g,src_nodes_g,edge_block,taken,degcum_out_t,degcum_in_t,edges_t_out,edges_t_in,neigh_out_t,neigh_in_t,roots_g,leafs_g,dim_roots_g,dim_leafs_g);
01746       free(degcum_in_t);free(degcum_out_t);
01747       free(neigh_out_t);free(neigh_in_t);free(edges_t_out);free(edges_t_in);
01748       free(roots_g);free(leafs_g);
01749       free(edge_block);
01750       free(taken);
01751       free(src_nodes_g);free(dst_nodes_g);
01752       //---------------------------------------------------------
01753       //PRINTINGS
01754       //---------------------------------------------------------
01755       /*std::cout<<std::endl;
01756       std::cout<<"Proc "<<Mpi_::mpi_rank<<" src_nodes = ";
01757       for (int i=0;i<dim_edge;i++)
01758         std::cout<<src_nodes[i]<<" ";
01759       std::cout<<std::endl;
01760       std::cout<<"Proc "<<Mpi_::mpi_rank<<" dst_nodes = ";
01761       for (int i=0;i<dim_edge;i++)
01762         std::cout<<dst_nodes[i]<<" ";
01763         std::cout<<std::endl;
01764       */
01765       /*std::cout<<std::endl;
01766       std::cout<<"Proc "<<Mpi_::mpi_rank<<" indexes_nodes = ";
01767       for (int i=0;i<dim_ind_no;i++)
01768         std::cout<<indexes_nodes[i]<<" ";
01769         std::cout<<std::endl;*/
01770       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" indexes_edges = ";
01771       for (int i=0;i<dim_ind_ed;i++)
01772         std::cout<<indexes_edges[i]<<" ";
01773         std::cout<<std::endl;*/
01774       /*
01775       std::cout<<std::endl;
01776       std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_out = ";
01777       for (int i=1;i<dim_node+1;i++)
01778         std::cout<<degcum_out[i]<<" ";
01779         std::cout<<std::endl;*/
01780       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_in = ";
01781       for (int i=1;i<dim_node+1;i++)
01782         std::cout<<degcum_in[i]<<" ";
01783         std::cout<<std::endl;*/
01784       
01785         /*std::cout<<std::endl;
01786       std::cout<<"Proc "<<Mpi_::mpi_rank<<" neigh_out = ";
01787       for (int i=0;i<dim_edge+dim_tor_out;i++)
01788         std::cout<<neigh_out[i]<<" ";
01789         std::cout<<std::endl;
01790       std::cout<<"Proc "<<Mpi_::mpi_rank<<" neigh_in = ";
01791       for (int i=0;i<dim_edge+dim_tor_in;i++)
01792         std::cout<<neigh_in[i]<<" ";
01793         std::cout<<std::endl;
01794       */
01795       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_out = ";
01796       for (int i=0;i<dim_edge+dim_tor_out;i++)
01797         std::cout<<edges_out[i]<<" ";
01798         std::cout<<std::endl;*/
01799       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_in = ";
01800       for (int i=0;i<dim_edge+dim_tor_in;i++)
01801         std::cout<<edges_in[i]<<" ";
01802         std::cout<<std::endl;*/
01803       
01804       //std::cout<<std::endl;
01805       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tor = ";
01806       for (int i=1;i<Mpi_::mpi_nb+1;i++)
01807         std::cout<<degcum_tor[i]<<" ";
01808         std::cout<<std::endl;*/
01809         /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tos = ";
01810       for (int i=0;i<Mpi_::mpi_nb+1;i++)
01811         std::cout<<degcum_tos[i]<<" ";
01812         std::cout<<std::endl;*/
01813 
01814       //std::cout<<std::endl;
01815       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tor_in = ";
01816       for (int i=1;i<Mpi_::mpi_nb+1;i++)
01817         std::cout<<degcum_tor_in[i]<<" ";
01818       std::cout<<std::endl;
01819       std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tos_in = ";
01820       for (int i=0;i<Mpi_::mpi_nb+1;i++)
01821         std::cout<<degcum_tos_in[i]<<" ";
01822       std::cout<<std::endl;
01823 
01824       //std::cout<<std::endl;
01825       std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tor_out = ";
01826       for (int i=1;i<Mpi_::mpi_nb+1;i++)
01827         std::cout<<degcum_tor_out[i]<<" ";
01828       std::cout<<std::endl;
01829       std::cout<<"Proc "<<Mpi_::mpi_rank<<" degcum_tos_out = ";
01830       for (int i=0;i<Mpi_::mpi_nb+1;i++)
01831         std::cout<<degcum_tos_out[i]<<" ";
01832         std::cout<<std::endl;*/
01833       
01834       //std::cout<<std::endl;
01835       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tor = ";
01836       for (int i=0;i<dim_tor_out+dim_tor_in;i++)
01837         std::cout<<edges_tor[i]<<" ";
01838         std::cout<<std::endl;*/
01839       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tos = ";
01840       for (int i=0;i<dim_tos_out+dim_tos_in;i++)
01841         std::cout<<edges_tos[i]<<" ";
01842         std::cout<<std::endl;*/
01843 
01844       //std::cout<<std::endl;
01845       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tor_in = ";
01846       for (int i=0;i<dim_tor_in;i++)
01847         std::cout<<edges_tor_in[i]<<" ";
01848         std::cout<<std::endl;*/
01849       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tos_in = ";
01850       for (int i=0;i<dim_tos_in;i++)
01851         std::cout<<edges_tos_in[i]<<" ";
01852         std::cout<<std::endl;*/
01853 
01854       //std::cout<<std::endl;
01855       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tor_out = ";
01856       for (int i=0;i<dim_tor_out;i++)
01857         std::cout<<edges_tor_out[i]<<" ";
01858         std::cout<<std::endl;*/
01859       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" edges_tos_out = ";
01860       for (int i=0;i<dim_tos_out;i++)
01861         std::cout<<edges_tos_out[i]<<" ";
01862         std::cout<<std::endl;*/
01863 
01864       /*std::cout<<"Proc "<<Mpi_::mpi_rank<<" nodes_tor = ";
01865       for (int i=0;i<dim_tor_out+dim_tor_in;i++)
01866         std::cout<<nodes_tor[i]<<" ";
01867       std::cout<<std::endl;
01868       std::cout<<"Proc "<<Mpi_::mpi_rank<<" nodes_tos = ";
01869       for (int i=0;i<dim_tos_out+dim_tos_in;i++)
01870         std::cout<<nodes_tos[i]<<" ";
01871         std::cout<<std::endl;*/
01872     }
01873     //-------------------------------------------------------------------------------
01874     //! Initialization of the DDAG_impl
01875     /*!
01876       \param file is the path to the .dot input file
01877     */
01878     //-------------------------------------------------------------------------------
01879     void init(const char * file)
01880     //-------------------------------------------------------------------------------
01881     {
01882       degcum_in = NULL;degcum_out = NULL;neigh_in = NULL;neigh_out = NULL;edges_out = NULL;edges_in=NULL;src_nodes = NULL;dst_nodes = NULL;indexes_nodes=NULL;indexes_edges=NULL;
01883       degcum_tos = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int));
01884       degcum_tos_in = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int));
01885       degcum_tos_out = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int));
01886       degcum_tor = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int));
01887       degcum_tor_in = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int));
01888       degcum_tor_out = (unsigned int *)calloc(Mpi_::mpi_nb+1,sizeof(unsigned int));
01889       /*edges_tor=NULL;*/edges_tor_in=NULL;edges_tor_out=NULL;/*edges_tos=NULL;*/edges_tos_in=NULL;edges_tos_out=NULL;nodes_tor=NULL;nodes_tos=NULL;
01890       dim_node=0;dim_edge=0;dim_roots=0;dim_leafs=0;dim_comm=0;dim_loc=0;
01891       dim_tor_out=0;dim_tor_in=0;dim_tos_out=0;dim_tos_in=0;
01892       //lecture du .dot, construction d'une structure séquentielle temporaire
01893       //algo distribution
01894       //remplissage structure locale
01895       distribute(file);
01896     }
01897     //-------------------------------------------------------------------------------
01898 
01899   public:
01900 
01901     //-------------------------------------------------------------------------------
01902     //! Constructor of the DDAG_impl
01903     /*!
01904       \param path to the input .dot file
01905     */
01906     //-------------------------------------------------------------------------------
01907     DDAG_impl(const char * file)
01908     //-------------------------------------------------------------------------------
01909     {
01910       //read file
01911       //distribution algorithm
01912       //data structure construction
01913       init(file);
01914     }
01915     //-------------------------------------------------------------------------------
01916     //! Destructor of the DDAG_impl
01917     /*!
01918     */
01919     //-------------------------------------------------------------------------------
01920     ~DDAG_impl()
01921     //-------------------------------------------------------------------------------
01922     {
01923       if(NULL!=degcum_in)
01924         free(degcum_in);
01925       if(NULL!=degcum_out)
01926         free(degcum_out);
01927       if(NULL!=neigh_in)
01928         free(neigh_in);
01929       if(NULL!=neigh_out)
01930         free(neigh_out);
01931       if(NULL!=edges_out)
01932         free(edges_out);
01933       if(NULL!=edges_in)
01934         free(edges_in);
01935       if(NULL!=src_nodes)
01936         free(src_nodes);
01937       if(NULL!=dst_nodes)
01938         free(dst_nodes);
01939       if(NULL!=indexes_nodes)
01940         free(indexes_nodes);
01941       if(NULL!=indexes_edges)
01942         free(indexes_edges);
01943       if(NULL!=degcum_tos)
01944         free(degcum_tos);
01945       if(NULL!=degcum_tos_in)
01946         free(degcum_tos_in);
01947       if(NULL!=degcum_tos_out)
01948         free(degcum_tos_out);
01949       if(NULL!=degcum_tor)
01950         free(degcum_tor);
01951       if(NULL!=degcum_tor_in)
01952         free(degcum_tor_in);
01953       if(NULL!=degcum_tor_out)
01954         free(degcum_tor_out);
01955       /*if(NULL!=edges_tor)
01956         free(edges_tor);*/
01957       /*if(NULL!=edges_tos)
01958         free(edges_tos);*/
01959       if(NULL!=edges_tor_in)
01960         free(edges_tor_in);
01961       if(NULL!=edges_tos_in)
01962         free(edges_tos_in);
01963       if(NULL!=edges_tor_out)
01964         free(edges_tor_out);
01965       if(NULL!=edges_tos_out)
01966         free(edges_tos_out);
01967       if(NULL!=nodes_tor)
01968         free(nodes_tor);
01969       if(NULL!=nodes_tos)
01970         free(nodes_tos);
01971     }
01972     //-------------------------------------------------------------------------------
01973     //! get the number of nodes
01974     /*!
01975       \return dim_node the number of nodes in the local data structure
01976     */
01977     //-------------------------------------------------------------------------------
01978     inline unsigned int getDimNode(){return dim_node;}
01979     //-------------------------------------------------------------------------------
01980     //! get the number of edges
01981     /*!
01982       \return dim_edge the number of edges in the local data structure
01983     */
01984     //-------------------------------------------------------------------------------
01985     inline unsigned int getDimEdge(){return dim_edge;}
01986     //-------------------------------------------------------------------------------
01987     //! get the number of pure local nodes
01988     /*!
01989       \return dim_node the number of pure local nodes
01990     */
01991     //-------------------------------------------------------------------------------
01992     inline unsigned int getDimLoc(){return dim_loc;}
01993     //-------------------------------------------------------------------------------
01994     //! get the number of communication nodes
01995     /*!
01996       \return dim_node the number of communication nodes
01997     */
01998     //-------------------------------------------------------------------------------
01999     inline unsigned int getDimComm(){return dim_comm;}
02000     //-------------------------------------------------------------------------------
02001     //! get the number of roots nodes
02002     /*!
02003       \return dim_node the number of roots nodes
02004     */
02005     //-------------------------------------------------------------------------------
02006     inline unsigned int getDimRoots(){return dim_roots;}
02007     //-------------------------------------------------------------------------------
02008     //! get the number of leafs nodes
02009     /*!
02010       \return dim_node the number of leafs nodes
02011     */
02012     //-------------------------------------------------------------------------------
02013     inline unsigned int getDimLeafs(){return dim_leafs;}
02014     //-------------------------------------------------------------------------------
02015     //! get the number of elements to receive in
02016     /*!
02017       \return the number of elements
02018     */
02019     //-------------------------------------------------------------------------------
02020     inline unsigned int getDimTorIn(){return dim_tor_in;}
02021     //-------------------------------------------------------------------------------
02022     //! get the number of elements to receive out
02023     /*!
02024       \return the number of elements
02025     */
02026     //-------------------------------------------------------------------------------
02027     inline unsigned int getDimTorOut(){return dim_tor_out;}
02028     //-------------------------------------------------------------------------------
02029     //! get the global index of a local node
02030     /*!
02031       \return the global index of a local node
02032     */
02033     //-------------------------------------------------------------------------------
02034     inline unsigned int getIndexNode(unsigned int ind){return indexes_nodes[ind];}
02035     //-------------------------------------------------------------------------------
02036     //! get the global index of a local edge
02037     /*!
02038       \return the global index of a local edge
02039     */
02040     //-------------------------------------------------------------------------------
02041     inline unsigned int getIndexEdge(unsigned int ind){return indexes_edges[ind];}
02042     //-------------------------------------------------------------------------------
02043     //!  to get the iterator rank on the source node of the index edge
02044     /*!
02045       \return the iterator rank on the source node
02046     */
02047     //-------------------------------------------------------------------------------
02048     inline unsigned int getSrcNode(unsigned int r){return src_nodes[r];}
02049     //-------------------------------------------------------------------------------
02050     //!  to get the iterator rank on the destination node of the index edge
02051     /*!
02052       \return the iterator rank on the destination node
02053     */
02054     //-------------------------------------------------------------------------------
02055     inline unsigned int getDstNode(unsigned int r){return dst_nodes[r];}
02056     //-------------------------------------------------------------------------------
02057     //!  to get a vector of iterator on input edges for the node at rank r
02058     /*!
02059       \param r is the rank of the node to get in edges
02060       \return a vector of iterator
02061     */
02062     //-------------------------------------------------------------------------------
02063     std::vector<iterator_dag> getInEdges(unsigned int r)
02064     {
02065       std::vector<iterator_dag> v;
02066       for(int i=degcum_in[r];i<degcum_in[r+1];i++)
02067           v.push_back(iterator_dag(edges_in[i]));
02068       return v;
02069     }
02070     //-------------------------------------------------------------------------------
02071     //!  to get a vector of iterator on output edges for the node at rank r
02072     /*!
02073       \param r is the rank of the node to get out edges
02074       \return a vector of iterator
02075     */
02076     //-------------------------------------------------------------------------------
02077     std::vector<iterator_dag> getOutEdges(unsigned int r)
02078     {
02079       std::vector<iterator_dag> v;
02080       for(int i=degcum_out[r];i<degcum_out[r+1];i++)
02081           v.push_back(iterator_dag(edges_out[i]));
02082       return v;
02083     }
02084     //-------------------------------------------------------------------------------
02085     //!  to get a vector of iterator on input nodes for the node at rank r
02086     /*!
02087       \param r is the rank of the node to get in nodes
02088       \return a vector of iterator
02089     */
02090     //-------------------------------------------------------------------------------
02091     std::vector<iterator_dag> getInNodes(unsigned int r)
02092     {
02093       std::vector<iterator_dag> v;
02094       for(int i=degcum_in[r];i<degcum_in[r+1];i++)
02095           v.push_back(iterator_dag(neigh_in[i]));
02096       return v;
02097     }
02098     //-------------------------------------------------------------------------------
02099     //!  to get a vector of iterator on output nodes for the node at rank r
02100     /*!
02101       \param r is the rank of the node to get out nodes
02102       \return a vector of iterator
02103     */
02104     //-------------------------------------------------------------------------------
02105     std::vector<iterator_dag> getOutNodes(unsigned int r)
02106     {
02107       std::vector<iterator_dag> v;
02108       for(int i=degcum_out[r];i<degcum_out[r+1];i++)
02109           v.push_back(iterator_dag(neigh_out[i]));
02110       return v;
02111     }
02112     //-------------------------------------------------------------------------------
02113     //!  to get the number of elements to send to a precised processor rank
02114     /*!
02115       \param rank is the rank of the processor to send elements to
02116       \return the number of elements to send to this processor
02117     */
02118     //-------------------------------------------------------------------------------
02119     inline unsigned int getNbNodesToSend(unsigned int rank){return degcum_tos[rank+1]-degcum_tos[rank];}
02120     //-------------------------------------------------------------------------------
02121     //!  to fill a table with indexes to send to other processors
02122     /*!
02123       \param rank is the rank of the processor to send data to
02124       \return a table with indexes to send
02125     */
02126     //-------------------------------------------------------------------------------
02127     unsigned int * getNodesToSend(unsigned int rank)
02128     //-------------------------------------------------------------------------------
02129     {
02130       unsigned int * ret = (unsigned int *)calloc(degcum_tos[rank+1]-degcum_tos[rank],sizeof(unsigned int));
02131       for(unsigned int i=0;i<degcum_tos[rank+1]-degcum_tos[rank];i++)
02132           ret[i] = nodes_tos[degcum_tos[rank]+i];
02133 
02134       return ret;
02135     }
02136     //-------------------------------------------------------------------------------
02137     //!  to get the number of edges to send to a precised processor rank
02138     /*!
02139       \param rank is the rank of the processor to send edges to
02140       \return the number of edges to send to this processor
02141     */
02142     //-------------------------------------------------------------------------------
02143     inline unsigned int getNbEdgesToSend(unsigned int rank){return (degcum_tos_in[rank+1]+degcum_tos_out[rank+1])-(degcum_tos_in[rank]+degcum_tos_out[rank]);}
02144     //-------------------------------------------------------------------------------
02145     //!  to get the number of edges to send in to a precised processor rank
02146     /*!
02147       \param rank is the rank of the processor to send edges to
02148       \return the number of edges to send in to this processor
02149     */
02150     //-------------------------------------------------------------------------------
02151     inline unsigned int getNbEdgesToSendIn(unsigned int rank){return degcum_tos_in[rank+1]-degcum_tos_in[rank];}
02152     //-------------------------------------------------------------------------------
02153     //!  to get the number of edges to send out to a precised processor rank, those edges go inside the processor rank
02154     /*!
02155       \param rank is the rank of the processor to send edges to
02156       \return the number of edges to send out to this processor
02157     */
02158     //-------------------------------------------------------------------------------
02159     inline unsigned int getNbEdgesToSendOut(unsigned int rank){return degcum_tos_out[rank+1]-degcum_tos_out[rank];}
02160     //-------------------------------------------------------------------------------
02161     //!  to fill a table with indexes to send to other processors, those edges go outside the processor rank
02162     /*!
02163       \param rank is the rank of the processor to send data to
02164       \return a table with indexes to send
02165     */
02166     //-------------------------------------------------------------------------------
02167     unsigned int * getEdgesToSend(unsigned int rank)
02168     //-------------------------------------------------------------------------------
02169     {
02170       unsigned int * ret = (unsigned int *)calloc((degcum_tos_in[rank+1]+degcum_tos_out[rank+1])-(degcum_tos_in[rank]+degcum_tos_out[rank]),sizeof(unsigned int));
02171       for(unsigned int i=0;i<degcum_tos_in[rank+1]-degcum_tos_in[rank];i++)
02172         ret[i] = edges_tos_in[degcum_tos_in[rank]+i];
02173       for(unsigned int i=0;i<degcum_tos_out[rank+1]-degcum_tos_out[rank];i++)
02174         ret[degcum_tos_in[rank+1]-degcum_tos_in[rank]+i] = edges_tos_out[degcum_tos_out[rank]+i];
02175 
02176       return ret;
02177     }
02178     //-------------------------------------------------------------------------------
02179     //!  to fill a table with indexes to send in to other processors
02180     /*!
02181       \param rank is the rank of the processor to send in data to
02182       \return a table with indexes to send in
02183     */
02184     //-------------------------------------------------------------------------------
02185     unsigned int * getEdgesToSendIn(unsigned int rank)
02186     //-------------------------------------------------------------------------------
02187     {
02188       unsigned int * ret = (unsigned int *)calloc(degcum_tos_in[rank+1]-degcum_tos_in[rank],sizeof(unsigned int));
02189       for(unsigned int i=0;i<degcum_tos_in[rank+1]-degcum_tos_in[rank];i++)
02190         ret[i] = edges_tos_in[degcum_tos_in[rank]+i];
02191 
02192       return ret;
02193     }
02194     //-------------------------------------------------------------------------------
02195     //!  to fill a table with indexes to send out to other processors
02196     /*!
02197       \param rank is the rank of the processor to send out data to
02198       \return a table with indexes to send out
02199     */
02200     //-------------------------------------------------------------------------------
02201     unsigned int * getEdgesToSendOut(unsigned int rank)
02202     //-------------------------------------------------------------------------------
02203     {
02204       unsigned int * ret = (unsigned int *)calloc(degcum_tos_out[rank+1]-degcum_tos_out[rank],sizeof(unsigned int));
02205       for(unsigned int i=0;i<degcum_tos_out[rank+1]-degcum_tos_out[rank];i++)
02206         ret[degcum_tos_in[rank+1]-degcum_tos_in[rank]+i] = edges_tos_out[degcum_tos_out[rank]+i];
02207 
02208       return ret;
02209     }
02210     //-------------------------------------------------------------------------------
02211     //!  to get the number of elements to receive to a precised processor rank
02212     /*!
02213       \param rank is the rank of the processor to receive elements to
02214       \return the number of elements to receive to this processor
02215     */
02216     //-------------------------------------------------------------------------------
02217     inline unsigned int getNbNodesToRecv(unsigned int rank){return degcum_tor[rank+1]-degcum_tor[rank];}
02218     //-------------------------------------------------------------------------------
02219     //!  to fill a table with indexes to receive to other processors
02220     /*!
02221       \param rank is the rank of the processor to receive data to
02222       \return a table with indexes to receive
02223     */
02224     //-------------------------------------------------------------------------------
02225     unsigned int * getNodesToRecv(unsigned int rank)
02226     //-------------------------------------------------------------------------------
02227     {
02228       unsigned int * ret = (unsigned int *)calloc(degcum_tor[rank+1]-degcum_tor[rank],sizeof(unsigned int));
02229       for(unsigned int i=0;i<degcum_tor[rank+1]-degcum_tor[rank];i++)
02230         ret[i] = nodes_tor[degcum_tor[rank]+i];;
02231 
02232       return ret;
02233     }
02234     //-------------------------------------------------------------------------------
02235     //!  to get the number of edges to receive to a precised processor rank
02236     /*!
02237       \param rank is the rank of the processor to receive edges to
02238       \return the number of edges to receive to this processor
02239     */
02240     //-------------------------------------------------------------------------------
02241     inline unsigned int getNbEdgesToRecv(unsigned int rank){return (degcum_tor_in[rank+1]+degcum_tor_out[rank+1])-(degcum_tor_in[rank]+degcum_tor_out[rank]);}
02242     //-------------------------------------------------------------------------------
02243     //!  to get the number of edges to receive in to a precised processor rank
02244     /*!
02245       \param rank is the rank of the processor to receive edges to
02246       \return the number of edges to receive in to this processor
02247     */
02248     //-------------------------------------------------------------------------------
02249     inline unsigned int getNbEdgesToRecvIn(unsigned int rank){return degcum_tor_in[rank+1]-degcum_tor_in[rank];}
02250     //-------------------------------------------------------------------------------
02251     //!  to get the number of edges to receive out to a precised processor rank
02252     /*!
02253       \param rank is the rank of the processor to receive edges to
02254       \return the number of edges to receive out to this processor
02255     */
02256     //-------------------------------------------------------------------------------
02257     inline unsigned int getNbEdgesToRecvOut(unsigned int rank){return degcum_tor_out[rank+1]-degcum_tor_out[rank];}
02258     //-------------------------------------------------------------------------------
02259     //!  to fill a table with indexes to receive to other processors
02260     /*!
02261       \param rank is the rank of the processor to receive data to
02262       \return a table with indexes to receive
02263     */
02264     //-------------------------------------------------------------------------------
02265     unsigned int * getEdgesToRecv(unsigned int rank)
02266     //-------------------------------------------------------------------------------
02267     {
02268       unsigned int * ret = (unsigned int *)calloc((degcum_tor_in[rank+1]+degcum_tor_out[rank+1])-(degcum_tor_in[rank]+degcum_tor_out[rank]),sizeof(unsigned int));
02269       for(unsigned int i=0;i<degcum_tor_in[rank+1]-degcum_tor_in[rank];i++)
02270           ret[i] = edges_tor_in[degcum_tor_in[rank]+i];
02271       for(unsigned int i=0;i<degcum_tor_out[rank+1]-degcum_tor_out[rank];i++)
02272           ret[degcum_tor_in[rank+1]-degcum_tor_in[rank]+i] = edges_tor_out[degcum_tor_out[rank]+i];
02273 
02274       return ret;
02275     }
02276     //-------------------------------------------------------------------------------
02277     //!  to fill a table with indexes to receive in to other processors
02278     /*!
02279       \param rank is the rank of the processor to receive in data to
02280       \return a table with indexes to receive in
02281     */
02282     //-------------------------------------------------------------------------------
02283     unsigned int * getEdgesToRecvIn(unsigned int rank)
02284     //-------------------------------------------------------------------------------
02285     {
02286       unsigned int * ret = (unsigned int *)calloc(degcum_tor_in[rank+1]-degcum_tor_in[rank],sizeof(unsigned int));
02287       for(unsigned int i=0;i<degcum_tor_in[rank+1]-degcum_tor_in[rank];i++)
02288           ret[i] = edges_tor_in[degcum_tor_in[rank]+i];
02289 
02290       return ret;
02291     }
02292     //-------------------------------------------------------------------------------
02293     //!  to fill a table with indexes to receive out to other processors
02294     /*!
02295       \param rank is the rank of the processor to receive out data to
02296       \return a table with indexes to receive out
02297     */
02298     //-------------------------------------------------------------------------------
02299     unsigned int * getEdgesToRecvOut(unsigned int rank)
02300     //-------------------------------------------------------------------------------
02301     {
02302       unsigned int * ret = (unsigned int *)calloc(degcum_tor_out[rank+1]-degcum_tor_out[rank],sizeof(unsigned int));
02303       for(unsigned int i=0;i<degcum_tor_out[rank+1]-degcum_tor_out[rank];i++)
02304           ret[degcum_tor_in[rank+1]-degcum_tor_in[rank]+i] = edges_tor_out[degcum_tor_out[rank]+i];
02305 
02306       return ret;
02307     }
02308     //-------------------------------------------------------------------------------
02309 
02310   };
02311 
02312   //-------------------------------------------------------------------------------
02313   //!  Second specialization of the DDAG_impl class
02314   /*!
02315     Computations on edges only
02316   */
02317   //-------------------------------------------------------------------------------
02318   template<> struct DDAG_impl<false,true>
02319   //-------------------------------------------------------------------------------
02320   {
02321   protected:
02322 
02323   public:
02324     DDAG_impl(const char * binFile)
02325     {
02326     }
02327     ~DDAG_impl()
02328     {
02329     }
02330 
02331   };
02332 
02333   //-------------------------------------------------------------------------------
02334   //!  Third specialization of the DDAG_impl class
02335   /*!
02336     Computations on nodes only
02337   */
02338   //-------------------------------------------------------------------------------
02339   template<> struct DDAG_impl<true,false>
02340   //-------------------------------------------------------------------------------
02341   {
02342   protected:
02343 
02344   public:
02345     DDAG_impl(const char * binFile)
02346     {
02347     }
02348     ~DDAG_impl()
02349     {
02350     }
02351 
02352   };
02353 
02354 }
02355 
02356 #endif
 All Classes Files Functions Variables Defines