mobility-Centrality

# https://stackoverflow.com/questions/32424604/find-all-nearest-neighbors-within-a-specific-distance

import networkx as nx

from scipy.spatial import KDTree

from scipy.spatial.distance import cdist

import code  # code.interact(local=dict(globals(), **locals()))

import graph_tool.all as gt

import numpy as np

from pprint import pprint

import time

from heapq import nsmallest

from collections import defaultdict

def second_smallest(numbers):

    return nsmallest(2, numbers)[-1]

def reconnectGraph(g, distM):

    labels, hist=gt.label_components(g, directed=False)

    # While not only a single component

    while (not all(e==0 for e in labels.a)):

        #code.interact(local=dict(globals(), **locals()))

        # Divide node by component

        comp2nodes = defaultdict(list)

        for i in range(len(labels.a)):

            comp2nodes[labels.a[i]].append(i)

        # se il grafo e' sconnesso solo per un singolo nodo staccato

        if len(set(labels.a))==2 and min(map(len, comp2nodes.values()))==1:

            #print "Isolated node"

            #code.interact(local=dict(globals(), **locals()))

            out=g.get_out_degrees(g.get_vertices())

            for i in range(0,len(out),1):

                if out[i]==0:

                    dp=distM[i]

                    closest=second_smallest(dp)

                    near_neigh=[k for k in range(len(dp)) if dp[k]==closest][0]

                    g.add_edge(g.vertex(i), g.vertex(near_neigh))

                    break   

        else:

            #iteratively attach the smallest compo to the closest

            #print "Separated Compo"

            #code.interact(local=dict(globals(), **locals()))

            d={k:len(v) for k,v in comp2nodes.items()}

            minCompoLabel=min(d, key=d.get)

            minCompo=comp2nodes[minCompoLabel]

            couple=None

            nearest_dist=10000000

            for n in minCompo:

                dp=distM[n]

                for v in range(0,len(distM), 1):

                    if n==v: continue

                    if labels.a[v] == labels.a[n]: continue

                    closest=distM[n][v]

                    if closest < nearest_dist:

                        nearest_dist = closest

                        couple=n,v

            g.add_edge(g.vertex(couple[0]), g.vertex(couple[1]))

            #print "Connecting %d--%d, which are %.04f distant" % (couple[0], couple[1], nearest_dist)

        labels, hist=gt.label_components(g, directed=False)

class UnitDiskGraph:

    def __init__(self, points, radius):

        self.nxG = nx.Graph()

        self.nxG.add_nodes_from(range(len(points)))

        self.gtG = gt.Graph(directed=False)

        self.gtG.add_vertex(len(points))

        self.edge_weights = self.gtG.new_edge_property('float')

        self.gtG.edge_properties['weight'] = self.edge_weights        

        self.generateGraphCDIST(points, radius)

    def genereateGraphFromKDtree(self, points, radius):

        tree = KDTree(points)

        edges = tree.query_pairs(r=radius)

        #edges = [e+(1.0,) for e in edges]

        #pos = {k:points[k] for k in range(0,len(points))}        

        #self.G.add_weighted_edges_from(edges, weight='weight')

        for e in edges:

            e = self.G.add_edge(e[0],e[1])

            self.edge_weights[e] = 1.0

    def generateGraphCDIST(self, points, radius):

        distM = cdist(points, points, 'euclidean')

        edges = []

        for r in range(len(points)):

            for c in range(len(points)):

                if r==c:

                    continue

                if distM[r][c] <= radius:

                    edges.append([r,c, 1.0])

        self.nxG.add_weighted_edges_from(edges, weight='weight')

        self.gtG.ep["weight"] = self.gtG.new_edge_property("float")

        eprops = [self.gtG.ep["weight"]]

        self.gtG.add_edge_list(edges, eprops=eprops)

        #out=self.gtG.get_out_degrees(self.gtG.get_vertices())

        reconnectGraph(self.gtG, distM)

    def getGraph(self):

        return self.gtG, self.nxG