Enumerate all triangles in a large undirected graph

[Yanshuo Sun]

Hi everyone,

I tried to find the most efficient implementation for generating all triangles in a large graph.

I found https://stackoverflow.com/questions/1705824/finding-cycle-of-3-nodes-or-triangles-in-a-graph

http://www.mail-archive.com/algo...@googlegroups.com/msg05642.html

https://groups.google.com/forum/#!msg/networkx-discuss/SHjKJFIFNtM/rgfnU0SMCfAJ;context-place=msg/networkx-discuss/SHjKJFIFNtM/rgfnU0SMCfAJ

It seems if I use Networkx, I have to use something like this:

cycls_3 = [c for c in nx.cycle_basis(G) if len(c)==3]

or 

all_cliques = list(nx.enumerate_all_cliques(G))
selected_3_cli = [clq for clq in all_cliques if len(clq)== 3]

Can anyone point me to the best approach to do this?

Thank you in advance.

Shawn

[Daniel Schult]

If you don't care about multiple copies of the same triangle in different order then a list of tuples works:

    [(n,nbr,nbr2) for n in G for nbr, nbr2 in itertools.combinations(G[n],2) if nbr in G[nbr2]]

The logic here is to check each pair of neighbors of every node to see if they are connected. G[n] is a fast way to iterate over or look up neighbors.

If you want to get rid of reorderings, turn each triple into a frozenset and make a set of the frozensets:

    set(frozenset([n,nbr,nbr2]) for n in G for nbr, nbr2 in itertools.combinations(G[n]) if nbr in G[nbr2])

If you want a list of sets that are rid of reorderings then:

    [set(triple) for triple in set(frozenset((n,nbr,nbr2)) for n in G for nbr, nbr2 in itertools.combinations(G[n],2) if nbr in G[nbr2])]

or perhaps for readably:

    triangles = set(frozenset(n, nbr, nbr2)) for n in G for nbr, nbr2 in itertools.combinations(G[n],2) if nbr in G[nbr2])

    nice_triangles = [set(tri) for tri in triangles]

The "set of frozensets" idiom is often used to remove duplicate groups from a list of groups.

To much fun.... :}

Dan

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discuss+unsubscribe@googlegroups.com.
To post to this group, send email to networkx-discuss@googlegroups.com.
Visit this group at https://groups.google.com/group/networkx-discuss.
For more options, visit https://groups.google.com/d/optout.