So... ok... first off, you are talking about "cycles" and you are using what http://www.jsoftware.com/help/dictionary/samp20.htm suggests is an "arc" representation of the graph.
But the examples you give all specify arcs from a lower-numbered node to a higher-numbered node. And if you were working with a directed graph this would mean that you could have no cycles. So you are not working with "directed graphs" but with "undirected graphs". This means that each arc is implicitly accompanied by a reverse arc. In other words, given: connections=: (#. e.~ [: i. [ , [)~ (1 + >./@,) the connections for k33=: 9 2 $ 1 4 1 5 1 6 2 4 2 5 2 6 3 4 3 5 3 6 are not just connections k33 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 but also include the reverse connections: connections (,|."1)k33 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 1 1 0 0 0 But that also means that every arc is itself a cycle. So I'm having a little trouble understanding the purpose of your secondary partitioning, since it doesn't list those cycles. And it's also not just cycles, since you've got branches in some of them. I can see separating out unconnected graph segments, like you have here: e=: 10 2 $ 1 2 1 3 2 3 3 4 5 6 5 7 6 8 8 9 7 9 5 9 connections (,|."1)e 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 But I guess I am looking for a description of what your selection criteria is supposed to be doing. Thanks, -- Raul On Fri, Sep 18, 2015 at 9:43 AM, 'Jon Hough' via Programming <[email protected]> wrote: > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
