I am trying to write a function to find all cycles on a (not necessarily
connected) undirected graph. Two cycles are equivalent if they contain the
exact same edges, regardless of edge order.
My method follows. I am essentially doing a DFS on the edges (not vertices),
after first partitioning the graph into connected subgraphs. Going through each
edge and marking it as visited, and stopping if I find a cycle.
The main verb iscycles
e.g. define k4 (complete graph on 4 vertices) k4=: 6 2 $ 1 2 1 3 1 4 2 3 2 4 3 4
cycles k4
┌─────────────────────────────┐│┌───┬───┬───┬───┬───┬───┬───┐│││2 3│1 2│1 3│1
3│1 2│1 2│1 2││││2 4│1 3│1 4│1 4│1 3│1 4│1 4││││3 4│2 4│3 4│2 3│2 3│2 3│2 4││││
│3 4│ │2 4│ │3 4│
│││└───┴───┴───┴───┴───┴───┴───┘│└─────────────────────────────┘
this gives 7 cycles (agreeing with Wolfram
http://mathworld.wolfram.com/CompleteGraph.html )
So here is my method. It is terribly slow on k5 and k6 takes way too long,
which strikes me as an appalling flaw in my algorithm. So I'm wondering if
anyone knows a good method for finding all cycles in an arbitrary unidrected
graph.
I assume there is no efficient algorithm for a general case, making no
assumptions about the graph.
Anyway, here is my code:
CONCOMP=. connected_components ya:-.~ component_cycles&.> CONCOMP)
component_cycles=: 3 : 0HEAD=. {. yPATH=. 1 2 $ HEADVISIT=. 1 2 $ HEADEDGES=.
y-.HEAD
~. /:~&.> HEAD cyc PATH;VISIT;EDGES
)V=: (1 2 $ 1 2)num=: 0NB. X: current edge, Y: current path, visited edges,
remaining edgesNB. Depth first search of all remaining edges, marking
previously visited edges.NB. This algorithm is not efficient, and sturggles
with K6+ graphs.cyc=: 4 : 0num=: num+1CYCLES=. ''CE=. xPATH=. >0{ yVISITED=.
>1{yEDGES=. >2{yNEWVISITED=. ~.VISITED,CEEDGES=. EDGES-.CE
for_j. i. # EDGES do.MAYBE=. j{ EDGESif. (CE isAdjacent MAYBE) *. (0 = MAYBE
isOnGraph NEWVISITED) do.ADJ=. MAYBE getAdjacent PATH -. CEVERT=. (CE
joinVertex MAYBE)NB. get the vertices of the PATH that do not have VERTADJ=.
VERT (-.@:(0&<@:+/"1)@:e."1 1 # ]) ADJif. 0 < # ADJ do.FIRST=. 0{ ADJINDEX=. I.
(FIRST) -:"1 1 ( PATH)CYC=. INDEX }.PATH,MAYBEif. 0 = ''$(# ((#/./~, CYC)-. 2))
do.CYCLES=. CYCLES, < CYCelse.if. 1 < # EDGES-.MAYBE do.NEWPATH=. PATH,MAYBE
CYCLES=. ~. CYCLES, MAYBE cyc NEWPATH;NEWVISITED;(EDGES-.MAYBE)
else. CYCLES end.end.else.if. 1 < # EDGES-.MAYBE do.NEWPATH=. PATH,MAYBE
CYCLES=. ~. CYCLES, MAYBE cyc NEWPATH;NEWVISITED;(EDGES-.MAYBE)
else. CYCLES end.end.else.continue.end.end.CYCLES)
NB. some graphsg1=: 10 2 $ 1 2 1 3 2 3 3 4 5 6 5 7 6 8 8 9 7 9 5 9g2=: 10 2 $ 1
10 11 12 12 13 14 16 15 17 15 18 15 19 16 19 18 19 19 20NB. k5k5=: 10 2 $ 1 2 1
3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5NB. k33k33=: 9 2 $ 1 4 1 5 1 6 2 4 2 5 2 6 3 4
3 5 3 6k6=: 15 2 $ 1 2 1 3 1 4 1 5 1 6 2 3 2 4 2 5 2 6 3 4 3 5 3 6 4 5 4 6 5 6
Thanks,Jon
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
