| # -*- coding: utf-8 -*- |
| """ |
| Various small and named graphs, together with some compact generators. |
| |
| """ |
| __author__ ="""Aric Hagberg (hagberg@lanl.gov)\nPieter Swart (swart@lanl.gov)""" |
| # Copyright (C) 2004-2008 by |
| # Aric Hagberg <hagberg@lanl.gov> |
| # Dan Schult <dschult@colgate.edu> |
| # Pieter Swart <swart@lanl.gov> |
| # All rights reserved. |
| # BSD license. |
| |
| __all__ = ['make_small_graph', |
| 'LCF_graph', |
| 'bull_graph', |
| 'chvatal_graph', |
| 'cubical_graph', |
| 'desargues_graph', |
| 'diamond_graph', |
| 'dodecahedral_graph', |
| 'frucht_graph', |
| 'heawood_graph', |
| 'house_graph', |
| 'house_x_graph', |
| 'icosahedral_graph', |
| 'krackhardt_kite_graph', |
| 'moebius_kantor_graph', |
| 'octahedral_graph', |
| 'pappus_graph', |
| 'petersen_graph', |
| 'sedgewick_maze_graph', |
| 'tetrahedral_graph', |
| 'truncated_cube_graph', |
| 'truncated_tetrahedron_graph', |
| 'tutte_graph'] |
| |
| import networkx as nx |
| from networkx.generators.classic import empty_graph, cycle_graph, path_graph, complete_graph |
| from networkx.exception import NetworkXError |
| |
| #------------------------------------------------------------------------------ |
| # Tools for creating small graphs |
| #------------------------------------------------------------------------------ |
| def make_small_undirected_graph(graph_description, create_using=None): |
| """ |
| Return a small undirected graph described by graph_description. |
| |
| See make_small_graph. |
| """ |
| if create_using is not None and create_using.is_directed(): |
| raise NetworkXError("Directed Graph not supported") |
| return make_small_graph(graph_description, create_using) |
| |
| def make_small_graph(graph_description, create_using=None): |
| """ |
| Return the small graph described by graph_description. |
| |
| graph_description is a list of the form [ltype,name,n,xlist] |
| |
| Here ltype is one of "adjacencylist" or "edgelist", |
| name is the name of the graph and n the number of nodes. |
| This constructs a graph of n nodes with integer labels 0,..,n-1. |
| |
| If ltype="adjacencylist" then xlist is an adjacency list |
| with exactly n entries, in with the j'th entry (which can be empty) |
| specifies the nodes connected to vertex j. |
| e.g. the "square" graph C_4 can be obtained by |
| |
| >>> G=nx.make_small_graph(["adjacencylist","C_4",4,[[2,4],[1,3],[2,4],[1,3]]]) |
| |
| or, since we do not need to add edges twice, |
| |
| >>> G=nx.make_small_graph(["adjacencylist","C_4",4,[[2,4],[3],[4],[]]]) |
| |
| If ltype="edgelist" then xlist is an edge list |
| written as [[v1,w2],[v2,w2],...,[vk,wk]], |
| where vj and wj integers in the range 1,..,n |
| e.g. the "square" graph C_4 can be obtained by |
| |
| >>> G=nx.make_small_graph(["edgelist","C_4",4,[[1,2],[3,4],[2,3],[4,1]]]) |
| |
| Use the create_using argument to choose the graph class/type. |
| """ |
| ltype=graph_description[0] |
| name=graph_description[1] |
| n=graph_description[2] |
| |
| G=empty_graph(n, create_using) |
| nodes=G.nodes() |
| |
| if ltype=="adjacencylist": |
| adjlist=graph_description[3] |
| if len(adjlist) != n: |
| raise NetworkXError("invalid graph_description") |
| G.add_edges_from([(u-1,v) for v in nodes for u in adjlist[v]]) |
| elif ltype=="edgelist": |
| edgelist=graph_description[3] |
| for e in edgelist: |
| v1=e[0]-1 |
| v2=e[1]-1 |
| if v1<0 or v1>n-1 or v2<0 or v2>n-1: |
| raise NetworkXError("invalid graph_description") |
| else: |
| G.add_edge(v1,v2) |
| G.name=name |
| return G |
| |
| |
| def LCF_graph(n,shift_list,repeats,create_using=None): |
| """ |
| Return the cubic graph specified in LCF notation. |
| |
| LCF notation (LCF=Lederberg-Coxeter-Fruchte) is a compressed |
| notation used in the generation of various cubic Hamiltonian |
| graphs of high symmetry. See, for example, dodecahedral_graph, |
| desargues_graph, heawood_graph and pappus_graph below. |
| |
| n (number of nodes) |
| The starting graph is the n-cycle with nodes 0,...,n-1. |
| (The null graph is returned if n < 0.) |
| |
| shift_list = [s1,s2,..,sk], a list of integer shifts mod n, |
| |
| repeats |
| integer specifying the number of times that shifts in shift_list |
| are successively applied to each v_current in the n-cycle |
| to generate an edge between v_current and v_current+shift mod n. |
| |
| For v1 cycling through the n-cycle a total of k*repeats |
| with shift cycling through shiftlist repeats times connect |
| v1 with v1+shift mod n |
| |
| The utility graph K_{3,3} |
| |
| >>> G=nx.LCF_graph(6,[3,-3],3) |
| |
| The Heawood graph |
| |
| >>> G=nx.LCF_graph(14,[5,-5],7) |
| |
| See http://mathworld.wolfram.com/LCFNotation.html for a description |
| and references. |
| |
| """ |
| if create_using is not None and create_using.is_directed(): |
| raise NetworkXError("Directed Graph not supported") |
| |
| if n <= 0: |
| return empty_graph(0, create_using) |
| |
| # start with the n-cycle |
| G=cycle_graph(n, create_using) |
| G.name="LCF_graph" |
| nodes=G.nodes() |
| |
| n_extra_edges=repeats*len(shift_list) |
| # edges are added n_extra_edges times |
| # (not all of these need be new) |
| if n_extra_edges < 1: |
| return G |
| |
| for i in range(n_extra_edges): |
| shift=shift_list[i%len(shift_list)] #cycle through shift_list |
| v1=nodes[i%n] # cycle repeatedly through nodes |
| v2=nodes[(i + shift)%n] |
| G.add_edge(v1, v2) |
| return G |
| |
| |
| #------------------------------------------------------------------------------- |
| # Various small and named graphs |
| #------------------------------------------------------------------------------- |
| |
| def bull_graph(create_using=None): |
| """Return the Bull graph. """ |
| description=[ |
| "adjacencylist", |
| "Bull Graph", |
| 5, |
| [[2,3],[1,3,4],[1,2,5],[2],[3]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def chvatal_graph(create_using=None): |
| """Return the Chvátal graph.""" |
| description=[ |
| "adjacencylist", |
| "Chvatal Graph", |
| 12, |
| [[2,5,7,10],[3,6,8],[4,7,9],[5,8,10], |
| [6,9],[11,12],[11,12],[9,12], |
| [11],[11,12],[],[]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def cubical_graph(create_using=None): |
| """Return the 3-regular Platonic Cubical graph.""" |
| description=[ |
| "adjacencylist", |
| "Platonic Cubical Graph", |
| 8, |
| [[2,4,5],[1,3,8],[2,4,7],[1,3,6], |
| [1,6,8],[4,5,7],[3,6,8],[2,5,7]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def desargues_graph(create_using=None): |
| """ Return the Desargues graph.""" |
| G=LCF_graph(20, [5,-5,9,-9], 5, create_using) |
| G.name="Desargues Graph" |
| return G |
| |
| def diamond_graph(create_using=None): |
| """Return the Diamond graph. """ |
| description=[ |
| "adjacencylist", |
| "Diamond Graph", |
| 4, |
| [[2,3],[1,3,4],[1,2,4],[2,3]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def dodecahedral_graph(create_using=None): |
| """ Return the Platonic Dodecahedral graph. """ |
| G=LCF_graph(20, [10,7,4,-4,-7,10,-4,7,-7,4], 2, create_using) |
| G.name="Dodecahedral Graph" |
| return G |
| |
| def frucht_graph(create_using=None): |
| """Return the Frucht Graph. |
| |
| The Frucht Graph is the smallest cubical graph whose |
| automorphism group consists only of the identity element. |
| |
| """ |
| G=cycle_graph(7, create_using) |
| G.add_edges_from([[0,7],[1,7],[2,8],[3,9],[4,9],[5,10],[6,10], |
| [7,11],[8,11],[8,9],[10,11]]) |
| |
| G.name="Frucht Graph" |
| return G |
| |
| def heawood_graph(create_using=None): |
| """ Return the Heawood graph, a (3,6) cage. """ |
| G=LCF_graph(14, [5,-5], 7, create_using) |
| G.name="Heawood Graph" |
| return G |
| |
| def house_graph(create_using=None): |
| """Return the House graph (square with triangle on top).""" |
| description=[ |
| "adjacencylist", |
| "House Graph", |
| 5, |
| [[2,3],[1,4],[1,4,5],[2,3,5],[3,4]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def house_x_graph(create_using=None): |
| """Return the House graph with a cross inside the house square.""" |
| description=[ |
| "adjacencylist", |
| "House-with-X-inside Graph", |
| 5, |
| [[2,3,4],[1,3,4],[1,2,4,5],[1,2,3,5],[3,4]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def icosahedral_graph(create_using=None): |
| """Return the Platonic Icosahedral graph.""" |
| description=[ |
| "adjacencylist", |
| "Platonic Icosahedral Graph", |
| 12, |
| [[2,6,8,9,12],[3,6,7,9],[4,7,9,10],[5,7,10,11], |
| [6,7,11,12],[7,12],[],[9,10,11,12], |
| [10],[11],[12],[]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| |
| def krackhardt_kite_graph(create_using=None): |
| """ |
| Return the Krackhardt Kite Social Network. |
| |
| A 10 actor social network introduced by David Krackhardt |
| to illustrate: degree, betweenness, centrality, closeness, etc. |
| The traditional labeling is: |
| Andre=1, Beverley=2, Carol=3, Diane=4, |
| Ed=5, Fernando=6, Garth=7, Heather=8, Ike=9, Jane=10. |
| |
| """ |
| description=[ |
| "adjacencylist", |
| "Krackhardt Kite Social Network", |
| 10, |
| [[2,3,4,6],[1,4,5,7],[1,4,6],[1,2,3,5,6,7],[2,4,7], |
| [1,3,4,7,8],[2,4,5,6,8],[6,7,9],[8,10],[9]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def moebius_kantor_graph(create_using=None): |
| """Return the Moebius-Kantor graph.""" |
| G=LCF_graph(16, [5,-5], 8, create_using) |
| G.name="Moebius-Kantor Graph" |
| return G |
| |
| def octahedral_graph(create_using=None): |
| """Return the Platonic Octahedral graph.""" |
| description=[ |
| "adjacencylist", |
| "Platonic Octahedral Graph", |
| 6, |
| [[2,3,4,5],[3,4,6],[5,6],[5,6],[6],[]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def pappus_graph(): |
| """ Return the Pappus graph.""" |
| G=LCF_graph(18,[5,7,-7,7,-7,-5],3) |
| G.name="Pappus Graph" |
| return G |
| |
| def petersen_graph(create_using=None): |
| """Return the Petersen graph.""" |
| description=[ |
| "adjacencylist", |
| "Petersen Graph", |
| 10, |
| [[2,5,6],[1,3,7],[2,4,8],[3,5,9],[4,1,10],[1,8,9],[2,9,10], |
| [3,6,10],[4,6,7],[5,7,8]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| |
| def sedgewick_maze_graph(create_using=None): |
| """ |
| Return a small maze with a cycle. |
| |
| This is the maze used in Sedgewick,3rd Edition, Part 5, Graph |
| Algorithms, Chapter 18, e.g. Figure 18.2 and following. |
| Nodes are numbered 0,..,7 |
| """ |
| G=empty_graph(0, create_using) |
| G.add_nodes_from(range(8)) |
| G.add_edges_from([[0,2],[0,7],[0,5]]) |
| G.add_edges_from([[1,7],[2,6]]) |
| G.add_edges_from([[3,4],[3,5]]) |
| G.add_edges_from([[4,5],[4,7],[4,6]]) |
| G.name="Sedgewick Maze" |
| return G |
| |
| def tetrahedral_graph(create_using=None): |
| """ Return the 3-regular Platonic Tetrahedral graph.""" |
| G=complete_graph(4, create_using) |
| G.name="Platonic Tetrahedral graph" |
| return G |
| |
| def truncated_cube_graph(create_using=None): |
| """Return the skeleton of the truncated cube.""" |
| description=[ |
| "adjacencylist", |
| "Truncated Cube Graph", |
| 24, |
| [[2,3,5],[12,15],[4,5],[7,9], |
| [6],[17,19],[8,9],[11,13], |
| [10],[18,21],[12,13],[15], |
| [14],[22,23],[16],[20,24], |
| [18,19],[21],[20],[24], |
| [22],[23],[24],[]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
| def truncated_tetrahedron_graph(create_using=None): |
| """Return the skeleton of the truncated Platonic tetrahedron.""" |
| G=path_graph(12, create_using) |
| # G.add_edges_from([(1,3),(1,10),(2,7),(4,12),(5,12),(6,8),(9,11)]) |
| G.add_edges_from([(0,2),(0,9),(1,6),(3,11),(4,11),(5,7),(8,10)]) |
| G.name="Truncated Tetrahedron Graph" |
| return G |
| |
| def tutte_graph(create_using=None): |
| """Return the Tutte graph.""" |
| description=[ |
| "adjacencylist", |
| "Tutte's Graph", |
| 46, |
| [[2,3,4],[5,27],[11,12],[19,20],[6,34], |
| [7,30],[8,28],[9,15],[10,39],[11,38], |
| [40],[13,40],[14,36],[15,16],[35], |
| [17,23],[18,45],[19,44],[46],[21,46], |
| [22,42],[23,24],[41],[25,28],[26,33], |
| [27,32],[34],[29],[30,33],[31], |
| [32,34],[33],[],[],[36,39], |
| [37],[38,40],[39],[],[], |
| [42,45],[43],[44,46],[45],[],[]] |
| ] |
| G=make_small_undirected_graph(description, create_using) |
| return G |
| |
