def Bestplacement(graph, colors,avg_weight,max_weight,inter_weight):
    subG = subGraph(graph,colors)              

    controllers = []
    for subg in subG:
        controllerplace = ''
        mintl = -1
        for node in subg:
            lenghts = nx.single_source_shortest_path_length(subg,node)
            lenghts_graph = nx.single_source_shortest_path_length(graph,node)
            mx = -1
            ag = 0.0
            wg = 0.0
            for l in lenghts:
                if lenghts[l]>mx:
                    mx = lenghts[l]
                ag += lenghts[l]
            for l in lenghts_graph:
                wg += lenghts_graph[l]
            tl = tradeoff_function(ag/nx.number_of_nodes(subg),avg_weight,mx,max_weight,wg/nx.number_of_nodes(graph),inter_weight)
            #tl = avg_weight*(ag/nx.number_of_nodes(subg))+max_weight*mx
            if mintl < 0:
                mintl = tl
                controllerplace = node
            elif tl < mintl:
                mintl = tl
                controllerplace = node
        controllers.append(controllerplace)
    return controllers

def ego_graph(G,n,radius=1,center=True,undirected=False,distance=None):
    """Returns induced subgraph of neighbors centered at node n within
    a given radius.
    
    Parameters
    ----------
    G : nxgraph
      A NetworkX Graph or DiGraph

    n : node 
      A single node 

    radius : number, optional
      Include all neighbors of distance<=radius from n.
      
    center : bool, optional
      If False, do not include center node in nxgraph

    undirected : bool, optional      
      If True use both in- and out-neighbors of directed graphs.

    distance : key, optional      
      Use specified edge data key as distance.  For example, setting
      distance='weight' will use the edge weight to measure the
      distance from the node n.

    Notes
    -----
    For directed graphs D this produces the "out" neighborhood
    or successors.  If you want the neighborhood of predecessors
    first reverse the nxgraph with D.reverse().  If you want both
    directions use the keyword argument undirected=True.

    Node, edge, and nxgraph attributes are copied to the returned subgraph.
    """
    if undirected:
        if distance is not None:
            sp,_=nx.single_source_dijkstra(G.to_undirected(),
                                           n,cutoff=radius,
                                           weight=distance)
        else:
            sp=nx.single_source_shortest_path_length(G.to_undirected(),
                                                     n,cutoff=radius)
    else:
        if distance is not None:
            sp,_=nx.single_source_dijkstra(G,
                                           n,cutoff=radius,
                                           weight=distance)
        else:
            sp=nx.single_source_shortest_path_length(G,n,cutoff=radius)

    H=G.subgraph(sp).copy()
    if not center:
        H.remove_node(n)
    return  H

def calc_LDEglob_node(G, xNode):
    '''
    A function to calculate the nodal contribution of path length
    L, diameter D, and global efficiency Eglob from a node xNode.
    
    input parameters:
          G:      A graph in networkX format.
          xNode:  The node where the nodal global efficiency is calculated.
    
    returns:
          L:         The nodal path length at xNode.
          D:         The nodal diameter at xNode.
          EglobSum:  The nodal global efficiency.
    '''
         
    NNodes = len(G.nodes())
    Dx = list(nx.single_source_shortest_path_length(G, xNode).values())
    indZ = np.nonzero(np.array(Dx)==0)[0]
    nzDx = np.delete(Dx, indZ)
    if len(nzDx)>0:
        EglobSum = np.sum(1.0/nzDx)
        L = np.mean(nzDx)
        D = np.max(nzDx)
    else:
        EglobSum = 0
        L = 0
        D = 0
    # returning the nodal global efficiency
    return L, D, EglobSum

def obca(g):
    diameter = nx.diameter(g)
    lb_max = diameter + 1

    # Rank the nodes according to their degree
    results = nx.degree_centrality(g)
    nodes = next(zip(*sorted(results.items(), key=operator.itemgetter(1))))
    results = dict()

    for lb in range(2, lb_max):
        covered_frequency = [0] * len(g.nodes())
        boxes = list()

        for i in range(0, len(nodes)):
            node = nodes[i]

            if covered_frequency[i] > 0:
                continue

            box = list(nx.single_source_shortest_path_length(g, node, lb-1).keys())

            # Verify that all paths within the box have the length less then lb
            index = 0
            while True:
                node = box[index]
                for j in range(index+1, len(box)):
                    neighbor = box[j]

                    if nx.shortest_path_length(g, node, neighbor) >= lb:
                        box.remove(neighbor)

                index += 1
                if index >= len(box):
                    break

            for node in box:
                node_index = nodes.index(node)
                covered_frequency[node_index] += 1

            boxes.append(box)

        for box in boxes:
            redundant_box = True

            for node in box:
                node_index = nodes.index(node)
                if covered_frequency[node_index] == 1:
                    redundant_box = False
                    break

            if redundant_box:
                for node in box:
                    node_index = nodes.index(node)
                    covered_frequency[node_index] -= 1
                boxes.remove(box)

        print("lb: {}, boxes: {}, cf: {}".format(lb, boxes, covered_frequency))
        results[lb] = boxes

    return results

def savegraph(G, i):

    G = nx.random_geometric_graph(200, 0.125)
    # position is stored as node attribute data for random_geometric_graph
    # pos=nx.get_node_attributes(G,'pos')

    # find node near center (0.5,0.5)
    # dmin=1
    # ncenter=0
    # for n in pos:
    #    x,y=pos[n]
    #    d=(x-0.5)**2+(y-0.5)**2
    #    if d<dmin:
    #        ncenter=n
    #        dmin=d

    ncenter = 0.5
    dmin = 0.5

    # color by path length from node near center
    p = nx.single_source_shortest_path_length(G, ncenter)

    plt.figure(figsize=(8, 8))
    nx.draw_networkx_edges(G, pos, nodelist=[ncenter], alpha=0.4)
    nx.draw_networkx_nodes(G, pos, nodelist=p.keys(), node_size=80, node_color=p.values(), cmap=plt.cm.Reds_r)

    plt.xlim(-0.05, 1.05)
    plt.ylim(-0.05, 1.05)
    plt.axis("off")
    name = "graph " + str(i) + ".png"
    plt.savefig(name)

def _global_relabeling_heuristic(G, t, labels_dict=None, res_capacity='res_capacity', 
                                 capacity='capacity',preflow='preflow',
                                 distance='distance',excess='excess'):
    """
    The global relabeling heuristic updates the distance function by computing
    shortest path distances in the residual graph from all nodes to the sink.
    """
    res_G = nx.DiGraph()
    for u,v in G.edges_iter():
        if G[u][v][capacity] - G[u][v][preflow] > 0:
            res_G.add_edge(u,v,res_capacity=G[u][v][capacity]-G[u][v][preflow])
        if G[u][v][preflow] > 0:
            res_G.add_edge(v,u,res_capacity=G[u][v][preflow])

    distances = nx.single_source_shortest_path_length(
                               res_G.reverse(copy=False), t)
    for v in distances:
        G.node[v][distance] = distances[v]
            
    if labels_dict is not None:
        for v in distances:
            if G.node[v][excess] > 0 and labels_dict.has_key(G.node[v][distance]):
                labels_dict[G.node[v][distance]].remove(v)
                if labels_dict.has_key(distances[v]):
                    labels_dict[distances[v]].append(v)
                else:
                    labels_dict[distances[v]] = [v]

def approximate_cpl(graph, q=0.5, delta=0.15, eps=0.05):
    """
    Computes the approximate CPL for the specified graph
    :param graph: the graph
    :param q: the q-median to use (default 1/2-median, i.e., median)
    :param delta: used to compute the size of the sample
    :param eps: used to compute the size of the sample
    :return: the median
    :rtype: float
    """
    import networkx
    assert isinstance(graph, networkx.Graph)
    s = _estimate_s(q, delta, eps)
    s = int(math.ceil(s))
    if graph.number_of_nodes() <= s:
        sample = graph.nodes_iter()
    else:
        sample = random.sample(graph.adj.keys(), s)

    averages = []
    for node in sample:
        path_lengths = networkx.single_source_shortest_path_length(graph, node)
        average = sum(path_lengths.values()) / float(len(path_lengths))
        averages.append(average)
    averages.sort()
    median_index = int(len(averages) * q + 1)
    return averages[median_index]

def get_neighbors(graph, node, level):
    """Get neighbors of a given node up to a certain level"""

    min_level = int(level)
    if min_level < level:
        max_level = min_level + 1
        percentaje = level - min_level
    else:
        max_level = level
        percentaje = 0

    # All neighbors up to max_level
    all_neighbors = nx.single_source_shortest_path_length(graph, node,
                                                          cutoff=max_level)

    if percentaje > 0:
        neighbors_min_level = [k for (k, v) in all_neighbors.items() if (1 <= v <= min_level)]
        neighbors_max_level = [k for (k, v) in all_neighbors.items() if v == max_level]
        n = np.round(len(neighbors_max_level) * percentaje)
        additional_neighbors = random.sample(neighbors_max_level, int(n))
        neighbors = neighbors_min_level + additional_neighbors
    else:
        neighbors = [k for (k, v) in all_neighbors.items() if (1 <= v <= max_level)]

    return neighbors

def node_connected_component(G,n):
    """Return nodes in connected components of graph containing node n.

    Parameters
    ----------
    G : NetworkX Graph
       An undirected graph.

    n : node label       
       A node in G

    Returns
    -------
    comp : lists
       A list of nodes in component of G containing node n.

    See Also       
    --------
    connected_components

    Notes
    -----
    For undirected graphs only. 
    """
    if G.is_directed():
        raise nx.NetworkXError("""Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph.""")
    return list(nx.single_source_shortest_path_length(G,n).keys())

    def show_geo_graph(graph):
        node_position = nx.get_node_attributes(graph,'pos')

        # Find node near center (0.5,0.5)
        d_min            = 1
        node_near_center = 0
        for node in node_position:
            x, y = node_position[node]
            distance = (x - 0.5)**2 + (y - 0.5)**2
            if distance < d_min:
                node_near_center = node
                d_min = distance

        # Color by path length from node near center
        color_node        = dict(nx.single_source_shortest_path_length(graph, node_near_center))
        array_color_node  = np.array(list(color_node.values()))

        sns.set_style('darkgrid')
        cmap = sns.cubehelix_palette(start = .5, rot = -.65, dark = .4, light = .6, as_cmap = True)
        plt.figure(figsize = (10, 8))
        nx.draw_networkx_edges(graph, node_position, nodelist=[node_near_center],alpha=0.4)
        nx.draw_networkx_nodes(graph, node_position, nodelist=color_node.keys(),
                               node_size = 80,
                               node_color = array_color_node,
                               cmap = cmap)

        plt.xlim(0,1)
        plt.ylim(0,1)
        plt.axis('off')
        file = str(graph_path) + "/graph.pdf"
        plt.savefig(file, transparent = True)

def add_pseudo_edges(g, dg, threshold):
    """ flawed logic, needs to be fixed """

    if threshold == -1 : return -1

    if len(dg) == 0:
        dg = nx.read_edgelist(sys.argv[2], create_using=dg)

    new_edges = []
    for n in dg.nodes():

        if not g.has_node(n): continue

        fw_count = {}
        n_dists = nx.single_source_shortest_path_length(g,n,4)
        followings = set(dg.successors(n))

        for node, dist in n_dists.iteritems():
            if dist > 2: continue

            for f in dg.successors(node):
                if f not in followings:
                    if f in fw_count:
                        fw_count[f] = fw_count[f] + 1
                    else: fw_count[f] = 1

        for k,v in fw_count.iteritems():
            if v >= threshold and k in n_dists and n_dists[k] <= 4: 
                new_edges.append((n,k))

    for e in new_edges: dg.add_edge(*e)
    print >> sys.stderr, "new edges", len(new_edges)
    return 0

def graphStats(graph):

    pathlengths = []

    #print("source vertex {target:length, }")
    for v in graph.nodes():
        spl = networkx.single_source_shortest_path_length(graph, v)
        #print('%s %s' % (v,spl))
        for p in spl.values():
            pathlengths.append(p)

    print('')
    print(
        "average shortest path length %s" %
         (sum(pathlengths) / len(pathlengths)))

    # histogram of path lengths
    dist = {}
    for p in pathlengths:
        if p in dist:
            dist[p] += 1
        else:
            dist[p] = 1

    print('')

    def _distances_from_function_exit(function):
        """
        :param function:    A normalized Function object.
        :returns:           A dictionary of basic block addresses and their distance to the exit of the function.
        """
        reverse_graph = function.graph.reverse()
        # we aren't guaranteed to have an exit from the function so explicitly add the node
        reverse_graph.add_node("start")
        found_exits = False
        for n in function.graph.nodes():
            if len(function.graph.successors(n)) == 0:
                reverse_graph.add_edge("start", n)
                found_exits = True

        # if there were no exits (a function with a while 1) let's consider the block with the highest address to
        # be the exit. This isn't the most scientific way, but since this case is pretty rare it should be okay
        if not found_exits:
            last = max(function.graph.nodes(), key=lambda x:x.addr)
            reverse_graph.add_edge("start", last)

        dists = networkx.single_source_shortest_path_length(reverse_graph, "start")

        # remove temp node
        del dists["start"]

        # correct for the added node
        for n in dists:
            dists[n] -= 1

        return dists

def r2_neighbors(graph, n):
    dict = nx.single_source_shortest_path_length(graph, n, 2)
    dict = gt.invert_dict(dict)
    if 2 in dict:
        return dict[2]
    else:
        return []

    def test_shortest_path(self):
        deg = [3, 2, 2, 1]
        G = nx.generators.havel_hakimi_graph(deg)
        cs1 = nxt.creation_sequence(deg, with_labels=True)
        for n, m in [(3, 0), (0, 3), (0, 2), (0, 1), (1, 3),
                     (3, 1), (1, 2), (2, 3)]:
            assert_equal(nxt.shortest_path(cs1, n, m),
                         nx.shortest_path(G, n, m))

        spl = nxt.shortest_path_length(cs1, 3)
        spl2 = nxt.shortest_path_length([t for v, t in cs1], 2)
        assert_equal(spl, spl2)

        spld = {}
        for j, pl in enumerate(spl):
            n = cs1[j][0]
            spld[n] = pl
        assert_equal(spld, nx.single_source_shortest_path_length(G, 3))

        assert_equal(nxt.shortest_path(['d', 'd', 'd', 'i', 'd', 'd'], 1, 2), [1, 2])
        assert_equal(nxt.shortest_path([3, 1, 2], 1, 2), [1, 2])
        assert_raises(TypeError, nxt.shortest_path, [3., 1., 2.], 1, 2)
        assert_raises(ValueError, nxt.shortest_path, [3, 1, 2], 'a', 2)
        assert_raises(ValueError, nxt.shortest_path, [3, 1, 2], 1, 'b')
        assert_equal(nxt.shortest_path([3, 1, 2], 1, 1), [1])

def depth_crawl(web, depth):
    random.seed(42)
    page_db = aduana.PageDB(tempfile.mkdtemp(prefix='test-', dir='./'))
    backend = aduana.frontera.Backend(
        aduana.BFScheduler.from_settings(
            page_db,
            settings={
                'MAX_CRAWL_DEPTH': depth
            }
        )
    )
    backend.frontier_start()
    backend.add_seeds([FakeLink('https://news.ycombinator.com/', 1.0)])

    crawled = []
    requests = True
    while requests:
        requests = backend.get_next_requests(10)
        for req in requests:
            crawled.append(req.url)
            links = web.crawl(req.url)
            backend.page_crawled(FakeResponse(req.url), map(FakeLink, links))

    dist = nx.single_source_shortest_path_length(
        web.graph,
        'https://news.ycombinator.com/',
        cutoff=depth
    )
    for page in crawled:
        assert dist[page] <= (depth - 1)

    backend.frontier_stop()

def connected_components(G):
    """Return nodes in connected components of graph.

    Parameters
    ----------
    G : NetworkX Graph
       An undirected graph.

    Returns
    -------
    comp : list of lists
       A list of nodes for each component of G.

    See Also       
    --------
    strongly_connected_components

    Notes
    -----
    The list is ordered from largest connected component to smallest.
    For undirected graphs only. 
    """
    if G.is_directed():
        raise nx.NetworkXError("""Not allowed for directed graph G.
              Use UG=G.to_undirected() to create an undirected graph.""")
    seen={}
    components=[]
    for v in G:      
        if v not in seen:
            c=nx.single_source_shortest_path_length(G,v)
            components.append(list(c.keys()))
            seen.update(c)
    components.sort(key=len,reverse=True)            
    return components            

def random_graph():
    G=nx.random_geometric_graph(200,0.125)
    # position is stored as node attribute data for random_geometric_graph
    pos=nx.get_node_attributes(G,'pos')

    # find node near center (0.5,0.5)
    dmin=1
    ncenter=0
    for n in pos:
        x,y=pos[n]
        d=(x-0.5)**2+(y-0.5)**2
        if d<dmin:
            ncenter=n
            dmin=d

    # color by path length from node near center
    p=nx.single_source_shortest_path_length(G,ncenter)

    plt.figure(figsize=(8,8))
    nx.draw_networkx_edges(G,pos,nodelist=[ncenter],alpha=0.4)
    nx.draw_networkx_nodes(G,pos,nodelist=p.keys(),
                           node_size=80,
                           node_color=p.values(),
                           cmap=plt.cm.Reds_r)

    plt.xlim(-0.05,1.05)
    plt.ylim(-0.05,1.05)
    plt.axis('off')
    #plt.savefig('random_geometric_graph.png')
    plt.show()

 def test_single_source_shortest_path_length(self):
     ans = dict(nx.shortest_path_length(self.cycle, 0))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans,
                  dict(nx.single_source_shortest_path_length(self.cycle,
                                                             0)))
     ans = dict(nx.shortest_path_length(self.grid, 1))
     assert_equal(ans[16], 6)
     # now with weights
     ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight'))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans, dict(nx.single_source_dijkstra_path_length(
         self.cycle, 0)))
     ans = dict(nx.shortest_path_length(self.grid, 1, weight='weight'))
     assert_equal(ans[16], 6)
     # weights and method specified
     ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight',
                                        method='dijkstra'))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans, dict(nx.single_source_dijkstra_path_length(
         self.cycle, 0)))
     ans = dict(nx.shortest_path_length(self.cycle, 0, weight='weight',
                                        method='bellman-ford'))
     assert_equal(ans, {0: 0, 1: 1, 2: 2, 3: 3, 4: 3, 5: 2, 6: 1})
     assert_equal(ans, dict(nx.single_source_bellman_ford_path_length(
         self.cycle, 0)))

def findNeighbours_of_Nulls(fileName, writer):
   G = nx.Graph()
   
   with open(fileName, 'r') as meterFile:
      distReader = csv.reader(meterFile, delimiter=',')
      next(distReader, None)
      for row in distReader:
        G.add_node(row[0], lat=row[1], lng=row[2])
        G.add_node(row[3], lat=row[4], lng=row[5])
        G.add_edge(row[0],row[3], length= row[-1])
   coord_neighbors = {}     
   nulls = [n for n in G.nodes() if G.node[n]['lat'] == "null" and G.node[n]['lng'] == "null"]
   for node in nulls:
     length = nx.single_source_shortest_path_length(G,node)
     sorted_length = sorted(length.items(), key=operator.itemgetter(1))
     neighCoords = []
     # exclude the firs item of list from the loop which is the node itself with the distance of zero from the node! i.e. ('node',0)
     for l in sorted_length[1:]:
       # check the distance of node from the neigbor and if the neighbor has coordinate
       if 0 < l[1] and G.node[l[0]]['lat'] != "null" and G.node[l[0]]['lng'] != "null":
           # add the neighbor to array
           neighCoords.append( l[1])
       # limit the neighbors to two to have at leat two neighbours with 
       if len(neighCoords) >= 2:
         break
     writer.writerow([node,neighCoords])