Connected Graphs with Restricted Number of Edges

No algorithm description given

The algorithm gives the number of connected labeled graphs on `n` vertices restricted to `k` edges. def memoize ( func ): 
 cache = {} 
 def memof ( * args , ** kwargs ): 
 k = args 
 if k in cache : 
 return cache [ k ] 
 else : 
 result = func ( * args , ** kwargs ) 
 cache [ k ] = result 
 return result 
 memof . _cache = cache 
 return memof 

 @memoize 
 def binomial ( n , k ): 
 if k < 0 or k > n : 
 return 0 
 if k == 0 or k == n : 
 return 1 
 k , c = min ( k , n - k ), 1 
 for i in xrange ( k ): 
 c = c * ( n - i ) / ( i + 1 ) 
 return c 

 @memoize 
 def c ( n , k ): 
 if k < n - 1 or k > binomial ( n , 2 ): 
 return 0 
 elif k == binomial ( n , 2 ): 
 return 1 
 elif k == n - 1 : 
 return n ** ( n - 2 ) 
 else : 
 s , t = binomial ( binomial ( n , 2 ), k ), 0 
 for i in xrange ( 1 , n ): 
 for j in xrange ( i - 1 , min ( binomial ( i , 2 ) + 1 , k + 1 )): 
 t += ( binomial ( n - 1 , i - 1 ) * 
 binomial ( binomial ( n - i , 2 ), k - j ) * 
 c ( i , j )) 
 return s - t 

 def apply ( nk ): 
 assert len ( nk ) == 2 and set ( map ( type , nk )) == set ([ int ]) 
 return str ( c ( * nk )) 
 The implementation makes use of recurrences given by Marko Riedel (see below) and Brendan McKay et al (eqn 1.11 of [1]). For large `n` there will be integer wrap around. A simple way to use arbitrary precision is to convert the return value to the python `decimal.Decimal` type where the wraparound occurs: import decimal 

 c = decimal . Context ( prec = 256 ) 
 decimal . setcontext ( c ) 

 @memoize 
 def c ( n , k ): 
 if k < n - 1 or k > binomial ( n , 2 ): 
 return 0 
 elif k == binomial ( n , 2 ): 
 return 1 
 elif k == n - 1 : 
 return Decimal ( n ) ** ( n - 2 ) 
 else : 
 s , t = binomial ( binomial ( n , 2 ), k ), 0 
 for i in xrange ( 1 , n ): 
 for j in xrange ( i - 1 , min ( binomial ( i , 2 ) + 1 , k + 1 )): 
 t += ( binomial ( n - 1 , i - 1 ) * 
 binomial ( binomial ( n - i , 2 ), k - j ) * 
 c ( i , j )) 
 return s - t 
 This is OEIS A123527 . A wide range of approaches with Maple and C implementations is discussed by Marko Riedel  at these links: http://math.stackexchange.com/questions/689526/how-many-connected-graphs-over-v-vertices-and-e-edges http://math.stackexchange.com/questions/1071564/how-many-good-graphs-of-size-n-are-there References: [1] Bender, E. A., Canfield, E. R. and McKay, B. D. (1990), The asymptotic number of labeled connected graphs with a given number of vertices and edges. Random Struct. Alg., 1: 127–169. doi: 10.1002/rsa.3240010202 [2] Flajolet and  Sedgewick ,  Analytic Combinatorics [3] Harary and Palmer, Graphical Enumeration ( helpful OEIS link ) Table of values: 1 0 1
 2 1 1
 3 2 3
 3 3 1
 4 3 16
 4 4 15
 4 5 6
 4 6 1
 5 4 125
 5 5 222
 5 6 205
 5 7 120
 5 8 45
 5 9 10
 5 10 1
 6 5 1296
 6 6 3660
 6 7 5700
 6 8 6165
 6 9 4945
 6 10 2997
 6 11 1365
 6 12 455
 6 13 105
 6 14 15
 6 15 1
 7 6 16807
 7 7 68295
 7 8 156555
 7 9 258125
 7 10 331506
 7 11 343140
 7 12 290745
 7 13 202755
 7 14 116175
 7 15 54257
 7 16 20349
 7 17 5985
 7 18 1330
 7 19 210
 7 20 21
 7 21 1
 8 7 262144
 8 8 1436568
 8 9 4483360
 8 10 10230360
 8 11 18602136
 8 12 28044072
 8 13 35804384
 8 14 39183840
 8 15 37007656
 8 16 30258935
 8 17 21426300
 8 18 13112470
 8 19 6905220
 8 20 3107937
 8 21 1184032
 8 22 376740
 8 23 98280
 8 24 20475
 8 25 3276
 8 26 378
 8 27 28
 8 28 1
 9 8 4782969
 9 9 33779340
 9 10 136368414
 9 11 405918324
 9 12 974679363
 9 13 1969994376
 9 14 3431889000
 9 15 5228627544
 9 16 7032842901
 9 17 8403710364
 9 18 8956859646
 9 19 8535294180
 9 20 7279892361
 9 21 5557245480
 9 22 3792906504
 9 23 2309905080
 9 24 1251493425
 9 25 600775812
 9 26 254183454
 9 27 94143028
 9 28 30260331
 9 29 8347680
 9 30 1947792
 9 31 376992
 9 32 58905
 9 33 7140
 9 34 630
 9 35 36
 9 36 1
 10 9 100000000
 10 10 880107840
 10 11 4432075200
 10 12 16530124800
 10 13 50088981600
 10 14 128916045720
 10 15 288982989000
 10 16 573177986865
 10 17 1016662746825
 10 18 1624745199910
 10 19 2352103292070
 10 20 3096620034795
 10 21 3717889913655
 10 22 4078716030900
 10 23 4093594934220
 10 24 3761135471805
 10 25 3163862003211
 10 26 2435820178050
 10 27 1714943046390
 10 28 1102765999275
 10 29 646542946125
 10 30 344847947664
 10 31 166867565040
 10 32 73005619995
 10 33 28759950345
 10 34 10150589610
 10 35 3190186926
 10 36 886163125
 10 37 215553195
 10 38 45379620
 10 39 8145060
 10 40 1221759
 10 41 148995
 10 42 14190
 10 43 990
 10 44 45
 10 45 1

 ...

 20 19 262144000000000000000000
 20 20 8765006377126199463936000
 20 21 165302832533722012508160000
 20 22 2308679811324625848791040000
 20 23 26475493254511544166850560000 
 20 24 262531375188086694499173888000
 20 25 2319409283218421983604361216000
 20 26 18609460830276453968696568576000
 20 27 137389515051337171399458435328000
 20 28 942286943592166927670520784780800
 20 29 6047449583948914817459539926604800
 20 30 36525524751295516417034996099750400
 20 31 208571200052782924641061209874483200
 20 32 1130300650993207566827148319301771880
 20 33 5831738934026048895826705179092277120
 20 34 28723888612157111882953788103273970340
 20 35 135376304331236127351814277357418826380
 20 36 611755203820630100932668139569655653840
 20 37 2655349100798421324674003273937347141440
 20 38 11088128409801591093117635255497606675800
 20 39 44606287696335732082661932475125008999720
 20 40 173093184087559388557367970317932248105360
 20 41 648634853134996172634225003614446597429320
 20 42 2349635408113437646955354971698533883712740
 20 43 8235373529177470880652460053802218808087980
 20 44 27952196835136685448917879439461869334410800
 20 45 91946325761953831526022842342180418988526640
 20 46 293323596830287357305947764536461608867858880
 20 47 908108519771992451439632625351722372571708480
 20 48 2730038400735615036002612889636029395562762940
 20 49 7974117537961181949550849258775727551874918300
 20 50 22641461465708071138697884315996625477663213040
 20 51 62523528991427060772830373925248588518522574480
 20 52 167994340448833310311473061857592690452647157960
 20 53 439379609944055570033573267043656746906954879560
 20 54 1119049560306988683013921063482443621234880458640
 20 55 2776400987013110803265071299784514459932820123440
 20 56 6712555103215350665474943224055436396502752517340
 20 57 15820003938512717669745201297125355031702332505620
 20 58 36355507329631394056324975255739939114129383525800
 20 59 81489719357083942168990372106284892841284143009440
 20 60 178205593469776626899179292865881830060256015277000
 20 61 380308445861969151464175305627521253582430617881200
 20 62 792229041509562288598344955587763758895313623436280
 20 63 1611253663378636285865154999161614458562821550550880
 20 64 3200134580885618414286699298034529266460857650169165
 20 65 6207996169249222497599923902980061119984393973560250
 20 66 11765121908406564458627012904714069001823741708809275
 20 67 21786207173226748678138947749938428180363721989737580
 20 68 39425860884511872102812365759471792027341500604140505
 20 69 69737314285580496469788594028337934658321806251330250
 20 70 120586868444914951946513467750933860571722138276133275
 20 71 203867609196437603533590129055793402004778274865911400
 20 72 337030365222188758030716978552941677096026008360126685
 20 73 544901842008654214368467275419586144121980197935690890
 20 74 861685216190423321548918666774119739779339168907460355
 20 75 1332937402373577118386130640579382271972565593132180356
 20 76 2017196958767237366974987508530256487182717131607867025
 20 77 2986813834341124743685220889482239558678124795956947690
 20 78 4327433786974669795474079704565108222943346091264022315
 20 79 6135551696813670525966684708099083381721260355072930000
 20 80 8513607726769030832716554358246595936380401384020592513
 20 81 11562291195436147058886026241015740143479912300177563970
 20 82 15370054806994526508193862134521986786696256523149495575
 20 83 20000313432783641272263388727030230896705466444525947180
 20 84 25477356873473639512476772908693816013722495702600032265
 20 85 31772556908599627440874194901507570438850872714755099978
 20 86 38792878749685698523603124984130516187889410469921596635
 20 87 46373890655353938344432935729914028056658332719926497720
 20 88 54279298250968782996315993072086727268668100407156688305
 20 89 62208459118903581653828763547308584092082785451805733650
 20 90 69812382963304726732245548458093917009834278334432962271
 20 91 76717506045668481889353643116268866438527555477778106580
 20 92 82555237341550578889317411945876816255247591325493788865
 20 93 86994146659895802590632485182513335241221849734798385290
 20 94 89770938575812625664252966870363776177858044360302789675
 20 95 90716210270590805577577419830401049909124355624633204320
 20 96 89771501959259118937676830983896956955582521303871633745
 20 97 86995261363941848917313195432844412346436616602276915330
 20 98 82556878852697422386984420202467010899908906906684189235
 20 99 76719636824248060278044888112048942753870048740116907380
 20 100 69814952030673113533958686801674332836149373773174947651
 20 101 62211402220234022386699832166692349370338847735769908830
 20 102 54282538963593584953787999506246943286043499332391242305
 20 103 46377342671349122394327736400967867346067152183569536520
 20 104 38796449351781662565196741539454848888798436467192045645
 20 105 31776151426229594201547195880717770354922595172775700058
 20 106 25480883701496407817663668469924390103410432416186941015
 20 107 20003689063008568275297739448428650099169952329309482060
 20 108 15373208289341682977649269463785287033042365636678730255
 20 109 11565167516449011402405138671907133965148772688639329910
 20 110 8516169751079597685524387014004417017329057631967548293
 20 111 6137780527785119153464081430114271153553168659165335280
 20 112 4329327623593330337833251497674502522149498526168623305
 20 113 2988385591700145044370076954621392876110910469340910090
 20 114 2018471048709153668977817177972559866040717903848861115
 20 115 1333946124145551613639320775313257003485862242518875116
 20 116 862465186021095880698295410618976586046560021104845675
 20 117 545490810771206073783501354122993645556725678544692350
 20 118 337464658482089079589796002636713575541484023559577465
 20 119 204180299547899591305891389147541363257662066887845000
 20 120 120806678106523419570559217427068210462880032100327765
 20 121 69888161263681650706591562873335577601622672740326850
 20 122 39526911035657022046321030330037891630371170361766175
 20 123 21852276083541036529943285114979161479083281732230260
 20 124 11807278231651869372879200108022171539044509244428375
 20 125 6234242915997603351903923705384889650448442799563206
 20 126 3216077698373482420749432886919342476289677315472285
 20 127 1620700573717262362712203729107789750445621786084480
 20 128 797688564086512130591907009078193504214907493183515
 20 129 383385201500820331780828273089260443941545849770710
 20 130 179896133063826131842513709857257062904264905996913
 20 131 82395175465721245931076845124914283097905692458260
 20 132 36828146614847099084196809802025358257033343217885
 20 133 16060394765923896864645582921613298110347681525090
 20 134 6831660460584231682152503775706989901188533361375
 20 135 2833873968962289754536610283559185323442863118728
 20 136 1146051972776748949124410694797914711532731704375
 20 137 451728514826216907648143959019480617455776185230
 20 138 173489936855856105192048869240464720776227201445
 20 139 64902710191244780984114223496919476839032288700
 20 140 23643130141229444309401933290813427173865172001
 20 141 8384088702593846915190463977517362799384283370
 20 142 2893101031183346045538679183398654219815743275
 20 143 971110835643346096476727486469808705931189200
 20 144 316959786633870808135160881728570717701504075
 20 145 100552759897695587573031656203698583528764070
 20 146 30992289009573660394831397048018733786528705
 20 147 9276603513071427256300896471050539487552100
 20 148 2695229399068347141922652342853832086738825
 20 149 759729092354883999355974194033869350173850
 20 150 207659285243675636633614664479122587930787
 20 151 55009082183756205442539852390164099951640
 20 152 14114172402411279476175267710544671473935
 20 153 3505480727396284813243037292390512525230
 20 154 842225889049759124780061125294485068365
 20 155 195613754876073363889867008010760639676
 20 156 43887701414503669503181582956431178405
 20 157 9504342981484874177139099402831015570
 20 158 1985084293601271480782780206077345495
 20 159 399513820095853405480892548907818560
 20 160 77405802643571599400105648837693511
 20 161 14423441486379801286095416614735710
 20 162 2581974093240828635856898201152485
 20 163 443529292090449091470400458532960
 20 164 73020066380744667533756230135455
 20 165 11506192278177947613104886925062
 20 166 1732860282858124640600590327845
 20 167 249033813105359229789524810400
 20 168 34093914889424180268881778375
 20 169 4438261109865869620803019350
 20 170 548255784159901541393346645
 20 171 64123483527473864490450280
 20 172 7083408064081415263479975
 20 173 737001995106736848223350
 20 174 72005942050658197814925
 20 175 6583400416060178085936
 20 176 561085262732401541415
 20 177 44379625300867918530
 20 178 3241208589389230005
 20 179 217287726662965140
 20 180 13278694407181203
 20 181 733629525258630
 20 182 36278383117185
 20 183 1585940245560
 20 184 60334683255
 20 185 1956800538
 20 186 52602165
 20 187 1125180
 20 188 17955
 20 189 190
 20 190 1

0.842158794403 sec to compute and print The table was printed with import time
ti = time.time()
for n in range(1, 21):
 for k in range(n - 1, binomial(n, 2) + 1):
 print '{:3d} {:4d} {}'.format(n, k, answer(n, k))
print time.time() - ti, 'sec'

Tags
(no tags)

Cost Breakdown

0 cr
royalty per call
1 cr
usage per second
avg duration
This algorithm has permission to call other algorithms which may incur separate royalty and usage costs.

Cost Calculator

API call duration (sec)
×
API calls
=
Estimated cost
per calls
for large volume discounts
For additional details on how pricing works, see Algorithmia pricing.

Calls other algorithms

This algorithm has permission to call other algorithms. This allows an algorithm to compose sophisticated functionality using other algorithms as building blocks, however it also carries the potential of incurring additional royalty and usage costs from any algorithm that it calls.


To understand more about how algorithm permissions work, see the permissions documentation.

1. Type your input

2. See the result

Running algorithm...

3. Use this algorithm

curl -X POST -d '{{input | formatInput:"curl"}}' -H 'Content-Type: application/json' -H 'Authorization: Simple YOUR_API_KEY' https://api.algorithmia.com/v1/algo/douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0
View cURL Docs
algo auth
# Enter API Key: YOUR_API_KEY
algo run algo://douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0 -d '{{input | formatInput:"cli"}}'
View CLI Docs
import com.algorithmia.*;
import com.algorithmia.algo.*;

String input = "{{input | formatInput:"java"}}";
AlgorithmiaClient client = Algorithmia.client("YOUR_API_KEY");
Algorithm algo = client.algo("algo://douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0");
AlgoResponse result = algo.pipeJson(input);
System.out.println(result.asJsonString());
View Java Docs
import com.algorithmia._
import com.algorithmia.algo._

val input = {{input | formatInput:"scala"}}
val client = Algorithmia.client("YOUR_API_KEY")
val algo = client.algo("algo://douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0")
val result = algo.pipeJson(input)
System.out.println(result.asJsonString)
View Scala Docs
var input = {{input | formatInput:"javascript"}};
Algorithmia.client("YOUR_API_KEY")
           .algo("algo://douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0")
           .pipe(input)
           .then(function(output) {
             console.log(output);
           });
View Javascript Docs
var input = {{input | formatInput:"javascript"}};
Algorithmia.client("YOUR_API_KEY")
           .algo("algo://douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0")
           .pipe(input)
           .then(function(response) {
             console.log(response.get());
           });
View NodeJS Docs
import Algorithmia

input = {{input | formatInput:"python"}}
client = Algorithmia.client('YOUR_API_KEY')
algo = client.algo('douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0')
print algo.pipe(input)
View Python Docs
library(algorithmia)

input <- {{input | formatInput:"r"}}
client <- getAlgorithmiaClient("YOUR_API_KEY")
algo <- client$algo("douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0")
result <- algo$pipe(input)$result
print(result)
View R Docs
require 'algorithmia'

input = {{input | formatInput:"ruby"}}
client = Algorithmia.client('YOUR_API_KEY')
algo = client.algo('douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0')
puts algo.pipe(input).result
View Ruby Docs
use algorithmia::*;

let input = {{input | formatInput:"rust"}};
let client = Algorithmia::client("YOUR_API_KEY");
let algo = client.algo('douglarocca/ConnectedGraphswithRestrictedNumberofEdges/0.1.0');
let response = algo.pipe(input);
View Rust Docs
Discussion
  • {{comment.username}}