User:Devon McCormick/Graphs/graphPlay.ijs

Here's some preliminary work I've done from studying the books Graphs, Networks, and Algorithms by Dieter Jungnickel and Graph Algorithms by Shimon Even.

NB.* graphPlay.ijs: play with graphs and algorithms for working with them.
NB. Based on the books "Graphs, Networks, and Algorithms" by Dieter Jungnickel and
NB. "Graph Algorithms" by Shimon Even.

egPic=: 0 : 0
0-2-5
|   |
1---4
|
3
)

NB. The picture above corresponds to this adjacency matrix representation of a graph.
ameg=: ".&><;._2 ] 0 : 0
0 1 1 0 0 0
1 0 0 1 1 0
1 0 0 0 0 1
0 1 0 0 0 0
0 1 0 0 0 1
0 0 1 0 1 0
)

NB. Vertex Array representation of same graph as above.
vaeg=: ,&.>1 2;0 3 4;0 5;1;1 5;2 4
NB. The ",&.>" ensures all vertex lists are vectors.

NB.* vaFromam: convert to vertex array from adjacency matrix representation.
vaFromam=: [: ,&.> [: I.&.> <"1
NB.* amFromva: convert to adjacency matrix from vertex array representation.
amFromva=: 3 : '1 (<"1 ;y,"0~&.>i.#y)}0$~2$#y'
NB.* etFromva: edge table from vertex array
etFromva=: [: ; ] ,"0~&.> [: i. #

trace=: 3 : 0
   et=. etFromva y [ p=. 0 2$0
   while. 0<#et do. et=. }.et [ p=. p,edge=. 0{et
       if. 0<#et do. et=. et|.~(0{"1 et) i. _1{edge end.
   end.
   p
)

NB.* egDAG: example picture of a directed acyclic graph with the
NB. characters "V>" (and, potentially, "^<") representing directional
NB. arrowheads.
egDAG=: 0 : 0
0->2->5
|     |
|     V
V>--->4
|
V
1
|
V
3
)

NB. The picture above corresponds to this adjacency matrix representation.
amDAGeg=: ".&><;._2 ] 0 : 0
0 1 1 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 1 0
)

NB. Vertex Array representation of same graph as above.
vaDAGeg=: ,&.>1 2;3;5;(i.0);(i.0);4
NB. A (nodes);(edges) representation of the above DAG.
neDAGeg=: 0 1 2 3 4 5;|:0 1,0 2,1 3,2 5,:5 4

egDAG0=: 0 : 0
0->2->3
|\    |
V \   |
1  \  |
|  |  V
V  -->4
5
)

Different Ways of Representing the Same Graph

NB. This (drawn differently but same as preceding with nodes
NB. 3 and 5 swapped) is a DAG because we can re-write the AM
NB. as (here, upper-) triangular matrix.
amDAG0=: ".&><;._2 ] 0 : 0
0 1 1 0 0 0
0 0 0 0 0 1
0 0 0 1 0 0
0 0 0 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0
)

NB. Vertex Array representation
vaDAG0=: ,&.>1 2;5;3;4;(i.0);i.0
NB. Nodes;Edges representation
neDAG0=: 0 1 2 3 4 5;|:0 1,0 2,1 5,2 3,:3 4

NB. Same as preceding but with
NB. lower-triangular adjacency matrix:
NB. swapped node "n" with "5-n".
egDAG1=: 0 : 0
5->3->2
|\    |
V \   |
4  \  |
|  |  V
V  -->1
0
)

NB. A DAG is defined as one that can be
NB. written as a triangular adjacency
NB. matrix: here it¡¯s lower-triangular.
amDAG1=: ".&><;._2 ] 0 : 0
0 0 0 0 0 0
0 0 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 0
1 0 0 0 0 0
0 0 0 1 1 0
)
NB. assert. amDAG1 -: |.|. "1 amDAG0

NB. Vertex Array representation
vaDAG1=: ,&.>(i.0);(i.0);1;2;0;3 4
NB. assert. vaDAG1 -: 5-&.>|.vaDAG0

NB. Nodes;Edges representation
neDAG1=: 0 1 2 3 4 5;|:2 1,3 2,4 0,5 3,:5 4
NB. assert. (1{neDAG1) -: <|."1]5->1{neDAG0
NB. assert. neDAG1 -: (<|."1]5->1{neDAG0) 1}neDAG0

-- Devon McCormick <<DateTime>>