Fossil

Check-in [0f27a598]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Improved graph layout algorithm attempts to keep merge arrows in between their source and destination.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:0f27a59808e214b274d76aba89d669fd7abe34c7
User & Date: drh 2010-02-23 21:30:36
Context
2010-02-24
04:11
Updates to the file format documentation. check-in: f01ec9db user: drh tags: trunk
2010-02-23
21:30
Improved graph layout algorithm attempts to keep merge arrows in between their source and destination. check-in: 0f27a598 user: drh tags: trunk
16:14
Fix the Makefile so that all parameters are commented and so that it works with non-GNU makes. check-in: 8fe33aa5 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/graph.c.

150
151
152
153
154
155
156
157





158
159


160
161
162
163
164
165
166







167


168
169
170
171
172
173
174
175
176
...
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
...
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
...
271
272
273
274
275
276
277

278
279
280
281
282
283
284
285
  p->pLast = pRow;
}

/*
** Return the index of a rail currently not in use for any row between
** top and bottom, inclusive.  
*/
static int findFreeRail(GraphContext *p, int top, int btm, u32 inUseMask){





  GraphRow *pRow;
  int i;


  for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
  while( pRow && pRow->idx<=btm ){
    inUseMask |= pRow->railInUse;
    pRow = pRow->pNext;
  }
  for(i=0; i<32; i++){
    if( (inUseMask & (1<<i))==0 ) return i;







  }


  p->nErr++;
  return 0;
}

/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc;
................................................................................

  /* Identify rows where the primary parent is off screen.  Assign
  ** each to a rail and draw descenders to the bottom of the screen.
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
      if( omitDescenders ){
        pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0);
      }else{
        pRow->iRail = ++p->mxRail;
      }
      mask = 1<<(pRow->iRail);
      if( omitDescenders ){
        pRow->railInUse |= mask;
        if( pRow->pNext ) pRow->pNext->railInUse |= mask;
................................................................................
      pRow->iRail = ++p->mxRail;
      pRow->railInUse = 1<<pRow->iRail;
      continue;
    }
    if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
      pRow->iRail = pDesc->iRail;
    }else{
      pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse);
    }
    pDesc->aiRaiser[pRow->iRail] = pRow->idx;
    mask = 1<<pRow->iRail;
    if( pRow->isLeaf ){
      inUse &= ~mask;
    }else{
      inUse |= mask;
................................................................................
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      int parentRid = pRow->aParent[i];
      for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
          pDesc=pDesc->pNext){}
      if( pDesc==0 ) continue;
      if( pDesc->mergeOut<0 ){

        pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0);
        pDesc->mergeUpto = pRow->idx;
        mask = 1<<pDesc->mergeOut;
        pDesc->railInUse |= mask;
        for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
             pDesc=pDesc->pNext){
          pDesc->railInUse |= mask;
        }







|
>
>
>
>
>


>
>






|
>
>
>
>
>
>
>
|
>
>
|
|







 







|







 







|







 







>
|







150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
...
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
...
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
...
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
  p->pLast = pRow;
}

/*
** Return the index of a rail currently not in use for any row between
** top and bottom, inclusive.  
*/
static int findFreeRail(
  GraphContext *p,         /* The graph context */
  int top, int btm,        /* Span of rows for which the rail is needed */
  u32 inUseMask,           /* Mask or rails already in use */
  int iNearto              /* Find rail nearest to this rail */
){
  GraphRow *pRow;
  int i;
  int iBest = 0;
  int iBestDist = 9999;
  for(pRow=p->pFirst; pRow && pRow->idx<top; pRow=pRow->pNext){}
  while( pRow && pRow->idx<=btm ){
    inUseMask |= pRow->railInUse;
    pRow = pRow->pNext;
  }
  for(i=0; i<32; i++){
    if( (inUseMask & (1<<i))==0 ){
      int dist;
      if( iNearto<=0 ) return i;
      dist = i - iNearto;
      if( dist<0 ) dist = -dist;
      if( dist<iBestDist ){
        iBestDist = dist;
        iBest = i;
      }
    }
  }
  if( iBestDist>1000 ) p->nErr++;
  return iBest;
}

/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc;
................................................................................

  /* Identify rows where the primary parent is off screen.  Assign
  ** each to a rail and draw descenders to the bottom of the screen.
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->nParent==0 || !bag_find(&allRids,pRow->aParent[0]) ){
      if( omitDescenders ){
        pRow->iRail = findFreeRail(p, pRow->idx, pRow->idx, 0, 0);
      }else{
        pRow->iRail = ++p->mxRail;
      }
      mask = 1<<(pRow->iRail);
      if( omitDescenders ){
        pRow->railInUse |= mask;
        if( pRow->pNext ) pRow->pNext->railInUse |= mask;
................................................................................
      pRow->iRail = ++p->mxRail;
      pRow->railInUse = 1<<pRow->iRail;
      continue;
    }
    if( pDesc->aiRaiser[pDesc->iRail]==0 && pDesc->zBranch==pRow->zBranch ){
      pRow->iRail = pDesc->iRail;
    }else{
      pRow->iRail = findFreeRail(p, 0, pDesc->idx, inUse, 0);
    }
    pDesc->aiRaiser[pRow->iRail] = pRow->idx;
    mask = 1<<pRow->iRail;
    if( pRow->isLeaf ){
      inUse &= ~mask;
    }else{
      inUse |= mask;
................................................................................
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      int parentRid = pRow->aParent[i];
      for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
          pDesc=pDesc->pNext){}
      if( pDesc==0 ) continue;
      if( pDesc->mergeOut<0 ){
        int iTarget = (pRow->iRail + pDesc->iRail)/2;
        pDesc->mergeOut = findFreeRail(p, pRow->idx, pDesc->idx, 0, iTarget);
        pDesc->mergeUpto = pRow->idx;
        mask = 1<<pDesc->mergeOut;
        pDesc->railInUse |= mask;
        for(pDesc=pRow->pNext; pDesc && pDesc->rid!=parentRid;
             pDesc=pDesc->pNext){
          pDesc->railInUse |= mask;
        }