1 (in-package #:topic-maps.ctm.tests)
3 (defun graph-components (nodes edges)
4 ;; Independent reachability oracle, without using the model's identity logic.
5 (let ((remaining (copy-list nodes)) (components nil))
6 (loop while remaining do
7 (let ((component (list (pop remaining))) (changed t))
11 (when (some (lambda (node) (member node component)) edge)
13 (unless (member node component)
14 (push node component) (setf remaining (remove node remaining) changed t))))))
15 (push component components)))
18 (defun run-merging-graph-checks ()
19 ;; Every undirected graph on four topics (64), in both edge orders.
20 ;; Shared edge SIs encode its connections; each Topic starts with one Name.
21 (let ((possible '((0 1) (0 2) (0 3) (1 2) (1 3) (2 3))))
23 (let* ((edges (loop for edge in possible for bit from 0 when (logbitp bit mask) collect edge))
24 (components (graph-components '(0 1 2 3) edges)))
25 (dolist (reverse-order '(nil t))
26 (let* ((map (topic-maps.tmdm:make-topic-map))
27 (topics (loop for i below 4 collect
28 (topic-maps.tmdm:intern-topic map :item-identifier (format nil "urn:node:~D" i))))
29 (names (mapcar (lambda (topic) (topic-maps.tmdm:add-default-name topic "Shared")) topics))
30 (order (if reverse-order (reverse edges) edges))
31 (label (format nil "graph:~D:~S:" mask reverse-order)))
33 (let ((locator (format nil "urn:edge:~D:~D" (first edge) (second edge))))
35 (topic-maps.tmdm:add-topic-identifier (nth node topics) :subject-identifier locator))))
36 (check (concatenate 'string label "component-count")
37 (= (1+ (length components)) (length (topic-map-topics map))))
38 (check (concatenate 'string label "component-identities")
39 (every (lambda (component)
40 (let ((root (topic-maps.tmdm:canonical-topic (nth (first component) topics))))
41 (and (every (lambda (node) (eq root (topic-maps.tmdm:canonical-topic (nth node topics)))) component)
42 (same-locator-set-p (topic-item-identifiers root)
43 (mapcar (lambda (node) (format nil "urn:node:~D" node)) component)))))
45 (check (concatenate 'string label "name-coalescence-and-handles")
46 (every (lambda (component)
47 (let* ((root (topic-maps.tmdm:canonical-topic (nth (first component) topics)))
48 (name (first (topic-names root))))
49 (and (= 1 (length (topic-names root)))
50 (every (lambda (node) (eq name (topic-maps.tmdm:canonical-topic-name (nth node names)))) component))))
52 (check (concatenate 'string label "raw-reference-integrity") (raw-reference-invariants map))))))))