Naufraghi nella rete - PHP - Informatica - Linux - Blog - Appartamento a Firenze - Gruppo di discussione

Naufraghi nella Rete

import time, random, array
def timing(f, n, a):
    r = range(n)
    t1 = time.clock()
    for i in r:
        f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a); f(a)
    t2 = time.clock()
    return f.__name__, round(t2-t1, 3)

grafo = {'A':[(1,'B'),(5,'C'),(8,'D')],
         'B':[(1,'A'),(3,'C'),(2,'E')],
         'C':[(5,'A'),(3,'B'),(1,'F')],
         'D':[(8,'A'),(1,'F')],
         'E':[(2,'B'),(4,'F'),(2,'G')],
         'F':[(1,'C'),(1,'D'),(4,'E'),(1,'G')],
         'G':[(2,'E'),(1,'F')]}
disegno = """
      
    (B)--2--(E)
    / \      |\ 
   1   3     | 2 
  /     \    |  \ 
(A)--5--(C)  4  (G)
  \       \  |  /
   8       1 | 1
    \       \|/ 
    (D)--1--(F)

"""

def prim(grafo, start = grafo.keys()[0]):
    Q = {start:(0,start)}
    D = {}

    def get_min(Q, D):
        list = Q.values()
        list.sort()
        min = list[0]
        for nodo in Q.keys():
            if Q[nodo] == min:
                break
        D[nodo] = Q[nodo]
        del Q[nodo]
        return nodo

    def priorita(grafo, Q, D, new):
        for arco in grafo[new]:
            if arco[1] not in D.keys():
                if arco[1] not in Q.keys() or arco[0] < Q[arco[1]]:
                    Q[arco[1]] = (arco[0], new)

    while len(Q) > 0:
        new = get_min(Q, D)
        priorita(grafo, Q, D, new)

    return D

def dijkstra(grafo, start = grafo.keys()[0]):
    Q = {start:(0,start)}
    D = {}

    def get_min(Q, D):
        list = Q.values()
        list.sort()
        min = list[0]
        for nodo in Q.keys():
            if Q[nodo] == min:
                break
        D[nodo] = Q[nodo]
        del Q[nodo]
        return nodo

    def priorita(grafo, Q, D, new):
        for arco in grafo[new]:
            if arco[1] not in D.keys():
                dist = D[new][0] + arco[0]
                if arco[1] not in Q.keys() or dist < Q[arco[1]][0]:
                    Q[arco[1]] = (dist, new)

    while len(Q) > 0:
        new = get_min(Q, D)
        priorita(grafo, Q, D, new)

    return D

def breadthfirst(grafo, start):
    open = [start,]
    closed = []
    while len(open) > 0:
        active = open.pop(0)
        closed.append(active)
        for node in grafo[active]:
            if (node[1] not in open) and (node[1] not in closed):
                open.append(node[1])
    return closed

def depthfirst(grafo, start):
    open = [start,]
    closed = []
    while len(open) > 0:
        lenght = len(open)
        top = open[-1]
        if top not in closed:
            closed.append(top)
        for node in grafo[top]:
            if node[1] not in closed:
                open.append(node[1])
                break
        if len(open) == lenght:
            open.pop()
    return closed

def kruskal(grafo):
    archi = []
    tree = {}
    parts = map(lambda x: [x,], grafo.keys())
    nodes = grafo.keys()
    while len(nodes) > 0:
        nodo = nodes.pop()
        for arco in grafo[nodo]:
            if arco[1] in nodes:
                archi.append((arco[0], nodo, arco[1]))
    archi.sort()
    while len(archi) > 0:
        short = archi.pop(0)
        for part1 in parts:
            if short[1] in part1:
                if short[2] not in part1:
                    for part2 in parts:
                        if short[2] in part2:
                            parts[parts.index(part1)] = part1 + part2
                            parts.remove(part2)
                            tree[short[1]] = (short[0], short[2])
                            break
                break
    return tree

def stampa(grafo):
    text = ""
    for nodo in grafo.keys():
        text = text + str(nodo) + " --- "
        try:
            for arco in grafo[nodo]:
                text = text + ", " + str(arco[1]) + "(" + str(arco[0]) + ")"
            text += "\n"
        except:
            arco = grafo[nodo]
            text = text + ", " + str(arco[1]) + "(" + str(arco[0]) + ")" + "\n"
    return text

start = 'A'
spath = dijkstra(grafo, start)
aprim = prim(grafo, start)
krusk = kruskal(grafo)

print disegno
print "Attraversamento in Ampiezza"
print breadthfirst(grafo, start)
print "\nAttraversamento in Profondita'"
print depthfirst(grafo, start)
print "\nShortest Path (Dijkstra)"
print stampa(spath)
print "Minimo albero ricoprente (Prim)"
print stampa(aprim)
print "Minimo albero ricoprente (Kruskal)"
print stampa(krusk)

stats()

def stats():
    def crea_grafo(nodes, n_arcs):
        grafo = {}
        for nodo in nodes:
            grafo[nodo] = []
        for n in range(n_arcs):
            node1 = random.choice(nodes)
            node2 = random.choice(nodes)
            lenght = random.randrange(10)
            if (lenght, node2) not in grafo[node1]:
                grafo[node1].append((lenght, node2))
                grafo[node2].append((lenght, node1))
        return grafo

    for i in range(30, 151, 30):
        nodi = range(65,71+i*20/300)
        nodes = array.array("b", nodi).tostring()
        grafo = crea_grafo(nodes, i)
        print "--",i,"archi, ",len(nodi),"nodi"
        #print stampa(grafo)
        prim_t = timing(prim, 10, grafo)
        kruskal_t = timing(kruskal, 10, grafo)
        dij_t = timing(dijkstra, 10, grafo)
        print prim_t[0],prim_t[1],"-",kruskal_t[0],kruskal_t[1], "=", prim_t[1] - kruskal_t[1]
        print dij_t[0],dij_t[1]

Ultima modifica 08/03/2004
Per ogni suggerimento/errore contattatemi liberamente: Matteo Bertini

Creative Commons License
This work is licensed under a Creative Commons License.
Nota: I link esterni sono in corsivo e aprono una nuova pagina.


Naufraghi nella rete - PHP - Informatica - Linux - Blog - Appartamento a Firenze - Gruppo di discussione