Click here to Skip to main content
Rate this: bad
good
Please Sign up or sign in to vote.
See more: Algorithms
I need to write a method to find the count of 4 cycles(cycles containing 4 edges) in an undirected graph. Please give me some advices if you have any idea about the algorithm.
Posted 1-Feb-13 3:43am
Comments
Andreas Gieriet at 2-Feb-13 6:10am
   
Why do you add a solution to your own questions. Use [Improve question] button here above and [x] delete your solution below.
Andi
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 1

See Robert Sedgewick[^]'s book list: Part 5: Graph Algorithms is the book to read (you choose: C, C++, Java). It would be a nice exercise if you write all the code of the book in C#. Wink | ;-)
Cheers
Andi
  Permalink  
v4
Comments
venera_soft at 2-Feb-13 2:06am
   
Thanks, will try :)
Rate this: bad
good
Please Sign up or sign in to vote.

Solution 2

I have done this myself. The algorithm uses DFS. And on every step it goes 4 levels and finds if the found vertex is the same as the one for which is done the step. In formal language it should be something like this:
 
for path in dfs(start=node, max_depth=4):
        if len(path) == 4 and path[1] == path[4]:
            output.append(path)
  Permalink  

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

  Print Answers RSS
0 Maciej Los 315
1 OriginalGriff 233
2 Aajmot Sk 224
3 Richard MacCutchan 220
4 Marcin Kozub 210
0 OriginalGriff 7,853
1 Sergey Alexandrovich Kryukov 7,107
2 DamithSL 5,604
3 Manas Bhardwaj 4,986
4 Maciej Los 4,790


Advertise | Privacy | Mobile
Web03 | 2.8.1411023.1 | Last Updated 2 Feb 2013
Copyright © CodeProject, 1999-2014
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100