BGI/SOAPdenovo2/standardPregraph/compactEdge.c

   1 /*
   2  * compactEdge.c
   3  *
   4  * Copyright (c) 2008-2012 BGI-Shenzhen <soap at genomics dot org dot cn>.
   5  *
   6  * This file is part of SOAPdenovo.
   7  *
   8  * SOAPdenovo is free software: you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation, either version 3 of the License, or
  11  * (at your option) any later version.
  12  *
  13  * SOAPdenovo is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  * GNU General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU General Public License
  19  * along with SOAPdenovo.  If not, see <http://www.gnu.org/licenses/>.
  20  *
  21  */
  22
  23 #include "stdinc.h"
  24 #include "newhash.h"
  25 #include "kmerhash.h"
  26 #include "extfunc.h"
  27 #include "extvab.h"
  28
  29 void copyEdge ( unsigned int source, unsigned int target )
  30 {
  31         edge_array[target].from_vt = edge_array[source].from_vt;
  32         edge_array[target].to_vt = edge_array[source].to_vt;
  33         edge_array[target].length = edge_array[source].length;
  34         edge_array[target].cvg = edge_array[source].cvg;
  35         edge_array[target].multi = edge_array[source].multi;
  36         edge_array[target].flag = edge_array[source].flag;
  37
  38         if ( edge_array[target].seq )
  39         {
  40                 free ( ( void * ) edge_array[target].seq );
  41         }
  42
  43         edge_array[target].seq = edge_array[source].seq;
  44         edge_array[source].seq = NULL;
  45         edge_array[target].arcs = edge_array[source].arcs;
  46         edge_array[source].arcs = NULL;
  47         edge_array[target].markers = edge_array[source].markers;
  48         edge_array[source].markers = NULL;
  49         edge_array[target].deleted = edge_array[source].deleted;
  50 }
  51
  52 //move edge from source to target
  53 void edgeMove ( unsigned int source, unsigned int target )
  54 {
  55         unsigned int bal_source, bal_target;
  56         ARC * arc;
  57         copyEdge ( source, target );
  58         bal_source = getTwinEdge ( source );
  59
  60         //bal_edge
  61         if ( bal_source != source )
  62         {
  63                 bal_target = target + 1;
  64                 copyEdge ( bal_source, bal_target );
  65                 edge_array[target].bal_edge = 2;
  66                 edge_array[bal_target].bal_edge = 0;
  67         }
  68         else
  69         {
  70                 edge_array[target].bal_edge = 1;
  71                 bal_target = target;
  72         }
  73
  74         //take care of the arcs
  75         arc = edge_array[target].arcs;
  76
  77         while ( arc )
  78         {
  79                 arc->bal_arc->to_ed = bal_target;
  80                 arc = arc->next;
  81         }
  82
  83         if ( bal_target == target )
  84         {
  85                 return;
  86         }
  87
  88         arc = edge_array[bal_target].arcs;
  89
  90         while ( arc )
  91         {
  92                 arc->bal_arc->to_ed = target;
  93                 arc = arc->next;
  94         }
  95 }
  96
  97 /*************************************************
  98 Function:
  99     compactEdgeArray
 100 Description:
 101     Compacts the edge array by removing deleted edges.
 102 Input:
 103     None.
 104 Output:
 105     None.
 106 Return:
 107     None.
 108 *************************************************/
 109 void compactEdgeArray ()
 110 {
 111         unsigned int i;
 112         unsigned int validCounter = 0;
 113         unsigned int bal_ed;
 114         fprintf ( stderr, "Before compacting, %d edge(s) existed.\n", num_ed );
 115
 116         for ( i = 1; i <= num_ed; i++ )
 117         {
 118                 if ( edge_array[i].deleted )
 119                 {
 120                         continue;
 121                 }
 122
 123                 validCounter++;
 124
 125                 if ( i == validCounter )
 126                 {
 127                         continue;
 128                 }
 129
 130                 bal_ed = getTwinEdge ( i );
 131                 edgeMove ( i, validCounter );
 132
 133                 if ( bal_ed != i )
 134                 {
 135                         i++;
 136                         validCounter++;
 137                 }
 138         }
 139
 140         num_ed = validCounter;
 141         fprintf ( stderr, "After compacting, %d edge(s) left.\n", num_ed );
 142 }