CODEWITHSUNDEEP
pythonalgorithmgraph
user2779485
user2779485

Reputation: 137

How to search shapes in a graph?

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.

Upvotes: 0

Views: 681

Answers (1)

flyman
flyman

Reputation: 210

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

Upvotes: 2

Related Questions