Searching cycles in graph

Hello,

I often have to solve examples of searching isomorphisms in graphs.
I'm first looking for cycles of length 3 (triangles)
then cycles of length 4, 5, 6, ... and compare the graphs if the number of cycles of length N is different. And so, I can say that those graphs aren't isomorphic.
and now my question...
Do you know some algorithm how to effectively find all cycles of length N? (N equals 3, 4, 5, 6, ...).
I'm doing it with my eye and many times happens that I forget something.

thanks for help
LVL 6
xRalfAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

xRalfAuthor Commented:
and now my question...
Do you know some algorithm how to effectively find all cycles of length N? (N equals 3, 4, 5, 6, ...).
I'm doing it with my eye and many times happens that I forget something.
0
Introducing Cloud Class® training courses

Tech changes fast. You can learn faster. That’s why we’re bringing professional training courses to Experts Exchange. With a subscription, you can access all the Cloud Class® courses to expand your education, prep for certifications, and get top-notch instructions.

ozoCommented:
Are you talking about a directed graph?
If so
http://www.cs.utk.edu/~parker/Courses/CS302-fall05/Notes/GraphIntro/
0
ozoCommented:
If not, you can adapt
http://en.wikipedia.org/wiki/Shortest_path_problem
where a cycle is detected any time there are multiple paths between nodes
0
xRalfAuthor Commented:
The graph is undirected.
and I'd like to find all cycles of length N in each graph.
for example: How would you find all cycles of length 6? It is easy to forget something. And that's way I'm looking for some algorithm that will guarantee it.

I attached the file graphs.bmp
graphs.bmp
0
TalmashCommented:
you need to define "connectivity matrix" A[nxn]
1. initiate A = I[n] (main diagonal set to 1, upper and lower triangles set to zero)
2. foreach arc in the graph that connect nodes i & j , set A[i,j] = A[j,i] = 1

now the algo:
find all nodes with distance = 1 from node i = D(i,1)
find all nodes with distance = 2 from node i = D(i,2)
find nodes that belong to both D(i,1) & D(i,1) => all the circles with legth 3

and so on...
0
ozoCommented:
Yes, a cycle is detected any time there are multiple paths between nodes
0
xRalfAuthor Commented:
Hi Talmash,

it seems too complex. What if the length is 8? We have to try 1+7, 2+6, 3+5, 4+4? And how would you count the cycles? We have to examine all of the nodes, so we could count the same cycle twice.
0
ozoCommented:
If you have a fully connected graph on 8 nodes, would you want to count 2520 cycles of length 8?
0
ozoCommented:
>  graphs.bmp
Will all the node have degree (exactly/no more than/no less than) three?
0
ozoCommented:
@graphsA=(
[0,1],[0,5],[0,9],
[1,0],[1,2],[1,4],
[2,1],[2,3],[2,6],
[3,2],[3,4],[3,8],
[4,1],[4,3],[4,5],
[5,0],[5,4],[5,7],
[6,2],[6,7],[6,8],
[7,5],[7,6],[7,9],
[8,3],[8,6],[8,9],
[9,0],[9,7],[9,8],
);
$paths[1]{$_->[0]}{$_->[1]}{1<<$_->[1]}=1 for @graphsA;
$paths[1]{$_->[1]}{$_->[0]}{1<<$_->[0]}==1 or die "@$_" for @graphsA;
for$l( 2..6 ){
     for $a (keys %{$paths[$l-1]} ){
      $pa=$paths[$l-1]{$a};
      for $b (keys %$pa ){
          next if $b eq $a;
          $pb=$pa->{$b};
          for $c (keys %{$paths[1]{$b}} ){
              if( $l==3 ){
                  print;
              }
              $m = 1<<$c;
              $paths[$l]{$a}{$c}{$m|$_} += $pb->{$_} for grep!($m&$_),keys %$pb;
          }
      }
   }
}
for $l (3..6){
 $n=0;
 for $a (keys %{$paths[$l]} ){
   $n+= $_ for values%{$paths[$l]{$a}{$a}};
 }
 print "length $l cycles",$n/(2*$l),"\n";
}

gets:
length 3 cycles 0
length 4 cycles 5
length 5 cycles 0
length 6 cycles 15
0
xRalfAuthor Commented:
This is the typical example on my exam. I have only a pen and a paper and 30 minutes. It would interest me how would you solve it if you don't want to forget something. The question is which of the graphs A, B, C, D are isomorphic. And the only reasonable possibility is to count the cycles of various lengths. The problem is, that it is not suffiecient to say that graph A has more cycles of length 6. We have to also say exactly how many cycles and enumerate them... This is the wish of our teacher.
0
ozoCommented:
Maybe coloured pens?

But two graphs can have the same number of cycles and not be isomorphic.
To find an isomorphism you can reorder the vertices so than the graphs are identical.
In the examples in graphs.bmp, you you may want to start by reordering them do show that they are bipartite graphs
0
xRalfAuthor Commented:
I'm not sure if I can use colored pens...

>>But two graphs can have the same number of cycles and not be isomorphic.

Yes. I'm first trying to find the different number of cycles of length N. Then I try to find the bijection between graphs (numbering of vertices).

>>In the examples in graphs.bmp, you you may want to start by reordering them do show that they are bipartite graphs

That's good idea. I tried it and found e.g. that A and B aren't isomorphic. But the teacher is quite strict and wants some proof (that's because I'm counting the cycles)

This is the comment from teacher: It is not sufficient to write for example that graphs contains various number of C4, you have to also write how many and which.
0
ozoCommented:
To prove that graphs are isomorphic, it is sufficient to show a bijection that makes them identical.
To prove that graphs are not isomorphic, it is sufficient but not necessary to show that one graph has a different number of cycles than another.
Looking at a form of the graphs that make their bipartite nature obvious may make it easier
to transform them in ways that make the differences or similarities more obvious.
You may be able to enumerate all C4 cycles by hand in 30 minutes, but to prove that you have not missed any you may need to display all intermediate steps of finding an exhaustive list of paths of length <=4
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
xRalfAuthor Commented:
You can notice that graphs on the picture have the same number of C4. So I would look for C5, C6, ... Is it real requirement from our teacher to show the exact differences?
0
JimFiveCommented:
To do this by hand, I wouldn't use cycles.

I would first label each graph and then write out the connections for each point
A -> B,C,D
B -> A,F,G

Then, by putting the lists next to each other it should be possible to reorder the lists and find the bijection.

Alternatively, you might try to redraw each of the graphs in a way that minimizes line crossings, For example, in your graph A1, If we label the leftmost point A and thus around clockwise. you could move point B and point J inside the circle as a first step.
--
JimFive
0
xRalfAuthor Commented:
Hi JimFive,

I don't know exactly how you mean it. Try to solve the example with your strategy and paste a result as a picture or something. It is a little different to solve it theoretically and practically.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.