def main():
    
    ### Undirected graph ###
    
    # Initialize model using the Petersen graph
    model=gmm.gmm(nx.petersen_graph())
    old_graph=model.get_base()
    model.set_termination(node_ceiling)
    model.set_rule(rand_add)
    
    # Run simualation with tau=4 and Poisson density for motifs
    gmm.algorithms.simulate(model,4)   

    # View results
    new_graph=model.get_base()
    print(nx.info(new_graph))
    
    # Draw graphs
    old_pos=nx.spring_layout(old_graph)
    new_pos=nx.spring_layout(new_graph,iterations=2000)
    fig1=plt.figure(figsize=(15,7))
    fig1.add_subplot(121)
    #fig1.text(0.1,0.9,"Base Graph")
    nx.draw(old_graph,pos=old_pos,node_size=25,with_labels=False)
    fig1.add_subplot(122)
    #fig1.text(0.1,0.45,"Simulation Results")
    nx.draw(new_graph,pos=new_pos,node_size=20,with_labels=False)
    fig1.savefig("undirected_model.png")
    
    ### Directed graph ###
    
    # Initialize model using random directed Barabasi-Albert model
    directed_base=nx.barabasi_albert_graph(25,2).to_directed()
    directed_model=gmm.gmm(directed_base)
    directed_model.set_termination(node_ceiling)
    directed_model.set_rule(rand_add)
    
    # Run simualation with tau=4 and Poisson density for motifs
    gmm.algorithms.simulate(directed_model,4)
    
    # View results
    new_directed=directed_model.get_base()
    print(nx.info(new_directed))
    
    # Draw directed graphs
    old_dir_pos=new_pos=nx.spring_layout(directed_base)
    new_dir_pos=new_pos=nx.spring_layout(new_directed,iterations=2000)
    fig2=plt.figure(figsize=(7,10))
    fig2.add_subplot(211)
    fig2.text(0.1,0.9,"Base Directed Graph")
    nx.draw(directed_base,pos=old_dir_pos,node_size=25,with_labels=False)
    fig2.add_subplot(212)
    fig2.text(0.1,0.45, "Simualtion Results")
    nx.draw(new_directed,pos=new_dir_pos,node_size=20,with_labels=False)
    fig2.savefig("directed_model.png")
    
    # Export files
    nx.write_graphml(model.get_base(), "base_model.graphml")
    nx.write_graphml(directed_model.get_base(), "directed_model.graphml")
    nx.write_graphml(nx.petersen_graph(), "petersen_graph.graphml")

def torrents_and_ferraro_graph():
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
                                           label_attribute='labels')
    rlabels = nx.get_node_attributes(G, 'labels')
    labels = {v: k for k, v in rlabels.items()}

    for nodes in [(labels[(0, 4)], labels[(1, 4)]),
                  (labels[(3, 4)], labels[(4, 4)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing a node
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        # Commenting this makes the graph not biconnected !!
        # This stupid mistake make one reviewer very angry :P
        G.add_edge(new_node + 16, new_node + 8)

    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
                  (labels[(3, 0)], labels[(4, 0)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing two nodes
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        nbrs2 = G[new_node + 9]
        G.remove_node(new_node + 9)
        for nbr in nbrs2:
            G.add_edge(new_node + 18, nbr)
    return G

def test_petersen():
    G = nx.petersen_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 test160_petersengraph(self):
     """ Petersen graph. """
     g = nx.petersen_graph()
     mate1 = mv.max_cardinality_matching( g )
     mate2 = nx.max_weight_matching( g, True )
     td.showGraph(g, mate1, "test160_petersengraph")
     self.assertEqual( len(mate1), len(mate2) )

def graph_example_1():
    G = nx.convert_node_labels_to_integers(nx.grid_graph([5, 5]),
                                           label_attribute='labels')
    rlabels = nx.get_node_attributes(G, 'labels')
    labels = {v: k for k, v in rlabels.items()}

    for nodes in [(labels[(0, 0)], labels[(1, 0)]),
                  (labels[(0, 4)], labels[(1, 4)]),
                  (labels[(3, 0)], labels[(4, 0)]),
                  (labels[(3, 4)], labels[(4, 4)])]:
        new_node = G.order() + 1
        # Petersen graph is triconnected
        P = nx.petersen_graph()
        G = nx.disjoint_union(G, P)
        # Add two edges between the grid and P
        G.add_edge(new_node + 1, nodes[0])
        G.add_edge(new_node, nodes[1])
        # K5 is 4-connected
        K = nx.complete_graph(5)
        G = nx.disjoint_union(G, K)
        # Add three edges between P and K5
        G.add_edge(new_node + 2, new_node + 11)
        G.add_edge(new_node + 3, new_node + 12)
        G.add_edge(new_node + 4, new_node + 13)
        # Add another K5 sharing a node
        G = nx.disjoint_union(G, K)
        nbrs = G[new_node + 10]
        G.remove_node(new_node + 10)
        for nbr in nbrs:
            G.add_edge(new_node + 17, nbr)
        G.add_edge(new_node + 16, new_node + 5)

    G.name = 'Example graph for connectivity'
    return G

def test_petersen_disjoint_paths():
    G = nx.petersen_graph()
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge disjoint paths
        edge_dpaths = list(nx.edge_disjoint_paths(G, 0, 6, **kwargs))
        assert_true(are_edge_disjoint_paths(G, edge_dpaths), msg=msg.format(flow_func.__name__))
        assert_equal(3, len(edge_dpaths), msg=msg.format(flow_func.__name__))
        # node disjoint paths
        node_dpaths = list(nx.node_disjoint_paths(G, 0, 6, **kwargs))
        assert_true(are_node_disjoint_paths(G, node_dpaths), msg=msg.format(flow_func.__name__))
        assert_equal(3, len(node_dpaths), msg=msg.format(flow_func.__name__))

 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 __test():
    return tutte_poly(nx.petersen_graph()) == [[0, 36, 84, 75, 35, 9, 1],
                                               [36, 168, 171, 65, 10],
                                               [120, 240, 105, 15],
                                               [180, 170, 30],
                                               [170, 70],
                                               [114, 12],
                                               [56],
                                               [21],
                                               [6],
                                               [1]
                                               ]

 def test_dimension(self):
     """ Check first embedding coordinates not changed by adding more
     dimensions"""
     G = nx.DiGraph()
     for edge in nx.petersen_graph().edges():
         if edge[0] < edge[1]:
             G.add_edge(edge[0], edge[1])
     X_2, nodes = dag.minkowski_embed(G, 2)
     X_5, nodes = dag.minkowski_embed(G, 5)
     for i in range(10):
         for j in range(2):
             assert_equal(X_2[i,j], X_5[i,j])

def test_tensor_product_classic_result():
    K2 = nx.complete_graph(2)
    G = nx.petersen_graph()
    G = tensor_product(G,K2)
    assert_true(nx.is_isomorphic(G,nx.desargues_graph()))

    G = nx.cycle_graph(5)
    G = tensor_product(G,K2)
    assert_true(nx.is_isomorphic(G,nx.cycle_graph(10)))

    G = nx.tetrahedral_graph()
    G = tensor_product(G,K2)
    assert_true(nx.is_isomorphic(G,nx.cubical_graph()))

    def test_is_eulerian(self):
        assert_true(is_eulerian(nx.complete_graph(5)))
        assert_true(is_eulerian(nx.complete_graph(7)))
        assert_true(is_eulerian(nx.hypercube_graph(4)))
        assert_true(is_eulerian(nx.hypercube_graph(6)))

        assert_false(is_eulerian(nx.complete_graph(4)))
        assert_false(is_eulerian(nx.complete_graph(6)))
        assert_false(is_eulerian(nx.hypercube_graph(3)))
        assert_false(is_eulerian(nx.hypercube_graph(5)))

        assert_false(is_eulerian(nx.petersen_graph()))
        assert_false(is_eulerian(nx.path_graph(4)))

def test_petersen_cutset():
    G = nx.petersen_graph()
    # edge cuts
    edge_cut = nx.minimum_edge_cut(G)
    assert_equal(3, len(edge_cut))
    H = G.copy()
    H.remove_edges_from(edge_cut)
    assert_false(nx.is_connected(H))
    # node cuts
    node_cut = nx.minimum_node_cut(G)
    assert_equal(3,len(node_cut))
    H = G.copy()
    H.remove_nodes_from(node_cut)
    assert_false(nx.is_connected(H))

    def test_petersen(self):
        """Check boundaries in the petersen graph

        cheeger(G,k)=min(|bdy(S)|/|S| for |S|=k, 0<k<=|V(G)|/2)
        """
        from itertools import combinations
        P=nx.petersen_graph()
        def cheeger(G,k):
            return min( float(len(nx.node_boundary(G,nn)))/k
                        for nn in combinations(G,k) )

        assert_almost_equals(cheeger(P,1),3.00,places=2)
        assert_almost_equals(cheeger(P,2),2.00,places=2)
        assert_almost_equals(cheeger(P,3),1.67,places=2)
        assert_almost_equals(cheeger(P,4),1.00,places=2)
        assert_almost_equals(cheeger(P,5),0.80,places=2)

def test_petersen_cutset():
    G = nx.petersen_graph()
    for flow_func in flow_funcs:
        kwargs = dict(flow_func=flow_func)
        # edge cuts
        edge_cut = nx.minimum_edge_cut(G, **kwargs)
        assert_equal(3, len(edge_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_edges_from(edge_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))
        # node cuts
        node_cut = nx.minimum_node_cut(G, **kwargs)
        assert_equal(3, len(node_cut), msg=msg.format(flow_func.__name__))
        H = G.copy()
        H.remove_nodes_from(node_cut)
        assert_false(nx.is_connected(H), msg=msg.format(flow_func.__name__))

    def test_petersen(self):
        """Check boundaries in the petersen nxgraph

        cheeger(G,k)=min(|bdy(S)|/|S| for |S|=k, 0<k<=|V(G)|/2)
        """
        from random import sample
        P=nx.petersen_graph()
        def cheeger(G,k):
            return min([float(len(nx.node_boundary(G,sample(G.nodes(),k))))/k 
                        for n in range(100)])

        assert_almost_equals(cheeger(P,1),3.00,places=2)
        assert_almost_equals(cheeger(P,2),2.00,places=2)
        assert_almost_equals(cheeger(P,3),1.67,places=2)
        assert_almost_equals(cheeger(P,4),1.00,places=2)
        assert_almost_equals(cheeger(P,5),0.80,places=2)

def petersenGraph():
    print "petersenGraph()"
    # Sigui G = (Vg,Eg) el graf original
    # Vèrtex inicial d'exploració: v
    # Sigui H = (Vh,Eh) el graf resultant d'aplicar DFS
    # El graf H està buit  
    G=nx.petersen_graph()
    print "number of edges: ",G.number_of_edges()
    print "number of nodes: ",G.number_of_nodes() 
    print "edges: ",G.edges()
    print "nodes: ",G.nodes()
    print "neighbors: ",G.neighbors()      
    H = nx.dfs_tree(G,0)
    Eh = {}
    Vh ={}
    visitats = {}
    explora(v)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors()   
    H = nx.dfs_tree(G,5)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors() 
    G.add_edge(1000,1001)
    print "number of edges: ",G.number_of_edges()
    print "number of nodes: ",G.number_of_nodes() 
    print "edges: ",G.edges()
    print "nodes: ",G.nodes()
    print "neighbors: ",G.neighbors()    
    H = nx.dfs_tree(G,0)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors() 
    H = nx.dfs_tree(G,1000)
    print "number of edges: ",H.number_of_edges()
    print "number of nodes: ",H.number_of_nodes() 
    print "edges: ",H.edges()
    print "nodes: ",H.nodes()
    print "neighbors: ",H.neighbors()    

    def test_num_orbits(self):

        # build a simple example graph
        g = nx.petersen_graph()
        sym = stats.BalancedTreeAutomorphismStatistics(self.sc)
        dg = sym._format_graph_as_nauty(g)
        nauty_format = sym._get_raw_nauty_output(dg)
        log.info("%s", nauty_format)

        o = re.compile('(\d+) orbit;')
        m = o.search(nauty_format)
        if m:
            num_orbits = m.group(1)
            #log.debug("num_orbits match: %s", num_orbits)

            log.info("orbits in petersen graph: %s", num_orbits)
            self.assertEqual(1, int(num_orbits))
        else:
            self.assertTrue(False)

 def test_similar_output_to_naive_peterson(self):
     G = nx.petersen_graph()
     G2 = graphpca.reduce_graph_efficiently(G, 2)
     G2n = graphpca.reduce_graph_naively(G, 2)
     self.assertTrue(np.allclose(G2, G2n, rtol=1e-04, atol=1e-06),
                     'Regular result:\n{}\nNaive result:\n{}\n'.format(G2, G2n))

def petersen_graph():
    return EquibelGraph(nx.petersen_graph())

# グラフジェネレーターとグラフオペレータ

# 典型的なグラフ操作
# subgraph(G, nbunch)      - induce subgraph of G on nodes in nbunch
# union(G1,G2)             - graph union
# disjoint_union(G1,G2)    - graph union assuming all nodes are different
# cartesian_product(G1,G2) - return Cartesian product graph
# compose(G1,G2)           - combine graphs identifying nodes common to both
# complement(G)            - graph complement
# create_empty_copy(G)     - return an empty copy of the same graph class
# convert_to_undirected(G) - return an undirected representation of G
# convert_to_directed(G)   - return a directed representation of G


petersen=nx.petersen_graph() # ピーターセングラフ 10個の頂点と15個の辺からなる無向グラフ。グラフ理論の様々な問題の例、あるいは反例としてよく使われる。
tutte=nx.tutte_graph() # Tutte グラフ
maze=nx.sedgewick_maze_graph() 
tet=nx.tetrahedral_graph() # テトラへドラル

K_5=nx.complete_graph(5) # 完全グラフ
K_3_5=nx.complete_bipartite_graph(3,5) #完全二部グラフ 2部グラフのうち特に第1の集合に属するそれぞれの頂点から第2の集合に属する全ての頂点に辺が伸びているもの
barbell=nx.barbell_graph(10,10) # 
lollipop=nx.lollipop_graph(10,20) # 

er=nx.erdos_renyi_graph(100,0.15)
ws=nx.watts_strogatz_graph(30,3,0.1)
ba=nx.barabasi_albert_graph(100,5)
red=nx.random_lobster(100,0.9,0.9)

nx.write_gml(red,"path.to.file")