Changeset 5329:b6da7b25f5ad


Ignore:
Timestamp:
06/10/07 20:28:01 (6 years ago)
Author:
Robert L Miller <rlm@…>
Branch:
default
Message:

Random Graphs Galore!

File:
1 edited

Legend:

Unmodified
Added
Removed

  • sage/graphs/graph_generators.py

    r5328 r5329  
    7777            - CompleteBipartiteGraph 
    7878            - CubeGraph 
    79             - RandomGNP 
    80             - RandomGNPFast 
    8179            - BalancedTree 
    8280            - LCFGraph 
    8381        Pseudofractal Graphs: 
    8482            - DorogovtsevGoltsevMendesGraph 
     83        Random Graphs: 
     84            - RandomGNP 
     85            - RandomGNPFast 
     86            - RandomBarabasiAlbert 
     87            - RandomGNM 
     88            - RandomNewmanWattsStrogatz 
     89            - RandomHolmeKim 
     90            - RandomLobster 
     91            - RandomTreePowerlaw 
     92            - RandomRegular 
     93            - RandomShell 
    8594    \end{verbatim} 
    8695 
    … …  
    163172            - CompleteBipartiteGraph 
    164173            - CubeGraph 
    165             - RandomGNP 
    166             - RandomGNPFast 
    167174            - BalancedTree 
    168175            - LCFGraph 
    169176        Pseudofractal Graphs: 
    170177            - DorogovtsevGoltsevMendesGraph 
     178        Random Graphs: 
     179            - RandomGNP 
     180            - RandomGNPFast 
     181            - RandomBarabasiAlbert 
     182            - RandomGNM 
     183            - RandomNewmanWattsStrogatz 
     184            - RandomHolmeKim 
     185            - RandomLobster 
     186            - RandomTreePowerlaw 
     187            - RandomRegular 
     188            - RandomShell 
    171189    \end{verbatim} 
    172190    """ 
    … …  
    614632         
    615633        REFERENCES:   
    616             Kreps, V. (2002). "Social Network Analysis". [Online] Available: http://www.fsu.edu/~spap/water/network/intro.htm [2007, January 17] 
     634            [1] Kreps, V. (2002). "Social Network Analysis". [Online] 
     635                Available: http://www.fsu.edu/~spap/water/network/intro.htm 
     636                [2007, January 17] 
    617637         
    618638        This constructor depends on NetworkX numeric labeling. 
    … …  
    12161236     
    12171237    def ChvatalGraph(self): 
    1218         u""" 
    1219         Returns the Chv‡tal graph. 
    1220  
    1221         The Chv‡tal graph has 12 vertices. It is a 4-regular, 4-chromatic 
    1222         graph. It is one of the few known graphs to satisfy GrŸnbaum's 
     1238        """ 
     1239        Returns the Chvatal graph. 
     1240 
     1241        The Chvatal graph has 12 vertices. It is a 4-regular, 4-chromatic 
     1242        graph. It is one of the few known graphs to satisfy Grunbaum's 
    12231243        conjecture that for every m > 1, n > 2, there is an m-regular, 
    12241244        m-chromatic graph of girth at least n. 
    … …  
    12801300         
    12811301        REFERENCES:   
    1282             Weisstein, E. (1999). "Flower Snark -- from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/FlowerSnark.html [2007, February 17] 
     1302            [1] Weisstein, E. (1999). "Flower Snark -- from Wolfram MathWorld". 
     1303                [Online] Available: http://mathworld.wolfram.com/FlowerSnark.html 
     1304                [2007, February 17] 
    12831305         
    12841306        EXAMPLES: 
    … …  
    13231345             
    13241346        REFERENCES:   
    1325             Weisstein, E. (1999). "Frucht Graph -- from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/FruchtGraph.html [2007, February 17] 
     1347            [1] Weisstein, E. (1999). "Frucht Graph -- from Wolfram MathWorld". 
     1348                [Online] Available: http://mathworld.wolfram.com/FruchtGraph.html 
     1349                [2007, February 17] 
    13261350         
    13271351        EXAMPLES: 
    … …  
    13651389         
    13661390        REFERENCES:   
    1367             Weisstein, E. (1999). "Heawood Graph -- from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/HeawoodGraph.html [2007, February 17] 
     1391            [1] Weisstein, E. (1999). "Heawood Graph -- from Wolfram MathWorld". 
     1392                [Online] Available: http://mathworld.wolfram.com/HeawoodGraph.html 
     1393                [2007, February 17] 
    13681394         
    13691395        EXAMPLES: 
    … …  
    14041430         
    14051431        REFERENCES:   
    1406             Weisstein, E. (1999). "Moebius-Kantor Graph -- from Wolfram MathWorld". [Online] Available: http://mathworld.wolfram.com/Moebius-KantorGraph.html [2007, February 17] 
     1432            [1] Weisstein, E. (1999). "Moebius-Kantor Graph -- from Wolfram 
     1433            MathWorld". [Online] 
     1434            Available: http://mathworld.wolfram.com/Moebius-KantorGraph.html 
     1435            [2007, February 17] 
    14071436         
    14081437        EXAMPLES: 
    … …  
    17901819        return graph.Graph(data=d, pos=pos, name="%d-Cube"%n) 
    17911820         
    1792     def RandomGNP(self, n, p, seed=None): 
    1793         r""" 
    1794         Returns a Random graph on $n$ nodes.  Each edge is inserted 
    1795         independently with probability $p$. 
    1796  
    1797         IMPLEMENTATION: 
    1798         This function calls the NetworkX function \code{gnp_random_graph}. 
    1799          
    1800         REFERENCES: 
    1801             P. Erdos and A. Renyi, On Random Graphs, Publ. Math. 6, 290 (1959). 
    1802             E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959). 
    1803          
    1804         PLOTTING: 
    1805         When plotting, this graph will use the default spring-layout 
    1806         algorithm, unless a position dictionary is specified. 
    1807                  
    1808         EXAMPLES: 
    1809         We plot a random graph on 12 nodes with probability $p = .71$: 
    1810             sage: gnp = graphs.RandomGNP(12,.71) 
    1811             sage.: gnp.show() 
    1812  
    1813         We view many random graphs using a graphics array: 
    1814             sage: g = [] 
    1815             sage: j = [] 
    1816             sage: for i in range(9): 
    1817             ...    k = graphs.RandomGNP(i+3,.43) 
    1818             ...    g.append(k) 
    1819             ... 
    1820             sage: for i in range(3): 
    1821             ...    n = [] 
    1822             ...    for m in range(3): 
    1823             ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False)) 
    1824             ...    j.append(n) 
    1825             ... 
    1826             sage: G = sage.plot.plot.GraphicsArray(j) 
    1827             sage: G.save('sage.png') 
    1828  
    1829         TIMINGS: 
    1830         The following timings compare the speed of RandomGNP and 
    1831         RandomGNPFast for sparse and dense graphs: 
    1832          
    1833             time regular_sparse = graphs.RandomGNP(1559,.22) 
    1834             CPU time: 31.79 s,  Wall time: 38.78 s 
    1835             time fast_sparse =  graphs.RandomGNPFast(1559,.22) 
    1836             CPU time: 21.72 s,  Wall time: 26.44 s 
    1837             time regular_dense = graphs.RandomGNP(1559,.88) 
    1838             CPU time: 38.75 s,  Wall time: 47.65 s 
    1839             time fast_dense = graphs.RandomGNP(1559,.88) 
    1840             CPU time: 39.15 s,  Wall time: 48.22 s 
    1841         """ 
    1842         import networkx 
    1843         G = networkx.gnp_random_graph(n, p, seed) 
    1844         return graph.Graph(G) 
    1845  
    1846     def RandomGNPFast(self, n, p, seed=None): 
    1847         """ 
    1848         Returns a Random graph on $n$ nodes, with each edge inserted 
    1849         independently with probability $p$. 
    1850  
    1851         This function calls the NetworkX function \code{fast_gnp_random_graph}. 
    1852          
    1853         PLOTTING: 
    1854         When plotting, this graph will use the default spring-layout 
    1855         algorithm, unless a position dictionary is specified. 
    1856          
    1857         EXAMPLES: 
    1858         Plot a random graph on 12 nodes with p = .71 
    1859             sage: fast = graphs.RandomGNPFast(12,.71) 
    1860             sage.: fast.show() 
    1861  
    1862         View many random graphs using a SAGE Graphics Array 
    1863             sage: g = [] 
    1864             sage: j = [] 
    1865             sage: for i in range(9): 
    1866             ...    k = graphs.RandomGNPFast(i+3,.43) 
    1867             ...    g.append(k) 
    1868             ... 
    1869             sage.: for i in range(3): 
    1870             ...    n = [] 
    1871             ...    for m in range(3): 
    1872             ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False)) 
    1873             ...    j.append(n) 
    1874             ... 
    1875             sage.: G = sage.plot.plot.GraphicsArray(j) 
    1876             sage.: G.show() 
    1877  
    1878         TIMINGS: See the documentation for RandomGNP. 
    1879         """ 
    1880         import networkx 
    1881         G = networkx.fast_gnp_random_graph(n, p, seed) 
    1882         return graph.Graph(G) 
    1883  
    18841821    def BalancedTree(self, r, h): 
    18851822        r""" 
    … …  
    19341871        The largest cubic nonplanar graph of diameter three: 
    19351872            sage: G = graphs.LCFGraph(20, [-10,-7,-5,4,7,-10,-7,-4,5,7,-10,-7,6,-5,7,-10,-7,5,-6,7], 1) 
    1936             sage: G.degree()[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] 
     1873            sage: G.degree() 
     1874            [3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3] 
    19371875            sage: G.diameter() 
    19381876            3 
    … …  
    19461884            [1] Frucht, R. "A Canonical Representation of Trivalent 
    19471885                Hamiltonian Graphs." J. Graph Th. 1, 45-60, 1976. 
    1948             [2] GrŸnbaum, B. Convex Polytopes. New York: Wiley, pp. 362-364, 
     1886            [2] Grunbaum, B. Convex Polytopes. New York: Wiley, pp. 362-364, 
    19491887                1967. 
    19501888            [3] Lederberg, J. "DENDRAL-64: A System for Computer Construction, 
    … …  
    19651903                           pos=pos_dict, name="LCF Graph") 
    19661904         
    1967  
    19681905################################################################################ 
    19691906#   Pseudofractal Graphs 
    … …  
    19821919               name="Dorogovtsev-Goltsev-Mendes Graph, %d-th generation"%n) 
    19831920 
     1921################################################################################ 
     1922#   Random Graphs 
     1923################################################################################ 
     1924 
     1925    def RandomGNP(self, n, p, seed=None): 
     1926        r""" 
     1927        Returns a Random graph on $n$ nodes.  Each edge is inserted 
     1928        independently with probability $p$. 
     1929 
     1930        IMPLEMENTATION: 
     1931        This function calls the NetworkX function \code{gnp_random_graph}. 
     1932         
     1933        REFERENCES: 
     1934            [1] P. Erdos and A. Renyi, On Random Graphs, Publ. Math. 6, 290 (1959). 
     1935            [2] E. N. Gilbert, Random Graphs, Ann. Math. Stat., 30, 1141 (1959). 
     1936         
     1937        PLOTTING: 
     1938        When plotting, this graph will use the default spring-layout 
     1939        algorithm, unless a position dictionary is specified. 
     1940                 
     1941        EXAMPLES: 
     1942        We plot a random graph on 12 nodes with probability $p = .71$: 
     1943            sage: gnp = graphs.RandomGNP(12,.71) 
     1944            sage.: gnp.show() 
     1945 
     1946        We view many random graphs using a graphics array: 
     1947            sage: g = [] 
     1948            sage: j = [] 
     1949            sage: for i in range(9): 
     1950            ...    k = graphs.RandomGNP(i+3,.43) 
     1951            ...    g.append(k) 
     1952            ... 
     1953            sage: for i in range(3): 
     1954            ...    n = [] 
     1955            ...    for m in range(3): 
     1956            ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False)) 
     1957            ...    j.append(n) 
     1958            ... 
     1959            sage: G = sage.plot.plot.GraphicsArray(j) 
     1960            sage: G.save('sage.png') 
     1961 
     1962        TIMINGS: 
     1963        The following timings compare the speed of RandomGNP and 
     1964        RandomGNPFast for sparse and dense graphs: 
     1965         
     1966            time regular_sparse = graphs.RandomGNP(1559,.22) 
     1967            CPU time: 31.79 s,  Wall time: 38.78 s 
     1968            time fast_sparse =  graphs.RandomGNPFast(1559,.22) 
     1969            CPU time: 21.72 s,  Wall time: 26.44 s 
     1970            time regular_dense = graphs.RandomGNP(1559,.88) 
     1971            CPU time: 38.75 s,  Wall time: 47.65 s 
     1972            time fast_dense = graphs.RandomGNP(1559,.88) 
     1973            CPU time: 39.15 s,  Wall time: 48.22 s 
     1974        """ 
     1975        import networkx 
     1976        G = networkx.gnp_random_graph(n, p, seed) 
     1977        return graph.Graph(G) 
     1978 
     1979    def RandomGNPFast(self, n, p, seed=None): 
     1980        """ 
     1981        Returns a Random graph on $n$ nodes, with each edge inserted 
     1982        independently with probability $p$. 
     1983 
     1984        This function calls the NetworkX function \code{fast_gnp_random_graph}. 
     1985         
     1986        PLOTTING: 
     1987        When plotting, this graph will use the default spring-layout 
     1988        algorithm, unless a position dictionary is specified. 
     1989         
     1990        EXAMPLES: 
     1991        Plot a random graph on 12 nodes with p = .71 
     1992            sage: fast = graphs.RandomGNPFast(12,.71) 
     1993            sage.: fast.show() 
     1994 
     1995        View many random graphs using a SAGE Graphics Array 
     1996            sage: g = [] 
     1997            sage: j = [] 
     1998            sage: for i in range(9): 
     1999            ...    k = graphs.RandomGNPFast(i+3,.43) 
     2000            ...    g.append(k) 
     2001            ... 
     2002            sage.: for i in range(3): 
     2003            ...    n = [] 
     2004            ...    for m in range(3): 
     2005            ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False)) 
     2006            ...    j.append(n) 
     2007            ... 
     2008            sage.: G = sage.plot.plot.GraphicsArray(j) 
     2009            sage.: G.show() 
     2010 
     2011        TIMINGS: See the documentation for RandomGNP. 
     2012        """ 
     2013        import networkx 
     2014        G = networkx.fast_gnp_random_graph(n, p, seed) 
     2015        return graph.Graph(G) 
     2016 
     2017    def RandomBarabasiAlbert(self, n, m, seed=None): 
     2018        u""" 
     2019        Return a random graph created using the Barabasi-Albert preferential 
     2020        attachment model. 
     2021         
     2022        A graph with m vertices and no edges is initialized, and a graph of n 
     2023        vertices is grown by attaching new veritces each with m edges that are 
     2024        attached to existing vertices, preferentially with high degree. 
     2025         
     2026        INPUT: 
     2027            n -- number of vertices in the graph 
     2028            m -- number of edges to attach from each new node 
     2029            seed -- for random number generator 
     2030         
     2031        EXAMPLES: 
     2032        We plot a random graph on 12 nodes with m = 3. 
     2033            sage: ba = graphs.RandomBarabasiAlbert(12,3) 
     2034            sage: ba.plot().save('sage.png')  # or ba.show() 
     2035             
     2036        We view many random graphs using a graphics array: 
     2037            sage: g = [] 
     2038            sage: j = [] 
     2039            sage: for i in range(9): 
     2040            ...    k = graphs.RandomBarabasiAlbert(i+3, 3) 
     2041            ...    g.append(k) 
     2042            ... 
     2043            sage: for i in range(3): 
     2044            ...    n = [] 
     2045            ...    for m in range(3): 
     2046            ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False)) 
     2047            ...    j.append(n) 
     2048            ... 
     2049            sage: G = sage.plot.plot.GraphicsArray(j) 
     2050            sage: G.save('sage.png')  # or G.show() 
     2051 
     2052        """ 
     2053        import networkx 
     2054        return graph.Graph(networkx.barabasi_albert_graph(n,m,seed)) 
     2055 
     2056    def RandomGNM(self, n, m, dense=False, seed=None): 
     2057        """ 
     2058        Returns a graph randomly picked out of all graphs on n vertices with 
     2059        m edges. 
     2060         
     2061        INPUT: 
     2062            n -- number of vertices. 
     2063            m -- number of edges. 
     2064            dense -- whether to use NetworkX's dense_gnm_random_graph or 
     2065        gnm_random_graph 
     2066         
     2067        EXAMPLES: 
     2068        We plot a random graph on 12 nodes with m = 12. 
     2069            sage: gnm = graphs.RandomGNM(12, 12) 
     2070            sage: gnm.plot().save('sage.png')  # or gnm.show() 
     2071             
     2072        We view many random graphs using a graphics array: 
     2073            sage: g = [] 
     2074            sage: j = [] 
     2075            sage: for i in range(9): 
     2076            ...    k = graphs.RandomGNM(i+3, i^2-i) 
     2077            ...    g.append(k) 
     2078            ... 
     2079            sage: for i in range(3): 
     2080            ...    n = [] 
     2081            ...    for m in range(3): 
     2082            ...        n.append(g[3*i + m].plot(node_size=50, vertex_labels=False)) 
     2083            ...    j.append(n) 
     2084            ... 
     2085            sage: G = sage.plot.plot.GraphicsArray(j) 
     2086            sage: G.save('sage.png')  # or G.show() 
     2087 
     2088        """ 
     2089        import networkx 
     2090        if dense: 
     2091            return graph.Graph(networkx.dense_gnm_random_graph(n, m, seed)) 
     2092        else: 
     2093            return graph.Graph(networkx.gnm_random_graph(n, m, seed)) 
     2094 
     2095    def RandomNewmanWattsStrogatz(self, n, k, p, seed=None): 
     2096        """ 
     2097        Returns a Newman-Watts-Strogatz small world random graph on n vertices. 
     2098         
     2099        From the NetworkX documentation: 
     2100        First create a ring over n nodes.  Then each node in the ring is 
     2101        connected with its k nearest neighbors.  Then shortcuts are created by 
     2102        adding new edges as follows: for each edge u-v in the underlying 
     2103        "n-ring with k nearest neighbors"; with probability p add a new edge 
     2104        u-w with randomly-chosen existing node w. In contrast with 
     2105        watts_strogatz_graph(), no edges are removed. 
     2106         
     2107        INPUT: 
     2108            n -- number of vertices. 
     2109            k -- each vertex is connected to its k nearest neighbors 
     2110            p -- the probability of adding a new edge for each edge 
     2111            seed -- for the random number generator 
     2112         
     2113        EXAMPLE: 
     2114            sage: G = graphs.RandomNewmanWattsStrogatz(12, 2, .3)        
     2115            sage: G.plot().save('sage.png')  # or G.show() 
     2116 
     2117        REFERENCE: 
     2118            [1] Newman, M.E.J., Watts, D.J. and Strogatz, S.H. Random graph 
     2119                models of social networks. Proc. Nat. Acad. Sci. USA 99, 2566-2572. 
     2120 
     2121        """ 
     2122        import networkx 
     2123        return graph.Graph(networkx.newman_watts_strogatz_graph(n, k, p, seed)) 
     2124 
     2125    def RandomHolmeKim(self, n, m, p, seed=None): 
     2126        """ 
     2127        Returns a random graph generated by the Holme and Kim algorithm for 
     2128        graphs with powerlaw degree distribution and approximate average 
     2129        clustering. 
     2130         
     2131        INPUT: 
     2132            n -- number of vertices. 
     2133            m -- number of random edges to add for each new node. 
     2134            p -- probability of adding a triangle after adding a random edge. 
     2135            seed -- for the random number generator. 
     2136             
     2137        From the NetworkX documentation: 
     2138        The average clustering has a hard time getting above a certain cutoff 
     2139        that depends on m. This cutoff is often quite low. Note that the 
     2140        transitivity (fraction of triangles to possible triangles) seems to go 
     2141        down with network size. It is essentially the Barabasi-Albert growth 
     2142        model with an extra step that each random edge is followed by a chance 
     2143        of making an edge to one of its neighbors too (and thus a triangle). 
     2144        This algorithm improves on B-A in the sense that it enables a higher 
     2145        average clustering to be attained if desired. It seems possible to 
     2146        have a disconnected graph with this algorithm since the initial m 
     2147        nodes may not be all linked to a new node on the first iteration like 
     2148        the BA model. 
     2149         
     2150        EXAMPLE: 
     2151            sage: G = graphs.RandomHolmeKim(12, 3, .3) 
     2152            sage: G.plot().save('sage.png')  # or G.show() 
     2153 
     2154        REFERENCE: 
     2155            [1] Holme, P. and Kim, B.J. Growing scale-free networks with 
     2156                tunable clustering, Phys. Rev. E (2002). vol 65, no 2, 026107. 
     2157        """ 
     2158        import networkx 
     2159        return graph.Graph(networkx.powerlaw_cluster_graph(n, m, p, seed)) 
     2160 
     2161    def RandomLobster(self, n, p, q, seed=None): 
     2162        """ 
     2163        Returns a random lobster. 
     2164         
     2165        A lobster is a tree that reduces to a caterpillar when pruning all 
     2166        leaf vertices. A caterpillar is a tree that reduces to a path when 
     2167        pruning all leaf vertices (q=0). 
     2168         
     2169        INPUT: 
     2170            n -- expected number of vertices in the backbone 
     2171            p -- probability of adding an edge to the backbone 
     2172            q -- probability of adding an edge (claw) to the arms 
     2173            seed -- for the random number generator 
     2174         
     2175        EXAMPLE: 
     2176            sage: G = graphs.RandomLobster(9, .6, .3) 
     2177            sage: G.plot().save('sage.png')  # or G.show() 
     2178         
     2179        """ 
     2180        import networkx 
     2181        return graph.Graph(networkx.random_lobster(n, p, q, seed)) 
     2182 
     2183    def RandomTreePowerlaw(self, n, gamma=3, tries=100, seed=None): 
     2184        """ 
     2185        Returns a tree with a powerlaw degree distribution. Returns False on 
     2186        failure. 
     2187         
     2188        From the NetworkX documentation: 
     2189        A trial powerlaw degree sequence is chosen and then elements are 
     2190        swapped with new elements from a powerlaw distribution until the 
     2191        sequence makes a tree (size = order - 1). 
     2192         
     2193        INPUT: 
     2194            n -- number of vertices 
     2195            gamma -- exponent of power law 
     2196            tries -- number of attempts to adjust sequence to make a tree 
     2197            seed -- for the random number generator 
     2198         
     2199        EXAMPLE: 
     2200            sage: G = graphs.RandomTreePowerlaw(15, 2)  # VERY random output 
     2201            sage: if G: 
     2202            ...    G.plot().save('sage.png')  # or G.show() (random output) 
     2203         
     2204        """ 
     2205        import networkx 
     2206        try: 
     2207            return graph.Graph(networkx.random_powerlaw_tree(n, gamma, seed, tries)) 
     2208        except: 
     2209            return False 
     2210 
     2211    def RandomRegular(self, d, n, seed=None): 
     2212        """ 
     2213        Returns a random d-regular graph on n vertices, or returns False on 
     2214        failure. 
     2215         
     2216        Since every edge is incident to two vertices, n*d must be even. 
     2217         
     2218        INPUT: 
     2219            n -- number of vertices 
     2220            d -- degree 
     2221            seed -- for the random number generator 
     2222         
     2223        EXAMPLE: 
     2224            sage: G = graphs.RandomRegular(3, 20)  # VERY random output 
     2225            sage: if G: 
     2226            ...    G.plot().save('sage.png')  # or G.show() (random output) 
     2227         
     2228        REFERENCES: 
     2229            [1] Kim, Jeong Han and Vu, Van H. Generating random regular graphs. 
     2230                Proc. 35th ACM Symp. on Thy. of Comp. 2003, pp 213-222. ACM 
     2231                Press, San Diego, CA, USA. 
     2232                http://doi.acm.org/10.1145/780542.780576 
     2233            [2] Steger, A. and Wormald, N. Generating random regular graphs 
     2234                quickly. Prob. and Comp. 8 (1999), pp 377-396. 
     2235        """ 
     2236        import networkx 
     2237        try: 
     2238            return graph.Graph(networkx.random_regular_graph(d, n, seed)) 
     2239        except: 
     2240            return False 
     2241 
     2242    def RandomShell(self, constructor, seed=None): 
     2243        """ 
     2244        Returns a random shell graph for the constructor given. 
     2245         
     2246        INPUT: 
     2247            constructor -- a list of 3-tuples (n,m,d), each representing a shell 
     2248                n -- the number of vertices in the shell 
     2249                m -- the number of edges in the shell 
     2250                d -- the ratio of inter (next) shell edges to intra shell edges 
     2251            seed -- for the random number generator 
     2252         
     2253        EXAMPLE: 
     2254            sage: G = graphs.RandomShell([(10,20,0.8),(20,40,0.8)]) 
     2255            sage: G.plot().save('sage.png')  # or G.show() 
     2256         
     2257        """ 
     2258        import networkx 
     2259        return graph.Graph(networkx.random_shell_graph(constructor, seed)) 
     2260 
    19842261# Easy access to the graph database from the command line: 
    19852262graphs = GraphGenerators() 
Note: See TracChangeset for help on using the changeset viewer.