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