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?
>

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

```

• Prev by Date: Re: Can't apply Differences[] to a SparseArray[]?
• Next by Date: Re: Solving the system with inexact coefficients
• Previous by thread: Re: number of Trangles in a graph-network
• Next by thread: Re: number of Trangles in a graph-network