Hi - The first piece of your code is ungrammatical:
CONCOMP=. connected_components y a:-.~ component_cycles&.> CONCOMP ) Is there something before this? Regards, Devon On Fri, Sep 18, 2015 at 8:04 AM, 'Jon Hough' via Programming < [email protected]> wrote: > 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 > -- Devon McCormick, CFA ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
