nadroj
Dołączył: 23 Paź 2010
Posty: 14
Przeczytał: 0 tematów
Ostrzeżeń: 0/5
|
 Wysłany: Sob 10:44, 25 Cze 2011 Temat postu: |
|
|
| Kod: |
#!/usr/bin/env python
## -*- coding: utf-8 -*-
# Tomasz Nowacki
# drzewo->kod Prufera, rank, unrank
def prufer(T, n):
""" Metoda wyznacza kod Prufera dla zadanego drzewa T
na n wierzcholkach.
Parametry:
T - drzewo w postaci listy krawedzi (lista list)
n - liczba wierzcholkow
Return:
L - kod Prufera
"""
# inicjalizacja tablic
d = [0]*(n+1)
L = [0]*(n-2)
# utworzenie tablicy stopni wierzcholkow
for t in T:
x, y = t
d[x] = d[x]+1
d[y] = d[y]+1
for i in xrange(0, n-2):
# wyznaczenie najwiekszego wierzcholka stopnia jeden
x = n
while d[x] != 1:
x = x - 1
# wyznaczenie wierzcholka y, polaczonego z x
# krawedz moze byc postaci [x,y] lub [y,x]
y = n
while True:
if [x,y] in T:
xy = True
break
elif [y,x] in T:
xy = False
break
else:
y = y - 1
# wstaw y do L
L[i] = y
# usun krawedz [x,y] lub [y, x] z T
if xy:
T.remove([x,y])
else:
T.remove([y,x])
# zmniejsz stopnie x i y w d o 1
d[x] = d[x]-1
d[y] = d[y]-1
return L
def rank(L, n):
""" Metoda oblicza rank dla zadanego kodu Prufera.
Parametry:
L - kod Prufera
n - liczba wierzcholkow
Return:
r - rank zadanego ciagu L
"""
r = 0
p = 1
for i in xrange((n-2)-1, -1, -1):
r = r + p*(L[i] - 1)
p = p*n
return r
def unrank(r, n):
""" Metoda wyznacza kod Prufera na podstawie rangi.
Parametry:
r - ranga
n - liczba wierzcholkow
Return:
L - kod Prufera
"""
L = [0]*(n-2)
for i in xrange((n-2)-1, -1, -1):
L[i] = r%n +1
r = (r - L[i] + 1)/n
return L
def main():
n = 7
T = [[4,6],[5,6],[5,1],[6,2],[2,3],[2,7]]
print 'Drzewo T: %s' % T
L = prufer(T, n)
print 'Kod Prufera: %s' % L
r = rank(L, n)
print 'Rank: %s' % r
ur = unrank(r, n)
print 'Unrank: %s' % ur
if __name__ == '__main__':
main()
|
Post został pochwalony 0 razy
|
|
))