def neighbor_bound(G, v, w, radius):
    g1 = nx.ego_graph(G, v, radius=radius, undirected=False)
    g2 = nx.ego_graph(G, w, radius=radius, undirected=False)
    if len(set(g1.edges()) & set(g2.edges())) > 0:
        return True
    else:
        return False

def node_clique_number(G, nodes=None, cliques=None):
    """ Returns the size of the largest maximal clique containing
    each given node.

    Returns a single or list depending on input nodes.
    Optional list of cliques can be input if already computed.
    """
    if cliques is None:
        if nodes is not None:
            # Use ego_graph to decrease size of graph
            if isinstance(nodes, list):
                d = {}
                for n in nodes:
                    H = nx.ego_graph(G, n)
                    d[n] = max((len(c) for c in find_cliques(H)))
            else:
                H = nx.ego_graph(G, nodes)
                d = max((len(c) for c in find_cliques(H)))
            return d
        # nodes is None--find all cliques
        cliques = list(find_cliques(G))

    if nodes is None:
        nodes = list(G.nodes())   # none, get entire graph

    if not isinstance(nodes, list):   # check for a list
        v = nodes
        # assume it is a single value
        d = max([len(c) for c in cliques if v in c])
    else:
        d = {}
        for v in nodes:
            d[v] = max([len(c) for c in cliques if v in c])
    return d

def build_activity_graph(activity_uri, activity_id):
    G = nx.DiGraph()
    
    q_activity_to_resource = render_template('activity_to_resource.q', activity_uri = activity_uri)
    
    G = build_graph(G, activity_uri, "activity", "concept", q_activity_to_resource)
    
    q_resource_to_activity = render_template('resource_to_activity.q', activity_uri = activity_uri)
    
    G = build_graph(G, activity_uri, "concept", "activity", q_resource_to_activity)
    
    print activity_uri, activity_id
    
    # origin_node_id = "{}".format(activity_id.lower())
    origin_node_id = activity_id
    
    G.node[origin_node_id]['type'] = 'origin'
    
    names = {}
    for n, nd in G.nodes(data=True):
        if nd['type'] == 'activity' or nd['type'] == 'origin':
            label = nd['label'].replace('Activity','').upper()            
            names[n] = label
        else :
            names[n] = nd['label']
            
    
    
    
    
    nx.set_node_attributes(G,'label', names)
    
    
    
    deg = nx.degree(G)
    nx.set_node_attributes(G,'degree',deg)
    
    
    outG = nx.ego_graph(G,origin_node_id,50)
    inG = nx.ego_graph(G.reverse(),origin_node_id,50)
    
    inG = inG.reverse()
    
    sG = nx.compose(outG,inG)
    
    
            
    
    assign_weights(sG, [])
            
            
    print sG.edges(data=True)
    
    
    
    g_json = json_graph.node_link_data(sG) # node-link format to serialize

    
    return g_json

def neighbor_bound(G, v, w, radius):
    """
    test if the node v and the node w are connected within a radius in graph G
    """
    g1 = nx.ego_graph(G, v, radius=radius, undirected=False)
    g2 = nx.ego_graph(G, w, radius=radius, undirected=False)
    if len(set(g1.edges()) & set(g2.edges())) > 0:
        return True
    else:
        return False

 def test_ego_distance(self):
     G=nx.Graph()                                                            
     G.add_edge(0,1,weight=2,distance=1)
     G.add_edge(1,2,weight=2,distance=2)
     G.add_edge(2,3,weight=2,distance=1) 
     assert_equal(sorted(nx.ego_graph(G,0,radius=3).nodes()),[0,1,2,3])
     eg=nx.ego_graph(G,0,radius=3,distance='weight')
     assert_equal(sorted(eg.nodes()),[0,1])
     eg=nx.ego_graph(G,0,radius=3,distance='distance')
     assert_equal(sorted(eg.nodes()),[0,1,2])

def subgraph(G, node_list, radius=0):

    _graph = nx.ego_graph(G,node_list[0],radius=radius)

    for node in node_list[1:]:

        if G.has_node(node):
            _graph = nx.compose(_graph, nx.ego_graph(G, node, radius=radius))

    return _graph

 def test_ego(self):
     G=nx.star_graph(3)
     H=nx.ego_graph(G,0)
     assert_true(nx.is_isomorphic(G,H))
     G.add_edge(1,11)
     G.add_edge(2,22)
     G.add_edge(3,33)
     H=nx.ego_graph(G,0)
     assert_true(nx.is_isomorphic(nx.star_graph(3),H))
     G=nx.path_graph(3)
     H=nx.ego_graph(G,0)
     assert_equal(H.edges(), [(0, 1)])

def extract_ego_graph(G, activity_uri):
    sG = None
    inG = None
    outG = None
    
    app.logger.debug(u"Extracting ego graph (forward) {}".format(activity_uri))
    outG = nx.ego_graph(G,activity_uri,50)
    app.logger.debug(u"Extracting ego graph (backward) {}".format(activity_uri))
    inG = nx.ego_graph(G.reverse(),activity_uri,50)
    app.logger.debug(u"Reversing backward ego graph {}".format(activity_uri))
    inG = inG.reverse()
    app.logger.debug(u"Joining ego graphs {}".format(activity_uri))
    sG = nx.compose(outG,inG)
    
    return sG

def get_ego_graph(graph, character):
    """
    Expecting a graph_from_gdf
    """

    # Graph and Position
    ego = nx.ego_graph(graph, character, 3)
    pos = nx.spring_layout(ego)
    plt.figure(figsize=(12,12))
    plt.axis('off')

    # Coloration and Configuration
    ego.node[character]["TYPE"] = "center"
    valmap = { "comic": 0.25, "hero": 0.54, "center": 0.87 }
    types  = nx.get_node_attributes(ego, "TYPE")
    values = [valmap.get(types[node], 0.25) for node in ego.nodes()]

    # Draw
    nx.draw_networkx_edges(ego, pos, alpha=0.4)
    nx.draw_networkx_nodes(ego, pos,
                           node_size=80,
                           node_color=values,
                           cmap=plt.cm.hot, with_labels=False)

    #plt.show()
    plt.savefig("figure/longbow_ego_2hop.png")

def Similarity(G,asin,amazonBooks,maxnumber):
    simitems=[]
    neighbors=(G.neighbors(asin))

#egoNetwork: get_ego_network(coPurchaseGraph, asin, radius = 1)
#threshold = median(weights of edges in egoNetwork)

    ego = networkx.ego_graph(G, asin, radius=1)
    
    mediansimilarity =statistics.median([ego[x][asin]['weight'] for x in neighbors ])   
    similaritydict={}
    threshold = mediansimilarity
#    islandGraph: A graph, initialized to null
    gIslands = networkx.Graph()
    #create islandGraph with the threshold
    for f,t,e in ego.edges(data = True):
        if(e['weight'] > threshold):
            gIslands.add_edge(f,t,e)
    nodelist=gIslands.nodes(data = False)
    for n in nodelist:       
        if(n != asin):
         if(ego[n][asin]['weight'] == 0):
             print("error: edge weight is zero")
             similaritydict[n]=maxnumber
         else:
#    Rank the nodes with the Sales Rank as follows
#   	Rank[node] = salesRank/weight
          similaritydict[n]=(amazonBooks[n]['SalesRank'])/(ego[n][asin]['weight']) 
          #simItems = Sort(Rank)
    sortedsim=(sorted(similaritydict.items(), key = lambda x:x[1])[:100])
    simitems = [x[0] for x in sortedsim]
    return simitems

    def execute(self):
        """
        Execute Demon algorithm

        """

        for n in self.g.nodes():
            self.g.node[n]['communities'] = [n]

        all_communities = {}

        for ego in tqdm.tqdm(nx.nodes(self.g), ncols=35, bar_format='Exec: {l_bar}{bar}'):

            ego_minus_ego = nx.ego_graph(self.g, ego, 1, False)
            community_to_nodes = self.__overlapping_label_propagation(ego_minus_ego, ego)

            # merging phase
            for c in community_to_nodes.keys():
                if len(community_to_nodes[c]) > self.min_community_size:
                    actual_community = community_to_nodes[c]
                    all_communities = self.__merge_communities(all_communities, actual_community)

        # write output on file
        if self.file_output:
            with open(self.file_output, "w") as out_file_com:
                for idc, c in enumerate(all_communities.keys()):
                    out_file_com.write("%d\t%s\n" % (idc, str(sorted(c))))

        return list(all_communities.keys())

def numCommunitiesEgoCentricNetwork(G, ego):
    ego_net = nx.ego_graph(G,n)
    ego_net.remove_node(ego)
    if len(ego_net.edges()) == 0:
        return len(ego_net.nodes())
    else:
        return findCommunities(ego_net)

    def get_triadic_recommendations(self, commid, userid, k):
        """ Given a graph give neighbor of neighbor recommendations 
        """
        # get the ego network of the user 2 step
        G = self.community_data[commid]['graph']
        EG = nx.ego_graph(G, userid, 2)
        
        
        nbrs = []
        for n in EG.neighbors(userid):
            if n != userid:
                for non in G.neighbors(n):
                    if non != userid and non in self.tsusers:
                        nbrs.append(n)


        #print "neighbors of neighbors on", nbrs
        # get neighbors and neighbors of neighbors
        # that is not you
        # neighbors = set(EG.neighbors) - set([userid])
        #nons = set(neighbors_of_neighbors)-set([userid])

        # for 
        reccos = []
        for n in nbrs:
            reason = "neighbor who likes a townsquare member"
            reccos.append((n, reason))
        
        if len(reccos) >= k:
            return reccos[0:k]
        return reccos

    def ego_graph(self, radius=1, types=None, min_degree=None):
        '''Generate an undirected ego graph around the current entity.

        :param radius: radius or degree of the ego graph; defaults to 1
        :param types: node types to be included in the graph (e.g., restrict
            to people and organizations only)
        :param min_degree: optionally filter nodes in the generated ego graph
            by minimum degree
        '''
        network = network_data()
        undirected_net = network.to_undirected()

        # filter network *before* generating ego graph
        # so we don't get disconnected nodes
        if types is not None:
            for n in undirected_net.nodes():
                if 'type' not in undirected_net.node[n] or \
                   undirected_net.node[n]['type'] not in types:
                    undirected_net.remove_node(n)

        # converted multidigraph to undirected
        # to make it possible to find all neighbors,
        # not just outbound connections
        # (should be a way to get this from a digraph...)

        eg = nx.ego_graph(undirected_net, self.nx_node_id,
                            radius=radius)
        if min_degree is not None:
            return filter_graph(eg, min_degree=min_degree)
        return eg

 def get_center_ego(graph):
     bt = nx.betweenness_centrality(graph)
     print(bt)
     for (node, betweenness) in sorted(bt.items(), key=lambda x: x[1], reverse=True):
         nodes = nx.ego_graph(graph, node).nodes()
         print(nodes)
         return nodes

def drawGraph(spammers):
    for i in range(1, ver + 1):
        if i in spammers:
            spamTag.append('r')
        else:
            spamTag.append('b')

    nodes = []
    for t in range(1, ver + 1):
        nodes.append(t);
    G = nx.Graph()
    G.add_nodes_from(nodes)
    G.add_edges_from(edges)
    #G=nx.generators.barabasi_albert_graph(len(nodes),len(edges)
    # find node with largest degree
    node_and_degree = G.degree()
    (largest_hub, degree) = sorted(node_and_degree.items(), key=itemgetter(1))[-1]
    # Create ego graph of main hub
    hub_ego = nx.ego_graph(G, largest_hub)
    # Draw graph
    pos = nx.spring_layout(hub_ego)
    nx.draw(hub_ego, pos, node_color=spamTag, node_size=50, with_labels=False)
    # Draw ego as large and red
    nx.draw_networkx_nodes(hub_ego, pos, nodelist=[largest_hub], node_size=300, node_color='r')
    plt.savefig(name+"/"+ name+'_MCLGraph.png')
    plt.show()

def get_weighted_ego_graph(graph, character, hops=1):
    # Graph and Position
    ego = nx.ego_graph(graph, character, hops)
    pos = nx.spring_layout(ego)
    plt.figure(figsize=(12,12))
    plt.axis('off')

    # Coloration and Configuration
    ego.node[character]["TYPE"] = "center"
    valmap = { "hero": 0.0, "center": 1.0 }
    types  = nx.get_node_attributes(ego, "TYPE")
    values = [valmap.get(types[node], 0.25) for node in ego.nodes()]

    char_edges = ego.edges(data=True, nbunch=[character,])
    nonchar_edges = ego.edges(nbunch=[n for n in ego.nodes() if n != character])
    elarge=[(u,v) for (u,v,d) in char_edges if d['weight'] >=0.12]
    esmall=[(u,v) for (u,v,d) in char_edges if d['weight'] < 0.12]
    print set([d['weight'] for (u,v,d) in char_edges])

    # Draw
    nx.draw_networkx_nodes(ego, pos,
                           node_size=200,
                           node_color=values,
                           cmap=plt.cm.Paired, with_labels=False)

    nx.draw_networkx_edges(ego,pos,edgelist=elarge,
                        width=1.5, edge_color='b')
    nx.draw_networkx_edges(ego,pos,edgelist=esmall,
                        width=1,alpha=0.5,edge_color='b',style='dashed')
    nx.draw_networkx_edges(ego,pos,edgelist=nonchar_edges,
                        width=0.5,alpha=0.2,style='dashed')

    plt.show()

 def test_ego(self):
     G = nx.star_graph(3)
     H = nx.ego_graph(G, 0)
     assert_true(nx.is_isomorphic(G, H))
     G.add_edge(1, 11)
     G.add_edge(2, 22)
     G.add_edge(3, 33)
     H = nx.ego_graph(G, 0)
     assert_true(nx.is_isomorphic(nx.star_graph(3), H))
     G = nx.path_graph(3)
     H = nx.ego_graph(G, 0)
     assert_edges_equal(H.edges(), [(0, 1)])
     H = nx.ego_graph(G, 0, undirected=True)
     assert_edges_equal(H.edges(), [(0, 1)])
     H = nx.ego_graph(G, 0, center=False)
     assert_edges_equal(H.edges(), [])

 def __init__(self, view, controller, use_ego_betw=False, **kwargs):
     super(CacheLessForMore, self).__init__(view, controller)
     topology = view.topology()
     if use_ego_betw:
         self.betw = dict((v, nx.betweenness_centrality(nx.ego_graph(topology, v))[v])
                          for v in topology.nodes_iter())
     else:
         self.betw = nx.betweenness_centrality(topology)

def largest_hub_in_graph(G):
    # find node with largest degree
    node_and_degree = G.degree()
    (largest_hub, degree) = sorted(node_and_degree.items(), key=itemgetter(1))[-1]
    # Create ego graph of main hub
    hub_ego = nx.ego_graph(G, largest_hub)
    hub_degree = nx.degree(G, largest_hub)
    print "largest hub ID: " + str(largest_hub) + "\t" + "largest hub degree: " + str(hub_degree)