johnson_test.go

Documentation: gonum.org/v1/plot/plotter

     1  // Copyright ©2015 The Gonum Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package plotter
     6  
     7  import (
     8  	"fmt"
     9  	"reflect"
    10  	"sort"
    11  	"testing"
    12  )
    13  
    14  func linksTo(i ...int) set {
    15  	if len(i) == 0 {
    16  		return nil
    17  	}
    18  	s := make(set)
    19  	for _, v := range i {
    20  		s[v] = struct{}{}
    21  	}
    22  	return s
    23  }
    24  
    25  func (s set) String() string {
    26  	a := make([]int, 0, len(s))
    27  	for v := range s {
    28  		a = append(a, v)
    29  	}
    30  	sort.Ints(a)
    31  	return fmt.Sprint(a)
    32  }
    33  
    34  var graphTests = []struct {
    35  	path path
    36  	g    graph
    37  
    38  	// Tarjan tests.
    39  	orderIsAmbiguous bool
    40  	wantSCCs         [][]int
    41  	wantAdj          graph
    42  
    43  	// Johnson tests.
    44  	wantCycles     [][]int
    45  	wantCyclePaths []path
    46  }{
    47  	{
    48  		path: path{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {7, 7}, {8, 8}, {9, 9}},
    49  
    50  		wantSCCs: [][]int{{9}, {8}, {7}, {6}, {5}, {4}, {3}, {2}, {1}, {0}},
    51  		wantAdj:  nil,
    52  
    53  		wantCycles:     nil,
    54  		wantCyclePaths: nil,
    55  	},
    56  	{
    57  		path: path{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {4, 4}, {7, 7}, {8, 8}, {9, 9}},
    58  
    59  		wantSCCs: [][]int{
    60  			{10}, {9}, {8},
    61  			{4, 5, 6},
    62  			{3}, {2}, {1}, {0},
    63  			{7 /*second point{4, 4}*/},
    64  		},
    65  		wantAdj: graph{
    66  			4:  linksTo(5),
    67  			5:  linksTo(6),
    68  			6:  linksTo(4),
    69  			10: nil,
    70  		},
    71  
    72  		wantCycles: [][]int{
    73  			{4, 5, 6, 4},
    74  		},
    75  		wantCyclePaths: []path{
    76  			{{4, 4}, {5, 5}, {6, 6}, {4, 4}},
    77  		},
    78  	},
    79  	{
    80  		path: path{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {4, 4}, {7, 7}, {2, 2}, {9, 9}},
    81  
    82  		wantSCCs: [][]int{
    83  			{10},
    84  			{2, 3, 4, 5, 6, 8},
    85  			{1}, {0},
    86  			{7 /*second point{4, 4}*/},
    87  			{9 /*second point{2, 2}*/},
    88  		},
    89  		wantAdj: graph{
    90  			2:  linksTo(3),
    91  			3:  linksTo(4),
    92  			4:  linksTo(5, 8),
    93  			5:  linksTo(6),
    94  			6:  linksTo(4),
    95  			8:  linksTo(2),
    96  			10: nil,
    97  		},
    98  
    99  		wantCycles: [][]int{
   100  			{4, 5, 6, 4},
   101  			{2, 3, 4, 8, 2},
   102  		},
   103  		wantCyclePaths: []path{
   104  			{{4, 4}, {5, 5}, {6, 6}, {4, 4}},
   105  			{{2, 2}, {3, 3}, {4, 4}, {7, 7}, {2, 2}},
   106  		},
   107  	},
   108  	{
   109  		path: path{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {2, 2}, {7, 7}, {2, 2}, {9, 9}},
   110  
   111  		wantSCCs: [][]int{{9},
   112  			{2, 3, 4, 5, 7},
   113  			{1}, {0},
   114  			{6 /*second point{2, 2}*/},
   115  			{8 /*third point{2, 2}*/},
   116  		},
   117  		wantAdj: graph{
   118  			2: linksTo(3, 7),
   119  			3: linksTo(4),
   120  			4: linksTo(5),
   121  			5: linksTo(2),
   122  			7: linksTo(2),
   123  			9: nil,
   124  		},
   125  
   126  		wantCycles: [][]int{
   127  			{2, 7, 2},
   128  			{2, 3, 4, 5, 2},
   129  		},
   130  		wantCyclePaths: []path{
   131  			{{2, 2}, {7, 7}, {2, 2}},
   132  			{{2, 2}, {3, 3}, {4, 4}, {5, 5}, {2, 2}},
   133  		},
   134  	},
   135  	{
   136  		path: path{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}, {6, 6}, {3, 3}, {8, 8}, {9, 9}, {5, 5}, {10, 10}},
   137  
   138  		wantSCCs: [][]int{
   139  			{11},
   140  			{3, 4, 5, 6, 8, 9},
   141  			{2}, {1}, {0},
   142  			{7 /*second point{4, 4}*/},
   143  			{10 /*second point{2, 2}*/},
   144  		},
   145  		wantAdj: graph{
   146  			3:  linksTo(4, 8),
   147  			4:  linksTo(5),
   148  			5:  linksTo(6),
   149  			6:  linksTo(3),
   150  			8:  linksTo(9),
   151  			9:  linksTo(5),
   152  			11: nil,
   153  		},
   154  
   155  		wantCycles: [][]int{
   156  			{3, 4, 5, 6, 3},
   157  			{3, 8, 9, 5, 6, 3},
   158  		},
   159  		wantCyclePaths: []path{
   160  			{{3, 3}, {4, 4}, {5, 5}, {6, 6}, {3, 3}},
   161  			{{3, 3}, {8, 8}, {9, 9}, {5, 5}, {6, 6}, {3, 3}},
   162  		},
   163  	},
   164  	{
   165  		path: path{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {0, 0}, {5, 5}, {6, 6}, {7, 7}, {5, 5}, {9, 9}, {10, 10}, {9, 9}},
   166  
   167  		wantSCCs: [][]int{
   168  			{9, 10},
   169  			{5, 6, 7},
   170  			{0, 1, 2, 3},
   171  			{4 /*second point{0, 0}*/},
   172  			{8 /*second point{5, 5}*/},
   173  			{11 /*second point{9, 9}*/},
   174  		},
   175  		wantAdj: graph{
   176  			0:  linksTo(1),
   177  			1:  linksTo(2),
   178  			2:  linksTo(3),
   179  			3:  linksTo(0),
   180  			5:  linksTo(6),
   181  			6:  linksTo(7),
   182  			7:  linksTo(5),
   183  			9:  linksTo(10),
   184  			10: linksTo(9),
   185  			11: nil,
   186  		},
   187  
   188  		wantCycles: [][]int{
   189  			{9, 10, 9},
   190  			{5, 6, 7, 5},
   191  			{0, 1, 2, 3, 0},
   192  		},
   193  		wantCyclePaths: []path{
   194  			{{9, 9}, {10, 10}, {9, 9}},
   195  			{{5, 5}, {6, 6}, {7, 7}, {5, 5}},
   196  			{{0, 0}, {1, 1}, {2, 2}, {3, 3}, {0, 0}},
   197  		},
   198  	},
   199  
   200  	{
   201  		g: graph{
   202  			0: linksTo(1),
   203  			1: linksTo(2, 7),
   204  			2: linksTo(3, 6),
   205  			3: linksTo(4),
   206  			4: linksTo(2, 5),
   207  			6: linksTo(3, 5),
   208  			7: linksTo(0, 6),
   209  		},
   210  
   211  		wantSCCs: [][]int{
   212  			{5},
   213  			{2, 3, 4, 6},
   214  			{0, 1, 7},
   215  		},
   216  		wantAdj: graph{
   217  			0: linksTo(1),
   218  			1: linksTo(7),
   219  			2: linksTo(3, 6),
   220  			3: linksTo(4),
   221  			4: linksTo(2),
   222  			6: linksTo(3),
   223  			7: linksTo(0),
   224  		},
   225  
   226  		wantCycles: [][]int{
   227  			{0, 1, 7, 0},
   228  			{2, 3, 4, 2},
   229  			{2, 6, 3, 4, 2},
   230  		},
   231  	},
   232  	{
   233  		g: graph{
   234  			0: linksTo(1, 2, 3),
   235  			1: linksTo(2),
   236  			2: linksTo(3),
   237  			3: linksTo(1),
   238  		},
   239  
   240  		wantSCCs: [][]int{
   241  			{1, 2, 3},
   242  			{0},
   243  		},
   244  		wantAdj: graph{
   245  			1: linksTo(2),
   246  			2: linksTo(3),
   247  			3: linksTo(1),
   248  		},
   249  
   250  		wantCycles: [][]int{
   251  			{1, 2, 3, 1},
   252  		},
   253  	},
   254  	{
   255  		g: graph{
   256  			0: linksTo(1),
   257  			1: linksTo(0, 2),
   258  			2: linksTo(1),
   259  		},
   260  
   261  		wantSCCs: [][]int{
   262  			{0, 1, 2},
   263  		},
   264  		wantAdj: graph{
   265  			0: linksTo(1),
   266  			1: linksTo(0, 2),
   267  			2: linksTo(1),
   268  		},
   269  
   270  		wantCycles: [][]int{
   271  			{0, 1, 0},
   272  			{1, 2, 1},
   273  		},
   274  	},
   275  	{
   276  		g: graph{
   277  			0: linksTo(1),
   278  			1: linksTo(2, 3),
   279  			2: linksTo(4, 5),
   280  			3: linksTo(4, 5),
   281  			4: linksTo(6),
   282  			5: nil,
   283  			6: nil,
   284  		},
   285  
   286  		orderIsAmbiguous: true,
   287  		wantSCCs: [][]int{
   288  			// Node pairs (2, 3) and (4, 5) are not
   289  			// relatively orderable within each pair.
   290  			{6}, {5}, {4}, {3}, {2}, {1}, {0},
   291  		},
   292  		wantAdj: nil,
   293  
   294  		wantCycles: nil,
   295  	},
   296  	{
   297  		g: graph{
   298  			0: linksTo(1),
   299  			1: linksTo(2, 3, 4),
   300  			2: linksTo(0, 3),
   301  			3: linksTo(4),
   302  			4: linksTo(3),
   303  		},
   304  
   305  		orderIsAmbiguous: true,
   306  		wantSCCs: [][]int{
   307  			// SCCs are not relatively ordable.
   308  			{3, 4}, {0, 1, 2},
   309  		},
   310  		wantAdj: graph{
   311  			0: linksTo(1),
   312  			1: linksTo(2),
   313  			2: linksTo(0),
   314  			3: linksTo(4),
   315  			4: linksTo(3),
   316  		},
   317  
   318  		wantCycles: [][]int{
   319  			{3, 4, 3},
   320  			{0, 1, 2, 0},
   321  		},
   322  	},
   323  }
   324  
   325  func TestTarjan(t *testing.T) {
   326  	for i, test := range graphTests {
   327  		var g graph
   328  		if test.path != nil {
   329  			g = graphFrom(test.path)
   330  		} else {
   331  			g = test.g
   332  		}
   333  		tar := newTarjan(g)
   334  		gotSCCs := tar.sccs
   335  		if test.orderIsAmbiguous {
   336  			// We lose topological order here, but that
   337  			// is not important for this use case.
   338  			sort.Sort(byComponentLengthOrStart(test.wantSCCs))
   339  			sort.Sort(byComponentLengthOrStart(gotSCCs))
   340  		}
   341  		// tarjan.strongconnect does range iteration over maps,
   342  		// so sort SCC members to ensure consistent ordering.
   343  		for _, scc := range gotSCCs {
   344  			sort.Ints(scc)
   345  		}
   346  		if !reflect.DeepEqual(gotSCCs, test.wantSCCs) {
   347  			t.Errorf("unexpected tarjan scc result for %d:\n\tgot:%v\n\twant:%v", i, gotSCCs, test.wantSCCs)
   348  		}
   349  		gotAdj := tar.sccSubGraph(2)
   350  		if !reflect.DeepEqual(gotAdj, test.wantAdj) {
   351  			t.Errorf("unexpected tarjan sccSubGraph(2) result for %d:\n\tgot:%#v\n\twant:%#v", i, gotAdj, test.wantAdj)
   352  		}
   353  	}
   354  }
   355  
   356  func TestJohnson(t *testing.T) {
   357  	for i, test := range graphTests {
   358  		var g graph
   359  		if test.path != nil {
   360  			g = graphFrom(test.path)
   361  		} else {
   362  			g = test.g
   363  		}
   364  		gotCycles := cyclesIn(g)
   365  		// johnson.circuit does range iteration over maps,
   366  		// so sort to ensure consistent ordering.
   367  		sort.Sort(byComponentLengthOrStart(gotCycles))
   368  		if !reflect.DeepEqual(gotCycles, test.wantCycles) {
   369  			t.Errorf("unexpected johnson result for %d:\n\tgot:%#v\n\twant:%#v", i, gotCycles, test.wantCycles)
   370  		}
   371  
   372  		// Don't do path reconstruction tests without a path definition.
   373  		if test.path == nil {
   374  			continue
   375  		}
   376  
   377  		// Test we reconstruct paths correctly from cycles.
   378  		var gotPaths []path
   379  		for _, pi := range gotCycles {
   380  			gotPaths = append(gotPaths, test.path.subpath(pi))
   381  		}
   382  		if !reflect.DeepEqual(gotPaths, test.wantCyclePaths) {
   383  			t.Errorf("unexpected johnson path result for %d:\n\tgot:%#v\n\twant:%#v", i, gotPaths, test.wantCyclePaths)
   384  		}
   385  	}
   386  }
   387  
   388  type byComponentLengthOrStart [][]int
   389  
   390  func (c byComponentLengthOrStart) Len() int { return len(c) }
   391  func (c byComponentLengthOrStart) Less(i, j int) bool {
   392  	return len(c[i]) < len(c[j]) || (len(c[i]) == len(c[j]) && c[i][0] < c[j][0])
   393  }
   394  func (c byComponentLengthOrStart) Swap(i, j int) { c[i], c[j] = c[j], c[i] }
   395
View as plain text