]> dreyeck.freedombox.rocks Git - topic-maps.git/blob - tests/merge-graphs.lisp
Document XTM normative coverage and remaining qualification gaps
[topic-maps.git] / tests / merge-graphs.lisp
1 (in-package #:topic-maps.ctm.tests)
2
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))
8 (loop while changed do
9 (setf changed nil)
10 (dolist (edge edges)
11 (when (some (lambda (node) (member node component)) edge)
12 (dolist (node edge)
13 (unless (member node component)
14 (push node component) (setf remaining (remove node remaining) changed t))))))
15 (push component components)))
16 components))
17
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))))
22 (dotimes (mask 64)
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)))
32 (dolist (edge order)
33 (let ((locator (format nil "urn:edge:~D:~D" (first edge) (second edge))))
34 (dolist (node 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)))))
44 components))
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))))
51 components))
52 (check (concatenate 'string label "raw-reference-integrity") (raw-reference-invariants map))))))))