def updateCurrentDag(self, dst_prefix, new_activeDag):
        """
        :param dst_prefix:
        :param new_activeDag: DAG directing any possible router towards dst_prefix
        """
        # Get current complete DAG
        c_completeDag = self.getCurrentDag(dst_prefix)
        
        # Get current active DAG
        c_activeDag = self.getActiveDag(dst_prefix)

        # Get edges to set 'active' = False in c_completeDag
        edges_to_inactive = nx.difference(c_activeDag, new_activeDag)
        # Set them
        for (x, y) in edges_to_inactive.edges_iter():
            if not c_completeDag.has_edge(x, y):
                c_completeDag.add_edge(x, y)
                c_completeDag[x][y]['default'] = False
            c_completeDag[x][y]['active'] = False
            c_completeDag[x][y]['ongoing_flows'] = False
            
        # Get edges to set 'active' = True in c_completeDag
        edges_to_active = nx.difference(new_activeDag, c_activeDag)
        # Set them
        for (x, y) in edges_to_active.edges_iter():
            if not c_completeDag.has_edge(x, y):
                c_completeDag.add_edge(x, y)
                c_completeDag[x][y]['default'] = False
            c_completeDag[x][y]['active'] = True
            c_completeDag[x][y]['ongoing_flows'] = True

        # Set new computed curren complete DAG to dict attribute
        self.setCurrentDag(dst_prefix, c_completeDag)

 def draw_difference(self, path_old, path_new):
     self.draw_path(path_old)
     H = self.G.copy()
     H.add_edges_from(path_edges(path_new.path))
     H_ = nx.difference(self.G, H)
     nx.draw(self.G, self.pos)
     nx.draw(H_, self.pos, edge_color='blue')

def difference(graph2, graph1):

    D1 = nx.difference(graph2, graph1)
    pos = nx.circular_layout(D1)
    D2 = nx.difference(graph1, graph2)  # edges in graph1 but not in graph2
    pos = nx.circular_layout(D2)

    nx.draw_networkx_nodes(D1,pos, node_color="g", node_size=1000)
    nx.draw_networkx_edges(D1,pos, edge_color='g',width=10) 
    nx.draw_networkx_nodes(D2,pos, node_color="r", node_size=1000)
    nx.draw_networkx_edges(D2,pos, edge_color='r',width=10) 

    plt.show()
#   plt.savefig("M.PDF",facecolor='pink')  #save graph

    return difference

def test_difference(testgraph):
    """
    Test the Difference of the two graphs are same
    """

    a = nx.difference(testgraph[0], testgraph[1])
    b = sg.digraph_operations.difference(testgraph[2], testgraph[3])
    digraph_equals(a, b)

def test_difference():
    G=nx.Graph()
    H=nx.Graph()
    G.add_nodes_from([1,2,3,4])
    G.add_edge(1,2)
    G.add_edge(2,3)
    H.add_nodes_from([1,2,3,4])
    H.add_edge(2,3)
    H.add_edge(3,4)
    D=nx.difference(G,H)
    assert_equal( set(D.nodes()) , set([1,2,3,4]) )    
    assert_equal( sorted(D.edges()) , [(1,2)] )    
    D=nx.difference(H,G)
    assert_equal( set(D.nodes()) , set([1,2,3,4]) )    
    assert_equal( sorted(D.edges()) , [(3,4)] )    
    D=nx.symmetric_difference(G,H)
    assert_equal( set(D.nodes()) , set([1,2,3,4]) )    
    assert_equal( sorted(D.edges()) , [(1,2),(3,4)] )    

  def calcConvergeTime(self, t1, t2, converge_time = -1):
    # calculate the exact time that the network becomes stable:
    # switch states and controller states match with the physical network
    converged = True

    # controllers should be consistent with each other and the underlying graph
    for c in self.controller_names:
      ctrl = self.objs[c]
      if not nx.is_isomorphic(self.graph, ctrl.graph):
        converged = False
        cgraph = nx.Graph(ctrl.graph)
        node_diff = set(self.graph.nodes()) - set(cgraph.nodes())
        cgraph.add_nodes_from(list(node_diff))
        node_diff = set(cgraph.nodes()) - set(self.graph.nodes())
        self.graph.add_nodes_from(list(node_diff))
        diff = nx.difference(self.graph, cgraph)
        print "%f %s not converged %s"%(self.ctx.now, ctrl.name, diff.edges())
        #break
      else: 
        print "%f %s converged"%(self.ctx.now, ctrl.name)
    # switches should also be consistent with each other and the controllers
    if converged:
      c = self.objs[self.controller_names[0]]
      rules = {}
      for s in self.switch_names:
        rules[s] = {}
      sp = nx.shortest_paths.all_pairs_shortest_path(c.graph)
      for host in c.hosts:
        for h2 in c.hosts:
          if h2 == host:
            continue
          if h2.name in sp[host.name]:
            p = SourceDestinationPacket(host.address, h2.address)
            path = zip(sp[host.name][h2.name], \
                       sp[host.name][h2.name][1:])
            for (a, b) in path[1:]:
              link = c.graph[a][b]['link']
              rules[a][p.pack()] = link

      for s in self.switch_names:
        sw = self.objs[s]
        if rules[s] != sw.rules:
          print self.ctx.now, s, len(rules), len(sw.rules)
          converged = False
          break

    if converged:
      if converge_time == -1:
        print "CONVERGE_TIME: ", t1, t2, self.ctx.now
        self.ctx.schedule_task(10, lambda: self.calcConvergeTime(t1, t2, self.ctx.now))
      else:
        self.ctx.schedule_task(10, lambda: self.calcConvergeTime(t1, t2, converge_time))
    else:
      self.ctx.schedule_task(10, lambda: self.calcConvergeTime(t1, t2, -1))

    def difference(cls,topo1,topo2):
        try:
            self = cls(nx.difference(topo1,topo2))
        except nx.NetworkXError:
            return None

        if len(self.edges()) == 0:
            return None

        self.copy_attributes(topo1)
        self.reconcile_attributes(topo1)
        return self

def test_difference_multigraph_attributes():
    g = nx.MultiGraph()
    g.add_edge(0, 1, key=0)
    g.add_edge(0, 1, key=1)
    g.add_edge(0, 1, key=2)
    h = nx.MultiGraph()
    h.add_edge(0, 1, key=0)
    h.add_edge(0, 1, key=3)
    gh = nx.difference(g, h)
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
    assert_equal( sorted(gh.edges()) , [(0,1)] )
    assert_equal( sorted(gh.edges(keys=True)) , [(0,1,3)] )

def test_difference_attributes():
    g = nx.Graph()
    g.add_node(0, x=4)
    g.add_node(1, x=5)
    g.add_edge(0, 1, size=5)
    g.graph['name'] = 'g'

    h = g.copy()
    h.graph['name'] = 'h'
    h.graph['attr'] = 'attr'
    h.node[0]['x'] = 7

    gh = nx.difference(g, h)
    assert_equal( set(gh.nodes()) , set(g.nodes()) )
    assert_equal( set(gh.nodes()) , set(h.nodes()) )
    assert_equal( sorted(gh.edges()) , [])

    h.remove_node(0)
    assert_raises(nx.NetworkXError, nx.intersection, g, h)

G1.edges()

""" Intersection de graphes """
# Les noeuds de H et G doivent etre les memes
H.clear()
H.add_nodes_from([1,2,3,4])
H.add_edge(1,2)
GH4=nx.intersection(G,H)
GH4.nodes()
#[1,2,3,4]
GH4.edges()
#[(1,2)]

""" Difference de graphes """
# Les noeuds de H et G doivent etre les memes
GH5=nx.difference(G,H)
GH5.nodes()
# [1,2,3,4]
GH5.edges()
# [((2,3),(3,4)]
# Retourne un graphe avec des aretes qui existent dans G mais pas dans H

""" Difference symetrique de graphes """
# Les noeuds de H et G doivent etre les memes
GH6=nx.symmetric_difference(G,H)
GH6.nodes()
# [1,2,3,4]
GH6.edges()
# [((2,3),(3,4)]
# Retourne un graphe avec des aretes qui sont soit dans G soit dans H mais pas les deux

    def run(self, raw_data, objects):
        graphs = []
        new_objects = []
        for overlay in self.__sub_overlays:
            g = overlay.substitutes(raw_data)
            graphs.append(g)

        graph = graphs.pop(0)
        for h in graphs:
            graph = nx.compose(graph, h)

        components = nx.connected_component_subgraphs(graph)
        closed_polygons = []
        polygons = []
        for component in components:
            minimum_cycles = planar_cycles(component)
            collected_options = itertools.chain(*nx.get_node_attributes(component,'options').values())
            options = list(set(collected_options))

            # the polygons are the same as the minimum cycles
            closed_polygons += minimum_cycles
            path_graph = nx.Graph()
            path_graph.add_nodes_from(component.nodes())

            for polygon in minimum_cycles:
                polygons.append(Polygon(polygon, options))
                path_graph.add_cycle(polygon)

            remaining_graph = nx.difference(component, path_graph)
            for n in remaining_graph.nodes():
                if remaining_graph.degree(n) == 0:
                    remaining_graph.remove_node(n)
            if len(remaining_graph.edges()) > 0:
                remaining_components = nx.connected_component_subgraphs(remaining_graph)
                for c in remaining_components:
                    new_objects.append(OpenGraph(c, options))

        
        new_objects = new_objects + polygons
        z_order_graph = nx.DiGraph()
        z_order_graph.add_nodes_from(new_objects)
        
        for i in range(0, len(polygons)):
            polygon1 = polygons[i]
            for j in range(i + 1, len(polygons)):
                polygon2 = polygons[j]
                if polygon1 != polygon2:
                    if polygon1.contains(polygon2):
                        z_order_graph.add_edge(polygon1, polygon2)
                    elif polygon2.contains(polygon1):
                        z_order_graph.add_edge(polygon2, polygon1)
            
       
        for obj in new_objects:
            for edge in obj.edges():
                if 'below' in graph[edge[0]][edge[1]]:
                    below = graph[edge[0]][edge[1]]['below']
                    if below != None:
                        for obj_above in new_objects:
                            if obj != obj_above:
                                if obj_above.has_edge(below.start(), below.end()):
                                    z_order_graph.add_edge(obj, obj_above)
                if 'above' in graph[edge[0]][edge[1]]:
                    above = graph[edge[0]][edge[1]]['above']
                    if above != None:
                        for obj_below in new_objects:
                            if obj != obj_below:
                                if obj_below.has_edge(above.start(), above.end()):
                                    z_order_graph.add_edge(obj_below, obj)
                if 'z_order' in graph[edge[0]][edge[1]]:
                    z_order = graph[edge[0]][edge[1]]['z_order']
                    if z_order != None:
                        for other_obj in new_objects:
                            if obj != other_obj:
                                if (isinstance(other_obj, Polygon) and other_obj.frame().intersects(edge)) or (isinstance(other_obj, OpenGraph) and other_obj.intersects(edge)):
                                    if z_order == 'above':
                                        z_order_graph.add_edge(other_obj, obj)
                                    elif z_order == 'below':
                                        z_order_graph.add_edge(obj, other_obj)
                                    else:
                                        raise ValueError, "Wrong value for z_order."

        cycle_gen = nx.simple_cycles(z_order_graph)
        try:
            cycles = list(cycle_gen)
            for cycle in cycles:
                cycle_edges = [(cycle[i], cycle[i + 1]) for i in range(0, len(cycle) - 1)]
                for edge in cycle_edges:
                    z_order_graph.remove_edge(edge[0], edge[1])
            if cycles:
                warnings.warn("The diagram contains objects. that have an ambiguous z-order. Shaape estimates their z-order.", RuntimeWarning)
        except:
            pass

        current_z_order = 0
        while z_order_graph.nodes():
            nodes_without_predecessors = [node for node in z_order_graph.nodes() if not z_order_graph.predecessors(node)]
            for node in nodes_without_predecessors:
                node.set_z_order(current_z_order)
            current_z_order = current_z_order + 1
#.........这里部分代码省略.........

    def removeAllocationEntry(self, prefix, flow):
        """
        """
        # Wait until flow finishes
        time.sleep(flow['duration']) 
        
        # Acquire locks for self.flow_allocation and self.dags
        # dictionaries
        self.flowAllocationLock.acquire()
        self.dagsLock.acquire()
        
        log.info(lineend)
        if prefix not in self.flow_allocation.keys():
            # prefix not in table
            raise KeyError("The is no such prefix allocated: %s"%str(prefix))
        else:
            if flow in self.flow_allocation[prefix].keys():
                path_list = self.flow_allocation[prefix].pop(flow, None)
            else:
                raise KeyError("%s is not alloacated in this prefix %s"%str(repr(flow)))

        t = time.strftime("%H:%M:%S", time.gmtime())
        log.info("%s - Flow REMOVED from Paths\n"%t)
        log.info("\t* Dest_prefix: %s\n"%prefix)
        to_log = "\t* Paths (%s): %s\n"
        log.info(to_log%(len(path_list), str(self.toLogRouterNames(path_list))))
        log.info("\t* Flow: %s\n"%self.toLogFlowNames(flow))

        # Current dag for destination
        current_dag = self.getCurrentDag(prefix)
        
        # Get the active Dag
        activeDag = self.getActiveDag(prefix)

        # Log active DAG
        to_log = "\t* removeAllocationEntry: current active DAG\n\t  %s\n"
        log.info(to_log%str(self.toLogDagNames(activeDag).edges()))
        
        # Get current remaining allocated flows for destination
        remaining_flows = self.getAllocatedFlows(prefix)

        # Create DAG showing remaining flow paths only
        edges_with_flows = []
        for (f, pl) in remaining_flows:
            edges_with_flows += self.getEdgesFromPathList(pl)
        edges_with_flows = list(set(edges_with_flows))
        remaining_traffic_dag = nx.DiGraph()
        remaining_traffic_dag.add_nodes_from(activeDag.nodes())
        remaining_traffic_dag.add_edges_from(edges_with_flows)
        
        # Difference with active DAG can be set to 'ongoing_flows' = False
        to_set_noflows = nx.difference(activeDag, remaining_traffic_dag)
        for (x, y) in to_set_noflows.edges_iter():
            current_dag[x][y]['ongoing_flows'] = False
            
        # Set the new calculated dag to its destination prefix dag
        self.setCurrentDag(prefix, current_dag)

        # Check if we can set destination forwarding to the initial
        # default OSPF DAG
        if len(remaining_flows) == 0:
            # Log a bit
            to_log = "\t* No more flows remain to prefix."
            to_log += " Re-setting to initial OSPF DAG\n"
            log.info(to_log)
            
            # Set forwarding to original
            self.setOSPFOriginalDAG(prefix)
        else:
            # Log it only
            log.info("\t* Some flows to prefix still remain.\n")

            # Log final DAG that is foced
            activeDag = self.getActiveDag(prefix)
            to_log = "\t* removePrefixLies: final active DAG\n\t  %s\n"
            log.info(to_log%str(self.toLogDagNames(activeDag).edges()))

            # Force it to fibbing
            self.sbmanager.add_dag_requirement(prefix, activeDag.copy())
            log.info(lineend)
        
        # Release locks
        self.flowAllocationLock.release()
        self.dagsLock.release()

def test_mixed_type_difference():
    G = nx.Graph()
    H = nx.MultiGraph()
    U = nx.difference(G,H)

def test_difference_raise():
    G = nx.path_graph(4)
    H = nx.path_graph(3)
    GH = nx.difference(G, H)

G_list['firstth'] = G6

G7 = nx.read_gml("hdb_collab_cluster_sample_firstth20.gml")
G_list['firstth20'] = G7


print 'ground truth sample cluster:'
print 'nodes:', len(G0.nodes())
print 'edges:', len(G0.edges())
print '\n\n'


for node in G1.nodes():
    for key, value in G_list.iteritems():
        if not value.has_node(node):
            value.add_node(node)


for key, value in G_list.iteritems():
    print key, 'sample cluster'
    print 'nodes:', len(value.nodes())
    print 'edges:', len(value.edges())

    print '\nDIFF normal test:'
    print 'missing edges:', len(nx.difference(G1, value).edges())
    print 'added edges:', len(nx.difference(value, G1).edges())
    print '\n\n'