def calculate_indegree(graph):
    # will only work on DiGraph (directed graph)
    print "Calculating indegree..."
    g = graph
    indeg = g.in_degree()
    nx.set_node_attributes(g, 'indegree', indeg)
    return g, indeg

    def update_pos(self,n,p,now=0.,p_pe='p'):
        """ 
        Update Position of a node

        Parameters
        ----------

        n      : float/string (or a list of)
            node ID
        p    : np.array  ( or a list of )
            node position 
                
        """

        if (isinstance(p,np.ndarray)) or (isinstance(n,list) and isinstance(p,list) ):
            # Tranfrom input as list
            if not(isinstance(n,list)):
                n=[n]
                p=[p]
            if len(n) == len(p):    
                d=dict(zip(n,p))    # transform data to be complient with nx.set_node_attributes            
                nowd=dict(zip(n,[now]*len(n)))
            else :
                raise TypeError('n and p must have the same length')
            # update position
            nx.set_node_attributes(self,p_pe,d)        
            # update time of ground truth position
            if p_pe=='p':
                nx.set_node_attributes(self,'t',nowd)
        else :
            raise TypeError('n and p must be either: a key and a np.ndarray, or 2 lists')

	def from_trial_data(cls, circuit, cycles, pos, resultinfo, trialid, step):
		# several parts of this script would require reconsideration to support trials
		# where the vertices weren't actually deleted
		if resultinfo['defect_mode']['mode'] != 'direct removal':
			raise RuntimeError('This script was only written with "remove" mode in mind')

		# Find change in currents
		before = analysis.trial_edge_currents_at_step(circuit, cycles, resultinfo, trialid, step)
		after  = analysis.trial_edge_currents_at_step(circuit, cycles, resultinfo, trialid, step+1)

		before = edict_remove_redundant_entries(before)
		delta  = {e: after.get(e, 0.0) - before[e] for e in before}

		# NOTE: this reconstruction will lack some isolated vertices
		defects = set(get_added_defects(resultinfo, trialid, step))
		defect_dict = {v:False for v in edict_vertices(delta)}
		defect_dict.update({v:True for v in defects})

		sources = {(s,t):s for (s,t) in delta}

		g = nx.Graph()
		g.add_edges_from(delta)
		g.add_nodes_from(defects) # in case any of the defects are isolated vertices

		# ``pos`` contains all vertices from the graph's initial state.  Limit it to those currently
		#  in the modified graph (because set_node_attributes crashes on nodes that don't exist)
		pos = {k:v for k,v in pos.items() if k in g}

		nx.set_edge_attributes(g, EATTR_CHANGE, delta)
		nx.set_edge_attributes(g, EATTR_SOURCE, sources)
		nx.set_node_attributes(g, VATTR_POS, pos)
		nx.set_node_attributes(g, VATTR_DEFECT, defect_dict)
		return cls(g)

def calculate_betweenness(graph):
	''' Calculate betweenness centrality of a node, sets value on node as attribute; returns graph, and dict of the betweenness centrality values
	'''
	g = graph
	bc=nx.betweenness_centrality(g)
	nx.set_node_attributes(g,'betweenness',bc)
	return g, bc

 def new_vertex_property(self, name):
     values = {v: None for v in self.nodes()}
     nx.set_node_attributes(self, name=name, values=values)
     if name == 'vertex_color':
         self.vertex_color = [0 for v in range(self.number_of_nodes())]
     if name == 'vertex_fill_color':
         self.vertex_fill_color = [0 for v in range(self.number_of_nodes())]

def import_layout(from_fname, to_graph):
    if not from_fname[-4:]  =='.gml': from_fname +='.gml'

    print 'importing layout from', from_fname+'..'
    g1 =  NX.read_gml(from_fname)
    labels1 = NX.get_node_attributes(g1, 'label')
    n1 = set(labels1.values())
    
    g2 =    to_graph
    n2 = set(g2.nodes())

    if not n1:
        print '   empty target graph'
        return
    if not n2:
        print '   empty layout graph'
        return

    mapping = {}
    for L1 in labels1:
        for name in n2:
            if labels1[L1]==name:
                mapping[L1] = name
                break

    intersection = len(n2.intersection(n1))
    percent=100.*intersection/len(n2)
    print '   %.1f%%'%percent,'(%i positions)'%intersection

    layout = NX.get_node_attributes(g1, 'graphics')
    attr = dict([  (  mapping[ID],  {'x':layout[ID]['x'],'y':layout[ID]['y']}  )   for ID in mapping])
    
    NX.set_node_attributes(g2, 'graphics', attr)

    def _parse(self):
        # Initialize variables
        self.tree = nx.DiGraph()
        self.name2taxon_id = defaultdict(int)
        self.taxon_id2name = defaultdict(str)
        ncbi_taxdmp_dir = self._downloaders[0].path
        # csv.field_size_limit(sys.maxsize)

        with open(os.path.join(ncbi_taxdmp_dir, 'names.dmp'), 'r') as handle:
            # csv_handle = csv.reader(handle, delimiter="\t")
            for cols in handle:
                cols = cols.split('\t')
                taxon_id = int(cols[0])
                name = cols[2]
                self.name2taxon_id[name] = taxon_id
                if cols[-2] == 'scientific name':
                    self.taxon_id2name[taxon_id] = name

        # construct node tree
        edges = []
        nodes = {}
        with open(os.path.join(ncbi_taxdmp_dir, 'nodes.dmp'), 'r') as handle:
            csv_handle = csv.reader(handle, delimiter="\t")
            for cols in csv_handle:
                parent_node = int(cols[2])
                child_node = int(cols[0])
                rank = cols[4]
                nodes[child_node] = rank
                if child_node != parent_node:
                    edges.append((child_node, parent_node))

        self.tree.add_edges_from(edges)
        nx.set_node_attributes(self.tree, 'rank', nodes)

	def __update_structure(self):
		if self.seed:
			random.seed(self.seed)

		prob_out = self.avg_intercomm /\
			(float)(self.comm_size * (self.num_comm - 1))
		prob_in = 0.5 - (float)(self.avg_intercomm / self.comm_size)

		self.structure.add_nodes_from(range(self.num_comm * self.comm_size))

		for left_node in self.structure.nodes():
			nx.set_node_attributes(
				self.structure,
				"community",
				{left_node: left_node % self.num_comm}
			)
			for right_node in self.structure.nodes():
				if left_node < right_node:
					rand = random.random()
					if left_node % self.num_comm == right_node % self.num_comm:
						if rand <= prob_in:
							self.structure.add_edge(
								left_node,
								right_node
							)
					else:
						if rand <= prob_out:
							self.structure.add_edge(
								left_node,
								right_node
							)

def detect_communities(graph, verbose=False):
    graph = graph_from_csv(graph)
    partition = community.best_partition(graph)
    if verbose:
        print "%i partitions" % len(set(partition.values()))
    nx.set_node_attributes(graph, 'partition', partition)
    return graph, partition

    def to_networkx(self):
        """Return a NetworkX DiGraph object representing the single linkage tree.

        Edge weights in the graph are the distance values at which child nodes
        merge to form the parent cluster.

        Nodes have a `size` attribute attached giving the number of points
        that are in the cluster.
        """
        try:
            from networkx import DiGraph, set_node_attributes
        except ImportError:
            raise ImportError('You must have networkx installed to export networkx graphs')

        max_node = 2 * self._linkage.shape[0]
        num_points = max_node - (self._linkage.shape[0] - 1)

        result = DiGraph()
        for parent, row in enumerate(self._linkage, num_points):
            result.add_edge(parent, row[0], weight=row[2])
            result.add_edge(parent, row[1], weight=row[2])

        size_dict = {parent : row[3] for parent, row in enumerate(self._linkage, num_points)}
        set_node_attributes(result, 'size', size_dict)

        return result

def create_graph_df(vtask_paths, graphs_dir_out):
    """
    Creates a frame that maps sourcefiles to networkx digraphs in terms of DOT files
    :param source_path_list:
    :param dest_dir_path:
    :param relabel:
    :return:
    """
    if not isdir(graphs_dir_out):
        raise ValueError('Invalid destination directory.')
    data = []
    graphgen_times = []

    print('Writing graph representations of verification tasks to {}'.format(graphs_dir_out), flush=True)

    common_prefix = commonprefix(vtask_paths)
    for vtask in tqdm(vtask_paths):
        short_prefix = dirname(common_prefix)
        path = join(graphs_dir_out, vtask[len(short_prefix):][1:])

        if not os.path.exists(dirname(path)):
            os.makedirs(dirname(path))

        ret_path = path + '.pickle'

        # DEBUG
        if isfile(ret_path):
            data.append(ret_path)
            continue

        start_time = time.time()

        graph_path, node_labels_path, edge_types_path, edge_truth_path, node_depths_path \
            = _run_cpachecker(abspath(vtask))
        nx_digraph = nx.read_graphml(graph_path)

        node_labels = _read_node_labeling(node_labels_path)
        nx.set_node_attributes(nx_digraph, 'label', node_labels)

        edge_types = _read_edge_labeling(edge_types_path)
        parsed_edge_types = _parse_edge(edge_types)
        nx.set_edge_attributes(nx_digraph, 'type', parsed_edge_types)

        edge_truth = _read_edge_labeling(edge_truth_path)
        parsed_edge_truth = _parse_edge(edge_truth)
        nx.set_edge_attributes(nx_digraph, 'truth', parsed_edge_truth)

        node_depths = _read_node_labeling(node_depths_path)
        parsed_node_depths = _parse_node_depth(node_depths)
        nx.set_node_attributes(nx_digraph, 'depth', parsed_node_depths)

        assert not isfile(ret_path)
        assert node_labels and parsed_edge_types and parsed_edge_truth and parsed_node_depths
        nx.write_gpickle(nx_digraph, ret_path)
        data.append(ret_path)

        gg_time = time.time() - start_time
        graphgen_times.append(gg_time)

    return pd.DataFrame({'graph_representation': data}, index=vtask_paths), graphgen_times

def random_binary_dgm(n=10, p=0.2):
    G = nx.gnr_graph(n, p)
    dgm = DGM()
    dgm.add_nodes_from(G.nodes())
    dgm.add_edges_from(G.edges())
    nx.set_node_attributes(dgm, 'CPD', { node: TableFactor(random_table_factor(dgm.in_degree(node) + 1), list(dgm.predecessors(node)) + [node]) for node in dgm.nodes() })
    return dgm

    def test_node_num_attribute(self):

        g = nx.karate_club_graph()
        attr = {n: {"even": int(n % 10)} for n in g.nodes()}
        nx.set_node_attributes(g, attr)

        model = gc.CompositeModel(g)
        model.add_status("Susceptible")
        model.add_status("Infected")

        c = cpm.NodeNumericalAttribute("even", value=0, op="==", probability=1)
        model.add_rule("Susceptible", "Infected", c)

        config = mc.Configuration()
        config.add_model_parameter('percentage_infected', 0.1)

        model.set_initial_status(config)
        iterations = model.iteration_bunch(10)
        self.assertEqual(len(iterations), 10)

        model = gc.CompositeModel(g)
        model.add_status("Susceptible")
        model.add_status("Infected")

        c = cpm.NodeNumericalAttribute("even", value=[3, 5], op="IN", probability=1)
        model.add_rule("Susceptible", "Infected", c)

        config = mc.Configuration()
        config.add_model_parameter('percentage_infected', 0.1)

        model.set_initial_status(config)
        iterations = model.iteration_bunch(10)
        self.assertEqual(len(iterations), 10)

def calculate_outdegree(graph):
    # will only work on DiGraph (directed graph)
    print "Calculating outdegree..."
    g = graph
    outdeg = g.out_degree()
    nx.set_node_attributes(g, 'outdegree', outdeg)
    return g, outdeg

    def _get_demand_nodes(self, input_proj=None):
        """
        Converts the dataset_store metrics records to a GeoGraph of nodes
        (prereq:  _run_metric_model to populate store)

        Args:
            input_proj:  projection of demand node coordinates

        Returns:
            GeoGraph:  demand nodes as GeoGraph
        """

        coords = [node.getCommonCoordinates() for node in
                  self.store.cycleNodes()]

        # set default projection
        if not input_proj:
            input_proj = self._get_default_proj4(coords)

        # NOTE:  Although dataset_store nodes id sequence starts at 1
        # leave the GeoGraph ids 0 based because there are places in the
        # network algorithm that assume 0 based coords
        # This will be realigned later
        coords_dict = {i: coord for i, coord in enumerate(coords)}
        budget_dict = {i: node.metric for i, node in
                       enumerate(self.store.cycleNodes())}

        geo_nodes = GeoGraph(input_proj, coords_dict)
        nx.set_node_attributes(geo_nodes, 'budget', budget_dict)
        return geo_nodes

def build_graph(df, cluster_id, case_id, date_col, color, gen_mean, gen_sd):
    """
    Generate a directed graph from data on transmission tree.
    Node color is determined by node attributes, e.g. case severity or gender.
    df = pandas dataframe
    """

    clusters = basics.cluster_builder(df=df, cluster_id=cluster_id, \
                case_id=case_id, date_col=date_col, attr_col=color, \
                gen_mean=gen_mean, gen_sd=gen_sd)

    G = nx.DiGraph()
    G.add_nodes_from(clusters['case_id'])

    edgelist = [pair for pair in clusters[['source_node']].dropna().itertuples()]
    G.add_edges_from(edgelist)
    nx.set_node_attributes(G, 'date', clusters['time'].to_dict())
    nx.set_node_attributes(G, 'pltdate', clusters['pltdate'].to_dict())
    nx.set_node_attributes(G, 'source_node', clusters['source_node'].to_dict())
    nx.set_node_attributes(G, color, clusters[color].to_dict())
    nx.set_node_attributes(G, 'index_node', clusters['index_node'].to_dict())
    G = nx.DiGraph.reverse(G)

    for i in G.nodes():
        G.node[i]['generation'] = _generations(G, i)
    
    return G

    def build(self, matrix, skim_depth=10):

        """
        Build graph, with PageRanks on nodes.

        :param matrix: A term matrix.
        :param skim_depth: The number of sibling edges.
        """

        # Register nodes and edges.
        for anchor in progress.bar(matrix.terms):

            n1 = matrix.text.unstem(anchor)

            # Heaviest pair scores:
            pairs = matrix.anchored_pairs(anchor).items()
            for term, weight in list(pairs)[:skim_depth]:

                n2 = matrix.text.unstem(term)
                self.graph.add_edge(n1, n2, weight=weight)

        # Compute PageRanks.
        ranks = nx.pagerank(self.graph)
        first = max(ranks.values())

        # Convert to 0->1 ratios.
        ranks = {k: v/first for k, v in ranks.items()}

        # Annotate the nodes.
        nx.set_node_attributes(self.graph, 'pagerank', ranks)

def compute_friends_installed(g, count=False, set_attribute=True):
    """
    Analyzes neighborhood app installation ("app_installed" attribute).
    Sets nodes' "at_least_one_friend" property (if set_attribute=True)

    :param g: networkx graph
    :param count: boolean,
        if True, computes (for each node) the number of neighbors that
            have the app installed;
        otherwise, indicates whether any of the friends have the app installed
    :param set_attribute: boolean,
        if True, sets nodes' "at_least_one_friend" property and returns the graph;
        otherwise, returns a vector with the results
    :return: networkx graph or vector
    """

    myfriends_installed = {}
    for n, d in g.nodes_iter(data=True):
        fs = g.neighbors(n)
        myfriends_installed[n] = False
        for f in fs:
            if g.node[f]['app_installed']:
                if count:
                    myfriends_installed[n] += 1
                else:
                    myfriends_installed[n] = True
                    break

    if set_attribute:
        nx.set_node_attributes(g, 'at_least_one_friend', myfriends_installed)
        return g
    else:
        return myfriends_installed

def copy_layout(from_fname, to_fname):
    if not from_fname[-4:]  =='.gml': from_name +='.gml'
    if not to_fname[-4:]    =='.gml': to_name   +='.gml'

    print 'reading A=', from_fname,'..',
    g1 =  NX.read_gml(from_fname)
    labels1 = NX.get_node_attributes(g1, 'label')
    n1 = set(labels1.values())
    print len(n1),'nodes'
    
    print 'reading B=', to_fname,'..',
    g2 =    NX.read_gml(to_fname)
    labels2 = NX.get_node_attributes(g2, 'label')
    n2 = set(labels2.values())
    print len(n2),'nodes'

    intersection = len(n2.intersection(n1))
    percent=100.*intersection/len(n2)
    print 'B.intersect(A)=',intersection,'(%.1f%%)'%percent

    print 'copying layout..',
    mapping = {}
    for L1 in labels1:
        for L2 in labels2:
            if labels1[L1]==labels2[L2]:
                mapping[L1] = L2
                break

    layout = NX.get_node_attributes(g1, 'graphics')
    attr = dict([  (  mapping[ID],  {'x':layout[ID]['x'],'y':layout[ID]['y']}  )   for ID in mapping])
    
    NX.set_node_attributes(g2, 'graphics', attr)
    NX.write_gml(g2, to_fname)
    print 'done.'

def closeness_neighbors(seed_num, graph=None, graph_json_filename=None, graph_json_str=None):
  if graph_json_filename is None and graph_json_str is None and graph is None:
    return []

  G = None
  if graph is not None:
    G = graph
  elif graph_json_str is None:
    G = util.load_graph(graph_json_filename=graph_json_filename)
  else:
    G = util.load_graph(graph_json_str=graph_json_str)

  clse_cent = nx.get_node_attributes(G, "centrality")
  if len(clse_cent) == 0:
    clse_cent = nx.closeness_centrality(G)
    nx.set_node_attributes(G, "centrality", clse_cent)
    print "closeness neighbors"

  collector = collections.Counter(clse_cent)
  clse_cent = collector.most_common(SURROUND_TOP)
  nodes = map(lambda (x, y): x, clse_cent)

  current_seed = 0
  rtn = []
  while current_seed < seed_num:
    current_node = nodes[current_seed % len(nodes)]
    current_neighbors = G.neighbors(current_node)
    rtn += random.sample(set(current_neighbors) - set(rtn) - set(nodes), 1)
    current_seed += 1

  return rtn