def normDAGl2Test(G_test, power):
    kern = nx.get_edge_attributes(G_test, 'kern_unnorm')
    tran = nx.get_edge_attributes(G_test, 'tran')

    kern = OrderedDict(sorted(kern.items(), key=lambda t: t[0]))
    val = kern.values()
    key = kern.keys()

    tran = OrderedDict(sorted(tran.items(), key=lambda t: t[0]))
    tran = tran.values()

    val = np.asarray(val, dtype=float)
    tran = np.asarray(tran, dtype=float)
    tran = np.log(1/tran)  # logarithm weighting
    tran[tran == np.inf] = 0
    tran[np.isnan(tran)] = 0

    if power == 2:
      tran = np.square(tran)

    if len(val.shape) == 2:
        # kern = val/tran[:, None]
        kern = val*tran[:, None]  # avoid numeric problems when using logarithm weighting
        kern = normalize(kern, norm='l2', axis=0)
    else:
        kern = val*tran
        kern = kern/np.linalg.norm(kern)

    kern = dict(zip(key, kern))
    nx.set_edge_attributes(G_test, 'kern', kern)

    return G_test

def _aux_digraph_edge_connectivity(G):
    """Auxiliary digraph for computing flow based edge connectivity

    If the input graph is undirected, we replace each edge (u,v) with
    two reciprocal arcs (u,v) and (v,u) and then we set the attribute
    'capacity' for each arc to 1. If the input graph is directed we simply
    add the 'capacity' attribute. Part of algorithm 1 in [1]_ .

    References
    ----------
    .. [1] Abdol-Hossein Esfahanian. Connectivity Algorithms. (this is a
        chapter, look for the reference of the book).
        http://www.cse.msu.edu/~cse835/Papers/Graph_connectivity_revised.pdf
    """
    if G.is_directed():
        if nx.get_edge_attributes(G, "capacity"):
            return G
        D = G.copy()
        capacity = dict((e, 1) for e in D.edges())
        nx.set_edge_attributes(D, "capacity", capacity)
        return D
    else:
        D = G.to_directed()
        capacity = dict((e, 1) for e in D.edges())
        nx.set_edge_attributes(D, "capacity", capacity)
        return D

def df_to_graph(df):
    G = nx.from_numpy_matrix(df.values, create_using=nx.DiGraph())
    G = nx.relabel_nodes(G, dict(enumerate(df.columns)))
    weights = nx.get_edge_attributes(G, 'weight')
    invW = dict([(k, 1/float(v)) for (k,v) in weights.items()])
    nx.set_edge_attributes(G, 'distance', invW)
    return G

 def test_constraint_weighted_directed(self):
     D = self.D.copy()
     nx.set_edge_attributes(D, 'weight', self.D_weights)
     constraint = nx.constraint(D, weight='weight')
     assert_almost_equal(round(constraint[0], 3), 0.840)
     assert_almost_equal(round(constraint[1], 3), 1.143)
     assert_almost_equal(round(constraint[2], 3), 1.378)

 def test_constraint_weighted_undirected(self):
     G = self.G.copy()
     nx.set_edge_attributes(G, 'weight', self.G_weights)
     constraint = nx.constraint(G, weight='weight')
     assert_almost_equal(round(constraint['G'], 3), 0.299)
     assert_almost_equal(round(constraint['A'], 3), 0.795)
     assert_almost_equal(round(constraint['C'], 3), 1)

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 set_transition_probabilities(graph, damping, start_node):
    # transition probabilities
    for_removal = []
    for node in graph.nodes_iter():
        # sum the weights
        weights_sum = 0.0
        for neighbor in graph.successors_iter(node):
            weights_sum += graph.get_edge_data(node, neighbor)['weight']

        # set the transition probability multiplied by (1 - damping)
        for neighbor in graph.successors_iter(node):
            transition = ((1-damping) * (graph[node][neighbor]['weight'] / weights_sum))
            nx.set_edge_attributes(graph, 'transition', {(node, neighbor): transition})

        # add the restart
        if graph.has_edge(node, start_node):
            graph[node][start_node]['transition'] += damping
        else:
            for_removal.append((node, start_node))
            if weights_sum > 0:
                graph.add_edge (node, start_node, {'weight': 0, 'transition': damping})
            else:
                graph.add_edge (node, start_node, {'weight': 0, 'transition': 1.0})

    return for_removal

def write_edge2cid(e2c,filename, outFile, delimiter="\t"):
    # write edge2cid three-column file
    f = open(filename+".edge2comm.txt",'w')
    c2c = dict( (c,i+1) for i,c in enumerate(sorted(list(set(e2c.values())))) ) # ugly...
    #print c2c
    for e,c in sorted(e2c.iteritems(), key=itemgetter(1)):
        f.write( "%s%s%s%s%s\n" % (str(e[0]),delimiter,str(e[1]),delimiter,str(c2c[c])) )
    f.close()
    
    cid2edges,cid2nodes = defaultdict(set),defaultdict(set) # faster to recreate here than
    for edge,cid in e2c.iteritems():                        # to keep copying all dicts
        cid2edges[cid].add( edge )                          # during the linkage...
        cid2nodes[cid] |= set(edge)
    cid2edges,cid2nodes = dict(cid2edges),dict(cid2nodes)
    
    # write list of edges for each comm, each comm on its own line
    f,g = open(filename+".comm2edges.txt", 'w'),open(filename+".comm2nodes.txt", 'w')
    for cid in sorted(cid2edges.keys()):
        nodes,edges = map(str,cid2nodes[cid]), ["%s,%s" % (ni,nj) for ni,nj in cid2edges[cid]]
        f.write( "\t".join(edges) ); f.write("\n")
        g.write( "\t".join([str(cid)] + nodes) ); g.write("\n")
    f.close(); g.close()
    #print e2c
    e2cRelabel=dict((edge,c2c.get(id)) for (edge, id) in e2c.items())
    g=nx.Graph()
    g.add_edges_from(e2cRelabel.keys())
    nx.set_edge_attributes(g,"label",e2cRelabel)
    nx.write_gml(g,outFile)

def planar_cycle_basis_impl(g):
	assert not g.is_directed()
	assert not g.is_multigraph()
	assert nx.is_biconnected(g) # BAND-AID

	# "First" nodes/edges for each cycle are chosen in an order such that the first edge
	#  may never belong to a later cycle.

	# rotate to (hopefully) break any ties or near-ties along the y axis
	rotate_graph(g, random.random() * 2 * math.pi)

	# NOTE: may want to verify that no ties exist after the rotation

	nx.set_edge_attributes(g, 'used_once', {e: False for e in g.edges()})

	# precompute edge angles
	angles = {}
	for s,t in g.edges():
		angles[s,t] = edge_angle(g,s,t) % (2*math.pi)
		angles[t,s] = (angles[s,t] + math.pi) % (2*math.pi)

	# identify and clear away edges which cannot belong to cycles
	for v in g:
		if degree(g,v) == 1:
			remove_filament_from_tip(g, v)

	cycles = []

	# sort ascendingly by y
	for root in sorted(g, key = lambda v: g.node[v]['y']):

		# Check edges in ccw order from the +x axis
		for target in sorted(g[root], key=lambda t: angles[root,t]):

			if not g.has_edge(root, target):
				continue

			discriminator, path = trace_ccw_path(g, root, target, angles)

			if discriminator == PATH_PLANAR_CYCLE:
				assert path[0] == path[-1]
				remove_cycle_edges(g, path)
				cycles.append(path)

			# Both the dead end and the initial edge belong to filaments
			elif discriminator == PATH_DEAD_END:
				remove_filament_from_edge(g, root, target)
				remove_filament_from_tip(g, path[-1])

			# The initial edge must be part of a filament
			# FIXME: Not necessarily true if graph is not biconnected
			elif discriminator == PATH_OTHER_CYCLE:
				remove_filament_from_edge(g, root, target)

			else: assert False # complete switch

			assert not g.has_edge(root, target)

	assert len(g.edges()) == 0
	return cycles

	def extract_edges(self, edge_attr):
		"""docstring for extract"""
		exEdges = nx.get_edge_attributes(self, edge_attr)
		sg = nx.Graph(data = exEdges.keys(), name = edge_attr) 
		if len(exEdges):
			nx.set_edge_attributes(sg, edge_attr, exEdges)
		return(sg)

def delete_links(G):
	'''
	Delete links in the graph if they disavantage the person.
	The link is deleted if (r1-r2)/affect(n1, n2)*deg(n1) > alpha
	where r1 > r2 and alpha is a random number between 0 and a given paramater beta.
	'''
	beta = 100
	reput = nx.get_node_attributes(G, "reput")
	affect = nx.get_edge_attributes(G, "affect")
	n = 0
	for edge in nx.edges(G):
		# Calculate alpha
		alpha = beta*random.random()

		# Define who has the higher reputation
		n1 = edge[1]
		n2 = edge[0]
		if(reput[edge[0]] > reput[edge[1]]):
			n1 = edge[0]
			n2 = edge[1]
		
		# Compute the coefficient
		coef = (reput[n1]-reput[n2])/affect[edge]*G.degree(n1)

		# Decide wether we delete the link
		if(coef > alpha):
			G.remove_edge(edge[0], edge[1])
			del affect[edge]

	# Set the new affect dict and return the graph
	nx.set_edge_attributes(G, "affect", affect)
	return G

def color_by_nids(graph, unique_nids=None, ibs=None, nid2_color_=None):
    """ Colors edges and nodes by nid """
    # TODO use ut.color_nodes
    import plottool as pt

    ensure_graph_nid_labels(graph, unique_nids, ibs=ibs)
    node_to_nid = nx.get_node_attributes(graph, 'nid')
    unique_nids = ut.unique(node_to_nid.values())
    ncolors = len(unique_nids)
    if (ncolors) == 1:
        unique_colors = [pt.UNKNOWN_PURP]
    else:
        if nid2_color_ is not None:
            unique_colors = pt.distinct_colors(ncolors + len(nid2_color_) * 2)
        else:
            unique_colors = pt.distinct_colors(ncolors)
    # Find edges and aids strictly between two nids
    nid_to_color = dict(zip(unique_nids, unique_colors))
    if nid2_color_ is not None:
        # HACK NEED TO ENSURE COLORS ARE NOT REUSED
        nid_to_color.update(nid2_color_)
    edge_aids = list(graph.edges())
    edge_nids = ut.unflat_take(node_to_nid, edge_aids)
    flags = [nids[0] == nids[1] for nids in edge_nids]
    flagged_edge_aids = ut.compress(edge_aids, flags)
    flagged_edge_nids = ut.compress(edge_nids, flags)
    flagged_edge_colors = [nid_to_color[nids[0]] for nids in flagged_edge_nids]
    edge_to_color = dict(zip(flagged_edge_aids, flagged_edge_colors))
    node_to_color = ut.map_dict_vals(ut.partial(ut.take, nid_to_color), node_to_nid)
    nx.set_edge_attributes(graph, 'color', edge_to_color)
    nx.set_node_attributes(graph, 'color', node_to_color)

def load_existing_networks(filename="existing_networks.shp", budget_value=0):
    """
    load existing_networks shp into GeoGraph nodes, edges and assign budget

    Args:
        filename:  existing_networks shapefile
        budget_value:  default budget value for nodes in existing network

    Returns:
        GeoGraph of existing networks with budget attribute
    """

    geo_net = nio.load_shp(filename)

    nx.set_node_attributes(geo_net, 'budget', {n: budget_value
        for n in geo_net.nodes()})

    # determine edge weight/distance function by whether they're geocentric
    # (assuming coordinates are not in 3-space here)

    distance = gm.spherical_distance if geo_net.is_geographic else \
        gm.euclidean_distance

    nx.set_edge_attributes(geo_net, 'weight', {(u, v):
                   distance(map(geo_net.coords.get, [u, v]))
                   for u, v in geo_net.edges()})

    return geo_net

def CopyDAG(G_train, data_total, pmin, pmax):
    edges = nx.edges(G_train)
    kern = dict.fromkeys(edges)
    M = len(data_total)
    kern_temp = {}

    for edge in edges:
        kern[edge] = np.zeros(M)

    for m in range(M):
        print('Data item: %d' % m)
        data = data_total[m]
        for i in range(0, len(data)-pmin+1+1):
            for j in range(pmin-1, pmax+1):
                if data[i:i+j] in kern_temp:
                    kern_temp[data[i:i+j]][m] += 1
                else:
                    kern_temp[data[i:i+j]] = np.zeros(M)
                    kern_temp[data[i:i+j]][m] = 1

    for edge in edges:
        key = edge[0]+edge[1][-1]
        if key in kern_temp:
            kern[edge] = kern_temp[key]

    G = nx.DiGraph()
    G.add_edges_from(edges)
    nx.set_edge_attributes(G, 'kern_unnorm', kern)

    return G

    def test_edge_num_attribute(self):

        g = nx.karate_club_graph()
        attr = {(u, v): {"even": int((u+v) % 10)} for (u, v) in g.edges()}
        nx.set_edge_attributes(g, attr)

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

        c = cpm.EdgeNumericalAttribute("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.EdgeNumericalAttribute("even", value=[3, 10], 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 __init__(self, dim=None, phi=np.pi, periodic=True, phases=None):
        if not dim: dim = [4, 4]
        dim = copy(dim)
        self.dim = copy(dim)
        self.nspins = np.prod(dim)

        self.G = nx.grid_graph(dim, periodic)

        if phases is not None:
            self.phases = phases
        else:
            self.phases = dict()
            binary_disorder = True
            if binary_disorder:
                for edge in self.G.edges():
                    self.phases[edge] = phi * np.random.random_integers(0, 1)
            else:
                for edge in self.G.edges():
                    self.phases[edge] = np.random.uniform(-phi, phi)
        nx.set_edge_attributes(self.G, "phase", self.phases)

        self.indices = dict()
        self.index2node = dict()
        nodes = sorted(self.G.nodes())
        for i, node in enumerate(nodes):
            self.indices[node] = i
            self.index2node[i] = node

        self.num_edges = self.G.number_of_edges()

        self.set_up_neighborlists()

 def __init__(self):
     self.graph = nx.Graph()
     self.node2min = dict()
     self.edge2ts = dict()
     nx.set_edge_attributes(self.graph, "ts", dict())
     #nx.set_node_attributes( self.graph )
     self.nmin = 0

 def _build_edge_wkt(self):
     r = self.results
     # Iterate through the nodes and their parent
     for rank, fnode, tnode in zip(r.index, r['Sequence..Upstream.id'], r['Sequence..Vertex.id']):
         if fnode is not None:
             # Set the edge attributes with those found in sequencing
             self.networkplan.network.edge[fnode][tnode]['rank'] = int(rank)
             self.networkplan.network.edge[fnode][tnode]['distance'] = float(self.networkplan._distance(fnode, tnode))
             self.networkplan.network.edge[fnode][tnode]['id'] = int(tnode)
             fnode_coords = self.networkplan.coords[fnode]
             tnode_coords = self.networkplan.coords[tnode]
             
             # Build WKT Linestring with from_node and to_node coords
             self.networkplan.network.edge[fnode][tnode]['Wkt'] = 'LINESTRING ({x1} {y1}, {x2} {y2})'.format(x1=fnode_coords[0], y1=fnode_coords[1],
                                                                                                             x2=tnode_coords[0], y2=tnode_coords[1])
     # Filter empty edges
     edges = {(k1, k2): attr for k1, v in self.networkplan.network.edge.iteritems() if v!={}
                             for k2, attr in v.iteritems() if attr!={}}
     self.networkplan.network.edge = edges
     # Clear all edges from the networkx 
     self.networkplan.network.remove_edges_from(self.networkplan.network.edges())
     # Reset with the filtered edges
     self.networkplan.network.add_edges_from(edges.keys())
     # Set the atrributes
     attrs = set([v for i in edges.values() for v in i.keys()]) 
     for attr in attrs:
         nx.set_edge_attributes(self.networkplan.network, attr, pd.DataFrame(edges).ix[attr].to_dict())

    def test_networkx_roundtrip(self):
        print("\n---------- NetworkX Data Roundtrip Test Start -----------\n")

        g = nx.newman_watts_strogatz_graph(100, 3, 0.5)
        nodes = g.nodes()
        edges = g.edges()

        # Add some attributes
        g.graph["name"] = "original"
        g.graph["density"] = nx.density(g)

        nx.set_node_attributes(g, "betweenness", nx.betweenness_centrality(g))
        nx.set_node_attributes(g, "degree", nx.degree(g))
        nx.set_node_attributes(g, "closeness", nx.closeness_centrality(g))

        nx.set_edge_attributes(g, "eb", nx.edge_betweenness(g))

        cyjs1 = util.from_networkx(g)
        g2 = util.to_networkx(cyjs1)

        self.assertEqual(len(g2.nodes()), len(nodes))
        self.assertEqual(len(g2.edges()), len(edges))

        edge_set = set(list(map(lambda x: (int(x[0]), int(x[1])), g2.edges())))
        self.assertEqual(0, len(edge_set.difference(set(edges))))

        node_original = g.node[1]
        node_generated = g2.node["1"]

        print(node_original)
        print(node_generated)

        self.assertEqual(node_original["degree"], node_generated["degree"])
        self.assertEqual(node_original["betweenness"], node_generated["betweenness"])
        self.assertEqual(node_original["closeness"], node_generated["closeness"])

def create_protein_graph(ingraph):
    pnodes = {}
    pnodes = defaultdict(lambda: 0, pnodes)

    pedges = {}
    pedges = defaultdict(lambda: 0, pedges)

    outgraph = nx.Graph()

    for node in ingraph.nodes_iter():
        pnodes[ingraph.node[node]['protein']]+=1

    for u,v,d in ingraph.edges(data=True):
        key=(ingraph.node[u]['protein'], ingraph.node[v]['protein'])
        pedges[key]+=1

    for key in pnodes.keys():
        outgraph.add_node(key)

    edges = combinations(pnodes.keys(), 2)

    outgraph.add_nodes_from(pnodes.keys())
    outgraph.add_edges_from(edges)
    nx.set_node_attributes(outgraph, 'count', pnodes)
    nx.set_edge_attributes(outgraph, 'weight', pedges)

    return outgraph