def load_dependency_graph(self):
        dep_path = Config.get("dependency_graph")
        self.log.info('Loading model dependency graph', path = dep_path)

        try:
            dep_graph_str = open(dep_path).read()

            # joint_dependencies is of the form { Model1 -> [(Model2, src_port, dst_port), ...] }
            # src_port is the field that accesses Model2 from Model1
            # dst_port is the field that accesses Model1 from Model2
            joint_dependencies = json.loads(dep_graph_str)

            model_dependency_graph = DiGraph()
            for src_model, deps in joint_dependencies.items():
                for dep in deps:
                    dst_model, src_accessor, dst_accessor = dep
                    if src_model != dst_model:
                        edge_label = {'src_accessor': src_accessor,
                                      'dst_accessor': dst_accessor}
                        model_dependency_graph.add_edge(
                            src_model, dst_model, edge_label)

            model_dependency_graph_rev = model_dependency_graph.reverse(
                copy=True)
            self.model_dependency_graph = {
                # deletion
                True: model_dependency_graph_rev,
                False: model_dependency_graph
            }
            self.log.info("Loaded dependencies", edges = model_dependency_graph.edges())
        except Exception as e:
            self.log.exception("Error loading dependency graph", e = e)
            raise e

def sample(n):
  T = DiGraph()
  alive = dict()
  heights = list()
  total = 0.0
  for i in range(n):
    alive[i] = 0.0

  k = n
  while k > 1:
    event = exponential(1.0/binom(k, 2))
    total += event
    heights.append(total)
    for c in alive.keys():
      alive[c] += event

    [a, b] = subset(alive.keys(), 2)
    c = new_node(k)
    alive[a]
    alive[b]
    T.add_edge(a, c, length = alive[a])
    T.add_edge(b, c, length = alive[b])

    del alive[a]
    del alive[b]
    alive[c] = 0.0

    k -= 1

  T.below = collapse(T)
  T.heights = heights

  return T

def lazy_load_trees(skeleton_ids, node_properties):
    """ Return a lazy collection of pairs of (long, DiGraph)
    representing (skeleton_id, tree).
    The node_properties is a list of strings, each being a name of a column
    in the django model of the Treenode table that is not the treenode id, parent_id
    or skeleton_id. """

    values_list = ('id', 'parent_id', 'skeleton_id')
    props = tuple(set(node_properties) - set(values_list))
    values_list += props

    ts = Treenode.objects.filter(skeleton__in=skeleton_ids) \
            .order_by('skeleton') \
            .values_list(*values_list)
    skid = None
    tree = None
    for t in ts:
        if t[2] != skid:
            if tree:
                yield (skid, tree)
            # Prepare for the next one
            skid = t[2]
            tree = DiGraph()

        fields = {k: v for k,v in izip(props, islice(t, 3, 3 + len(props)))}
        tree.add_node(t[0], fields)

        if t[1]:
            # From child to parent
            tree.add_edge(t[0], t[1])

    if tree:
        yield (skid, tree)

def build_graph(alternatives, outranking, credibility=False):
    """There are some conventions to follow in this function:
    1. labels (i.e. alternatives' ids) are kept in graph's dictionary (see:
       graph.graph)
    2. aggregated nodes (only numbers, as list) are kept under 'aggr' key in
       node's dict (see: graph.nodes(data=True))
    3. weights on the edges are kept under 'weight' key in edge's dict -
       similarly as with nodes (see: graph.edges(data=True))
    """
    graph = DiGraph()  # we need directed graph for this
    # creating nodes...
    for i, alt in enumerate(alternatives):
        graph.add_node(i)
        graph.graph.update({i: alt})
    # creating edges...
    for i, alt in enumerate(alternatives):
        relations = outranking.get(alt)
        if not relations:  # if graph is built from intersectionDistillation
            continue
        for relation in relations.items():
            if relation[1] == 1.0:
                weight = credibility[alt][relation[0]] if credibility else None
                graph.add_edge(i, alternatives.index(relation[0]),
                               weight=weight)
    return graph

    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 common_edge_ratio(ref_user_connections, eval_user_connections, is_directed=False):
    """ caulcalate the fraction of common edges fraction out of union of two graphs

    Parameters:
    ==========
    ref_user_connections: a list of edges
    eval_user_connections: a list of edges
    is_directed: boolean,
        False (default): edges forms an undirected graph
        True: edges forms a directed graph
    """
    ref_user_connections = _normalize_connections(ref_user_connections, is_directed)
    eval_user_connections = _normalize_connections(eval_user_connections, is_directed)

    if is_directed:
        ref_graph, eval_graph = DiGraph(), DiGraph()
    else:
        ref_graph, eval_graph = Graph(), Graph()

    ref_graph.add_edges_from(ref_user_connections)
    eval_graph.add_edges_from(eval_user_connections)

    ref_edges, eval_edges = ref_graph.edges(), eval_graph.edges()

    tot_common = sum([1 if edge in ref_edges else 0 for edge in eval_edges])
    union_size = len(ref_edges) + len(eval_edges) - tot_common
    return tot_common / union_size

def test_get_rc_chain():
    mock_g = DiGraph()
    mock_g.add_edges_from([('A', 'B', {'RC': 'I'}), ('B', 'C', {'RC': 'S'}),
                           ('C', 'D', {'RC': 'L'}), ('D', 'E', {'RC': 'O'})])
    tp = ['B', 'C', 'D']
    nt.assert_equal(MapGraph._get_rc_chain.im_func(mock_g, 'A', tp, 'E'),
                    'ISLO')

 def remove_edge(self, u,  v = None):
     temp = self.copy()
     DiGraph.remove_edge(temp, u, v = v)
     if not temp._is_connected():
         raise ValueError("Removing edge (%s, %s) creates disconnected graph" %(u, v) )
     else:
         DiGraph.remove_edge(self, u, v = v)

def build_network_from_db():
    """
    Creates a new graph with data inserted from the database,
    overwrites the current graph. This function will extract all
    producers from the database and iterate through their source_ratings
    to build the global network. Therefore, the time to complete running this
    function depends on the number of producers in the database
    and the number of ratings they have set on each other.

    Returns: the global network (type NetworkX DiGraph)

    """
    
    global graph
    # Users not included in graph.
    producers = Producer.objects()
    graph = DiGraph()
    tmp = []
    for p1 in producers:    
        try:
            tmp.append(extractor.get_producer(p1.name))
        except Exception:
            pass

    for p2 in tmp:
        for k,v in p2.source_ratings.iteritems():
            graph.add_edge(p2.name, k, v)  
    
    return graph
    
    """

    def test():
        bayesian_network = DiGraph()
        edges = [('A', 'C'), ('B', 'C'), ('C', 'D'), ('C', 'E'), ('D', 'F'), ('D', 'G')]
        bayesian_network.add_edges_from(edges)
        for node in bayesian_network.nodes():
            node_object = bayesian_network.node[node]
            #  All the variables are binary
            node_object['values'] = ['0', '1']

        conditional_probabilities = {
                                                'A1': 0.7,
                                                'A0':0.3,
                                                'B1': 0.4,
                                                'B0':0.6,
                                                'C1|A0,B0': 0.1, 'C1|A1,B0': 0.3,
                                                'C1|A0,B1': 0.5, 'C1|A1,B1': 0.9,
                                                'C0|A0,B0': 0.9, 'C0|A1,B0': 0.7,
                                                'C0|A0,B1': 0.5, 'C0|A1,B1': 0.1,
                                                'D1|C0': 0.8, 'D1|C1': 0.3,
                                                'D0|C0': 0.2, 'D0|C1': 0.7,
                                                'E1|C0': 0.2, 'E1|C1': 0.6,
                                                'E0|C0': 0.8, 'E0|C1': 0.4,
                                                'F1|D0': 0.1, 'F1|D1': 0.7,
                                                'F0|D0': 0.9, 'F0|D1': 0.3,
                                                'G1|D0': 0.9, 'G1|D1': 0.4,
                                                'G0|D0': 0.1, 'G0|D1': 0.6
                                     }
        inference = PearlsInference(bayesian_network, conditional_probabilities)
        print '-------------------------------'
        inference.add_evidence(['C', '1'])
        print '----------------------------------'
        inference.add_evidence(['A', '1'])
        pprint(conditional_probabilities)

    def add_nodes_from(self, nodes, **attr):
        H=copy.deepcopy(self)
        self.clear()
        if not H.nodes():
            DiGraph.add_nodes_from(self, nodes, **attr)

            self.names=names=sorted(nodes)
            for i, n in enumerate(self.names):
                self.node[i]={'name': n, 'pmf': Pmf()}
                self.node[i]['pmf'].Set(1,self.p)
                self.node[i]['pmf'].Set(0, 1-self.p)
                self.remove_node(n)
                self.edge[i]={}
                self.indep_vars+=[i]
            self.SetProbs()
            return

        DiGraph.add_nodes_from(self, nodes, **attr)
        #ind_vars=[var for var in H.indep_vars]
        #DiGraph.add_nodes_from(self, ind_vars)
        self.names=names=sorted(set(H.names + nodes))
        for i, n in enumerate(names):
            try:
                self.node[i], self.edge[i]=H.node[i], H.edge[i]
            except:
                self.node[i]={'name': n, 'pmf': Pmf()}
                self.node[i]['pmf'].Set(1,self.p)
                self.node[i]['pmf'].Set(0, 1-self.p)
                self.remove_node(n)
                self.edge[i]={}
                self.indep_vars+=[i]

        self.SetProbs()

def select_binary_groups(groups, root=desc.root):
    def get_bin_group(grps, bin_grps, rt, graph):
        level = grps.successors(rt)
        if not level:
            bin_grps.append(graph)
            return bin_grps
        elif len(level) == 2:
            graph.add_nodes_from(level)
            graph.add_edge(rt, level[0], grps.get_edge_data(rt, level[0]))
            graph.add_edge(rt, level[1], grps.get_edge_data(rt, level[1]))
            if grps.successors(level[0]):
                get_bin_group(grps, bin_grps, rt=level[0], graph=graph)
            else:
                get_bin_group(grps, bin_grps, rt=level[1], graph=graph)
        else:
            level.sort()
            for i in xrange(0, len(level), 2):
                g = DiGraph(graph)
                g.add_nodes_from([level[i], level[i + 1]])
                g.add_edge(rt, level[i], grps.get_edge_data(rt, level[i]))
                g.add_edge(rt, level[i + 1], grps.get_edge_data(rt, level[i + 1]))
                if grps.successors(level[i]):
                    get_bin_group(grps, bin_grps, rt=level[i], graph=g)
                else:
                    get_bin_group(grps, bin_grps, rt=level[i + 1], graph=g)

    dg = DiGraph()
    dg.add_node(root)
    bin_groups = []
    get_bin_group(groups, bin_grps=bin_groups, rt=root, graph=dg)
    return bin_groups

	def merge(self,minN):
		
		import numpy as np
		merged=[]
		merged_cliq=[]
		while len(DiGraph.nodes(self)):
			#print(len(self.nodes()))
			contcmp,ct_cliq=self.splitG(minN)

			if not DiGraph.nodes(self):
				break
			merged=merged+contcmp 
			merged_cliq=merged_cliq+ct_cliq

			try:
				#print("point1")
				cut_nodes=minimum_node_cut(self)

				#print("point2")
			except:
				nodes=DiGraph.nodes(self)
				index=np.random.randint(len(nodes))
				cut_nodes=[nodes[index]]

			for node in cut_nodes:
				DiGraph.remove_node(self,node)

		self.topics=merged
		self.topic_cliq=merged_cliq

 def remove_node(self, n):
     if n not in self.nodes():
         return
     if self.node[n]['conn'] is not None \
                 and not self.node[n]['conn'].disconnected:
         self.node[n]['conn'].disconnect()
     DiGraph.remove_node(self, n)

 def build_graph(self):
     new_graph = DiGraph()
     # Rebuild the graph from the LSDB
     for lsa in chain(self.routers.values(),
                      self.networks.values(),
                      self.ext_networks.values()):
         lsa.apply(new_graph, self)
     # Contract all IPs to their respective router-id
     for lsa in self.routers.values():
         lsa.contract_graph(new_graph, self.router_private_address.get(
             lsa.routerid, []))
     # Figure out the controllers layout
     base_net = ip_network(CFG.get(DEFAULTSECT, 'base_net'))
     controller_prefix = CFG.getint(DEFAULTSECT, 'controller_prefixlen')
     # Group by controller and log them
     for ip in new_graph.nodes_iter():
         addr = ip_address(ip)
         if addr in base_net:
             """1. Compute address diff to remove base_net
                2. Right shift to remove host bits
                3. Mask with controller mask
             """
             id = (((int(addr) - int(base_net.network_address)) >>
                    base_net.max_prefixlen - controller_prefix) &
                   ((1 << controller_prefix) - 1))
             self.controllers[id].append(ip)
     # Contract them on the graph
     for id, ips in self.controllers.iteritems():
         contract_graph(new_graph, ips, 'C_%s' % id)
     # Remove generated self loops
     new_graph.remove_edges_from(new_graph.selfloop_edges())
     self.apply_secondary_addresses(new_graph)
     return new_graph

 def remove_edges_from(self,  ebunch):
     temp = self.copy()
     DiGraph.remove_edges_from(temp, ebunch)
     if not temp._is_connected():
         raise ValueError("Removing edges %s creates disconnected graph" %(ebunch, ) )
     else:
         DiGraph.remove_edges_from(self,  ebunch)

def _graph(formula):
  """Build the implication graph"""
  G = DiGraph()
  for (a,b) in formula.iterclause():
		G.add_edge(-a,b)
		G.add_edge(-b,a)
		
  return G

def test_get_best_is():
    mock_mapp = DiGraph()
    mock_mapp.add_edges_from([('A-1', 'B-1', {'RC': 'I', 'PDC': 5}),
                              ('A-1', 'B-2', {'RC': 'I', 'PDC': 7}),
                              ('A-1', 'B-3', {'RC': 'S', 'PDC': 5})])
    result = MapGraph._get_best_is.im_func(mock_mapp, 'A-1',
                                           ['B-1', 'B-2', 'B-3'])
    nt.assert_equal(result, ('B-1', 5))

    def test_missing_edges(self):
        """A tournament must not have any pair of nodes without at least
        one edge joining the pair.

        """
        G = DiGraph()
        G.add_edges_from([(0, 1), (1, 2), (2, 3), (3, 0), (1, 3)])
        assert_false(is_tournament(G))

def test_get_worst_pdc():
    mock_mapp = DiGraph()
    mock_mapp.add_edges_from([('A-1', 'B-1', {'RC': 'L', 'PDC': 5}),
                              ('A-1', 'B-2', {'RC': 'O', 'PDC': 7}),
                              ('A-1', 'B-3', {'RC': 'L', 'PDC': 15})])
    result = MapGraph._get_worst_pdc.im_func(mock_mapp, 'A-1',
                                             ['B-1', 'B-2', 'B-3'])
    nt.assert_equal(result, 15)