Well yes, just wondering if there is a better way to do it. This isn't for work or anything, its just a bit of fun. My code struggles with k6 and k7 seems to fail to return. I.e. the cycle finding loop is too big ( it isn't infinite).
-------------------------------------------- On Fri, 9/18/15, Raul Miller <[email protected]> wrote: Subject: Re: [Jprogramming] Finding all cycles in a graph To: "Programming forum" <[email protected]> Date: Friday, September 18, 2015, 10:22 PM Looks like your code works? Are you looking for alternatives? Thanks, -- Raul On Fri, Sep 18, 2015 at 9:09 AM, Devon McCormick <[email protected]> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
