python/samba/tests/graph.py

   1 # -*- coding: utf-8 -*-
   2 # Test graph dot file generation
   3 #
   4 # Copyright (C) Andrew Bartlett 2018.
   5 #
   6 # Written by Douglas Bagnall <douglas.bagnall@catalyst.net.nz>
   7 #
   8 # This program is free software; you can redistribute it and/or modify
   9 # it under the terms of the GNU General Public License as published by
  10 # the Free Software Foundation; either version 3 of the License, or
  11 # (at your option) any later version.
  12 #
  13 # This program is distributed in the hope that it will be useful,
  14 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 # GNU General Public License for more details.
  17 #
  18 # You should have received a copy of the GNU General Public License
  19 # along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20
  21 """Tests for samba.graph"""
  22
  23 from __future__ import print_function
  24
  25 import samba
  26 import samba.tests
  27 from samba import graph
  28
  29 import re
  30 import itertools
  31
  32
  33 class DotFileTests(samba.tests.TestCaseInTempDir):
  34
  35     def assertMatch(self, exp, s):
  36         m = re.match(exp, s)
  37         if m is None:
  38             self.fail("%r did not match /%s/" % (s, exp))
  39         return m
  40
  41     def assertHeader(self, lines, title, directed):
  42         self.assertEqual(lines[0], '/* generated by samba */')
  43         if directed:
  44             exp = r'^digraph \w+ {$'
  45         else:
  46             exp = r'^graph \w+ {$'
  47         self.assertMatch(exp, lines[1])
  48         m = self.assertMatch(r'^label="([\w ]+)";$', lines[2])
  49         self.assertEqual(m.group(1), title)
  50         self.assertMatch(r'^fontsize=10;$', lines[3])
  51         self.assertMatch(r'$', lines[4])
  52         self.assertEqual(lines[5], 'node[fontname=Helvetica; fontsize=10];')
  53         self.assertEqual(lines[6], '')
  54
  55     def assertVertices(self, lines, names):
  56         for n, line in zip(names, lines):
  57             m = self.assertMatch(r'^"(\w+)";$', line)
  58             self.assertEqual(n, m.group(1))
  59
  60     def assertEdges(self, lines, edges, directed):
  61         connector = '->' if directed else '--'
  62
  63         for edge, line in zip(edges, lines):
  64             a, b = edge
  65             m = self.assertMatch((r'^"(\w+)" ([>-]{2}) '
  66                                   r'"(\w+)" ?(?:\[([^\]])\])?;$'),
  67                                  line)
  68             self.assertEqual(m.group(1), a)
  69             self.assertEqual(m.group(2), connector)
  70             self.assertEqual(m.group(3), b)
  71             if m.group(4):
  72                 self.assertMatch(r'^[\w ]*$', m.group(4))
  73
  74     def test_basic_dot_files(self):
  75         vertices = tuple('abcdefgh')
  76         all_edges = tuple(itertools.combinations(vertices, 2))
  77         line_edges = list(zip(vertices[1:], vertices[:-1]))
  78         ring_edges = line_edges + [(vertices[0], vertices[-1])]
  79         no_edges = []
  80         # even join to even numbers, odd to odd
  81         disjoint_edges = [(a, b) for a, b in all_edges if
  82                           ord(a) ^ ord(b) == 0]
  83
  84         for name, edges in (('all', all_edges),
  85                             ('line', line_edges),
  86                             ('ring', ring_edges),
  87                             ('no', no_edges),
  88                             ('disjoint', disjoint_edges)):
  89
  90             for directed, tag in ((True, "directed"),
  91                                   (False, "undirected")):
  92                 title = "%s %s" % (name, tag)
  93
  94                 g = graph.dot_graph(vertices, edges,
  95                                     directed=directed,
  96                                     title=title)
  97                 lines = g.split('\n')
  98                 self.assertHeader(lines, title, directed)
  99                 self.assertVertices(lines[7:], vertices)
 100                 self.assertEdges(lines[len(vertices) + 7:], edges, directed)
 101
 102
 103 class DistanceTests(samba.tests.TestCase):
 104
 105     def setUp(self):
 106         super(DistanceTests, self).setUp()
 107         # a sorted list of colour set names.
 108         self.sorted_colour_sets = sorted(
 109             graph.COLOUR_SETS,
 110             # return '' for None, so it's sortable.
 111             key=lambda name: name or '')
 112
 113     def test_simple_distance(self):
 114         edges = [('ant', 'bat'),
 115                  ('cat', 'dog'),
 116                  ('ant', 'elephant'),
 117                  ('elephant', 'dog'),
 118                  ('bat', 'dog'),
 119                  ('frog', 'elephant'),
 120                  ('frog', 'cat'),
 121                  ('bat', 'elephant'),
 122                  ('elephant', 'cat'),
 123                  ('cat', 'ant'),
 124                  ('cat', 'dog')]
 125
 126         expected = {
 127                 "utf8 True, colour None": '''
 128                  destination
 129          ╭────── ant
 130          │╭───── bat
 131          ││╭──── cat
 132          │││╭─── dog
 133          ││││╭── elephant
 134   source │││││╭─ frog
 135      ant ·1221-
 136      bat 3·211-
 137      cat 12·12-
 138      dog ---·--
 139 elephant 2311·-
 140     frog 23121·''',
 141                 'utf8 True, colour ansi': '''
 142                  \e[4mdestination\e[0m
 143          \e[0m\e[37m╭────── ant\e[0m
 144          \e[37m│\e[0m\e[1;30m╭───── bat\e[0m
 145          \e[37m│\e[1;30m│\e[0m\e[37m╭──── cat\e[0m
 146          \e[37m│\e[1;30m│\e[37m│\e[0m\e[1;30m╭─── dog\e[0m
 147          \e[37m│\e[1;30m│\e[37m│\e[1;30m│\e[0m\e[37m╭── elephant\e[0m
 148   \e[4msource\e[0m \e[37m│\e[1;30m│\e[37m│\e[1;30m│\e[37m│\e[0m\e[1;30m╭─ frog\e[0m
 149 \e[37m     ant\e[0m \e[0m\e[37m·\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[33m2\e[0m\e[1;32m1\e[0m\e[1;31m-\e[0m
 150 \e[1;30m     bat\e[0m \e[33m3\e[0m\e[0m\e[1;30m·\e[0m\e[33m2\e[0m\e[1;32m1\e[0m\e[1;32m1\e[0m\e[1;31m-\e[0m
 151 \e[37m     cat\e[0m \e[1;32m1\e[0m\e[33m2\e[0m\e[0m\e[37m·\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[1;31m-\e[0m
 152 \e[1;30m     dog\e[0m \e[1;31m-\e[1;31m-\e[1;31m-\e[0m\e[1;30m·\e[0m\e[1;31m-\e[1;31m-\e[0m
 153 \e[37melephant\e[0m \e[33m2\e[0m\e[33m3\e[0m\e[1;32m1\e[0m\e[1;32m1\e[0m\e[0m\e[37m·\e[0m\e[1;31m-\e[0m
 154 \e[1;30m    frog\e[0m \e[33m2\e[0m\e[33m3\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[1;32m1\e[0m\e[0m\e[1;30m·\e[0m\e[0m
 155                 ''',
 156                 'utf8 True, colour ansi-heatmap': '''
 157                  \e[4mdestination\e[0m
 158          \e[0m\e[37m╭────── ant\e[0m
 159          \e[37m│\e[0m\e[1;30m╭───── bat\e[0m
 160          \e[37m│\e[1;30m│\e[0m\e[37m╭──── cat\e[0m
 161          \e[37m│\e[1;30m│\e[37m│\e[0m\e[1;30m╭─── dog\e[0m
 162          \e[37m│\e[1;30m│\e[37m│\e[1;30m│\e[0m\e[37m╭── elephant\e[0m
 163   \e[4msource\e[0m \e[37m│\e[1;30m│\e[37m│\e[1;30m│\e[37m│\e[0m\e[1;30m╭─ frog\e[0m
 164 \e[37m     ant\e[0m \e[0m\e[37m·\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[43m2\e[0m\e[1;42m1\e[0m\e[1;41m-\e[0m
 165 \e[1;30m     bat\e[0m \e[43m3\e[0m\e[0m\e[1;30m·\e[0m\e[43m2\e[0m\e[1;42m1\e[0m\e[1;42m1\e[0m\e[1;41m-\e[0m
 166 \e[37m     cat\e[0m \e[1;42m1\e[0m\e[43m2\e[0m\e[0m\e[37m·\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[1;41m-\e[0m
 167 \e[1;30m     dog\e[0m \e[1;41m-\e[1;41m-\e[1;41m-\e[0m\e[1;30m·\e[0m\e[1;41m-\e[1;41m-\e[0m
 168 \e[37melephant\e[0m \e[43m2\e[0m\e[43m3\e[0m\e[1;42m1\e[0m\e[1;42m1\e[0m\e[0m\e[37m·\e[0m\e[1;41m-\e[0m
 169 \e[1;30m    frog\e[0m \e[43m2\e[0m\e[43m3\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[1;42m1\e[0m\e[0m\e[1;30m·\e[0m\e[0m
 170                 ''',
 171                 'utf8 True, colour xterm-256color': '''
 172                  \e[4mdestination\e[0m
 173          \e[0m\e[38;5;39m╭────── ant\e[0m
 174          \e[38;5;39m│\e[0m\e[38;5;45m╭───── bat\e[0m
 175          \e[38;5;39m│\e[38;5;45m│\e[0m\e[38;5;39m╭──── cat\e[0m
 176          \e[38;5;39m│\e[38;5;45m│\e[38;5;39m│\e[0m\e[38;5;45m╭─── dog\e[0m
 177          \e[38;5;39m│\e[38;5;45m│\e[38;5;39m│\e[38;5;45m│\e[0m\e[38;5;39m╭── elephant\e[0m
 178   \e[4msource\e[0m \e[38;5;39m│\e[38;5;45m│\e[38;5;39m│\e[38;5;45m│\e[38;5;39m│\e[0m\e[38;5;45m╭─ frog\e[0m
 179 \e[38;5;39m     ant\e[0m \e[0m\e[38;5;39m·\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;214m2\e[0m\e[38;5;112m1\e[0m\e[48;5;124m-\e[0m
 180 \e[38;5;45m     bat\e[0m \e[38;5;208m3\e[0m\e[0m\e[38;5;45m·\e[0m\e[38;5;214m2\e[0m\e[38;5;112m1\e[0m\e[38;5;112m1\e[0m\e[48;5;124m-\e[0m
 181 \e[38;5;39m     cat\e[0m \e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[0m\e[38;5;39m·\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[48;5;124m-\e[0m
 182 \e[38;5;45m     dog\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;45m·\e[0m\e[48;5;124m-\e[48;5;124m-\e[0m
 183 \e[38;5;39melephant\e[0m \e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[38;5;112m1\e[0m\e[38;5;112m1\e[0m\e[0m\e[38;5;39m·\e[0m\e[48;5;124m-\e[0m
 184 \e[38;5;45m    frog\e[0m \e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;112m1\e[0m\e[0m\e[38;5;45m·\e[0m\e[0m
 185                 ''',
 186             'utf8 True, colour xterm-256color-heatmap': '''
 187                  \e[4mdestination\e[0m
 188          \e[0m\e[38;5;171m╭────── ant\e[0m
 189          \e[38;5;171m│\e[0m\e[38;5;207m╭───── bat\e[0m
 190          \e[38;5;171m│\e[38;5;207m│\e[0m\e[38;5;171m╭──── cat\e[0m
 191          \e[38;5;171m│\e[38;5;207m│\e[38;5;171m│\e[0m\e[38;5;207m╭─── dog\e[0m
 192          \e[38;5;171m│\e[38;5;207m│\e[38;5;171m│\e[38;5;207m│\e[0m\e[38;5;171m╭── elephant\e[0m
 193   \e[4msource\e[0m \e[38;5;171m│\e[38;5;207m│\e[38;5;171m│\e[38;5;207m│\e[38;5;171m│\e[0m\e[38;5;207m╭─ frog\e[0m
 194 \e[38;5;171m     ant\e[0m \e[0m\e[38;5;171m·\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;214m2\e[0m\e[48;5;112m1\e[0m\e[48;5;124m-\e[0m
 195 \e[38;5;207m     bat\e[0m \e[48;5;208m3\e[0m\e[0m\e[38;5;207m·\e[0m\e[48;5;214m2\e[0m\e[48;5;112m1\e[0m\e[48;5;112m1\e[0m\e[48;5;124m-\e[0m
 196 \e[38;5;171m     cat\e[0m \e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[0m\e[38;5;171m·\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;124m-\e[0m
 197 \e[38;5;207m     dog\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;207m·\e[0m\e[48;5;124m-\e[48;5;124m-\e[0m
 198 \e[38;5;171melephant\e[0m \e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[48;5;112m1\e[0m\e[48;5;112m1\e[0m\e[0m\e[38;5;171m·\e[0m\e[48;5;124m-\e[0m
 199 \e[38;5;207m    frog\e[0m \e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;112m1\e[0m\e[0m\e[38;5;207m·\e[0m\e[0m
 200 ''',
 201             'utf8 False, colour None': '''
 202                  destination
 203          ,------ ant
 204          |,----- bat
 205          ||,---- cat
 206          |||,--- dog
 207          ||||,-- elephant
 208   source |||||,- frog
 209      ant 01221-
 210      bat 30211-
 211      cat 12012-
 212      dog ---0--
 213 elephant 23110-
 214     frog 231210
 215 ''',
 216             'utf8 False, colour ansi': '''
 217                  \e[4mdestination\e[0m
 218          \e[0m\e[37m,------ ant\e[0m
 219          \e[37m|\e[0m\e[1;30m,----- bat\e[0m
 220          \e[37m|\e[1;30m|\e[0m\e[37m,---- cat\e[0m
 221          \e[37m|\e[1;30m|\e[37m|\e[0m\e[1;30m,--- dog\e[0m
 222          \e[37m|\e[1;30m|\e[37m|\e[1;30m|\e[0m\e[37m,-- elephant\e[0m
 223   \e[4msource\e[0m \e[37m|\e[1;30m|\e[37m|\e[1;30m|\e[37m|\e[0m\e[1;30m,- frog\e[0m
 224 \e[37m     ant\e[0m \e[0m\e[37m0\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[33m2\e[0m\e[1;32m1\e[0m\e[1;31m-\e[0m
 225 \e[1;30m     bat\e[0m \e[33m3\e[0m\e[0m\e[1;30m0\e[0m\e[33m2\e[0m\e[1;32m1\e[0m\e[1;32m1\e[0m\e[1;31m-\e[0m
 226 \e[37m     cat\e[0m \e[1;32m1\e[0m\e[33m2\e[0m\e[0m\e[37m0\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[1;31m-\e[0m
 227 \e[1;30m     dog\e[0m \e[1;31m-\e[1;31m-\e[1;31m-\e[0m\e[1;30m0\e[0m\e[1;31m-\e[1;31m-\e[0m
 228 \e[37melephant\e[0m \e[33m2\e[0m\e[33m3\e[0m\e[1;32m1\e[0m\e[1;32m1\e[0m\e[0m\e[37m0\e[0m\e[1;31m-\e[0m
 229 \e[1;30m    frog\e[0m \e[33m2\e[0m\e[33m3\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[1;32m1\e[0m\e[0m\e[1;30m0\e[0m\e[0m
 230 ''',
 231             'utf8 False, colour ansi-heatmap': '''
 232                  \e[4mdestination\e[0m
 233          \e[0m\e[37m,------ ant\e[0m
 234          \e[37m|\e[0m\e[1;30m,----- bat\e[0m
 235          \e[37m|\e[1;30m|\e[0m\e[37m,---- cat\e[0m
 236          \e[37m|\e[1;30m|\e[37m|\e[0m\e[1;30m,--- dog\e[0m
 237          \e[37m|\e[1;30m|\e[37m|\e[1;30m|\e[0m\e[37m,-- elephant\e[0m
 238   \e[4msource\e[0m \e[37m|\e[1;30m|\e[37m|\e[1;30m|\e[37m|\e[0m\e[1;30m,- frog\e[0m
 239 \e[37m     ant\e[0m \e[0m\e[37m0\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[43m2\e[0m\e[1;42m1\e[0m\e[1;41m-\e[0m
 240 \e[1;30m     bat\e[0m \e[43m3\e[0m\e[0m\e[1;30m0\e[0m\e[43m2\e[0m\e[1;42m1\e[0m\e[1;42m1\e[0m\e[1;41m-\e[0m
 241 \e[37m     cat\e[0m \e[1;42m1\e[0m\e[43m2\e[0m\e[0m\e[37m0\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[1;41m-\e[0m
 242 \e[1;30m     dog\e[0m \e[1;41m-\e[1;41m-\e[1;41m-\e[0m\e[1;30m0\e[0m\e[1;41m-\e[1;41m-\e[0m
 243 \e[37melephant\e[0m \e[43m2\e[0m\e[43m3\e[0m\e[1;42m1\e[0m\e[1;42m1\e[0m\e[0m\e[37m0\e[0m\e[1;41m-\e[0m
 244 \e[1;30m    frog\e[0m \e[43m2\e[0m\e[43m3\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[1;42m1\e[0m\e[0m\e[1;30m0\e[0m\e[0m
 245 ''',
 246             'utf8 False, colour xterm-256color': '''
 247                  \e[4mdestination\e[0m
 248          \e[0m\e[38;5;39m,------ ant\e[0m
 249          \e[38;5;39m|\e[0m\e[38;5;45m,----- bat\e[0m
 250          \e[38;5;39m|\e[38;5;45m|\e[0m\e[38;5;39m,---- cat\e[0m
 251          \e[38;5;39m|\e[38;5;45m|\e[38;5;39m|\e[0m\e[38;5;45m,--- dog\e[0m
 252          \e[38;5;39m|\e[38;5;45m|\e[38;5;39m|\e[38;5;45m|\e[0m\e[38;5;39m,-- elephant\e[0m
 253   \e[4msource\e[0m \e[38;5;39m|\e[38;5;45m|\e[38;5;39m|\e[38;5;45m|\e[38;5;39m|\e[0m\e[38;5;45m,- frog\e[0m
 254 \e[38;5;39m     ant\e[0m \e[0m\e[38;5;39m0\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;214m2\e[0m\e[38;5;112m1\e[0m\e[48;5;124m-\e[0m
 255 \e[38;5;45m     bat\e[0m \e[38;5;208m3\e[0m\e[0m\e[38;5;45m0\e[0m\e[38;5;214m2\e[0m\e[38;5;112m1\e[0m\e[38;5;112m1\e[0m\e[48;5;124m-\e[0m
 256 \e[38;5;39m     cat\e[0m \e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[0m\e[38;5;39m0\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[48;5;124m-\e[0m
 257 \e[38;5;45m     dog\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;45m0\e[0m\e[48;5;124m-\e[48;5;124m-\e[0m
 258 \e[38;5;39melephant\e[0m \e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[38;5;112m1\e[0m\e[38;5;112m1\e[0m\e[0m\e[38;5;39m0\e[0m\e[48;5;124m-\e[0m
 259 \e[38;5;45m    frog\e[0m \e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;112m1\e[0m\e[0m\e[38;5;45m0\e[0m\e[0m
 260 ''',
 261             'utf8 False, colour xterm-256color-heatmap': '''
 262                  \e[4mdestination\e[0m
 263          \e[0m\e[38;5;171m,------ ant\e[0m
 264          \e[38;5;171m|\e[0m\e[38;5;207m,----- bat\e[0m
 265          \e[38;5;171m|\e[38;5;207m|\e[0m\e[38;5;171m,---- cat\e[0m
 266          \e[38;5;171m|\e[38;5;207m|\e[38;5;171m|\e[0m\e[38;5;207m,--- dog\e[0m
 267          \e[38;5;171m|\e[38;5;207m|\e[38;5;171m|\e[38;5;207m|\e[0m\e[38;5;171m,-- elephant\e[0m
 268   \e[4msource\e[0m \e[38;5;171m|\e[38;5;207m|\e[38;5;171m|\e[38;5;207m|\e[38;5;171m|\e[0m\e[38;5;207m,- frog\e[0m
 269 \e[38;5;171m     ant\e[0m \e[0m\e[38;5;171m0\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;214m2\e[0m\e[48;5;112m1\e[0m\e[48;5;124m-\e[0m
 270 \e[38;5;207m     bat\e[0m \e[48;5;208m3\e[0m\e[0m\e[38;5;207m0\e[0m\e[48;5;214m2\e[0m\e[48;5;112m1\e[0m\e[48;5;112m1\e[0m\e[48;5;124m-\e[0m
 271 \e[38;5;171m     cat\e[0m \e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[0m\e[38;5;171m0\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;124m-\e[0m
 272 \e[38;5;207m     dog\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;207m0\e[0m\e[48;5;124m-\e[48;5;124m-\e[0m
 273 \e[38;5;171melephant\e[0m \e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[48;5;112m1\e[0m\e[48;5;112m1\e[0m\e[0m\e[38;5;171m0\e[0m\e[48;5;124m-\e[0m
 274 \e[38;5;207m    frog\e[0m \e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;112m1\e[0m\e[0m\e[38;5;207m0\e[0m\e[0m
 275 '''
 276         }
 277         for utf8 in (True, False):
 278             for colour in self.sorted_colour_sets:
 279                 k = 'utf8 %s, colour %s' % (utf8, colour)
 280                 s = graph.distance_matrix(None, edges, utf8=utf8,
 281                                           colour=colour)
 282                 self.assertStringsEqual(s, expected[k], strip=True,
 283                                         msg='Wrong output: %s\n\n%s' % (k, s))
 284
 285     def test_simple_distance2(self):
 286         edges = [('ant', 'bat'),
 287                  ('cat', 'bat'),
 288                  ('bat', 'ant'),
 289                  ('ant', 'cat')]
 290         expected = {
 291             'utf8 True, colour None': '''
 292             destination
 293        ╭─── ant
 294        │╭── bat
 295 source ││╭─ cat
 296    ant ·11
 297    bat 1·2
 298    cat 21·
 299             ''',
 300             'utf8 True, colour ansi': '''
 301             \e[4mdestination\e[0m
 302        \e[0m\e[37m╭─── ant\e[0m
 303        \e[37m│\e[0m\e[1;30m╭── bat\e[0m
 304 \e[4msource\e[0m \e[37m│\e[1;30m│\e[0m\e[37m╭─ cat\e[0m
 305 \e[37m   ant\e[0m \e[0m\e[37m·\e[0m\e[1;32m1\e[0m\e[1;32m1\e[0m\e[0m
 306 \e[1;30m   bat\e[0m \e[1;32m1\e[0m\e[0m\e[1;30m·\e[0m\e[33m2\e[0m\e[0m
 307 \e[37m   cat\e[0m \e[33m2\e[0m\e[1;32m1\e[0m\e[0m\e[37m·\e[0m\e[0m
 308             ''',
 309             'utf8 True, colour ansi-heatmap': '''
 310             \e[4mdestination\e[0m
 311        \e[0m\e[37m╭─── ant\e[0m
 312        \e[37m│\e[0m\e[1;30m╭── bat\e[0m
 313 \e[4msource\e[0m \e[37m│\e[1;30m│\e[0m\e[37m╭─ cat\e[0m
 314 \e[37m   ant\e[0m \e[0m\e[37m·\e[0m\e[1;42m1\e[0m\e[1;42m1\e[0m\e[0m
 315 \e[1;30m   bat\e[0m \e[1;42m1\e[0m\e[0m\e[1;30m·\e[0m\e[43m2\e[0m\e[0m
 316 \e[37m   cat\e[0m \e[43m2\e[0m\e[1;42m1\e[0m\e[0m\e[37m·\e[0m\e[0m
 317         ''',
 318             'utf8 True, colour xterm-256color': '''
 319             \e[4mdestination\e[0m
 320        \e[0m\e[38;5;39m╭─── ant\e[0m
 321        \e[38;5;39m│\e[0m\e[38;5;45m╭── bat\e[0m
 322 \e[4msource\e[0m \e[38;5;39m│\e[38;5;45m│\e[0m\e[38;5;39m╭─ cat\e[0m
 323 \e[38;5;39m   ant\e[0m \e[0m\e[38;5;39m·\e[0m\e[38;5;112m1\e[0m\e[38;5;112m1\e[0m\e[0m
 324 \e[38;5;45m   bat\e[0m \e[38;5;112m1\e[0m\e[0m\e[38;5;45m·\e[0m\e[38;5;208m2\e[0m\e[0m
 325 \e[38;5;39m   cat\e[0m \e[38;5;208m2\e[0m\e[38;5;112m1\e[0m\e[0m\e[38;5;39m·\e[0m\e[0m
 326 ''',
 327             'utf8 True, colour xterm-256color-heatmap': '''
 328             \e[4mdestination\e[0m
 329        \e[0m\e[38;5;171m╭─── ant\e[0m
 330        \e[38;5;171m│\e[0m\e[38;5;207m╭── bat\e[0m
 331 \e[4msource\e[0m \e[38;5;171m│\e[38;5;207m│\e[0m\e[38;5;171m╭─ cat\e[0m
 332 \e[38;5;171m   ant\e[0m \e[0m\e[38;5;171m·\e[0m\e[48;5;112m1\e[0m\e[48;5;112m1\e[0m\e[0m
 333 \e[38;5;207m   bat\e[0m \e[48;5;112m1\e[0m\e[0m\e[38;5;207m·\e[0m\e[48;5;208m2\e[0m\e[0m
 334 \e[38;5;171m   cat\e[0m \e[48;5;208m2\e[0m\e[48;5;112m1\e[0m\e[0m\e[38;5;171m·\e[0m\e[0m
 335 ''',
 336             'utf8 False, colour None': '''
 337             destination
 338        ,--- ant
 339        |,-- bat
 340 source ||,- cat
 341    ant 011
 342    bat 102
 343    cat 210
 344 ''',
 345             'utf8 False, colour ansi': '''
 346             \e[4mdestination\e[0m
 347        \e[0m\e[37m,--- ant\e[0m
 348        \e[37m|\e[0m\e[1;30m,-- bat\e[0m
 349 \e[4msource\e[0m \e[37m|\e[1;30m|\e[0m\e[37m,- cat\e[0m
 350 \e[37m   ant\e[0m \e[0m\e[37m0\e[0m\e[1;32m1\e[0m\e[1;32m1\e[0m\e[0m
 351 \e[1;30m   bat\e[0m \e[1;32m1\e[0m\e[0m\e[1;30m0\e[0m\e[33m2\e[0m\e[0m
 352 \e[37m   cat\e[0m \e[33m2\e[0m\e[1;32m1\e[0m\e[0m\e[37m0\e[0m\e[0m
 353 ''',
 354             'utf8 False, colour ansi-heatmap': '''
 355             \e[4mdestination\e[0m
 356        \e[0m\e[37m,--- ant\e[0m
 357        \e[37m|\e[0m\e[1;30m,-- bat\e[0m
 358 \e[4msource\e[0m \e[37m|\e[1;30m|\e[0m\e[37m,- cat\e[0m
 359 \e[37m   ant\e[0m \e[0m\e[37m0\e[0m\e[1;42m1\e[0m\e[1;42m1\e[0m\e[0m
 360 \e[1;30m   bat\e[0m \e[1;42m1\e[0m\e[0m\e[1;30m0\e[0m\e[43m2\e[0m\e[0m
 361 \e[37m   cat\e[0m \e[43m2\e[0m\e[1;42m1\e[0m\e[0m\e[37m0\e[0m\e[0m
 362 ''',
 363             'utf8 False, colour xterm-256color': '''
 364             \e[4mdestination\e[0m
 365        \e[0m\e[38;5;39m,--- ant\e[0m
 366        \e[38;5;39m|\e[0m\e[38;5;45m,-- bat\e[0m
 367 \e[4msource\e[0m \e[38;5;39m|\e[38;5;45m|\e[0m\e[38;5;39m,- cat\e[0m
 368 \e[38;5;39m   ant\e[0m \e[0m\e[38;5;39m0\e[0m\e[38;5;112m1\e[0m\e[38;5;112m1\e[0m\e[0m
 369 \e[38;5;45m   bat\e[0m \e[38;5;112m1\e[0m\e[0m\e[38;5;45m0\e[0m\e[38;5;208m2\e[0m\e[0m
 370 \e[38;5;39m   cat\e[0m \e[38;5;208m2\e[0m\e[38;5;112m1\e[0m\e[0m\e[38;5;39m0\e[0m\e[0m
 371 ''',
 372             'utf8 False, colour xterm-256color-heatmap': '''
 373             \e[4mdestination\e[0m
 374        \e[0m\e[38;5;171m,--- ant\e[0m
 375        \e[38;5;171m|\e[0m\e[38;5;207m,-- bat\e[0m
 376 \e[4msource\e[0m \e[38;5;171m|\e[38;5;207m|\e[0m\e[38;5;171m,- cat\e[0m
 377 \e[38;5;171m   ant\e[0m \e[0m\e[38;5;171m0\e[0m\e[48;5;112m1\e[0m\e[48;5;112m1\e[0m\e[0m
 378 \e[38;5;207m   bat\e[0m \e[48;5;112m1\e[0m\e[0m\e[38;5;207m0\e[0m\e[48;5;208m2\e[0m\e[0m
 379 \e[38;5;171m   cat\e[0m \e[48;5;208m2\e[0m\e[48;5;112m1\e[0m\e[0m\e[38;5;171m0\e[0m\e[0m
 380 '''
 381         }
 382         for utf8 in (True, False):
 383             for colour in self.sorted_colour_sets:
 384                 k = 'utf8 %s, colour %s' % (utf8, colour)
 385                 s = graph.distance_matrix(None, edges, utf8=utf8,
 386                                           colour=colour)
 387                 self.assertStringsEqual(s, expected[k], strip=True,
 388                                         msg='Wrong output: %s\n\n%s' % (k, s))
 389
 390     def test_simple_distance3(self):
 391         edges = [('ant', 'bat'),
 392                  ('bat', 'cat'),
 393                  ('cat', 'dog'),
 394                  ('dog', 'ant'),
 395                  ('dog', 'eel')]
 396         expected = {
 397             'utf8 True, colour None': '''
 398               destination
 399        ╭───── ant
 400        │╭──── bat
 401        ││╭─── cat
 402        │││╭── dog
 403 source ││││╭─ eel
 404    ant ·1234
 405    bat 3·123
 406    cat 23·12
 407    dog 123·1
 408    eel ----·
 409 ''',
 410             'utf8 True, colour ansi': '''
 411               \e[4mdestination\e[0m
 412        \e[0m\e[37m╭───── ant\e[0m
 413        \e[37m│\e[0m\e[1;30m╭──── bat\e[0m
 414        \e[37m│\e[1;30m│\e[0m\e[37m╭─── cat\e[0m
 415        \e[37m│\e[1;30m│\e[37m│\e[0m\e[1;30m╭── dog\e[0m
 416 \e[4msource\e[0m \e[37m│\e[1;30m│\e[37m│\e[1;30m│\e[0m\e[37m╭─ eel\e[0m
 417 \e[37m   ant\e[0m \e[0m\e[37m·\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[33m3\e[0m\e[33m4\e[0m\e[0m
 418 \e[1;30m   bat\e[0m \e[33m3\e[0m\e[0m\e[1;30m·\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[33m3\e[0m\e[0m
 419 \e[37m   cat\e[0m \e[33m2\e[0m\e[33m3\e[0m\e[0m\e[37m·\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[0m
 420 \e[1;30m   dog\e[0m \e[1;32m1\e[0m\e[33m2\e[0m\e[33m3\e[0m\e[0m\e[1;30m·\e[0m\e[1;32m1\e[0m\e[0m
 421 \e[37m   eel\e[0m \e[1;31m-\e[1;31m-\e[1;31m-\e[1;31m-\e[0m\e[37m·\e[0m\e[0m
 422 ''',
 423             'utf8 True, colour ansi-heatmap': '''
 424               \e[4mdestination\e[0m
 425        \e[0m\e[37m╭───── ant\e[0m
 426        \e[37m│\e[0m\e[1;30m╭──── bat\e[0m
 427        \e[37m│\e[1;30m│\e[0m\e[37m╭─── cat\e[0m
 428        \e[37m│\e[1;30m│\e[37m│\e[0m\e[1;30m╭── dog\e[0m
 429 \e[4msource\e[0m \e[37m│\e[1;30m│\e[37m│\e[1;30m│\e[0m\e[37m╭─ eel\e[0m
 430 \e[37m   ant\e[0m \e[0m\e[37m·\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[43m3\e[0m\e[43m4\e[0m\e[0m
 431 \e[1;30m   bat\e[0m \e[43m3\e[0m\e[0m\e[1;30m·\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[43m3\e[0m\e[0m
 432 \e[37m   cat\e[0m \e[43m2\e[0m\e[43m3\e[0m\e[0m\e[37m·\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[0m
 433 \e[1;30m   dog\e[0m \e[1;42m1\e[0m\e[43m2\e[0m\e[43m3\e[0m\e[0m\e[1;30m·\e[0m\e[1;42m1\e[0m\e[0m
 434 \e[37m   eel\e[0m \e[1;41m-\e[1;41m-\e[1;41m-\e[1;41m-\e[0m\e[37m·\e[0m\e[0m
 435 ''',
 436             'utf8 True, colour xterm-256color': '''
 437               \e[4mdestination\e[0m
 438        \e[0m\e[38;5;39m╭───── ant\e[0m
 439        \e[38;5;39m│\e[0m\e[38;5;45m╭──── bat\e[0m
 440        \e[38;5;39m│\e[38;5;45m│\e[0m\e[38;5;39m╭─── cat\e[0m
 441        \e[38;5;39m│\e[38;5;45m│\e[38;5;39m│\e[0m\e[38;5;45m╭── dog\e[0m
 442 \e[4msource\e[0m \e[38;5;39m│\e[38;5;45m│\e[38;5;39m│\e[38;5;45m│\e[0m\e[38;5;39m╭─ eel\e[0m
 443 \e[38;5;39m   ant\e[0m \e[0m\e[38;5;39m·\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[38;5;208m4\e[0m\e[0m
 444 \e[38;5;45m   bat\e[0m \e[38;5;208m3\e[0m\e[0m\e[38;5;45m·\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[0m
 445 \e[38;5;39m   cat\e[0m \e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[0m\e[38;5;39m·\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[0m
 446 \e[38;5;45m   dog\e[0m \e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[0m\e[38;5;45m·\e[0m\e[38;5;112m1\e[0m\e[0m
 447 \e[38;5;39m   eel\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;39m·\e[0m\e[0m
 448 ''',
 449             'utf8 True, colour xterm-256color-heatmap': '''
 450               \e[4mdestination\e[0m
 451        \e[0m\e[38;5;171m╭───── ant\e[0m
 452        \e[38;5;171m│\e[0m\e[38;5;207m╭──── bat\e[0m
 453        \e[38;5;171m│\e[38;5;207m│\e[0m\e[38;5;171m╭─── cat\e[0m
 454        \e[38;5;171m│\e[38;5;207m│\e[38;5;171m│\e[0m\e[38;5;207m╭── dog\e[0m
 455 \e[4msource\e[0m \e[38;5;171m│\e[38;5;207m│\e[38;5;171m│\e[38;5;207m│\e[0m\e[38;5;171m╭─ eel\e[0m
 456 \e[38;5;171m   ant\e[0m \e[0m\e[38;5;171m·\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[48;5;208m4\e[0m\e[0m
 457 \e[38;5;207m   bat\e[0m \e[48;5;208m3\e[0m\e[0m\e[38;5;207m·\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[0m
 458 \e[38;5;171m   cat\e[0m \e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[0m\e[38;5;171m·\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[0m
 459 \e[38;5;207m   dog\e[0m \e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[0m\e[38;5;207m·\e[0m\e[48;5;112m1\e[0m\e[0m
 460 \e[38;5;171m   eel\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;171m·\e[0m\e[0m
 461 ''',
 462             'utf8 False, colour None': '''
 463               destination
 464        ,----- ant
 465        |,---- bat
 466        ||,--- cat
 467        |||,-- dog
 468 source ||||,- eel
 469    ant 01234
 470    bat 30123
 471    cat 23012
 472    dog 12301
 473    eel ----0
 474 ''',
 475             'utf8 False, colour ansi': '''
 476               \e[4mdestination\e[0m
 477        \e[0m\e[37m,----- ant\e[0m
 478        \e[37m|\e[0m\e[1;30m,---- bat\e[0m
 479        \e[37m|\e[1;30m|\e[0m\e[37m,--- cat\e[0m
 480        \e[37m|\e[1;30m|\e[37m|\e[0m\e[1;30m,-- dog\e[0m
 481 \e[4msource\e[0m \e[37m|\e[1;30m|\e[37m|\e[1;30m|\e[0m\e[37m,- eel\e[0m
 482 \e[37m   ant\e[0m \e[0m\e[37m0\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[33m3\e[0m\e[33m4\e[0m\e[0m
 483 \e[1;30m   bat\e[0m \e[33m3\e[0m\e[0m\e[1;30m0\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[33m3\e[0m\e[0m
 484 \e[37m   cat\e[0m \e[33m2\e[0m\e[33m3\e[0m\e[0m\e[37m0\e[0m\e[1;32m1\e[0m\e[33m2\e[0m\e[0m
 485 \e[1;30m   dog\e[0m \e[1;32m1\e[0m\e[33m2\e[0m\e[33m3\e[0m\e[0m\e[1;30m0\e[0m\e[1;32m1\e[0m\e[0m
 486 \e[37m   eel\e[0m \e[1;31m-\e[1;31m-\e[1;31m-\e[1;31m-\e[0m\e[37m0\e[0m\e[0m
 487 ''',
 488             'utf8 False, colour ansi-heatmap': '''
 489               \e[4mdestination\e[0m
 490        \e[0m\e[37m,----- ant\e[0m
 491        \e[37m|\e[0m\e[1;30m,---- bat\e[0m
 492        \e[37m|\e[1;30m|\e[0m\e[37m,--- cat\e[0m
 493        \e[37m|\e[1;30m|\e[37m|\e[0m\e[1;30m,-- dog\e[0m
 494 \e[4msource\e[0m \e[37m|\e[1;30m|\e[37m|\e[1;30m|\e[0m\e[37m,- eel\e[0m
 495 \e[37m   ant\e[0m \e[0m\e[37m0\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[43m3\e[0m\e[43m4\e[0m\e[0m
 496 \e[1;30m   bat\e[0m \e[43m3\e[0m\e[0m\e[1;30m0\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[43m3\e[0m\e[0m
 497 \e[37m   cat\e[0m \e[43m2\e[0m\e[43m3\e[0m\e[0m\e[37m0\e[0m\e[1;42m1\e[0m\e[43m2\e[0m\e[0m
 498 \e[1;30m   dog\e[0m \e[1;42m1\e[0m\e[43m2\e[0m\e[43m3\e[0m\e[0m\e[1;30m0\e[0m\e[1;42m1\e[0m\e[0m
 499 \e[37m   eel\e[0m \e[1;41m-\e[1;41m-\e[1;41m-\e[1;41m-\e[0m\e[37m0\e[0m\e[0m
 500 ''',
 501             'utf8 False, colour xterm-256color':
 502             '''              \e[4mdestination\e[0m
 503        \e[0m\e[38;5;39m,----- ant\e[0m
 504        \e[38;5;39m|\e[0m\e[38;5;45m,---- bat\e[0m
 505        \e[38;5;39m|\e[38;5;45m|\e[0m\e[38;5;39m,--- cat\e[0m
 506        \e[38;5;39m|\e[38;5;45m|\e[38;5;39m|\e[0m\e[38;5;45m,-- dog\e[0m
 507 \e[4msource\e[0m \e[38;5;39m|\e[38;5;45m|\e[38;5;39m|\e[38;5;45m|\e[0m\e[38;5;39m,- eel\e[0m
 508 \e[38;5;39m   ant\e[0m \e[0m\e[38;5;39m0\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[38;5;208m4\e[0m\e[0m
 509 \e[38;5;45m   bat\e[0m \e[38;5;208m3\e[0m\e[0m\e[38;5;45m0\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[0m
 510 \e[38;5;39m   cat\e[0m \e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[0m\e[38;5;39m0\e[0m\e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[0m
 511 \e[38;5;45m   dog\e[0m \e[38;5;112m1\e[0m\e[38;5;214m2\e[0m\e[38;5;208m3\e[0m\e[0m\e[38;5;45m0\e[0m\e[38;5;112m1\e[0m\e[0m
 512 \e[38;5;39m   eel\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;39m0\e[0m\e[0m
 513 ''',
 514             'utf8 False, colour xterm-256color-heatmap': '''
 515               \e[4mdestination\e[0m
 516        \e[0m\e[38;5;171m,----- ant\e[0m
 517        \e[38;5;171m|\e[0m\e[38;5;207m,---- bat\e[0m
 518        \e[38;5;171m|\e[38;5;207m|\e[0m\e[38;5;171m,--- cat\e[0m
 519        \e[38;5;171m|\e[38;5;207m|\e[38;5;171m|\e[0m\e[38;5;207m,-- dog\e[0m
 520 \e[4msource\e[0m \e[38;5;171m|\e[38;5;207m|\e[38;5;171m|\e[38;5;207m|\e[0m\e[38;5;171m,- eel\e[0m
 521 \e[38;5;171m   ant\e[0m \e[0m\e[38;5;171m0\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[48;5;208m4\e[0m\e[0m
 522 \e[38;5;207m   bat\e[0m \e[48;5;208m3\e[0m\e[0m\e[38;5;207m0\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[0m
 523 \e[38;5;171m   cat\e[0m \e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[0m\e[38;5;171m0\e[0m\e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[0m
 524 \e[38;5;207m   dog\e[0m \e[48;5;112m1\e[0m\e[48;5;214m2\e[0m\e[48;5;208m3\e[0m\e[0m\e[38;5;207m0\e[0m\e[48;5;112m1\e[0m\e[0m
 525 \e[38;5;171m   eel\e[0m \e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[48;5;124m-\e[0m\e[38;5;171m0\e[0m\e[0m
 526 '''
 527         }
 528         for utf8 in (True, False):
 529             for colour in self.sorted_colour_sets:
 530                 k = 'utf8 %s, colour %s' % (utf8, colour)
 531                 s = graph.distance_matrix(None, edges, utf8=utf8,
 532                                           colour=colour)
 533                 self.assertStringsEqual(s, expected[k], strip=True,
 534                                         msg='Wrong output: %s\n\n%s' % (k, s))