How to search shapes in a graph?

Question

I have an adjancency matrix am of a 5 node undirected graph where am(i,j) = 1 means node i is connected to node j. I generated all possible versions of this 5-node graph by the following code:

import itertools
graphs = list(itertools.product([0, 1], repeat=10))

This returns me an array of arrays where each element is a possible configuration of the matrix (note that I only generate these for upper triangle since matrix is symetric):

[ (0, 0, 0, 0, 0, 0, 1, 0, 1, 1),
  (0, 0, 0, 0, 0, 0, 1, 1, 0, 0),
  (0, 0, 0, 0, 0, 0, 1, 1, 0, 1),
  (0, 0, 0, 0, 0, 0, 1, 1, 1, 0),
  (0, 0, 0, 0, 0, 0, 1, 1, 1, 1),
....]

where (0, 0, 0, 0, 0, 0, 1, 1, 1, 1) actually corresponds to:

m =
     0     0     0     0     0
     0     0     0     0     0
     0     0     1     1     1
     0     0     0     0     1
     0     0     0     0     0

I would like to search for all possible triangle shapes in this graph. For example, here, (2, 4), (2,5) and (4, 5) together makes a triangle shape:

m =
     0     0     0     0     0
     0     0     0     1     1
     0     0     0     0     0
     0     0     0     0     1
     0     0     0     0     0

Is there a known algorithm to do such a search in a graph? Note that triangle shape is an example here, ideally I would like to find a solution that would search any particular shape, for example a square or a pentagon. How can I encode these shapes to search in the first place? Any help, reference, algorithm name is appreciated.

At least 2 things aren't clear: (1) How does `(0, 0, 0, 0, 0, 0, 1, 1, 1, 1)` correspond to that strange matrix beneath it? (2) Are you looking for graphs that *are* triangles or that *contain* triangles? Finally, regarding finding cycles of length k (like squares (k=4) or pentagons (k=5)), this is NP-hard for general k, since you can set k=n and you would then find a Hamiltonian cycle (a.k.a. TSP tour) if one exists, and this problem is NP-hard. So expect this to exponentially more time-consuming as you look for longer cycles. — j_random_hacker, Nov 17 '13 at 18:45
1) this array corresponds to the upper triangle of the adj. matrix. for example arr[0] = m[1, 2] or arr[9] = m[4,5] (last element of the upper triangle) 2) i am looking for graphs that *are* the triangle (or the given shape). 3) i am only interested graphs up to 5 nodes. But shapes are not necessarily cycles, e.g. one shape might be a string e.g. o_o_o_o_o (where each node connected via an edge) — user2779485, Nov 17 '13 at 19:43
Regarding the correspondence between the array and matrix, I think there's still a problem -- e.g. I don't know what it means for m[2, 2] (assuming 1-based indices here, as you seem to be doing) to be 1, as it is in your example (a node with an edge to itself?). Anyway, the problem you have here is called Graph Isomorphism. It's not known to be NP-hard, and should be solvable in a reasonable time for such small graphs. — j_random_hacker, Nov 17 '13 at 21:59

score 2 · Answer 1 · edited May 23 '17 at 11:54

Your explanation for the graph representation is not quite understandable.

However, finding cycles of size k is NP-complete problem when k is your input (since it includes the NP-complete hamiltonian-cycle problem). If that is the case, then you should have a look at these posts:

Finding all cycles of a certain length in a graph

Finding all cycles in undirected graphs

But, if you have fixes size lengths, then this problem can be solved in good polinomial time. Here is an article about this very issue:

Finding and Counting Given Length Cycles | Algorithmica

How to search shapes in a graph?

1 Answers1