Third time lucky... 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 is cycles 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 k6 and k7 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 y a:-.~ component_cycles&.> CONCOMP ) component_cycles=: 3 : 0 HEAD=. {. y PATH=. 1 2 $ HEAD VISIT=. 1 2 $ HEAD EDGES=. y-.HEAD ~. /:~&.> HEAD cyc PATH;VISIT;EDGES ) V=: (1 2 $ 1 2) num=: 0 NB. X: current edge, Y: current path, visited edges, remaining edges NB. Depth first search of all remaining edges, marking previously visited edges. NB. This algorithm is not efficient, and sturggles with K6+ graphs. cyc=: 4 : 0 num=: num+1 CYCLES=. '' CE=. x PATH=. >0{ y VISITED=. >1{y EDGES=. >2{y NEWVISITED=. ~.VISITED,CE EDGES=. EDGES-.CE for_j. i. # EDGES do. MAYBE=. j{ EDGES if. (CE isAdjacent MAYBE) *. (0 = MAYBE isOnGraph NEWVISITED) do. ADJ=. MAYBE getAdjacent PATH -. CE VERT=. (CE joinVertex MAYBE) NB. get the vertices of the PATH that do not have VERT ADJ=. VERT (-.@:(0&<@:+/"1)@:e."1 1 # ]) ADJ if. 0 < # ADJ do. FIRST=. 0{ ADJ INDEX=. I. (FIRST) -:"1 1 ( PATH) CYC=. INDEX }.PATH,MAYBE if. 0 = ''$(# ((#/./~, CYC)-. 2)) do. CYCLES=. CYCLES, < CYC else. 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 graphs g1=: 10 2 $ 1 2 1 3 2 3 3 4 5 6 5 7 6 8 8 9 7 9 5 9 g2=: 10 2 $ 1 10 11 12 12 13 14 16 15 17 15 18 15 19 16 19 18 19 19 20 NB. k5 k5=: 10 2 $ 1 2 1 3 1 4 1 5 2 3 2 4 2 5 3 4 3 5 4 5 NB. k33 k33=: 9 2 $ 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 k6=: 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 -------------------------------------------- On Fri, 9/18/15, 'Jon Hough' via Programming <[email protected]> wrote: Subject: Re: [Jprogramming] Finding all cycles in a graph To: "[email protected]" <[email protected]> Date: Friday, September 18, 2015, 8:43 PM Sorry, it seems I am having trouble with line endings. This should read better (I emailed it to myself first and it was fine): 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 k6 and k7 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 On Friday, September 18, 2015 8:09 PM, 'Jon Hough' via Programming <[email protected]> wrote: 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
