Fossil

Check-in [71edacd9]
Login

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

Overview
Comment:Improvements to the graph layout algorithm to render a more compact graph when there is lots of branching and merging.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 71edacd95f3b58aea2b158241732c99f2ed4d0a1
User & Date: drh 2010-03-03 04:08:18
References
2010-03-05
19:58 New ticket [a2de4526] timeline graphs shows trunk line many times. artifact: 4cf9a387 user: anonymous
Context
2010-03-03
13:52
Allow the type= attribute on the verbatim wiki tag. This attribute does not pass right through. If found, it is treated as the 'Language Type' and alters the output of the verbatim tag slightly. verbatim type='cpp' would render as pre name='code' class='cpp'. This allows JavaScript tools such as SyntaxHighlighter to function properly for any language. check-in: 63d31b04 user: jeremy_c tags: trunk
04:08
Improvements to the graph layout algorithm to render a more compact graph when there is lots of branching and merging. check-in: 71edacd9 user: drh tags: trunk
03:34
Add a hyperlink on branch tags of the info display that carries the user to a timeline of the branch. check-in: 732e3db3 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/graph.c.

187
188
189
190
191
192
193

194
195
196
197
198
199
200
201
202

203
204
205
206
207
208
209
...
214
215
216
217
218
219
220



221
222
223
224
225
226
227
...
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282

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

  int i;
  int nRow;
  u32 mask;
  u32 inUse;

  if( p==0 || p->pFirst==0 || p->nErr ) return;

  /* Initialize all rows */
  bag_init(&allRids);

  nRow = 0;
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->pNext ) pRow->pNext->pPrev = pRow;
    pRow->idx = ++nRow;
    pRow->iRail = -1;
    pRow->mergeOut = -1;
    bag_insert(&allRids, pRow->rid);
................................................................................
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      if( !bag_find(&allRids, pRow->aParent[i]) ){
        pRow->aParent[i] = pRow->aParent[--pRow->nParent];
        i--;
      }



    }
  }

  /* 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( 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(pDesc = pRow; ; pDesc=pDesc->pNext){
      assert( pDesc!=0 );
      pDesc->railInUse |= mask;
      if( pDesc->rid==parentRid ) break;
    }
  }







>









>







 







>
>
>







 







|
|

|







187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
...
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
...
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287

/*
** Compute the complete graph
*/
void graph_finish(GraphContext *p, int omitDescenders){
  GraphRow *pRow, *pDesc;
  Bag allRids;
  Bag notLeaf;
  int i;
  int nRow;
  u32 mask;
  u32 inUse;

  if( p==0 || p->pFirst==0 || p->nErr ) return;

  /* Initialize all rows */
  bag_init(&allRids);
  bag_init(&notLeaf);
  nRow = 0;
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    if( pRow->pNext ) pRow->pNext->pPrev = pRow;
    pRow->idx = ++nRow;
    pRow->iRail = -1;
    pRow->mergeOut = -1;
    bag_insert(&allRids, pRow->rid);
................................................................................
  */
  for(pRow=p->pFirst; pRow; pRow=pRow->pNext){
    for(i=1; i<pRow->nParent; i++){
      if( !bag_find(&allRids, pRow->aParent[i]) ){
        pRow->aParent[i] = pRow->aParent[--pRow->nParent];
        i--;
      }
    }
    if( pRow->nParent>0 && bag_find(&allRids, pRow->aParent[0]) ){
      bag_insert(&notLeaf, pRow->aParent[0]);
    }
  }

  /* 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( 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( bag_find(&notLeaf, pRow->rid) ){
      inUse |= mask;
    }else{
      inUse &= ~mask;
    }
    for(pDesc = pRow; ; pDesc=pDesc->pNext){
      assert( pDesc!=0 );
      pDesc->railInUse |= mask;
      if( pDesc->rid==parentRid ) break;
    }
  }