scripts/chg-len.py
author Peter Kovacs <kpeter@inf.elte.hu>
Tue, 24 Mar 2009 00:18:25 +0100
changeset 604 8c3112a66878
parent 376 4b2382fd80ef
child 733 abf31e4af617
permissions -rwxr-xr-x
Use XTI implementation instead of ATI in NetworkSimplex (#234)

XTI (eXtended Threaded Index) is an imporved version of the widely
known ATI (Augmented Threaded Index) method for storing and updating
the spanning tree structure in Network Simplex algorithms.

In the ATI data structure three indices are stored for each node:
predecessor, thread and depth. In the XTI data structure depth is
replaced by the number of successors and the last successor
(according to the thread index).
alpar@272
     1
#! /usr/bin/env python
alpar@272
     2
alpar@272
     3
import sys
alpar@376
     4
alpar@376
     5
from mercurial import ui, hg
alpar@422
     6
from mercurial import util
alpar@422
     7
alpar@422
     8
util.rcpath = lambda : []
alpar@272
     9
alpar@272
    10
if len(sys.argv)>1 and sys.argv[1] in ["-h","--help"]:
alpar@272
    11
    print """
alpar@272
    12
This utility just prints the length of the longest path
alpar@272
    13
in the revision graph from revison 0 to the current one.
alpar@272
    14
"""
alpar@272
    15
    exit(0)
alpar@272
    16
alpar@376
    17
u = ui.ui()
alpar@376
    18
r = hg.repository(u, ".")
alpar@376
    19
N = r.changectx(".").rev()
alpar@376
    20
lengths=[0]*(N+1)
alpar@376
    21
for i in range(N+1):
alpar@376
    22
    p=r.changectx(i).parents()
alpar@376
    23
    if p[0]:
alpar@376
    24
        p0=lengths[p[0].rev()]
alpar@272
    25
    else:
alpar@376
    26
        p0=-1
alpar@376
    27
    if len(p)>1 and p[1]:
alpar@376
    28
        p1=lengths[p[1].rev()]
alpar@272
    29
    else:
alpar@376
    30
        p1=-1
alpar@376
    31
    lengths[i]=max(p0,p1)+1
alpar@376
    32
print lengths[N]