Yes, sorry, some how the first bunch of verbs slipped out of my copy / paste.
getAdjacent=: I.@:([ isAdjacent"(_ 1) ]) { ]
isAdjacent=: 0&<@+/@e.
isOnGraph=: 0&<@:+/@:(<@:[ E. <"1@:])
NB. gets the joining vertex between two edges, if they are adjacent.
joinVertex=: I.@:e. { [
NB. Finds connected components by a depth first search
connected_components=: 3 : 0
edges=. ~.y
components=. ''
while. 0 < # edges do.
head=. {. edges
edges=. edges -. head
con=. >head cc edges
edges=. edges -. con
components=. components ,<con
end.
components
)
NB. connected components
cc=: 4 : 0
E=. x
ALL=. y
ADJ=. E getAdjacent ALL
NEXT=. ALL -. ADJ
if. (0=# ADJ) do.
<E
else.
a:-.~ ~.(<E), ,/ADJ cc"1 _ NEXT
end.
)
cycles=: 3 : 0
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
)
e=: 10 2 $ 1 2 1 3 2 3 3 4 5 6 5 7 6 8 8 9 7 9 5 9
f=: 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
k4=: 6 2 $ 1 2 1 3 1 4 2 3 2 4 3 4
--------------------------------------------
On Fri, 9/18/15, Devon McCormick <[email protected]> wrote:
Subject: Re: [Jprogramming] Finding all cycles in a graph
To: "J-programming forum" <[email protected]>
Date: Friday, September 18, 2015, 10:09 PM
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
