def test_cycles(self):
     K_undir = nx.all_pairs_node_connectivity(self.cycle)
     for source in K_undir:
         for target, k in K_undir[source].items():
             assert_true(k == 2)
     K_dir = nx.all_pairs_node_connectivity(self.directed_cycle)
     for source in K_dir:
         for target, k in K_dir[source].items():
             assert_true(k == 1)

 def test_paths(self):
     K_undir = nx.all_pairs_node_connectivity(self.path)
     for source in K_undir:
         for target, k in K_undir[source].items():
             assert_true(k == 1)
     K_dir = nx.all_pairs_node_connectivity(self.directed_path)
     for source in K_dir:
         for target, k in K_dir[source].items():
             if source < target:
                 assert_true(k == 1)
             else:
                 assert_true(k == 0)

        def set_connectivity(data):    
            df = data.copy()
            df['DateOfDeparture'] = pd.to_datetime(df['DateOfDeparture'])
            df['month'] = df['DateOfDeparture'].dt.week.astype(str)
            df['year'] = df['DateOfDeparture'].dt.year.astype(str)
            df['arr_dep'] = df[['Departure','Arrival']].apply(lambda x: '-'.join(x),axis=1)

            G = nx.Graph()
            connectivity = {}

            list_dep_arr = zip(df['Departure'], df['Arrival'])
            G.add_edges_from(list_dep_arr)
            #G.number_of_nodes()
            #G.number_of_edges()
            connectivity = nx.all_pairs_node_connectivity(G)
            for j, jtem in enumerate(connectivity):
                if j==0:
                    a=[jtem]*len(connectivity[jtem])
                    d = pd.DataFrame(connectivity[jtem].items())
                    d = pd.concat([pd.DataFrame(a),d], axis=1)
                    c = d.copy()
                a=[jtem]*len(connectivity[jtem])
                d = pd.DataFrame(connectivity[jtem].items())
                d = pd.concat([pd.DataFrame(a),d], axis=1)
                c = c.append(d)
            c['arr_dep'] = c[c.columns[[0]]].apply(lambda x: '-'.join(x),axis=1)
            connectivity_dep_arr = dict(zip(c['arr_dep'],c[1]))

            df['connectivity'] = df['arr_dep'].map(connectivity_dep_arr)
            return df

 def min_connectivity(self, graph):
     apnc = nx.all_pairs_node_connectivity(graph)
     # start with graph diameter; minimum won't be larger than this
     mc = nx.diameter(graph)
     for targets in apnc.itervalues():
         mc = min(min(targets.itervalues()), mc)
     return mc

 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_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 test_all_pairs_connectivity_directed(self):
     G = nx.DiGraph()
     nodes = [0, 1, 2, 3]
     G.add_path(nodes)
     A = dict.fromkeys(G, dict())
     for u, v in itertools.permutations(nodes, 2):
         A[u][v] = nx.node_connectivity(G, u, v)
     C = nx.all_pairs_node_connectivity(G)
     assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
                  sorted((k, sorted(v)) for k, v in C.items()))

 def test_all_pairs_connectivity(self):
     G = nx.Graph()
     nodes = [0, 1, 2, 3]
     nx.add_path(G, nodes)
     A = {n: {} for n in G}
     for u, v in itertools.combinations(nodes,2):
         A[u][v] = A[v][u] = nx.node_connectivity(G, u, v)
     C = nx.all_pairs_node_connectivity(G)
     assert_equal(sorted((k, sorted(v)) for k, v in A.items()),
                  sorted((k, sorted(v)) for k, v in C.items()))

def cal_para_order(para_list):
    """
    To record the parameter variable's all fixed order.
    :param para_list: the url's kinds of url's.
    :return: list -> all fixed parameter order.
    """
    result_order = list()

    order_collection = set()
    for order_seg in para_list:
        length = len(order_seg)
        for i in range(length - 1):
            order_collection.add((order_seg[i], order_seg[i + 1]))
    print 'G2:', sorted(list(order_collection))
    g = nx.DiGraph()
    g.add_edges_from(order_collection)
    connectivity_dict = dict([])
    for source_node, connect_dict in nx.all_pairs_node_connectivity(g).items():
        connectivity_dict[source_node] = []
        for target_node, hop in connect_dict.items():
            if hop > 0:
                connectivity_dict[source_node].append(target_node)
    print 'Connectivity_Original:', nx.all_pairs_node_connectivity(g)
    print 'Connectivity_dict:', connectivity_dict
    node_list = g.nodes()
    node_length = len(node_list)
    for i in range(node_length):
        for j in range(i + 1, node_length):
            node_1 = node_list[i]
            node_2 = node_list[j]
            connect_1_2 = node_2 in connectivity_dict[node_1]
            connect_2_1 = node_1 in connectivity_dict[node_2]
            if connect_1_2 and not connect_2_1:
                result_order.append((node_1, node_2))
            elif connect_2_1 and not connect_1_2:
                result_order.append((node_2, node_1))
            else:
                continue

    return result_order

    def __cal_variable_order_rule(variable_order_set):
        """
        To record the parameter variable's all fixed order.

        :param variable_order_set: set((v1, v2, v3), (v3, v4), ...)
        :return: set((v1, v2), (v1, v3), ...)
        """
        result_order = set()

        order_collection = set()
        for order_seg in variable_order_set:
            for i in range(len(order_seg) - 1):
                order_collection.add((order_seg[i], order_seg[i + 1]))

        g = nx.DiGraph()
        g.add_edges_from(order_collection)
        connectivity_dict = dict([])
        for source_node, connect_dict in nx.all_pairs_node_connectivity(g).items():
            connectivity_dict[source_node] = set()
            for target_node, hop in connect_dict.items():
                if hop > 0:
                    connectivity_dict[source_node].add(target_node)

        node_list = g.nodes()
        node_count = len(node_list)
        for i in range(node_count):
            for j in range(i + 1, node_count):
                node_1 = node_list[i]
                node_2 = node_list[j]
                # if node_1 connect to node_2
                connect_1_2 = node_2 in connectivity_dict[node_1]
                # if node_2 connect to node_1
                connect_2_1 = node_1 in connectivity_dict[node_2]
                if connect_1_2 and not connect_2_1:
                    result_order.add((node_1, node_2))
                elif connect_2_1 and not connect_1_2:
                    result_order.add((node_2, node_1))
                else:
                    continue

        return result_order

 def test_all_pairs_connectivity_icosahedral(self):
     G = nx.icosahedral_graph()
     C = nx.all_pairs_node_connectivity(G)
     assert_true(all(5 == C[u][v] for u, v in itertools.combinations(G, 2)))

 def test_complete(self):
     for G in [self.K10, self.K5, self.K20]:
         K = nx.all_pairs_node_connectivity(G)
         for source in K:
             for target, k in K[source].items():
                 assert_true(k == len(G)-1)