-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathadjacentList
51 lines (46 loc) · 1.82 KB
/
adjacentList
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#+BEGIN_SRC emacs-lisp :results silent
(defun make-adjacency-list (node links)
"Make the adjacency list of a node by collecting
all the nodes it's connected to in links."
(loop for link in links
if (= node (car link))
collect (cdr link)))
(defun make-adjacency-list-in-reverse (node links)
"Make the reverse adjacency list of a node by collecting
all the nodes connected to it in links."
(loop for link in links
if (= node (cdr link))
collect (car link)))
(defun make-adjacency-lists (nodes links)
"Make adjacency lists given a graph's nodes and links
by collecting the adjacency lists and reverse adjacency lists
for each of the graph's nodes, removing any duplicates found."
(let ((alists nil) the-nodes-alist)
(loop for node in nodes
do (setq the-nodes-alist
(remove-duplicates
(nconc (make-adjacency-list node links)
(make-adjacency-list-in-reverse node links)))
alists (nconc alists (list (cons node the-nodes-alist)))))
alists))
#+END_SRC
#+BEGIN_SRC emacs-lisp
(make-adjacency-lists nodes graph-11-27-links)
#+END_SRC
#+RESULTS:
| 1 | 2 | 9 | 10 | 11 | | | |
| 2 | 3 | 4 | 5 | 9 | 10 | 11 | 1 |
| 3 | 4 | 10 | 11 | 2 | | | |
| 4 | 5 | 10 | 11 | 2 | 3 | | |
| 5 | 6 | 7 | 9 | 2 | 4 | | |
| 6 | 7 | 9 | 5 | | | | |
| 7 | 8 | 9 | 5 | 6 | | | |
| 8 | 10 | 9 | 7 | | | | |
| 9 | 10 | 1 | 2 | 5 | 6 | 7 | 8 |
| 10 | 11 | 1 | 2 | 3 | 4 | 8 | 9 |
| 11 | 1 | 2 | 3 | 4 | 10 | | |
#+BEGIN_SRC emacs-lisp
(setq n '(make-adjacency-lists nodes graph-11-27-links)
(mapcar (lambda (y) (cdr (x) n )))
(mapcar (lambda (x) list (sort '> ))))
#+END_SRC