Re: number of Trangles in a graph-network
- To: mathgroup at smc.vnet.net
- Subject: [mg99374] Re: number of Trangles in a graph-network
- From: Peter Pein <petsie at dordos.net>
- Date: Mon, 4 May 2009 06:00:29 -0400 (EDT)
- References: <gtefaf$197$1@smc.vnet.net>
Luca Cinacchio schrieb: > Greetings, > > having a graph (network, i.e. one created with RandomGraph) wich can have > not connected nodes, I would like to count the total number of triangles > inside the graph. > I gave a look to Combinatorica and its related book by Pemmaraju Skiena, > but I did'nt find any solution (maybe I am wrong). Do you know if there is > a easy way to answer this problem with Mathematica and/or Combinatorica? > Thanks in advance. > It seems I'm writing too fast today :( I've got a slightly faster method: In[2]:= SeedRandom[123]; rg=RandomGraph[32,1/2]; In[4]:= (* this is from my 1st posting *) Timing@Total[ReplaceList[rg[[1]],{___,{{a_,b_}},___,{{a_,c_}},___,{{b_,c_}},___}:>1]] Out[4]= {5.98437,573} and faster but a little bit more brain-twisting: In[5]:= countTriangles[g_Graph]:=Total@ReplaceList[g[[1]],{___,{{a_,b_}},r___/;Length[{r}]>1}:>Count[Split[Sort[Reverse/@Flatten[{r},1]],#1[[1]]===#2[[1]]&][[All,All,2]],{___,a,___,b,___}]] In[6]:= Timing@countTriangles[rg] Out[6]= {0.100006,573} don't try this with my first method: In[7]:= Timing[countTriangles[RandomGraph[100,2/3]]] Out[7]= {16.705,45453} Cheers, Peter