Task 4.sagews

def graph_from_file(filename, directed=False, weighted=False, weight_type=int):
    if directed:
        G = DiGraph(weighted=weighted)
    else:
        G = Graph(weighted=weighted)
    with open(filename, 'r') as f:
        E = []
        for l in f:
            if not l[0].isdigit(): continue
            l = l.strip().replace(',', ' ')
            if not weighted:
                E.append(tuple(map(int, l.split())))
            else:
                u, v, w = l.split()
                E.append((int(u), int(v), weight_type(w)))
    G.add_edges(E)
    return G

def dijkstra(G, start):
    dist = {start: 0}
    q = {(0, start)}
    while len(q) > 0:
        # this lookup should be logarithmic, but Python does not have a suitable data structure
        top = min(q)
        d1, u = top
        q.remove(top)
        for e in G.edges_incident(u):
            if e[0] == u:
                v = e[1]
            else:
                v = e[0]
            w = e[2]
            if not isinstance(w, (int, long, float)):
                w = 1
            d2 = d1 + w
            if v not in dist:
                q.add((d2, v))
                dist[v] = d2
            elif d2 < dist[v]:
                q.remove((dist[v], v))
                q.add((d2, v))
                dist[v] = d2
    return dist

def diameter(G):
    return max(max(dijkstra(G, u).values()) for u in G.vertex_iterator())

import matplotlib.pyplot as plt

def stats(G, name):
    print "Graph:", name
    print "Number of vertices:", G.order()
    subgraphs = G.connected_components_subgraphs()
    print "Number of components:", len(subgraphs)
    print "Number of vertices and the diameter in each component:", sorted([(g.order(), g.diameter()) for g in subgraphs])[::-1]
    if isinstance(G, DiGraph):
        sccs = G.strongly_connected_components_subgraphs()
        print "Number of strongly connected components:", len(sccs)
        print "Number of vertices and the diameter in each SCC:", sorted([(g.order(), g.diameter()) for g in sccs])[::-1]
    plt.xlabel('degree')
    plt.ylabel('count')
    d = G.degree()
    plt.hist(d, bins=range(max(d)+1))
    plt.savefig(name + '_degree_hist.pdf')
    plt.show()

G_enron = graph_from_file('Graphs_web/email-Enron.txt', directed=True, weighted=False)
stats(G_enron, "enron")

Graph: enron vertices: 36692 components:

G_karate = graph_from_file('Graphs_web/karate.txt', directed=False, weighted=False)
stats(G_karate, "karate")

Graph: karate Number of vertices: 34 Number of components: 1 Number of vertices and the diameter in each component: [(34, 5)]

G_usairport = graph_from_file('Graphs_web/usairport.txt', directed=True, weighted=True, weight_type=float)
stats(G_usairport, "usairport")

Graph: usairport Number of vertices: 1574 Number of components: 2 Number of vertices and the diameter in each component: [(1572, +Infinity), (2, +Infinity)] Number of strongly connected components: 171 Number of vertices and the diameter in each SCC:

G_students = graph_from_file('Graphs_web/students_multigraph_hashAnonymized.csv', directed=False, weighted=True, weight_type=str)
stats(G_students, "students")

Graph: students Number of vertices: 185 Number of components: 12 Number of vertices and the diameter in each component: [(141, 17), (12, 7), (8, 3), (4, 1), (4, 1), (4, 1), (2, 1), (2, 1), (2, 1), (2, 1), (2, 1), (2, 1)]

timeit("dijkstra(G_usairport, 1)")
print "To get the diameter of US airports graph, we would need to run the above {} times".format(G_usairport.order())
print diameter(G_karate)

Error in lines 1-1 Traceback (most recent call last): File "/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/.sagemathcloud/sage_server.py", line 862, in execute exec compile(block+'\n', '', 'single') in namespace, locals File "", line 1, in <module> File "/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/.sagemathcloud/sage_salvus.py", line 1478, in timeit go(*args) File "/projects/b60781fb-41d7-40bf-97f4-94455eaaf2d4/.sagemathcloud/sage_salvus.py", line 1474, in go print sage.misc.sage_timeit.sage_timeit(code, globals_dict=salvus.namespace, **kwds) File "/usr/local/sage/sage-6.3.beta6/local/lib/python2.7/site-packages/sage/misc/sage_timeit.py", line 240, in sage_timeit if timer.timeit(number) >= 0.2: File "/usr/local/sage/sage-6.3.beta6/local/lib/python/timeit.py", line 195, in timeit timing = self.inner(it, self.timer) File "<magic-timeit>", line 6, in inner NameError: global name 'dijkstra' is not defined