def setUp(self):
        G1 = cnlti(nx.grid_2d_graph(2, 2), first_label=0, ordering="sorted")
        G2 = cnlti(nx.lollipop_graph(3, 3), first_label=4, ordering="sorted")
        G3 = cnlti(nx.house_graph(), first_label=10, ordering="sorted")
        self.G = nx.union(G1, G2)
        self.G = nx.union(self.G, G3)
        self.DG = nx.DiGraph([(1, 2), (1, 3), (2, 3)])
        self.grid = cnlti(nx.grid_2d_graph(4, 4), first_label=1)

        self.gc = []
        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (2, 3), (2, 8), (3, 4), (3, 7), (4, 5),
                          (5, 3), (5, 6), (7, 4), (7, 6), (8, 1), (8, 7)])
        C = [[3, 4, 5, 7], [1, 2, 8], [6]]
        self.gc.append((G, C))

        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (1, 3), (1, 4), (4, 2), (3, 4), (2, 3)])
        C = [[2, 3, 4],[1]]
        self.gc.append((G, C))

        G = nx.DiGraph()
        G.add_edges_from([(1, 2), (2, 3), (3, 2), (2, 1)])
        C = [[1, 2, 3]]
        self.gc.append((G,C))

        # Eppstein's tests
        G = nx.DiGraph({0:[1], 1:[2, 3], 2:[4, 5], 3:[4, 5], 4:[6], 5:[], 6:[]})
        C = [[0], [1], [2],[ 3], [4], [5], [6]]
        self.gc.append((G,C))

        G = nx.DiGraph({0:[1], 1:[2, 3, 4], 2:[0, 3], 3:[4], 4:[3]})
        C = [[0, 1, 2], [3, 4]]
        self.gc.append((G, C))

 def setUp(self):
     G1=cnlti(nx.grid_2d_graph(2,2),first_label=0,ordering="sorted")
     G2=cnlti(nx.lollipop_graph(3,3),first_label=4,ordering="sorted")
     G3=cnlti(nx.house_graph(),first_label=10,ordering="sorted")
     self.G=nx.union(G1,G2)
     self.G=nx.union(self.G,G3)
     self.DG=nx.DiGraph([(1,2),(1,3),(2,3)])
     self.grid=cnlti(nx.grid_2d_graph(4,4),first_label=1)

 def _and_gate(num, bp1, idx1, bp2, idx2):
     #
     # AND gates are constructed as follows:
     #
     # Given BP_1 and BP_2, we merge the acc node of BP_1 with the src
     # node of BP_2 and the rej node of BP_1 with the rej node of BP_2.
     #
     t1 = bp1.nlayers
     t2 = bp2.nlayers
     relabel_layers(bp2.graph, t1)
     oldlayer = bp2.graph.node[('src', idx2)]['layer']
     newnode = ('node-%d' % num, num)
     g = nx.union(bp1.graph, bp2.graph)
     g = contract(g, ('acc', idx1), ('src', idx2), newnode)
     g = contract(g, ('rej', idx1), ('rej', idx2), ('rej', num))
     g = relabel(g, num)
     g.node[newnode]['layer'] = oldlayer
     def eval(inp):
         if inp <= t1 - 1:
             return bp1.inp(inp)
         elif inp <= t1 + t2 - 1:
             return bp2.inp(inp - t1)
         else:
             raise Exception("andgate eval failed on %s!" % inp)
     return _Graph(eval, g, t1 + t2, num)

def core_substitution(graph, orig_cip, new_cip):
    """
    graph is the whole graph..
    subgraph is the interface region in that we will transplant
    new_cip_graph which is the interface and the new core
    """

    # preprocess
    graph = _edge_to_vertex(graph)
    assert (
    set(orig_cip.graph.nodes()) - set(graph.nodes()) == set([])), 'lsgg_compose_util orig_cip_graph not in graph'

    # get isomorphism
    iso = find_all_isomorphisms(orig_cip.interface_graph, new_cip.interface_graph).next()
    if len(iso) != len(orig_cip.interface_graph):
        logger.log(5, "lsgg_compose_util grammar hash collision, discovered in 'core_substution' ")
        return None

    # make graph union (the old graph and the new cip are now floating side by side)
    graph = nx.union(graph, new_cip.graph, rename=('', '-'))

    graph.remove_nodes_from(map(str, orig_cip.core_nodes))

    # merge interface nodes
    for k, v in iso.iteritems():
        merge(graph, str(k), '-' + str(v))

    graph = eg._revert_edge_to_vertex_transform(graph)
    re = nx.convert_node_labels_to_integers(graph)
    return re

    def __call__(self, code, charge_type):
        errors = {}
        for type in code.types:
            errors[type] = code.Syndrome(type, charge_type)

        shrunk_errs, shrunk_exts, matches = {}, {}, {}
        loops_graph = nx.Graph()
        for t1 in code.types:
            [t2, t3] = code.complementaryTypes(t1)
            shrunk_errs[t1] = nx.union(errors[t2], errors[t3])
            shrunk_exts[t1] = code.External[t2] + code.External[t3]
            alt_ext = code.External[t1][0]
            matches[t1] = DSP_Matching(shrunk_errs[t1], shrunk_exts[t1], 2, alt_ext)

            for start in matches[t1]:
                end = matches[t1][start]
                chain = DSP_Path(code.Dual[t1], start, end)
                links = len(chain) -1

                for i in range(links):
                    node1, node2 = chain[i], chain[i+1]
                    edge = (node1, node2)
                    if edge in loops_graph.edges():
                        loops_graph.remove_edge(*edge)
                    else:
                        loops_graph.add_edge(*edge)
        Exts = code.External['red']+code.External['blue']+code.External['green']

        code, loops_graph = correctLoops(code, loops_graph, charge_type)
        while hasConnectedBoundaries(code, loops_graph, Exts):
            ext1, ext2 = connectedBoundaries(loops_graph, Exts)
            code, loops_graph = makeBoundLoop(code, loops_graph, ext1, ext2)
            code, loops_graph = correctLoops(code, loops_graph, charge_type)
        return code

    def crearSubGrafo(self,key,key2,key3):

        temp = nx.Graph()

        for i in range(0,6):

            if i == 0:
                temp.add_node(key+str(i)+key3,extremo=True)
                temp.add_node(key2+str(i)+key3,extremo=True)
            elif i == 5:
                temp.add_node(key+str(i)+key3,extremo=True)
                temp.add_node(key2+str(i)+key3,extremo=True)
            else:
                temp.add_node(key+str(i)+key3)
                temp.add_node(key2+str(i)+key3)

            if (i != 0):

                temp.add_edge(key + str(i-1) +key3 , key+str(i)+key3)
                temp.add_edge(key2 + str(i-1)+key3 , key2+str(i)+key3)

            if (i == 2):

                temp.add_edge(key+'2'+key3 , key2+'0'+key3)
                temp.add_edge(key+'0'+key3 , key2+'2'+key3)

            if (i == 5):

                temp.add_edge(key+'3'+key3 , key2+'5'+key3)
                temp.add_edge(key+'5' +key3, key2+'3'+key3)


        self.grafo =  nx.union(self.grafo,temp)

def spingraph_from_graph(graph):
    # even_graph = nx.relabel_nodes(graph, lambda x:x*2)
    # odd_graph = nx.relabel_nodes(graph, lambda x:2*x+1)
    # union_graph  = nx.union(even_graph, odd_graph)
    # on the fly union saves about 20% memory, ugly but more efficient
    union_graph  = nx.union(nx.relabel_nodes(graph, lambda x:x*2),nx.relabel_nodes(graph, lambda x:2*x+1))
    # from pudb import set_trace; set_trace()
    for spin_down_node in xrange(1,union_graph.order(),2):
        spin_up_node = spin_down_node -1
        for spin_down_node_neighbour in union_graph[spin_down_node].keys():
            if spin_down_node_neighbour % 2 ==0:
                continue
            if spin_down_node_neighbour < spin_down_node:             # is either top or left neighbour
                if spin_down_node_neighbour == spin_down_node-2:      # is left neighbour
                    union_graph.add_edge(spin_up_node,spin_down_node_neighbour,weight=-p.tso)
                    union_graph.add_edge(spin_down_node_neighbour,spin_up_node,weight=-p.tso)
                else:
                    union_graph.add_edge(spin_up_node,spin_down_node_neighbour,weight=+1j*p.tso)
                    union_graph.add_edge(spin_down_node_neighbour,spin_up_node,weight=-1j*p.tso)
            if spin_down_node_neighbour > spin_down_node:             # is either right or bottom neighbour
                if spin_down_node_neighbour == spin_down_node+2:      # is right neighbour
                    union_graph.add_edge(spin_up_node,spin_down_node_neighbour,weight=p.tso)
                    union_graph.add_edge(spin_down_node_neighbour,spin_up_node,weight=p.tso)
                else:
                    union_graph.add_edge(spin_up_node,spin_down_node_neighbour,weight=-1j*p.tso)
                    union_graph.add_edge(spin_down_node_neighbour,spin_up_node,weight=+1j*p.tso)
    return union_graph

    def setUp(self):
        # G is the example graph in Figure 1 from Batagelj and
        # Zaversnik's paper titled An O(m) Algorithm for Cores
        # Decomposition of Networks, 2003,
        # http://arXiv.org/abs/cs/0310049.  With nodes labeled as
        # shown, the 3-core is given by nodes 1-8, the 2-core by nodes
        # 9-16, the 1-core by nodes 17-20 and node 21 is in the
        # 0-core.
        t1 = nx.convert_node_labels_to_integers(nx.tetrahedral_graph(), 1)
        t2 = nx.convert_node_labels_to_integers(t1, 5)
        G = nx.union(t1, t2)
        G.add_edges_from([(3, 7), (2, 11), (11, 5), (11, 12), (5, 12),
                          (12, 19), (12, 18), (3, 9), (7, 9), (7, 10),
                          (9, 10), (9, 20), (17, 13), (13, 14), (14, 15),
                          (15, 16), (16, 13)])
        G.add_node(21)
        self.G = G

        # Create the graph H resulting from the degree sequence
        # [0, 1, 2, 2, 2, 2, 3] when using the Havel-Hakimi algorithm.

        degseq = [0, 1, 2, 2, 2, 2, 3]
        H = nx.havel_hakimi_graph(degseq)
        mapping = {6: 0, 0: 1, 4: 3, 5: 6, 3: 4, 1: 2, 2: 5}
        self.H = nx.relabel_nodes(H, mapping)

    def computeDocumentGraph(self, verbose=False):
        """Create a single document graph from the union of the graphs created
           for each sentence in the archive. Note that the algorithm in NetworkX
           is different based on whether the Python version is greater than or
           equal to 2.6"""
        # Note that this as written does not include the currentGraph in the DocumentGraph
        # Maybe this should be changed
        self.__documentGraph = ConTextMarkup()
        if verbose:
            print "Document markup has %d edges" % self.__document.number_of_edges()
        markups = [e[1] for e in self.__document.edges(data=True) if e[2].get("category") == "markup"]
        if verbose:
            print "Document markup has %d conTextMarkup objects" % len(markups)
        ic = 0
        for i in range(len(markups)):
            # for m in markups:
            m = markups[i]
            if verbose:
                print "markup %d has %d total items including %d targets" % (
                    i,
                    m.number_of_nodes(),
                    m.getNumMarkedTargets(),
                )

            self.__documentGraph = nx.union(m, self.__documentGraph)
            if verbose:
                print "documentGraph now has %d nodes" % self.__documentGraph.number_of_nodes()

    def combine_graphs(self, true_class_bias=1,
                       multi_class_bias=0, multi_class_threshold=0,
                       class_graph=None, instance_graph=None):
        """Combine graphs."""
        probs = np.array([instance_graph.node[v]['prob']
                          for v in instance_graph.nodes()])

        id_offset = max(instance_graph.nodes()) + 1
        offset_pred_graph = \
            nx.relabel_nodes(class_graph, lambda x: x + id_offset)
        union_graph = nx.union(instance_graph, offset_pred_graph)

        if multi_class_bias != 0:
            for u in instance_graph.nodes():
                for group, prob in enumerate(probs[u]):
                    if prob >= multi_class_threshold:
                        group_id = group + id_offset
                        weight = prob * multi_class_bias
                        union_graph.add_edge(
                            u, group_id,
                            weight=weight,
                            len=self._weigth_to_len(weight))

        if true_class_bias != 0:
            for u in instance_graph.nodes():
                group_id = instance_graph.node[u]['group'] + id_offset
                union_graph.add_edge(u, group_id,
                                     weight=true_class_bias,
                                     len=self._weigth_to_len(true_class_bias))

        return union_graph

def draw_graph(label_flag=True, remove_isolated=True, different_size=True, iso_level=10, node_size=40):
    G=build_graph(fb.get_friends_network())
    betweenness=nx.betweenness_centrality(G)
    degree=nx.degree_centrality(G)
    degree_num=[ degree[v] for v in G]
    maxdegree=max(degree_num);mindegree=min(degree_num);
    print maxdegree,mindegree
    clustering=nx.clustering(G)
    print nx.transitivity(G)
    # Judge whether remove the isolated point from graph
    if remove_isolated is True:
        H = nx.empty_graph()
        for SG in nx.connected_component_subgraphs(G):
            if SG.number_of_nodes() > iso_level:
                H = nx.union(SG, H)
        G = H
    # Ajust graph for better presentation
    if different_size is True:
        L = nx.degree(G)
        G.dot_size = {}
        for k, v in L.items():
            G.dot_size[k] = v
        #node_size = [betweenness[v] *1000 for v in G]
        node_size = [G.dot_size[v] * 10 for v in G]
        node_color= [((degree[v]-mindegree))/(maxdegree-mindegree) for v in G]
        #edge_width = [getcommonfriends(u,v) for u,v in G.edges()]
    pos = nx.spring_layout(G, iterations=15)
    nx.draw_networkx_edges(G, pos, alpha=0.05)
    nx.draw_networkx_nodes(G, pos, node_size=node_size, node_color=node_color, vmin=0.0,vmax=1.0, alpha=0.3)
    # Judge whether shows label
    if label_flag is True:
        nx.draw_networkx_labels(G, pos, font_size=6,alpha=0.1)
    #nx.draw_graphviz(G)
    plt.show()
    return G

 def mergeNFA(self, nfa1, nfa2):
     nfa1.graph = nx.union(nfa1.graph, nfa2.graph)
     nfa1.graph.add_edge(nfa1.first, nfa2.first, label="epsilon")
     # nfa1.graph.add_edge(nfa2.last, nfa1.last, label='epsilon')
     nfa1.lastArr[nfa2.last] = nfa2.property
     nfa1.refresh()
     return nfa1

def _get_best_graph_cost_pair(semantic_forest, head_key, semantic_weight):
    assert isinstance(semantic_forest, SemanticForest)
    assert isinstance(semantic_weight, SemanticWeight)
    basic_ontology = semantic_forest.basic_ontology
    obj = semantic_forest.graph_nodes[head_key]

    if isinstance(obj, GroundedToken):
        function = obj.function
    else:
        raise Exception

    graph = nx.MultiDiGraph()
    graph.add_node(head_key)
    if function.valence == 0:
        cost = get_semantic_tree_graph_cost(semantic_forest, graph, semantic_weight)
        return GraphCostPair(graph, cost)

    else:
        all_pairs = [[] for _ in range(function.valence)]
        for u, v, edge_key, data in semantic_forest.forest_graph.edges(keys=True, data=True):
            v_graph, v_cost = _get_best_graph_cost_pair(semantic_forest, v, semantic_weight)
            arg_idx = data['arg_idx']
            pair = GraphHeadKeyCostPair(v_graph, v, edge_key, v_cost)
            all_pairs[arg_idx].append(pair)

        for arg_idx, pairs in enumerate(all_pairs):
            best_pair = min(pairs, key=lambda p: _get_cost(semantic_forest, head_key, p, semantic_weight))
            graph = nx.union(graph, best_pair.graph)
            graph.add_edge(head_key, best_pair.head, arg_idx=arg_idx, key=best_pair.key)

        cost = get_semantic_tree_graph_cost(semantic_forest, graph, semantic_weight)
        return GraphCostPair(graph, cost)

def draw_graph(username, password, filename='graph.txt', label_flag=True, remove_isolated=True, different_size=True, iso_level=10, node_size=40):
    """Reading data from file and draw the graph.If not exists, create the file and re-scratch data from net"""
    print "Generating graph..."
    try:
        with open(filename, 'r') as f:
            G = p.load(f)
    except:
        G = getgraph(username, password)
        with open(filename, 'w') as f:
            p.dump(G, f)
    #nx.draw(G)
    # Judge whether remove the isolated point from graph
    if remove_isolated is True:
        H = nx.empty_graph()
        for SG in nx.connected_component_subgraphs(G):
            if SG.number_of_nodes() > iso_level:
                H = nx.union(SG, H)
        G = H
    # Ajust graph for better presentation
    if different_size is True:
        L = nx.degree(G)
        G.dot_size = {}
        for k, v in L.items():
            G.dot_size[k] = v
        node_size = [G.dot_size[v] * 10 for v in G]
    pos = nx.spring_layout(G, iterations=50)
    nx.draw_networkx_edges(G, pos, alpha=0.2)
    nx.draw_networkx_nodes(G, pos, node_size=node_size, node_color='r', alpha=0.3)
    # Judge whether shows label
    if label_flag is True:
        nx.draw_networkx_labels(G, pos, alpha=0.5)
    #nx.draw_graphviz(G)
    plt.show()

    return G

    def copy_and_offset_with_mirror(self, original, offset_val, reflect=False):
        """Add a copy of the graph, offsetting all nodes by a given
        vector. For nodes with the "rung" attribute, add an edge
        between existing node and its offset copy."""
        # make an unchanged copy and an offset/mirrored copy
        orig_copy = original.copy()
        offset_copy = original.copy()
        for nodeid in offset_copy.node:
            # perform an offset
            xyz = offset_copy.node[nodeid]["xyz"]
            xyz = pt_plus_pt(xyz, offset_val)
            if reflect:
                ## also perform a mirror in the y axis
                xyz = [xyz[0], - xyz[1], xyz[2]]
            offset_copy.node[nodeid]["xyz"] = xyz

        # make a union of the original and copy, renaming nodes
        # note that this requires nx to be updated to svn 1520 or above
        # which fixes a bug where union discards node attributes
        new_graph = nx.union(orig_copy, offset_copy, rename=("G-", "H-"))
        # make edges between nodes in original and copy depending on label
        for nodeid in new_graph.node:
            if nodeid.startswith("G-"):
                h_node_id = nodeid.replace("G", "H")
                #connect nodes labelled walkway or join
                if  new_graph.node[nodeid]['label'] == 'walkway':
                    new_graph.node[h_node_id]['label'] = 'walkway'
                    new_graph.add_edge(nodeid, h_node_id, label='walkway')
                if  new_graph.node[nodeid]['label'] == 'join':
                    new_graph.node[h_node_id]['label'] = 'join'
                    new_graph.add_edge(nodeid, h_node_id, label='join')
        new_graph.frame_count = original.frame_count
        return new_graph

def union_all(graphs, rename=(None,) , name=None):
    graphs_names = zip_longest(graphs,rename)
    U, gname = next(graphs_names)
    for H,hname in graphs_names:
        U = nx.union(U, H, (gname,hname),name=name)
        gname = None
    return U

def patternsets2(MotifG1, MotifG2):
    #enumerate all possible permutations of node labels,
    #minimum is sharing one edge, all the way to max is the smaller number of edges, complexity 2^edgenum_max
    #return a set of possibly isomorphic collapses

    patternset = set()
    edgenum_max = min(MotifG1.number_of_edges(), MotifG2.number_of_edges())

    #select L (two+) edges to overlap
    for L in range(1, edgenum_max + 1):
        print L
        L_subsets = list(itertools.combinations(MotifG1.edges(),L))
        L_subsets2 = list(itertools.combinations(MotifG2.edges(),L))
        for subset1 in L_subsets:
            for subset2 in L_subsets2:
                print "already chose these" +str(L)+" edges in Motif2"
                print subset2
                permutations = list(itertools.permutations(subset1))
                i = 0
                for permutation in permutations:
                    print "this permutation is"
                    print permutation
                    print "in this particular order" + str(i)
                    if MotifG1 == MotifG2:
                        print "waring!!!same motif non-relabled"
                        G = nx.disjoint_union(MotifG1, MotifG2)
                    else:
                        G = nx.union(MotifG1, MotifG2)

                    if len(G) != 0:
                        G2 = nx.Graph()
                        G22 = nx.Graph()
                        Motif2merged_nodes = set()
                        for j in range(0, len(permutation)):
                            edge_1 = permutation[j]
                            edge_2 = subset2[j]
                            print "edge 1"
                            print edge_1
                            print "edge 2"
                            print edge_2

                            if edge_2[0] not in Motif2merged_nodes:
                                G1 = merge_nodes(G, edge_1[0], edge_2[0])
                                Motif2merged_nodes.add(edge_2[0])
                            if edge_2[1] not in Motif2merged_nodes:
                                G2 = merge_nodes(G1, edge_1[1], edge_2[1])
                                Motif2merged_nodes.add(edge_2[1])

                            if edge_2[0] not in Motif2merged_nodes:
                                G11 = merge_nodes(G, edge_1[1], edge_2[0])
                            if edge_2[1] not in Motif2merged_nodes:
                                G22 = merge_nodes(G11, edge_1[0], edge_2[1])

                        patternset.add(G2)
                        patternset.add(G22)
                        print G2.nodes()
                    i += 1


    return patternset

    def combine_graphs(self, true_class_bias=1,
                       multi_class_bias=0, multi_class_threshold=0,
                       class_graph=None, instance_graph=None):
        """Combine graphs."""
        probs = np.array([instance_graph.node[v]['prob']
                          for v in instance_graph.nodes()])

        id_offset = max(instance_graph.nodes()) + 1
        offset_pred_graph = \
            nx.relabel_nodes(class_graph, lambda x: x + id_offset)
        union_graph = nx.union(instance_graph, offset_pred_graph)

        mcb = multi_class_bias
        if mcb != 0:
            # add links from each instance to the class nodes
            # with a length inversely proportional to the prob
            for u in instance_graph.nodes():
                # find k-th largest prob value (k=multi_class_threshold)
                # and instantiate only the k most probable edges
                th = sorted(probs[u], reverse=True)[multi_class_threshold]
                for group, prob in enumerate(probs[u]):
                    if prob >= th:
                        group_id = group + id_offset
                        length = (1 - mcb) * self._prob_to_len(prob)
                        union_graph.add_edge(u, group_id, len=length)

        if true_class_bias != 0:
            # add links from each instance to its assigned class
            for u in instance_graph.nodes():
                group_id = instance_graph.node[u]['group'] + id_offset
                union_graph.add_edge(u, group_id,
                                     len=1 - true_class_bias)

        return union_graph

def load_graph(data_dir):
    import pickle
    aminer = pickle.load(open("D:\\Users\\chenwei\\experiment\\aminer_two_3.pickle"))
    linkedin = pickle.load(open("D:\\Users\\chenwei\\experiment\\linkedin_two_filter_3.pickle"))
    id = 0
    for n in aminer.nodes():
        n
    merge = nx.union(linkedin, aminer)
    return merge   

 def _xor_gate(num, bp1, idx1, bp2, idx2):
     #
     # XOR gates are constructed as follows:
     #
     # Given BP_1 and BP_2 (where BP_2 is the "smaller" of the two BPs),
     # produce NOT BP_2, merge the acc node of BP_1 with the src node of
     # NOT BP_2, and merge the rej node of BP_1 with the src node of
     # BP_2.
     #
     assert num > idx1 and num > idx2
     if len(bp1.graph) < len(bp2.graph):
         bp1, bp2 = bp2, bp1
     # choose a temporary idx outside the range of possible indices
     tmpidx = len(bp1.graph) + len(bp2.graph)
     t1 = bp1.nlayers
     t2 = bp2.nlayers
     relabel_layers(bp2.graph, t1)
     oldlayer = bp2.graph.node[('src', idx2)]['layer']
     # construct (G_2, not(G_2))
     bp2not = _not_gate(tmpidx, bp2, idx2)
     # Need to relabel the internal wires as bp2not so we don't end up
     # with duplicate node names when we merge the graphs
     bp2not.graph = relabel_internal(bp2not.graph, tmpidx)
     g = nx.union(bp2.graph, bp2not.graph)
     g = contract(g, ('acc', tmpidx), ('acc', idx2), ('acc', num))
     g = contract(g, ('rej', tmpidx), ('rej', idx2), ('rej', num))
     # construct XOR(G_1, G_2)
     g = nx.union(bp1.graph, g)
     accnode = ('acc-%d' % num, num)
     rejnode = ('rej-%d' % num, num)
     g = contract(g, ('acc', idx1), ('src', tmpidx), accnode)
     g = contract(g, ('rej', idx1), ('src', idx2), rejnode)
     g = relabel(g, num)
     g.node[accnode]['layer'] = oldlayer
     g.node[rejnode]['layer'] = oldlayer
     def eval(inp):
         if inp <= t1 - 1:
             return bp1.inp(inp)
         elif inp <= t1 + t2 - 1:
             return bp2.inp(inp - t1)
         else:
             raise Exception("xorgate eval failed on %s!" % inp)
     return _Graph(eval, g, t1 + t2, num)