Can you please suggest more elegant and eloquent ways for this problem? (Perhaps better ways to represent a graph with vertices and edges?)

Skyline problem is described here.

The Skyline problem from UVa Online Judge is as follows:

You are to design a program to assist an architect in drawing the skyline of a city given the locations of the buildings in the city. A building is specified by an ordered triple \$ (L_i,H_i,R_i) \$ where \$ L_i \$ and \$ R_i \$ are left and right coordinates, respectively, of building \$ i \$ and \$ H_i \$ is the height of the building.

The input is a sequence of building triples. All coordinates of buildings are integers less than 10,000 and there will be at least one and at most 5,000 buildings in the input file. Each building triple is on a line by itself in the input file. All integers in a triple are separated by one or more spaces. The triples will be sorted by \$ L_i \$, the left x-coordinate of the building, so the building with the smallest left x-coordinate is first in the input file.

The output should consist of the skyline vector \$ (v_1, v_2, v_3, \ldots, v_{n−2}, v_{n−1}, v_n)\$, the \$ v_i \$ such that \$ i \$ is an even number represent a horizontal line (height). The \$ v_i \$ such that \$ i \$ is an odd number represent a vertical line (x-coordinate). The skyline vector should represent the “path” taken, for example, by a bug starting at the minimum x-coordinate and traveling horizontally and vertically over all the lines that define the skyline. Thus the last entry in all skyline vectors will be a 0.

This is my solution:

Can you please suggest more elegant and eloquent ways for this problem? (Perhaps better ways to represent a graph with vertices and edges?)

Closest Pair of Points problem is described here.

def closest_pairs(points): # returns closest pairs in square distance.
    sq_dist = lambda p1, p2: sum((p1[i] - p2[i])**2 for i in range(2))
    points_by_Y = SortedDict()
    points_by_X = deque()
    pairs = []
    d = 2**31 - 1
    for p1 in points: # another sweep line algorithm
        x, y = p1
        while points_by_X and d < (x - points_by_X[0][0])**2:
            _, y2 = s.popleft()
            points_by_Y[y2].remove(p)
            if not points_by_Y[y2]:
                del points_by_Y[y2]
        b = points_by_Y.bisect_left(y-d)
        e = points_by_Y.bisect_right(y+d)
        for s in points_by_Y.values()[b:e]:
            for p2 in s:
                d2 = sq_dist(p1, p2)
                if not pairs or d > d2:
                    d = d2
                    pairs = [(p1, p2)]
                elif d == d2:
                    pairs.append((p1, p2))
        s = points_by_Y.setdefault(y, set())
        s.add(p1)
    return pairs
 
points = ((-2, -2), (4, -8), (8, -2), (10, 4), (13, -8), (14, 0), (17, -6))
assert [((17, -6), (13, -8))] == closest_pairs(points)

Can you please suggest more elegant and eloquent ways for this program? (Perhaps better ways to represent a graph with vertices and edges?)

# [SortedDict](http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html)
from sortedcontainers import SortedDict # pip3 install sortedcontainers
from collections import deque
import heapq
 
def skyline(buildings_by_L): # a deque.
    buildings_by_H = SortedDict() # a self-balancing binary tree.
    buildings_by_R = [] # a priority queue.
    skyline = []
    def add_point(x):
        h = buildings_by_H.iloc[-1] if buildings_by_H else 0
        if not skyline:
            skyline.append((x, h))
        else:
            x0, h0 = skyline[-1]
            if h != h0:
                if x == x0:
                    skyline[-1] = (x, max(h, h0))
                else:
                    skyline.append((x, h))
    def insert(b, sets=[set()]):
        heapq.heappush(buildings_by_R, (b[2], b))
        s = buildings_by_H.setdefault(b[1], sets[0])
        s.add(b)
        if s == sets[0]:
            sets[0] = set()
        add_point(b[0])
    def delete(b):
        buildings_by_H[b[1]].remove(b)
        if not buildings_by_H[b[1]]:
            del buildings_by_H[b[1]]
        add_point(b[2])
    while buildings_by_L or buildings_by_R:
        if (not buildings_by_R
            or buildings_by_L
               and buildings_by_L[0][0] <= buildings_by_R[0][0]):
            insert(buildings_by_L.popleft())
        else:
            delete(heapq.heappop(buildings_by_R)[1])
    return skyline
 
buildings = (
    (1,9,3), (1,11,5), (2,6,7), (3,13,9), (12,7,16), 
    (14,3,25), (19,18,22), (23,13,29), (24,4,28))
assert ([(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0)]
    == skyline(deque(buildings)))

def closest_pairs(points):
    sq_dist = lambda p1, p2: sum((p1[i] - p2[i])**2 for i in range(2))
    points_by_Y = SortedDict()
    points_by_X = deque()
    pairs = []
    d = 2**31 - 1
    for p1 in points:
        x, y = p1
        while points_by_X and d < (x - points_by_X[0][0])**2:
            _, y2 = s.popleft()
            points_by_Y[y2].remove(p)
            if not points_by_Y[y2]:
                del points_by_Y[y2]
        b = points_by_Y.bisect_left(y-d)
        e = points_by_Y.bisect_right(y+d)
        for s in points_by_Y.values()[b:e]:
            for p2 in s:
                d2 = sq_dist(p1, p2)
                if not pairs or d > d2:
                    d = d2
                    pairs = [(p1, p2)]
                elif d == d2:
                    pairs.append((p1, p2))
        s = points_by_Y.setdefault(y, set())
        s.add(p1)
    return pairs
 
points = ((-2, -2), (4, -8), (8, -2), (10, 4), (13, -8), (14, 0), (17, -6))
assert [((17, -6), (13, -8))] == closest_pairs(points)

Can you please suggest more elegant and eloquent ways for this problem? (Perhaps better ways to represent a graph with vertices and edges?)

# [SortedDict](http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html)
from sortedcontainers import SortedDict # pip3 install sortedcontainers
from collections import deque
import heapq
 
def skyline(buildings_by_L): # a deque.
    buildings_by_H = SortedDict() # a self-balancing binary tree.
    buildings_by_R = [] # a priority queue.
    skyline = []
    def add_point(x):
        h = buildings_by_H.iloc[-1] if buildings_by_H else 0
        if not skyline:
            skyline.append((x, h))
        else:
            x0, h0 = skyline[-1]
            if h != h0:
                if x == x0:
                    skyline[-1] = (x, max(h, h0))
                else:
                    skyline.append((x, h))
    def insert(b, sets=[set()]):
        heapq.heappush(buildings_by_R, (b[2], b))
        s = buildings_by_H.setdefault(b[1], sets[0])
        s.add(b)
        if s == sets[0]:
            sets[0] = set()
        add_point(b[0])
    def delete(b):
        buildings_by_H[b[1]].remove(b)
        if not buildings_by_H[b[1]]:
            del buildings_by_H[b[1]]
        add_point(b[2])
    while buildings_by_L or buildings_by_R: # another sweep line algorithm
        if (not buildings_by_R
            or buildings_by_L
               and buildings_by_L[0][0] <= buildings_by_R[0][0]):
            insert(buildings_by_L.popleft())
        else:
            delete(heapq.heappop(buildings_by_R)[1])
    return skyline

Test Cases:

buildings = (
    (1,9,3), (1,11,5), (2,6,7), (3,13,9), (12,7,16), 
    (14,3,25), (19,18,22), (23,13,29), (24,4,28))
assert ([(1, 11), (3, 13), (9, 0), (12, 7), (16, 3), (19, 18), (22, 3), (23, 13), (29, 0)]
    == skyline(deque(buildings)))

def closest_pairs(points): # returns closest pairs in square distance.
    sq_dist = lambda p1, p2: sum((p1[i] - p2[i])**2 for i in range(2))
    points_by_Y = SortedDict()
    points_by_X = deque()
    pairs = []
    d = 2**31 - 1
    for p1 in points: # another sweep line algorithm
        x, y = p1
        while points_by_X and d < (x - points_by_X[0][0])**2:
            _, y2 = s.popleft()
            points_by_Y[y2].remove(p)
            if not points_by_Y[y2]:
                del points_by_Y[y2]
        b = points_by_Y.bisect_left(y-d)
        e = points_by_Y.bisect_right(y+d)
        for s in points_by_Y.values()[b:e]:
            for p2 in s:
                d2 = sq_dist(p1, p2)
                if not pairs or d > d2:
                    d = d2
                    pairs = [(p1, p2)]
                elif d == d2:
                    pairs.append((p1, p2))
        s = points_by_Y.setdefault(y, set())
        s.add(p1)
    return pairs
 
points = ((-2, -2), (4, -8), (8, -2), (10, 4), (13, -8), (14, 0), (17, -6))
assert [((17, -6), (13, -8))] == closest_pairs(points)