def test_complete_graphs():
    for n in range(5, 25, 5):
        G = nx.complete_graph(n)
        assert_equal(n-1, nx.node_connectivity(G))
        assert_equal(n-1, nx.node_connectivity(G.to_directed()))
        assert_equal(n-1, nx.edge_connectivity(G))
        assert_equal(n-1, nx.edge_connectivity(G.to_directed()))

 def test_all_pairs_connectivity(self, nodelist=[0, 1, 2, 3]):
     G = nx.Graph()
     nodes = [0, 1, 2, 3]
     G.add_path(nodes)
     A = numpy.zeros((4, 4), dtype=int)
     for u, v in itertools.combinations(nodes, 2):
         A[u][v] = nx.node_connectivity(G, u, v)
         A[v][u] = nx.node_connectivity(G, u, v)
     C = nx.all_pairs_node_connectivity_matrix(G)
     assert_equal(A, C)

def test_brandes_erlebach():
    # Figure 1 chapter 7: Connectivity
    # http://www.informatik.uni-augsburg.de/thi/personen/kammer/Graph_Connectivity.pdf
    G = nx.Graph()
    G.add_edges_from([(1,2),(1,3),(1,4),(1,5),(2,3),(2,6),(3,4),
                    (3,6),(4,6),(4,7),(5,7),(6,8),(6,9),(7,8),
                    (7,10),(8,11),(9,10),(9,11),(10,11)])
    assert_equal(3,nx.local_edge_connectivity(G,1,11))
    assert_equal(3,nx.edge_connectivity(G,1,11))
    assert_equal(2,nx.local_node_connectivity(G,1,11))
    assert_equal(2,nx.node_connectivity(G,1,11))
    assert_equal(2,nx.edge_connectivity(G)) # node 5 has degree 2
    assert_equal(2,nx.node_connectivity(G))

def test_complete_graphs():
    for n in range(5, 20, 5):
        for flow_func in flow_funcs:
            G = nx.complete_graph(n)
            assert_equal(n-1, nx.node_connectivity(G, flow_func=flow_func),
                         msg=msg.format(flow_func.__name__))
            assert_equal(n-1, nx.node_connectivity(G.to_directed(),
                                                   flow_func=flow_func),
                         msg=msg.format(flow_func.__name__))
            assert_equal(n-1, nx.edge_connectivity(G, flow_func=flow_func),
                         msg=msg.format(flow_func.__name__))
            assert_equal(n-1, nx.edge_connectivity(G.to_directed(),
                                                   flow_func=flow_func),
                         msg=msg.format(flow_func.__name__))

    def updateGraphStats(self, graph):

        origgraph = graph
        if nx.is_connected(graph):
            random = 0
        else:
            connectedcomp = nx.connected_component_subgraphs(graph)
            graph = max(connectedcomp)

        if len(graph) > 1:
            pathlength = nx.average_shortest_path_length(graph)
        else:
            pathlength = 0

        # print graph.nodes(), len(graph), nx.is_connected(graph)

        stats = {
            "radius": nx.radius(graph),
            "density": nx.density(graph),
            "nodecount": len(graph.nodes()),
            "center": nx.center(graph),
            "avgcluscoeff": nx.average_clustering(graph),
            "nodeconnectivity": nx.node_connectivity(graph),
            "components": nx.number_connected_components(graph),
            "avgpathlength": pathlength
        }

        # print "updated graph stats", stats
        return stats

def test_tutte():
    G = nx.tutte_graph()
    for flow_func in flow_funcs:
        assert_equal(3, nx.node_connectivity(G, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))
        assert_equal(3, nx.edge_connectivity(G, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))

def test_icosahedral():
    G=nx.icosahedral_graph()
    for flow_func in flow_funcs:
        assert_equal(5, nx.node_connectivity(G, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))
        assert_equal(5, nx.edge_connectivity(G, flow_func=flow_func),
                     msg=msg.format(flow_func.__name__))

def test_node_cutset_random_graphs():
    for i in range(5):
        G = nx.fast_gnp_random_graph(50,0.2)
        cutset = nx.minimum_node_cut(G)
        assert_equal(nx.node_connectivity(G), len(cutset))
        G.remove_nodes_from(cutset)
        assert_false(nx.is_connected(G))

def test_graph_from_pr_2053():
    G = nx.Graph()
    G.add_edges_from([
        ('A', 'B'), ('A', 'D'), ('A', 'F'), ('A', 'G'),
        ('B', 'C'), ('B', 'D'), ('B', 'G'), ('C', 'D'),
        ('C', 'E'), ('C', 'Z'), ('D', 'E'), ('D', 'F'),
        ('E', 'F'), ('E', 'Z'), ('F', 'Z'), ('G', 'Z')])
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge disjoint paths
        edge_paths = list(nx.edge_disjoint_paths(G, 'A', 'Z', **kwargs))
        assert_true(are_edge_disjoint_paths(G, edge_paths), msg=msg.format(flow_func.__name__))
        assert_equal(
            nx.edge_connectivity(G, 'A', 'Z'),
            len(edge_paths),
            msg=msg.format(flow_func.__name__),
        )
        # node disjoint paths
        node_paths = list(nx.node_disjoint_paths(G, 'A', 'Z', **kwargs))
        assert_true(are_node_disjoint_paths(G, node_paths), msg=msg.format(flow_func.__name__))
        assert_equal(
            nx.node_connectivity(G, 'A', 'Z'),
            len(node_paths),
            msg=msg.format(flow_func.__name__),
        )

def test_articulation_points():
    Ggen = _generate_no_biconnected()
    for flow_func in flow_funcs:
        for i in range(3):
            G = next(Ggen)
            assert_equal(nx.node_connectivity(G, flow_func=flow_func), 1,
                         msg=msg.format(flow_func.__name__))

def draw_graph(nodes, edges, graphs_dir, default_lang='all'):
    lang_graph = nx.MultiDiGraph()
    lang_graph.add_nodes_from(nodes)
    for edge in edges:
        if edges[edge] == 0:
            lang_graph.add_edge(edge[0], edge[1])
        else:
            lang_graph.add_edge(edge[0], edge[1], weight=float(edges[edge]), label=str(edges[edge]))

    # print graph info in stdout
    # degree centrality
    print('-----------------\n\n')
    print(default_lang)
    print(nx.info(lang_graph))
    try:
        # When ties are associated to some positive aspects such as friendship or collaboration,
        #  indegree is often interpreted as a form of popularity, and outdegree as gregariousness.
        DC = nx.degree_centrality(lang_graph)
        max_dc = max(DC.values())
        max_dc_list = [item for item in DC.items() if item[1] == max_dc]
    except ZeroDivisionError:
        max_dc_list = []
    # https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%BF%D0%BB%D0%B5%D0%BA%D1%81%D0%BD%D1%8B%D0%B5_%D1%81%D0%B5%D1%82%D0%B8
    print('maxdc', str(max_dc_list), sep=': ')
    # assortativity coef
    AC = nx.degree_assortativity_coefficient(lang_graph)
    print('AC', str(AC), sep=': ')
    # connectivity
    print("Слабо-связный граф: ", nx.is_weakly_connected(lang_graph))
    print("количество слабосвязанных компонент: ", nx.number_weakly_connected_components(lang_graph))
    print("Сильно-связный граф: ", nx.is_strongly_connected(lang_graph))
    print("количество сильносвязанных компонент: ", nx.number_strongly_connected_components(lang_graph))
    print("рекурсивные? компоненты: ", nx.number_attracting_components(lang_graph))
    print("число вершинной связности: ", nx.node_connectivity(lang_graph))
    print("число рёберной связности: ", nx.edge_connectivity(lang_graph))
    # other info
    print("average degree connectivity: ", nx.average_degree_connectivity(lang_graph))
    print("average neighbor degree: ", sorted(nx.average_neighbor_degree(lang_graph).items(),
                                              key=itemgetter(1), reverse=True))
    # best for small graphs, and our graphs are pretty small
    print("pagerank: ", sorted(nx.pagerank_numpy(lang_graph).items(), key=itemgetter(1), reverse=True))

    plt.figure(figsize=(16.0, 9.0), dpi=80)
    plt.axis('off')
    pos = graphviz_layout(lang_graph)
    nx.draw_networkx_edges(lang_graph, pos, alpha=0.5, arrows=True)
    nx.draw_networkx(lang_graph, pos, node_size=1000, font_size=12, with_labels=True, node_color='green')
    nx.draw_networkx_edge_labels(lang_graph, pos, edges)

    # saving file to draw it with dot-graphviz
    # changing overall graph view, default is top-bottom
    lang_graph.graph['graph'] = {'rankdir': 'LR'}
    # marking with blue nodes with maximum degree centrality
    for max_dc_node in max_dc_list:
        lang_graph.node[max_dc_node[0]]['fontcolor'] = 'blue'
    write_dot(lang_graph, os.path.join(graphs_dir, default_lang + '_links.dot'))

    # plt.show()
    plt.savefig(os.path.join(graphs_dir, 'python_' + default_lang + '_graph.png'), dpi=100)
    plt.close()

def test_empty_graphs():
    for k in range(5, 25, 5):
        G = nx.empty_graph(k)
        for flow_func in flow_funcs:
            assert_equal(0, nx.node_connectivity(G, flow_func=flow_func),
                         msg=msg.format(flow_func.__name__))
            assert_equal(0, nx.edge_connectivity(G, flow_func=flow_func),
                         msg=msg.format(flow_func.__name__))

def _check_connectivity(G):
    result = nx.k_components(G)
    for k, components in result.items():
        if k < 3:
            continue
        for component in components:
            C = G.subgraph(component)
            assert_true(nx.node_connectivity(C) >= k)

 def test_all_pairs_connectivity_nbunch(self):
     G = nx.complete_graph(5)
     nbunch = [0, 2, 3]
     A = {n: {} for n in nbunch}
     for u, v in itertools.combinations(nbunch, 2):
         A[u][v] = A[v][u] = nx.node_connectivity(G, u, v)
     C = nx.all_pairs_node_connectivity(G, nbunch=nbunch)
     assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
                  sorted((k, sorted(v)) for k, v in C.items()))

def _check_separating_sets(G):
    for Gc in nx.connected_component_subgraphs(G):
        if len(Gc) < 3:
            continue
        for cut in nx.all_node_cuts(Gc):
            assert_equal(nx.node_connectivity(Gc), len(cut))
            H = Gc.copy()
            H.remove_nodes_from(cut)
            assert_false(nx.is_connected(H))

def _check_connectivity(G, k_components):
    for k, components in k_components.items():
        if k < 3:
            continue
        # check that k-components have node connectivity >= k.
        for component in components:
            C = G.subgraph(component)
            K = nx.node_connectivity(C)
            assert_greater_equal(K, k)

def _check_connectivity(G):
    result = nx.k_components(G)
    for k, components in result.items():
        if k < 3:
            continue
        for component in components:
            C = G.subgraph(component)
            K = nx.node_connectivity(C)
            assert_greater_equal(K, k)

 def test_all_pairs_connectivity_nbunch_iter(self):
     G = nx.complete_graph(5)
     nbunch = [0, 2, 3]
     A = dict.fromkeys(nbunch, dict())
     for u, v in itertools.combinations(nbunch, 2):
         A[u][v] = nx.node_connectivity(G, u, v)
     C = nx.all_pairs_node_connectivity(G, nbunch=iter(nbunch))
     assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
                  sorted((k, sorted(v)) for k, v in C.items()))

def test_white_harary_2():
    # Figure 8 white and harary (2001)
    # # http://eclectic.ss.uci.edu/~drwhite/sm-w23.PDF
    G = nx.disjoint_union(nx.complete_graph(4), nx.complete_graph(4))
    G.add_edge(0,4)
    # kappa <= lambda <= delta
    assert_equal(3, min(nx.core_number(G).values()))
    assert_equal(1, nx.node_connectivity(G))
    assert_equal(1, nx.edge_connectivity(G))

def test_not_connected():
    G = nx.Graph()
    G.add_path([1, 2, 3])
    G.add_path([4, 5])
    for flow_func in flow_funcs:
        assert_equal(nx.node_connectivity(G), 0,
                     msg=msg.format(flow_func.__name__))
        assert_equal(nx.edge_connectivity(G), 0,
                     msg=msg.format(flow_func.__name__))