1431.sagews

def number_of_edge_crossings(g):
        if g._pos is None:
            return -1

        edge_crossings = 0
        G = g.to_undirected()
	edges_remaining = G.edges(labels = False)
        for edge1 in G.edges(labels = False):
	    edges_remaining.remove(edge1)
            p1, p2 = g._pos[edge1[0]], g._pos[edge1[1]]
            dy = p2[1] - p1[1]
            dx = p2[0] - p1[0]
            for edge2 in edges_remaining:
                if edge1[0] == edge2[0] or edge1[0] == edge2[1] or edge1[1] == edge2[0] or edge1[1] == edge2[1]:
                    continue
                    
                q1, q2 = g._pos[edge2[0]], g._pos[edge2[1]]
                db = q2[1] - q1[1]
                da = q2[0] - q1[0]
		denom = dx*db - dy*da
		if denom != 0:
                    t1 = p1[1] - q1[1]
                    t2 = q1[0] - p1[0]
		    s = (dx*t1 + dy*t2)/denom
                    if s >= 0 and s <= 1:
                        t = (da*t1 + db*t2)/denom
                        if t >= 0 and t <= 1:
                            edge_crossings += 1
                            
        return edge_crossings

def barrycenter(g):
        if g._pos is None:
            return -1

        barrycenter_pos = [0, 0];
        vlist = g.vertices()
	for v in vlist:
            barrycenter_pos[0] += g._pos[v][0]
            barrycenter_pos[1] += g._pos[v][1]
        barrycenter_pos[0] /= float(len(vlist))
        barrycenter_pos[1] /= float(len(vlist))

        return barrycenter_pos

def fractional_length(g, test_angles=20):
	from math import cos, sin, pi
	if g._pos is None:
            return -1

	crossings = 0
	G = g.to_undirected()
        barrycenter_pos = barrycenter(g)
        for direction in range(test_angles):
            theta = direction*pi/test_angles

            q1 = [barrycenter_pos[0] - cos(theta)*100, barrycenter_pos[1] - sin(theta)*100]
            q2 = [barrycenter_pos[0] + cos(theta)*100, barrycenter_pos[1] + sin(theta)*100]
            db = q2[1] - q1[1]
            da = q2[0] - q1[0]

            for edge in G.edges(labels = False):
                p1, p2 = g._pos[edge[0]], g._pos[edge[1]]
                dy = p2[1] - p1[1]
                dx = p2[0] - p1[0]
                denom = dx*db - dy*da
		if denom != 0:
                    t1 = p1[1] - q1[1]
                    t2 = q1[0] - p1[0]
		    s = (dx*t1 + dy*t2)/denom
                    if s >= 0 and s <= 1:
                        t = (da*t1 + db*t2)/denom
                        if t >= 0 and t <= 1:
                            crossings += 1
                            
	return crossings / float(test_angles)

def edge_lengths(g):
	from math import sqrt
        if g._pos is None:
            return []

        G = g.to_undirected()
        lengths_list = []
        for edge in G.edges(labels = False):
            dx = g._pos[edge[0]][0] - g._pos[edge[1]][0] 
            dy = g._pos[edge[0]][1] - g._pos[edge[1]][1]
            lengths_list.append(sqrt(dx*dx + dy*dy))

        return lengths_list

def node_distances(g):
        from math import sqrt
        if g._pos is None:
            return []
       
        distances_list = []
	remaining_vertices = g.vertices()
        for v1 in g.vertices():
	    remaining_vertices.remove(v1)
            for v2 in remaining_vertices:
                dx = g._pos[v1][0] - g._pos[v2][0] 
                dy = g._pos[v1][1] - g._pos[v2][1]
                distances_list.append(sqrt(dx*dx + dy*dy))
        
	return distances_list

def deviations_from_graph_theoretic_distances(g):
        from math import sqrt
        if g._pos is None:
            return -1
 
        theoretic_ds = []
        euclidian_ds = []
        theoretic_avg = 0
        euclidian_avg = 0
        remaining_vertices = g.vertices()
        for v1 in g.vertices():
	    remaining_vertices.remove(v1)
            for v2 in remaining_vertices:
                dx = g._pos[v1][0] - g._pos[v2][0] 
                dy = g._pos[v1][1] - g._pos[v2][1]
                d = sqrt(dx*dx + dy*dy)
                euclidian_avg += d
                euclidian_ds.append(d)
                d2 = g.distance(v1, v2)
                theoretic_avg += d2
                theoretic_ds.append(d2)
        theoretic_avg /= float(len(theoretic_ds))
        euclidian_avg /= float(len(euclidian_ds))
        
	deviations = []
        for i in range(len(theoretic_ds)):
            deviations.append(theoretic_ds[i]/theoretic_avg - euclidian_ds[i]/euclidian_avg)
        return deviations

def vertice_edge_angles(g, v):
	from math import atan2, pi
        if g._pos is None:
            return []

	edge_angles = []
	for v2 in g.neighbors(v):
            angle = atan2(g._pos[v2][1] - g._pos[v][1], g._pos[v2][0] - g._pos[v][0])
            if(angle < 0):
                angle += 2*pi
            edge_angles.append(angle)
        edge_angles.sort()
   
	angles_between_edges = []
        for i in range(len(edge_angles)):
            if i+1 == len(edge_angles):
                theta = 2*pi + edge_angles[0] - edge_angles[i]
            else: 
                theta = edge_angles[i+1] - edge_angles[i]
            angles_between_edges.append(theta)
        return angles_between_edges

def edge_angles(g):
        if g._pos is None:
            return []

        angles = []
        for v in g.vertices():
            angles.extend(vertice_edge_angles(g, v))
        return angles

def layout_metrics(g): 
        if g._pos is None:
            print "No layout specified"
            return
        print "Graph is planar: ", g.is_planar()
        print "Number of edge crossings: ", number_of_edge_crossings(g)
        print "Fractional length: ", fractional_length(g)
        print "Variance of edge lengths: ", variance(edge_lengths(g))
        print "Variance of node distances: ", variance(node_distances(g))
        l = deviations_from_graph_theoretic_distances(g)
        print "Average deviation squared between graph-theoretic and euclidian distances: ", sum(x**2 for x in l)/float(len(l))
        print "Variance of edge angles: ", variance(edge_angles(g))

g = graphs.CompleteGraph(5)
layout_metrics(g)

Graph is planar: False Number of edge crossings: 5 Fractional length: 6.25 Variance of edge lengths: 0.146628901389 Variance of node distances: 0.146628901389 Average deviation squared between graph-theoretic and euclidian distances: 0.0557280900008 Variance of edge angles: 2.80504546136