connectGraphComponents.py 文件源码

def connectGraphComponents(graph, level=2, highway='path', connectNearest=False):
    if nx.is_connected(graph):
        return graph

    combinations = itertools.permutations(range(nx.number_connected_components(graph)),2)

    subgraphs = list(nx.connected_component_subgraphs(graph, copy=True))
    rtrees = [getGraphRtree(subgraph,'nodes') for subgraph in subgraphs]

    nearestComponents={}
    for i, j in combinations:
        if i not in nearestComponents:
            nearestComponents[i] = []
        smallest = i if len(subgraphs[i]) < len(subgraphs[j]) else j
        biggest = j if smallest is i else i
        candidates = {}
        nearestNeighbors = {}

        for node1, data in subgraphs[smallest].nodes(data=True):
            x, y = data['longitude'], data['latitude']
            hits = list(rtrees[biggest].nearest((x, y, x, y), 2, objects="raw"))
            for candidate in hits:
                data = json.loads(candidate)
                candidates[data['id']] = Point(data['geometry']['coordinates'])
            source = Point([x,y])
            distance, node2 = nearestNode(source, candidates)
            nearestNeighbors[distance] = node1, node2
            u,v = nearestNeighbors[min(nearestNeighbors.keys())]

        if connectNearest:
            nearestComponents[i].append((j, min(nearestNeighbors.keys()), (u,v)))
        else:
            newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
            graph.add_edge(u, v, newAttributes)

    if connectNearest:
        for i in nearestComponents.keys():
            data = nearestComponents[i]
            j, distance, (u,v) = sorted(data, key=lambda tup: tup[1])[0]

            if not graph.has_edge(u, v):
                newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
                graph.add_edge(u, v, newAttributes)
    return connectGraphComponents(graph, level, highway, connectNearest=connectNearest)