[Jprogramming] Finding all cycles in a graph
Raul Miller
rauldmiller at gmail.com
Fri Sep 18 14:12:19 UTC 2015
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
<programming at jsoftware.com> 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 <rauldmiller at gmail.com> wrote:
>
> Subject: Re: [Jprogramming] Finding all cycles in a graph
> To: "Programming forum" <programming at jsoftware.com>
> 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 <devonmcc at gmail.com>
> 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 <
> > programming at jsoftware.com>
> 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 <programming at jsoftware.com>
> >> wrote:
> >>
> >> Subject: Re: [Jprogramming] Finding
> all cycles in a graph
> >> To:
> "programming at jsoftware.com"
> <programming at jsoftware.com>
> >> 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 <programming at jsoftware.com>
> >> 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
More information about the Programming
mailing list