def test_single_nodes(self):

        # single nodes
        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(2,4)
        sbn=sb(G,nodes=[1,2])
        assert_almost_equal(sbn[1],0.85,places=2)
        assert_almost_equal(sbn[2],0.77,places=2)

        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(0,1)
        sbn=sb(G,nodes=[1,2])
        assert_almost_equal(sbn[1],0.73,places=2)
        assert_almost_equal(sbn[2],0.82,places=2)

 def test_write_sparse6(self):
     fh = StringIO()
     nx.write_sparse6(nx.complete_bipartite_graph(6,9), fh)
     fh.seek(0)
     assert_equal(fh.read(),
                  '>>sparse6<<:Nk?G`cJ?G`cJ?G`cJ?G`'+
                  'cJ?G`cJ?G`cJ?G`cJ?G`cJ?G`cJ\n')

def ClawGraph():
    """
    Returns a claw graph.

    A claw graph is named for its shape. It is actually a complete
    bipartite graph with (n1, n2) = (1, 3).

    PLOTTING: See CompleteBipartiteGraph.

    EXAMPLES: Show a Claw graph

    ::

        sage: (graphs.ClawGraph()).show() # long time

    Inspect a Claw graph

    ::

        sage: G = graphs.ClawGraph()
        sage: G
        Claw graph: Graph on 4 vertices
    """
    pos_dict = {0:(0,1),1:(-1,0),2:(0,0),3:(1,0)}
    import networkx
    G = networkx.complete_bipartite_graph(1,3)
    return graph.Graph(G, pos=pos_dict, name="Claw graph")

 def test_complete_bipartite(self):
     G = nx.complete_bipartite_graph(6, 9)
     result = BytesIO()
     nx.write_sparse6(G, result)
     # Compared with sage
     expected = b'>>sparse6<<:Nk' + b'?G`cJ' * 9 + b'\n'
     assert_equal(result.getvalue(), expected)

 def setUp(self):
     self.P4 = nx.path_graph(4)
     self.K3 = nx.complete_bipartite_graph(3,3)
     self.C4 = nx.cycle_graph(4)
     self.davis = nx.davis_southern_women_graph()
     self.top_nodes = [n for n,d in self.davis.nodes(data=True) 
                       if d['bipartite']==0]

    def test_bipartite_layout(self):
        G = nx.complete_bipartite_graph(3,5)
        top, bottom = nx.bipartite.sets(G)

        vpos = nx.bipartite_layout(G, top)
        assert_equal(len(vpos), len(G))

        top_x = vpos[list(top)[0]][0]
        bottom_x = vpos[list(bottom)[0]][0]
        for node in top:
            assert_equal(vpos[node][0], top_x)
        for node in bottom:
            assert_equal(vpos[node][0], bottom_x)

        vpos = nx.bipartite_layout(G, top,
                                   align='horizontal',
                                   center=(2,2),
                                   scale=2,
                                   aspect_ratio=1)
        assert_equal(len(vpos), len(G))

        top_y = vpos[list(top)[0]][1]
        bottom_y = vpos[list(bottom)[0]][1]
        for node in top:
            assert_equal(vpos[node][1], top_y)
        for node in bottom:
            assert_equal(vpos[node][1], bottom_y)

        assert_raises(ValueError, nx.bipartite_layout, G, top, align='foo')

def generate_connection_graph(graph_type, params, count):
    lower_type = graph_type.lower()
    if lower_type == 'complete':
        assert (len(params) == 0)
        return networkx.complete_graph(count)
    elif lower_type == 'complete-bipartite':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        n1 = int(round(count * float(params[0]) / float(params[1])))
        n2 = int(round(count * float(params[1]) / float(params[0])))
        n1 = 1 if n1 < 1 else n1
        n2 = 1 if n2 < 1 else n2
        return networkx.complete_bipartite_graph(n1, n2)
    elif lower_type == 'circular-ladder':
        assert (len(params) == 0)
        return networkx.circular_ladder_graph(count)
    elif lower_type == 'cycle':
        assert (len(params) == 0)
        return networkx.cycle_graph(count)
    elif lower_type == 'periodic-2grid':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        width = int(round(math.sqrt(count * float(params[0]) / float(params[1]))))
        height = int(round(math.sqrt(count * float(params[1]) / float(params[0]))))
        width = 1 if width < 1 else width
        height = 1 if height < 1 else height
        return networkx.grid_2d_graph(width, height, True)
    elif lower_type == 'nonperiodic-2grid':
        assert (len(params) == 2)
        assert (int(params[0]) > 0.0)
        assert (int(params[1]) > 0.0)
        width = int(round(math.sqrt(count * float(params[0]) / float(params[1]))))
        height = int(round(math.sqrt(count * float(params[1]) / float(params[0]))))
        width = 1 if width < 1 else width
        height = 1 if height < 1 else height
        return networkx.grid_2d_graph(width, height, False)
    elif lower_type == 'hypercube':
        assert (len(params) == 0)
        return networkx.hypercube_graph(int(round(math.log(count, 2))))
    elif lower_type == 'star':
        assert (len(params) == 0)
        return networkx.star_graph(count - 1)
    elif lower_type == 'wheel':
        assert (len(params) == 0)
        return networkx.wheel_graph(count)
    elif lower_type == 'erdos-reyni':
        assert (len(params) == 1)
        return networkx.erdos_renyi_graph(count, float(params[0]))
    elif lower_type == 'watts-strogatz':
        assert (len(params) == 2)
        if int(params[0]) >= count / 2:
            k = int(count / 2 - 1)
        else:
            k = int(params[0])
        return networkx.connected_watts_strogatz_graph(count, k, int(params[1]))
    else:
        print "Unknown graph type {}".format(lower_type)
        assert False

def bipartite_gnmk_random_graph(n, m, k, seed=None, directed=False):
    """Return a random bipartite nxgraph G_{n,m,k}.

    Produces a bipartite nxgraph chosen randomly out of the set of all graphs
    with n top nodes, m bottom nodes, and k edges.

    Parameters
    ----------
    n : int
        The number of nodes in the first bipartite set.
    m : int
        The number of nodes in the second bipartite set.
    k : int
        The number of edges
    seed : int, optional
        Seed for random number generator (default=None). 
    directed : bool, optional (default=False)
        If True return a directed nxgraph
        
    Examples
    --------
    G = nx.bipartite_gnmk_random_graph(10,20,50)

    See Also
    --------
    gnm_random_graph

    Notes
    -----
    If k > m * n then a complete bipartite nxgraph is returned.

    This nxgraph is a bipartite version of the `G_{nm}` random nxgraph model.
    """
    G = networkx.Graph()
    G=_add_nodes_with_bipartite_label(G,n,m)
    if directed:
        G=nx.DiGraph(G)
    G.name="bipartite_gnm_random_graph(%s,%s,%s)"%(n,m,k)
    if seed is not None:
        random.seed(seed)
    if n == 1 or m == 1:
        return G
    max_edges = n*m # max_edges for bipartite networks
    if k >= max_edges: # Maybe we should raise an exception here
        return networkx.complete_bipartite_graph(n, m, create_using=G)

    top = [n for n,d in G.nodes(data=True) if d['bipartite']==0]
    bottom = list(set(G) - set(top))
    edge_count = 0
    while edge_count < k:
        # generate random edge,u,v
        u = random.choice(top)
        v = random.choice(bottom)
        if v in G[u]:
            continue
        else:
            G.add_edge(u,v)
            edge_count += 1
    return G

    def test_complete_2_partite_graph(self):
        """Tests that the complete 2-partite graph is the complete bipartite
        graph.

        """
        G = nx.complete_multipartite_graph(2, 3)
        H = nx.complete_bipartite_graph(2, 3)
        assert_nodes_equal(G, H)
        assert_edges_equal(G.edges(), H.edges())

 def test_is_distance_regular(self):
     assert_true(nx.is_distance_regular(nx.icosahedral_graph()))
     assert_true(nx.is_distance_regular(nx.petersen_graph()))
     assert_true(nx.is_distance_regular(nx.cubical_graph()))
     assert_true(nx.is_distance_regular(nx.complete_bipartite_graph(3,3)))
     assert_true(nx.is_distance_regular(nx.tetrahedral_graph()))
     assert_true(nx.is_distance_regular(nx.dodecahedral_graph()))
     assert_true(nx.is_distance_regular(nx.pappus_graph()))
     assert_true(nx.is_distance_regular(nx.heawood_graph()))
     assert_true(nx.is_distance_regular(nx.cycle_graph(3)))
     # no distance regular
     assert_false(nx.is_distance_regular(nx.path_graph(4)))

    def obtain_graph(args,suffix=""):
        """Build a Bipartite graph according to command line arguments

        Arguments:
        - `args`: command line options
        """

        if getattr(args,"bp"+suffix) is not None:

            l,r,p = getattr(args,"bp"+suffix)
            G=bipartite_random_graph(l,r,p)

        elif getattr(args,"bm"+suffix)  is not None:

            l,r,m = getattr(args,"bm"+suffix)
            G=bipartite_gnmk_random_graph(l,r,m)

        elif getattr(args,"bd"+suffix) is not None:

            l,r,d = getattr(args,"bd"+suffix)
            G=bipartite_random_left_regular(l,r,d)

        elif getattr(args,"bregular"+suffix)  is not None:

            l,r,d = getattr(args,"bregular"+suffix)
            G=bipartite_random_regular(l,r,d)

        elif getattr(args,"bshift"+suffix) is not None:

            N,M,pattern = getattr(args,"bshift"+suffix)
            G=bipartite_shift(N,M,pattern)
            
        elif getattr(args,"bcomplete"+suffix) is not None:
            
            l,r = getattr(args,"bcomplete"+suffix)
            G=complete_bipartite_graph(l,r)
            # Workaround: the bipartite labels are missing in old version of networkx
            for i in range(0,l):
                G.add_node(i,bipartite=0)
            for i in range(l,l+r):
                G.add_node(i,bipartite=1)
            
        elif getattr(args,"graphformat"+suffix) is not None:

            try:
                print("INFO: reading bipartite graph {} from '{}'".format(suffix,getattr(args,"input"+suffix).name),
                      file=sys.stderr)
                G=readGraph(getattr(args,"input"+suffix),
                            "bipartite",
                            getattr(args,"graphformat"+suffix))
            except ValueError,e:
                print("ERROR ON '{}'. {}".format(getattr(args,"input"+suffix).name,e),file=sys.stderr)
                exit(-1)

    def setUp(self):
        try:
            global nx
            import networkx as nx
        except ImportError:
            raise SkipTest('networkx not available.')

        self.planar=[]
        self.planar.extend([nx.path_graph(5),
                            nx.complete_graph(4)])
        self.non_planar=[]
        self.non_planar.extend([nx.complete_graph(5),
                                nx.complete_bipartite_graph(3,3)])

def check_counterexample(G, sub_graph):
    """Raises an exception if the counterexample is wrong.

    Parameters
    ----------
    G : NetworkX graph
    subdivision_nodes : set
        A set of nodes inducing a subgraph as a counterexample
    """
    # 1. Create the sub graph
    sub_graph = nx.Graph(sub_graph)

    # 2. Remove self loops
    for u in sub_graph:
        if sub_graph.has_edge(u, u):
            sub_graph.remove_edge(u, u)

    # keep track of nodes we might need to contract
    contract = list(sub_graph)

    # 3. Contract Edges
    while len(contract) > 0:
        contract_node = contract.pop()
        if contract_node not in sub_graph:
            # Node was already contracted
            continue
        degree = sub_graph.degree[contract_node]
        # Check if we can remove the node
        if degree == 2:
            # Get the two neighbors
            neighbors = iter(sub_graph[contract_node])
            u = next(neighbors)
            v = next(neighbors)
            # Save nodes for later
            contract.append(u)
            contract.append(v)
            # Contract edge
            sub_graph.remove_node(contract_node)
            sub_graph.add_edge(u, v)

    # 4. Check for isomorphism with K5 or K3_3 graphs
    if len(sub_graph) == 5:
        if not nx.is_isomorphic(nx.complete_graph(5), sub_graph):
            raise nx.NetworkXException("Bad counter example.")
    elif len(sub_graph) == 6:
        if not nx.is_isomorphic(nx.complete_bipartite_graph(3, 3), sub_graph):
            raise nx.NetworkXException("Bad counter example.")
    else:
        raise nx.NetworkXException("Bad counter example.")

    def test_generate_graph6(self):
        assert_equal(nx.generate_graph6(nx.empty_graph(0)), '>>graph6<<?')
        assert_equal(nx.generate_graph6(nx.empty_graph(1)), '>>graph6<<@')

        G1 = nx.complete_graph(4)
        assert_equal(nx.generate_graph6(G1, header=True), '>>graph6<<C~')
        assert_equal(nx.generate_graph6(G1, header=False), 'C~')

        G2 = nx.complete_bipartite_graph(6,9)
        assert_equal(nx.generate_graph6(G2, header=False),
                     'N??F~z{~Fw^_~?~?^_?') # verified by Sage

        G3 = nx.complete_graph(67)
        assert_equal(nx.generate_graph6(G3, header=False),
                     '[email protected]' + '~' * 368 + 'w')

    def test_quotient_graph_complete_bipartite(self):
        """Tests that the quotient graph of the complete bipartite graph under
        the "same neighbors" node relation is `K_2`.

        """
        G = nx.complete_bipartite_graph(2, 3)
        # Two nodes are equivalent if they are not adjacent but have the same
        # neighbor set.
        same_neighbors = lambda u, v: (u not in G[v] and v not in G[u]
                                       and G[u] == G[v])
        expected = nx.complete_graph(2)
        actual = nx.quotient_graph(G, same_neighbors)
        # It won't take too long to run a graph isomorphism algorithm on such
        # small graphs.
        assert_true(nx.is_isomorphic(expected, actual))

    def setup(self):
        """Creates a bipartite graph for use in testing matching algorithms.

        The bipartite graph has a maximum cardinality matching that leaves
        vertex 1 and vertex 10 unmatched. The first six numbers are the left
        vertices and the next six numbers are the right vertices.

        """
        self.simple_graph = nx.complete_bipartite_graph(2, 3)
        self.simple_solution = {0: 2, 1: 3, 2: 0, 3: 1}

        edges = [(0, 7), (0, 8), (2, 6), (2, 9), (3, 8), (4, 8), (4, 9),
                 (5, 11)]
        self.top_nodes = set(range(6))
        self.graph = nx.Graph()
        self.graph.add_nodes_from(range(12))
        self.graph.add_edges_from(edges)

        # Example bipartite graph from issue 2127
        G = nx.Graph()
        G.add_nodes_from([
            (1, 'C'), (1, 'B'), (0, 'G'), (1, 'F'),
            (1, 'E'), (0, 'C'), (1, 'D'), (1, 'I'),
            (0, 'A'), (0, 'D'), (0, 'F'), (0, 'E'),
            (0, 'H'), (1, 'G'), (1, 'A'), (0, 'I'),
            (0, 'B'), (1, 'H'),
        ])
        G.add_edge((1, 'C'), (0, 'A'))
        G.add_edge((1, 'B'), (0, 'A'))
        G.add_edge((0, 'G'), (1, 'I'))
        G.add_edge((0, 'G'), (1, 'H'))
        G.add_edge((1, 'F'), (0, 'A'))
        G.add_edge((1, 'F'), (0, 'C'))
        G.add_edge((1, 'F'), (0, 'E'))
        G.add_edge((1, 'E'), (0, 'A'))
        G.add_edge((1, 'E'), (0, 'C'))
        G.add_edge((0, 'C'), (1, 'D'))
        G.add_edge((0, 'C'), (1, 'I'))
        G.add_edge((0, 'C'), (1, 'G'))
        G.add_edge((0, 'C'), (1, 'H'))
        G.add_edge((1, 'D'), (0, 'A'))
        G.add_edge((1, 'I'), (0, 'A'))
        G.add_edge((1, 'I'), (0, 'E'))
        G.add_edge((0, 'A'), (1, 'G'))
        G.add_edge((0, 'A'), (1, 'H'))
        G.add_edge((0, 'E'), (1, 'G'))
        G.add_edge((0, 'E'), (1, 'H'))
        self.disconnected_graph = G

    def test_star_graph(self):
        assert_true(is_isomorphic(star_graph(0), empty_graph(1)))
        assert_true(is_isomorphic(star_graph(1), path_graph(2)))
        assert_true(is_isomorphic(star_graph(2), path_graph(3)))
        assert_true(is_isomorphic(star_graph(5), nx.complete_bipartite_graph(1,5)))

        s=star_graph(10)
        assert_equal(sorted(d for n, d in s.degree()),
                     [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 10])

        assert_raises(networkx.exception.NetworkXError,
                      star_graph, 10, create_using=DiGraph())

        ms=star_graph(10, create_using=MultiGraph())
        assert_edges_equal(ms.edges(), s.edges())

        G=star_graph("abcdefg")
        assert_equal(len(G), 7)
        assert_equal(G.size(), 6)

    def test_generic_weighted_projected_graph_custom(self):
        def jaccard(G, u, v):
            unbrs = set(G[u])
            vnbrs = set(G[v])
            return float(len(unbrs & vnbrs)) / len(unbrs | vnbrs)

        def my_weight(G, u, v, weight="weight"):
            w = 0
            for nbr in set(G[u]) & set(G[v]):
                w += G.edge[u][nbr].get(weight, 1) + G.edge[v][nbr].get(weight, 1)
            return w

        B = nx.complete_bipartite_graph(2, 2)
        for i, (u, v) in enumerate(B.edges()):
            B.edge[u][v]["weight"] = i + 1
        G = bipartite.generic_weighted_projected_graph(B, [0, 1], weight_function=jaccard)
        assert_equal(G.edges(data=True), [(0, 1, {"weight": 1.0})])
        G = bipartite.generic_weighted_projected_graph(B, [0, 1], weight_function=my_weight)
        assert_equal(G.edges(data=True), [(0, 1, {"weight": 10})])
        G = bipartite.generic_weighted_projected_graph(B, [0, 1])
        assert_equal(G.edges(data=True), [(0, 1, {"weight": 2})])

    def obtain_graph(args):
        """Build a Bipartite graph according to command line arguments

        Arguments:
        - `args`: command line options
        """

        if args.bp is not None:

            l,r,p = args.bp
            G=bipartite_random_graph(l,r,p)

        elif args.bm is not None:

            l,r,m = args.bm
            G=bipartite_gnmk_random_graph(l,r,m)

        elif args.bd is not None:

            l,r,d = args.bd
            G=bipartite_random_left_regular(l,r,d)

        elif args.bregular is not None:

            l,r,d = args.bregular
            G=bipartite_random_regular(l,r,d)

        elif args.bcomplete is not None:
            
            l,r = args.bcomplete
            G=complete_bipartite_graph(l,r)

        elif args.graphformat is not None:

            try:
                G=readGraph(args.input, "bipartite", args.graphformat)
            except ValueError,e:
                print("ERROR ON '{}'. {}".format(args.input.name,e),file=sys.stderr)
                exit(-1)

    def k23_like(self):
        # K2,3-like
        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(0,1)
        assert_almost_equal(sb(G),0.769,places=3)

        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(2,4)
        assert_almost_equal(sb(G),0.829,places=3)

        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(2,4)
        G.add_edge(3,4)
        assert_almost_equal(sb(G),0.731,places=3)


        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(0,1)
        G.add_edge(2,4)
        assert_almost_equal(sb(G),0.692,places=3)

        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(2,4)
        G.add_edge(3,4)
        G.add_edge(0,1)
        assert_almost_equal(sb(G),0.645,places=3)

        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(2,4)
        G.add_edge(3,4)
        G.add_edge(2,3)
        assert_almost_equal(sb(G),0.645,places=3)

        G=nx.complete_bipartite_graph(2,3)
        G.add_edge(2,4)
        G.add_edge(3,4)
        G.add_edge(2,3)
        G.add_edge(0,1)
        assert_almost_equal(sb(G),0.597,places=3)