| OLD | NEW |
|---|
| (Empty) | |
| 1 package utils |
| 2 |
| 3 import ( |
| 4 "bytes" |
| 5 "fmt" |
| 6 "strings" |
| 7 "testing" |
| 8 ) |
| 9 |
| 10 //////////////////////////////////////////////////// |
| 11 // SimpleNode type |
| 12 //////////////////////////////////////////////////// |
| 13 |
| 14 // SimpleNode is a simple implementation of the |Node| interface used |
| 15 // for testing. |
| 16 type SimpleNode struct { |
| 17 // The value of this node |
| 18 value int |
| 19 |
| 20 // Is this node a square node? |
| 21 isSquare bool |
| 22 |
| 23 // The list of out-edges. The elements will be *SimpleNodes. |
| 24 edges []Node |
| 25 |
| 26 // Cache the fact that |SetKnownWellFounded| has been invoked. |
| 27 knownWellFounded bool |
| 28 } |
| 29 |
| 30 func (node *SimpleNode) DebugName() string { |
| 31 return fmt.Sprintf("Node%d", node.value) |
| 32 } |
| 33 |
| 34 func (node *SimpleNode) OutEdges() []Node { |
| 35 return node.edges |
| 36 } |
| 37 |
| 38 func (node *SimpleNode) IsSquare() bool { |
| 39 return node.isSquare |
| 40 } |
| 41 |
| 42 func (node *SimpleNode) KnownWellFounded() bool { |
| 43 return node.knownWellFounded |
| 44 } |
| 45 |
| 46 func (node *SimpleNode) SetKnownWellFounded() { |
| 47 if node.knownWellFounded { |
| 48 panic(fmt.Sprintf("SetKnownWellFounded invoked twice on %s", nod
e.DebugName())) |
| 49 } |
| 50 node.knownWellFounded = true |
| 51 } |
| 52 |
| 53 //Creates a new SimpleNode. |
| 54 func NewNode(value, numEdges int, isSquare bool) *SimpleNode { |
| 55 node := new(SimpleNode) |
| 56 node.value = value |
| 57 node.edges = make([]Node, numEdges) |
| 58 node.isSquare = isSquare |
| 59 return node |
| 60 } |
| 61 |
| 62 //////////////////////////////////////////////////// |
| 63 // Test Utilities |
| 64 //////////////////////////////////////////////////// |
| 65 |
| 66 // Builds a test graph containing only circle nodes. |
| 67 // The connection matrix should have the following form: |
| 68 // connectionMatrix[i][j] = k indicates that there is an edge in the graph |
| 69 // from Node i to Node K. k must be less than len(connectionMatrix). |
| 70 func buildCircleTestGraph(connectionMatrix [][]int) (nodes []*SimpleNode) { |
| 71 return buildTestGraph(connectionMatrix, nil) |
| 72 } |
| 73 |
| 74 // Builds a test graph. The connection matrix should have the following form: |
| 75 // connectionMatrix[i][j] = k indicates that there is an edge in the graph |
| 76 // from Node i to Node K. k must be less than len(connectionMatrix). |
| 77 // If |squares| is not nil then it must contain the list of indices of the nodes
that are squares. |
| 78 func buildTestGraph(connectionMatrix [][]int, squares []int) (nodes []*SimpleNod
e) { |
| 79 squareMap := make(map[int]bool) |
| 80 if squares != nil { |
| 81 for _, n := range squares { |
| 82 squareMap[n] = true |
| 83 } |
| 84 } |
| 85 nodes = make([]*SimpleNode, len(connectionMatrix)) |
| 86 for index, connectionList := range connectionMatrix { |
| 87 _, isSquare := squareMap[index] |
| 88 nodes[index] = NewNode(index, len(connectionList), isSquare) |
| 89 } |
| 90 for index, connectionList := range connectionMatrix { |
| 91 for i, target := range connectionList { |
| 92 nodes[index].edges[i] = nodes[target] |
| 93 } |
| 94 } |
| 95 return |
| 96 } |
| 97 |
| 98 // expectedDebugData is used to store an expectation for the value of the |debug
Data| populated |
| 99 // by the ethod |checkWellFounded|. This data captures the result of phase 1 of
the algorithm. |
| 100 type expectedDebugData struct { |
| 101 initialPendingSet []string |
| 102 initialFoundationSet []string |
| 103 } |
| 104 |
| 105 func compareDebugData(expected *expectedDebugData, actual *debugData) error { |
| 106 if expected == nil { |
| 107 panic("expected cannot be nil") |
| 108 return nil |
| 109 } |
| 110 if err := compareNodeSlice(expected.initialPendingSet, actual.initialPen
dingSet, "initialPendingSet"); err != nil { |
| 111 return err |
| 112 } |
| 113 return compareNodeSlice(expected.initialFoundationSet, actual.initialFou
ndationSet, "initialFoundationSet") |
| 114 } |
| 115 |
| 116 func compareNodeSlice(expected []string, actual []Node, name string) error { |
| 117 expectedMap := make(map[string]bool) |
| 118 actualMap := make(map[string]bool) |
| 119 for _, n := range expected { |
| 120 expectedMap[n] = true |
| 121 } |
| 122 for _, n := range actual { |
| 123 actualMap[n.DebugName()] = true |
| 124 } |
| 125 for _, n := range expected { |
| 126 if _, ok := actualMap[n]; !ok { |
| 127 return fmt.Errorf("%s: missing %s, actual: %s", name, n,
NodeSliceToString(actual)) |
| 128 } |
| 129 } |
| 130 for _, n := range actual { |
| 131 if _, ok := expectedMap[n.DebugName()]; !ok { |
| 132 return fmt.Errorf("%s: unexpected: %s, expected: %v, act
ual: %s", name, n.DebugName(), expected, NodeSliceToString(actual)) |
| 133 } |
| 134 } |
| 135 return nil |
| 136 } |
| 137 |
| 138 func NodeSliceToString(nodeSlice []Node) string { |
| 139 var buffer bytes.Buffer |
| 140 fmt.Fprintf(&buffer, "[") |
| 141 first := true |
| 142 for _, n := range nodeSlice { |
| 143 if !first { |
| 144 fmt.Fprintf(&buffer, ", ") |
| 145 } |
| 146 fmt.Fprintf(&buffer, "%s", n.DebugName()) |
| 147 first = false |
| 148 } |
| 149 fmt.Fprintln(&buffer, "]") |
| 150 return buffer.String() |
| 151 } |
| 152 |
| 153 //////////////////////////////////////////////////// |
| 154 // Tests |
| 155 //////////////////////////////////////////////////// |
| 156 |
| 157 type WellFoundedGraphTestCase struct { |
| 158 // The connection matrix describing the digraph for this case. |
| 159 connectionMatrix [][]int |
| 160 |
| 161 // If this is non-nil it should be the list of indices of the square nod
es. |
| 162 squares []int |
| 163 |
| 164 // The expected result when searching from Node0 |
| 165 expectedFirstA, expectedLastA, expectedPathA string |
| 166 |
| 167 // The expected result when searching from Node1 |
| 168 expectedFirstB, expectedLastB, expectedPathB string |
| 169 |
| 170 expectedDebugDataA, expectedDebugDataB expectedDebugData |
| 171 } |
| 172 |
| 173 // TestWellFoundedIsWellFoundedCirclesOnly tests the function |checkWellFounded| |
| 174 // on graphs that are well-founded and that contain only circles. For |
| 175 // graphs that contain only circles being well-founded is equivalent to |
| 176 // being acyclic. |
| 177 func TestWellFoundedIsWellFoundedCirclesOnly(t *testing.T) { |
| 178 cases := []WellFoundedGraphTestCase{ |
| 179 |
| 180 // Case: Single node, no self-loop |
| 181 { |
| 182 connectionMatrix: [][]int{ |
| 183 {}, |
| 184 }, |
| 185 }, |
| 186 |
| 187 // Case: Linear chain of length 4 |
| 188 { |
| 189 connectionMatrix: [][]int{ |
| 190 {1}, // 0 -> 1 |
| 191 {2}, // 1 -> 2 |
| 192 {3}, // 2 -> 3 |
| 193 {}, // 3 -> || |
| 194 }, |
| 195 }, |
| 196 |
| 197 // Case: Diamond |
| 198 // |
| 199 // 0 |
| 200 // 1 2 |
| 201 // 3 |
| 202 { |
| 203 connectionMatrix: [][]int{ |
| 204 {1, 2}, // 0 |
| 205 {3}, // 1 |
| 206 {3}, // 2 |
| 207 {}, // 3 |
| 208 }, |
| 209 }, |
| 210 |
| 211 // Case: Complex, double diamond with a tail |
| 212 // |
| 213 // 0 |
| 214 // 1 2 |
| 215 // 6 3 4 |
| 216 // 5 |
| 217 { |
| 218 connectionMatrix: [][]int{ |
| 219 {1, 2}, // 0 |
| 220 {3, 6}, // 1 |
| 221 {3, 4}, // 2 |
| 222 {5}, // 3 |
| 223 {5}, // 4 |
| 224 {}, // 5 |
| 225 {}, // 6 |
| 226 }, |
| 227 }, |
| 228 |
| 229 // Case: 0 and 1 are independent roots |
| 230 // |
| 231 // 0 1 |
| 232 // 7 2 | |
| 233 // 6 3 4 |
| 234 // 5 |
| 235 { |
| 236 connectionMatrix: [][]int{ |
| 237 {7, 2}, // 0 |
| 238 {4}, // 1 |
| 239 {3, 4}, // 2 |
| 240 {5}, // 3 |
| 241 {5}, // 4 |
| 242 {}, // 5 |
| 243 {}, // 6 |
| 244 {3, 6}, // 7 |
| 245 }, |
| 246 }, |
| 247 } |
| 248 |
| 249 for i, c := range cases { |
| 250 graph := buildCircleTestGraph(c.connectionMatrix) |
| 251 dbgData := debugData{} |
| 252 cycleDescription := checkWellFounded(graph[0], &dbgData) |
| 253 if cycleDescription != nil { |
| 254 t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescr
iption) |
| 255 } |
| 256 if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err
!= nil { |
| 257 t.Fatalf("Case %dA: %s", i, err.Error()) |
| 258 } |
| 259 if len(graph) > 1 { |
| 260 dbgData := debugData{} |
| 261 cycleDescription = checkWellFounded(graph[1], &dbgData) |
| 262 if cycleDescription != nil { |
| 263 t.Fatalf("Case %dB: Detected a cycle: %s", i, cy
cleDescription) |
| 264 } |
| 265 if err := compareDebugData(&c.expectedDebugDataB, &dbgDa
ta); err != nil { |
| 266 t.Fatalf("Case %dB: %s", i, err.Error()) |
| 267 } |
| 268 } |
| 269 } |
| 270 } |
| 271 |
| 272 // TestWellFoundedNotWellFoundedCirclesOnly tests the function |checkWellFounded
| |
| 273 // on graphs that are not well-founded and that contain only circles. For |
| 274 // graphs that contain only circles being well-founded is equivalent to |
| 275 // being acyclic. |
| 276 func TestWellFoundedNotWellFoundedCirclesOnly(t *testing.T) { |
| 277 |
| 278 cases := []WellFoundedGraphTestCase{ |
| 279 |
| 280 // Case: Single node with self-loop |
| 281 { |
| 282 connectionMatrix: [][]int{ |
| 283 {0}, |
| 284 }, |
| 285 |
| 286 expectedFirstA: "Node0", |
| 287 expectedLastA: "Node0", |
| 288 expectedPathA: "Node0", |
| 289 expectedDebugDataA: expectedDebugData{ |
| 290 initialPendingSet: []string{"Node0"}, |
| 291 }, |
| 292 }, |
| 293 |
| 294 // Case: Loop of length 4 |
| 295 { |
| 296 connectionMatrix: [][]int{ |
| 297 {1}, // 0 -> 1 |
| 298 {2}, // 1 -> 2 |
| 299 {3}, // 2 -> 3 |
| 300 {0}, // 3 -> 0 |
| 301 }, |
| 302 |
| 303 expectedFirstA: "Node0", |
| 304 expectedLastA: "Node3", |
| 305 expectedPathA: "Node0, Node1, Node2, Node3", |
| 306 expectedDebugDataA: expectedDebugData{ |
| 307 initialPendingSet: []string{"Node0", "Node1", "N
ode2", "Node3"}, |
| 308 }, |
| 309 |
| 310 expectedFirstB: "Node1", |
| 311 expectedLastB: "Node0", |
| 312 expectedPathB: "Node1, Node2, Node3, Node0", |
| 313 expectedDebugDataB: expectedDebugData{ |
| 314 initialPendingSet: []string{"Node0", "Node1", "N
ode2", "Node3"}, |
| 315 }, |
| 316 }, |
| 317 |
| 318 // Case: Diamond with a loop-back from bottom to top |
| 319 // |
| 320 // 0 <-- |
| 321 // 1 2 | |
| 322 // 3 ---| |
| 323 { |
| 324 connectionMatrix: [][]int{ |
| 325 {1, 2}, // 0 |
| 326 {3}, // 1 |
| 327 {3}, // 2 |
| 328 {0}, // 3 |
| 329 }, |
| 330 expectedFirstA: "Node0", |
| 331 expectedLastA: "Node3", |
| 332 expectedPathA: "Node0, Node1, Node3", |
| 333 expectedDebugDataA: expectedDebugData{ |
| 334 initialPendingSet: []string{"Node0", "Node1", "N
ode2", "Node3"}, |
| 335 }, |
| 336 |
| 337 expectedFirstB: "Node1", |
| 338 expectedLastB: "Node0", |
| 339 expectedPathB: "Node1, Node3, Node0", |
| 340 expectedDebugDataB: expectedDebugData{ |
| 341 initialPendingSet: []string{"Node0", "Node1", "N
ode2", "Node3"}, |
| 342 }, |
| 343 }, |
| 344 |
| 345 // Case: Complex, double diamond with a tail and a bridge and |
| 346 // a loop back to the top |
| 347 // |
| 348 // 0 |
| 349 // 1 2 <---- |
| 350 // 6 3 4 | |
| 351 // 5 ------| |
| 352 { |
| 353 connectionMatrix: [][]int{ |
| 354 {1, 2}, // 0 |
| 355 {3, 6}, // 1 |
| 356 {3, 4}, // 2 |
| 357 {5}, // 3 |
| 358 {5}, // 4 |
| 359 {2}, // 5 |
| 360 {}, // 6 |
| 361 }, |
| 362 expectedFirstA: "Node3", |
| 363 expectedLastA: "Node2", |
| 364 expectedPathA: "Node3, Node5, Node2", |
| 365 expectedDebugDataA: expectedDebugData{ |
| 366 initialPendingSet: []string{"Node0", "Node1", "N
ode2", "Node3", "Node4", "Node5"}, |
| 367 }, |
| 368 |
| 369 expectedFirstB: "Node3", |
| 370 expectedLastB: "Node2", |
| 371 expectedPathB: "Node3, Node5, Node2", |
| 372 expectedDebugDataB: expectedDebugData{ |
| 373 initialPendingSet: []string{"Node1", "Node2", "N
ode3", "Node4", "Node5"}, |
| 374 }, |
| 375 }, |
| 376 |
| 377 // Case: More complex |
| 378 // |
| 379 // |
| 380 // 0 |
| 381 // 1 2 3 <------ |
| 382 // 4 5 | |
| 383 // 6 8 7 | |
| 384 // 11 9 -------| |
| 385 // 12 10 |
| 386 { |
| 387 connectionMatrix: [][]int{ |
| 388 {1, 2, 3}, // 0 |
| 389 {4}, // 1 |
| 390 {4, 5}, // 2 |
| 391 {5}, // 3 |
| 392 {6}, // 4 |
| 393 {6, 7, 8}, // 5 |
| 394 {11}, // 6 |
| 395 {}, // 7 |
| 396 {9}, // 8 |
| 397 {10, 3}, // 9 |
| 398 {}, // 10 |
| 399 {12}, // 11 |
| 400 {}, // 12 |
| 401 }, |
| 402 expectedFirstA: "Node5", |
| 403 expectedLastA: "Node3", |
| 404 expectedPathA: "Node5, Node8, Node9, Node3", |
| 405 expectedDebugDataA: expectedDebugData{ |
| 406 initialPendingSet: []string{"Node0", "Node2", "N
ode3", "Node5", "Node8", "Node9"}, |
| 407 }, |
| 408 }, |
| 409 |
| 410 // Case: No loop from 0 but loop from 1 |
| 411 // |
| 412 // |
| 413 // 1 |
| 414 // 0 2 3 <---- |
| 415 // 4 5 | |
| 416 // 6 8 7 | |
| 417 // 11 9 ------| |
| 418 // 12 10 |
| 419 { |
| 420 connectionMatrix: [][]int{ |
| 421 {4}, // 0 |
| 422 {0, 2, 3}, // 1 |
| 423 {4, 5}, // 2 |
| 424 {5}, // 3 |
| 425 {6}, // 4 |
| 426 {6, 7, 8}, // 5 |
| 427 {11}, // 6 |
| 428 {}, // 7 |
| 429 {9}, // 8 |
| 430 {10, 3}, // 9 |
| 431 {}, // 10 |
| 432 {12}, // 11 |
| 433 {}, // 12 |
| 434 }, |
| 435 expectedFirstB: "Node5", |
| 436 expectedLastB: "Node3", |
| 437 expectedPathB: "Node5, Node8, Node9, Node3", |
| 438 expectedDebugDataB: expectedDebugData{ |
| 439 initialPendingSet: []string{"Node1", "Node2", "N
ode3", "Node5", "Node8", "Node9"}, |
| 440 }, |
| 441 }, |
| 442 } |
| 443 |
| 444 for i, c := range cases { |
| 445 graph := buildCircleTestGraph(c.connectionMatrix) |
| 446 // Test from root=Node0 |
| 447 dbgData := debugData{} |
| 448 cycleDescription := checkWellFounded(graph[0], &dbgData) |
| 449 if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err
!= nil { |
| 450 t.Fatalf("Case %dA: %s", i, err.Error()) |
| 451 } |
| 452 if len(c.expectedPathA) == 0 { |
| 453 if cycleDescription != nil { |
| 454 t.Fatalf("Case %dA: Detected a cycle: %s", i, cy
cleDescription) |
| 455 } |
| 456 } else { |
| 457 if cycleDescription == nil { |
| 458 t.Fatalf("Case %d: Expected a cycle.", i) |
| 459 } |
| 460 if !strings.Contains(cycleDescription.String(), fmt.Spri
ntf("first:%s", c.expectedFirstA)) { |
| 461 t.Fatalf("Case %d: got=%s expectedFirst=%q", i,
cycleDescription.String(), c.expectedFirstA) |
| 462 } |
| 463 if !strings.Contains(cycleDescription.String(), fmt.Spri
ntf("last:%s", c.expectedLastA)) { |
| 464 t.Fatalf("Case %d: got=%s expectedLast=%q", i, c
ycleDescription.String(), c.expectedLastA) |
| 465 } |
| 466 if !strings.Contains(cycleDescription.String(), fmt.Spri
ntf("{%s}", c.expectedPathA)) { |
| 467 t.Fatalf("Case %d: got=%s expectedPath=%q", i, c
ycleDescription.String(), c.expectedPathA) |
| 468 } |
| 469 } |
| 470 |
| 471 // Test from root=Node1 |
| 472 if len(graph) > 1 { |
| 473 dbgData := debugData{} |
| 474 cycleDescription := checkWellFounded(graph[1], &dbgData) |
| 475 if err := compareDebugData(&c.expectedDebugDataB, &dbgDa
ta); err != nil { |
| 476 t.Fatalf("Case %dB: %s", i, err.Error()) |
| 477 } |
| 478 if len(c.expectedPathB) == 0 { |
| 479 if cycleDescription != nil { |
| 480 t.Fatalf("Case %dB: Detected a cycle: %s
", i, cycleDescription) |
| 481 } |
| 482 } else { |
| 483 if cycleDescription == nil { |
| 484 t.Fatalf("Case %dB: Expected a cycle.",
i) |
| 485 } |
| 486 if !strings.Contains(cycleDescription.String(),
fmt.Sprintf("first:%s", c.expectedFirstB)) { |
| 487 t.Fatalf("Case %dB: got=%s expectedFirst
=%q", i, cycleDescription.String(), c.expectedFirstB) |
| 488 } |
| 489 if !strings.Contains(cycleDescription.String(),
fmt.Sprintf("last:%s", c.expectedLastB)) { |
| 490 t.Fatalf("Case %dB: got=%s expectedLast=
%q", i, cycleDescription.String(), c.expectedLastB) |
| 491 } |
| 492 if !strings.Contains(cycleDescription.String(),
fmt.Sprintf("{%s}", c.expectedPathB)) { |
| 493 t.Fatalf("Case %dB: got=%s expectedPath=
%q", i, cycleDescription.String(), c.expectedPathB) |
| 494 } |
| 495 } |
| 496 } |
| 497 } |
| 498 } |
| 499 |
| 500 // TestWellFoundedIsWellFounded tests the function |checkWellFounded| on graphs |
| 501 // that contain both circles and squares and are well-founded. |
| 502 func TestWellFoundedIsWellFounded(t *testing.T) { |
| 503 cases := []WellFoundedGraphTestCase{ |
| 504 |
| 505 // Case: Single square node, no self-loop |
| 506 { |
| 507 connectionMatrix: [][]int{ |
| 508 {}, |
| 509 }, |
| 510 squares: []int{0}, |
| 511 }, |
| 512 |
| 513 // Case: Loop through right branch but not through left branch. |
| 514 // |
| 515 // [0] <--| |
| 516 // 1 2--| |
| 517 { |
| 518 connectionMatrix: [][]int{ |
| 519 {1, 2}, // 0 |
| 520 {}, // 1 |
| 521 {0}, // 2 |
| 522 }, |
| 523 squares: []int{0}, |
| 524 }, |
| 525 |
| 526 // Case: Loop through left branch but not through rigt branch. |
| 527 // |
| 528 // [0] <--| |
| 529 // 2 1--| |
| 530 { |
| 531 connectionMatrix: [][]int{ |
| 532 {1, 2}, // 0 |
| 533 {0}, // 1 |
| 534 {}, // 2 |
| 535 }, |
| 536 squares: []int{0}, |
| 537 expectedDebugDataA: expectedDebugData{ |
| 538 initialPendingSet: []string{"Node1"}, |
| 539 initialFoundationSet: []string{"Node0"}, |
| 540 }, |
| 541 }, |
| 542 |
| 543 // Case: Loop through right branch below the root |
| 544 // |
| 545 // 0 <---| |
| 546 // [1] | |
| 547 // 2 3--| |
| 548 { |
| 549 connectionMatrix: [][]int{ |
| 550 {1}, // 0 |
| 551 {2, 3}, // 1 |
| 552 {}, // 2 |
| 553 {0}, // 3 |
| 554 }, |
| 555 squares: []int{1}, |
| 556 expectedDebugDataA: expectedDebugData{ |
| 557 initialPendingSet: []string{"Node3"}, |
| 558 initialFoundationSet: []string{"Node0"}, |
| 559 }, |
| 560 }, |
| 561 |
| 562 // Case: Loop through left branch below the root |
| 563 // |
| 564 // 0 <---| |
| 565 // [1] | |
| 566 // 3 2--| |
| 567 { |
| 568 connectionMatrix: [][]int{ |
| 569 {1}, // 0 |
| 570 {2, 3}, // 1 |
| 571 {0}, // 2 |
| 572 {}, // 3 |
| 573 }, |
| 574 squares: []int{1}, |
| 575 expectedDebugDataA: expectedDebugData{ |
| 576 initialPendingSet: []string{"Node2"}, |
| 577 initialFoundationSet: []string{"Node0"}, |
| 578 }, |
| 579 }, |
| 580 |
| 581 // Case: We know 0 is well-founded before we see the loop from 4
to 0 |
| 582 // |
| 583 // |
| 584 // 1 <-- [0] <--| |
| 585 // [2] | |
| 586 // 3 4--| |
| 587 { |
| 588 connectionMatrix: [][]int{ |
| 589 {1, 2}, // 0 |
| 590 {}, // 1 |
| 591 {3, 4}, // 2 |
| 592 {}, // 3 |
| 593 {0}, // 4 |
| 594 }, |
| 595 squares: []int{0, 2}, |
| 596 }, |
| 597 |
| 598 // Case: Well-founded becuase of 8 |
| 599 // 0 |
| 600 // 1 |
| 601 // 2 <-- |
| 602 // 3 | |
| 603 // 8 <-- [4] | |
| 604 // 5 | |
| 605 // 6---| |
| 606 // 7 |
| 607 { |
| 608 connectionMatrix: [][]int{ |
| 609 {1}, // 0 |
| 610 {2}, // 1 |
| 611 {3}, // 2 |
| 612 {4}, // 3 |
| 613 {5, 8}, // 4 |
| 614 {6}, // 5 |
| 615 {2, 7}, // 6 |
| 616 {}, // 7 |
| 617 {}, // 8 |
| 618 }, |
| 619 squares: []int{4}, |
| 620 expectedDebugDataA: expectedDebugData{ |
| 621 initialPendingSet: []string{"Node5", "Node6"}
, |
| 622 initialFoundationSet: []string{"Node2"}, |
| 623 }, |
| 624 }, |
| 625 |
| 626 // Case: Double loops through right branches |
| 627 // |
| 628 // 0 <---| |
| 629 // [1]<---|----- |
| 630 // 2 3--| | |
| 631 // [4] | |
| 632 // 5 6 7 --| |
| 633 // 8 9 10 |
| 634 { |
| 635 connectionMatrix: [][]int{ |
| 636 {1}, // 0 |
| 637 {2, 3}, // 1 |
| 638 {}, // 2 |
| 639 {0, 4}, // 3 |
| 640 {5, 6, 7}, // 4 |
| 641 {8}, // 5 |
| 642 {9}, // 6 |
| 643 {1, 10}, // 7 |
| 644 {}, // 8 |
| 645 {}, // 9 |
| 646 {}, // 10 |
| 647 }, |
| 648 squares: []int{1, 4}, |
| 649 expectedDebugDataA: expectedDebugData{ |
| 650 initialPendingSet: []string{"Node3"}, |
| 651 initialFoundationSet: []string{"Node0"}, |
| 652 }, |
| 653 }, |
| 654 |
| 655 // Case: Double loops through left branches |
| 656 // |
| 657 // 0 <---| |
| 658 // [1]<---|----- |
| 659 // 3 2--| | |
| 660 // [4] | |
| 661 // 7 6 5 --| |
| 662 // 8 9 10 |
| 663 { |
| 664 connectionMatrix: [][]int{ |
| 665 {1}, // 0 |
| 666 {2, 3}, // 1 |
| 667 {0, 4}, // 2 |
| 668 {}, // 3 |
| 669 {5, 6, 7}, // 4 |
| 670 {1, 10}, // 5 |
| 671 {9}, // 6 |
| 672 {8}, // 7 |
| 673 {}, // 8 |
| 674 {}, // 9 |
| 675 {}, // 10 |
| 676 }, |
| 677 squares: []int{1, 4}, |
| 678 expectedDebugDataA: expectedDebugData{ |
| 679 initialPendingSet: []string{"Node2", "Node5"}
, |
| 680 initialFoundationSet: []string{"Node0", "Node1"}
, |
| 681 }, |
| 682 }, |
| 683 |
| 684 // Case: Crossing up and down on right |
| 685 // |
| 686 // 0 -----| |
| 687 // 1 | |
| 688 // [2] <---|----- |
| 689 // 3 4 <-| | |
| 690 // 5 | |
| 691 // 6 | |
| 692 // 7 -------| |
| 693 // |
| 694 { |
| 695 connectionMatrix: [][]int{ |
| 696 {1, 4}, // 0 |
| 697 {2}, // 1 |
| 698 {3, 4}, // 2 |
| 699 {}, // 3 |
| 700 {5}, // 4 |
| 701 {6}, // 5 |
| 702 {7}, // 6 |
| 703 {2}, // 7 |
| 704 }, |
| 705 squares: []int{2}, |
| 706 }, |
| 707 |
| 708 // Case: Crossing up and down on left |
| 709 // |
| 710 // 0 -----| |
| 711 // 1 | |
| 712 // [2] <---|----- |
| 713 // 4 3 <-| | |
| 714 // 5 | |
| 715 // 6 | |
| 716 // 7 -------| |
| 717 // |
| 718 { |
| 719 connectionMatrix: [][]int{ |
| 720 {1, 3}, // 0 |
| 721 {2}, // 1 |
| 722 {3, 4}, // 2 |
| 723 {5}, // 3 |
| 724 {}, // 4 |
| 725 {6}, // 5 |
| 726 {7}, // 6 |
| 727 {2}, // 7 |
| 728 }, |
| 729 squares: []int{2}, |
| 730 expectedDebugDataA: expectedDebugData{ |
| 731 initialPendingSet: []string{"Node0", "Node3",
"Node5", "Node6", "Node7"}, |
| 732 initialFoundationSet: []string{"Node2"}, |
| 733 }, |
| 734 }, |
| 735 |
| 736 // Case: |
| 737 // |
| 738 // [0] <------| |
| 739 // |---->1 2 | |
| 740 // |<---[3]-------------| |
| 741 // |
| 742 // |
| 743 // |
| 744 { |
| 745 connectionMatrix: [][]int{ |
| 746 {1, 2}, // 0 |
| 747 {3}, // 1 |
| 748 {}, // 2 |
| 749 {0, 1}, // 3 |
| 750 }, |
| 751 squares: []int{0, 3}, |
| 752 expectedDebugDataA: expectedDebugData{ |
| 753 initialPendingSet: []string{"Node1", "Node3"}
, |
| 754 initialFoundationSet: []string{"Node0"}, |
| 755 }, |
| 756 }, |
| 757 |
| 758 // Case: |
| 759 // |
| 760 // |-----> 0 <------\ |
| 761 // | [1] --> [2]---|--> 4 |
| 762 // | ^ \ |
| 763 // |----|-------3 |
| 764 // |
| 765 // |
| 766 { |
| 767 connectionMatrix: [][]int{ |
| 768 {1, 2}, // 0 |
| 769 {2}, // 1 |
| 770 {0, 3, 4}, // 2 |
| 771 {0, 1}, // 3 |
| 772 {}, // 4 |
| 773 }, |
| 774 squares: []int{1, 2}, |
| 775 expectedDebugDataA: expectedDebugData{ |
| 776 initialPendingSet: []string{"Node3"}, |
| 777 initialFoundationSet: []string{"Node0", "Node1"}
, |
| 778 }, |
| 779 }, |
| 780 |
| 781 // Case: |
| 782 // |
| 783 // |-->[1] |
| 784 // [2]< -| 0 |
| 785 // ^ | |
| 786 // |----| |
| 787 // |
| 788 // |
| 789 { |
| 790 connectionMatrix: [][]int{ |
| 791 {}, // 0 |
| 792 {0, 2}, // 1 |
| 793 {1, 2}, // 2 |
| 794 }, |
| 795 squares: []int{1, 2}, |
| 796 }, |
| 797 |
| 798 // Case: Double loops through left branches |
| 799 // |
| 800 // 0 <---| |
| 801 // [1]<---|----- |
| 802 // 3 2--| | |
| 803 // [4] | |
| 804 // 7 6 5 --| |
| 805 // 8 9 10 |
| 806 { |
| 807 connectionMatrix: [][]int{ |
| 808 {1}, // 0 |
| 809 {2, 3}, // 1 |
| 810 {0, 4}, // 2 |
| 811 {}, // 3 |
| 812 {5, 6, 7}, // 4 |
| 813 {1, 10}, // 5 |
| 814 {9}, // 6 |
| 815 {8}, // 7 |
| 816 {}, // 8 |
| 817 {}, // 9 |
| 818 {}, // 10 |
| 819 }, |
| 820 squares: []int{1, 4}, |
| 821 expectedDebugDataA: expectedDebugData{ |
| 822 initialPendingSet: []string{"Node2", "Node5"}
, |
| 823 initialFoundationSet: []string{"Node0", "Node1"}
, |
| 824 }, |
| 825 }, |
| 826 } |
| 827 |
| 828 for i, c := range cases { |
| 829 graph := buildTestGraph(c.connectionMatrix, c.squares) |
| 830 dbgData := debugData{} |
| 831 cycleDescription := checkWellFounded(graph[0], &dbgData) |
| 832 if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err
!= nil { |
| 833 t.Fatalf("Case %dA: %s", i, err.Error()) |
| 834 } |
| 835 if cycleDescription != nil { |
| 836 t.Fatalf("Case %dA: Detected a cycle: %s", i, cycleDescr
iption) |
| 837 } |
| 838 if len(graph) > 1 { |
| 839 dbgData := debugData{} |
| 840 cycleDescription := checkWellFounded(graph[1], &dbgData) |
| 841 if err := compareDebugData(&c.expectedDebugDataB, &dbgDa
ta); err != nil { |
| 842 t.Fatalf("Case %dB: %s", i, err.Error()) |
| 843 } |
| 844 if cycleDescription != nil { |
| 845 t.Fatalf("Case %dB: Detected a cycle: %s", i, cy
cleDescription) |
| 846 } |
| 847 } |
| 848 } |
| 849 } |
| 850 |
| 851 // TestWellFoundedNotWellFounded tests the function |checkWellFounded| on graphs |
| 852 // that contain both circles and squares and are not well-founded. |
| 853 func TestWellFoundedNotWellFounded(t *testing.T) { |
| 854 |
| 855 cases := []WellFoundedGraphTestCase{ |
| 856 |
| 857 // Case: Single square node with self-loop |
| 858 { |
| 859 connectionMatrix: [][]int{ |
| 860 {0}, |
| 861 }, |
| 862 |
| 863 squares: []int{0}, |
| 864 |
| 865 expectedFirstA: "Node0", |
| 866 expectedLastA: "Node0", |
| 867 expectedPathA: "Node0", |
| 868 expectedDebugDataA: expectedDebugData{ |
| 869 initialPendingSet: []string{"Node0"}, |
| 870 initialFoundationSet: []string{}, |
| 871 }, |
| 872 }, |
| 873 |
| 874 // Case: Loop of length 4 with 1 square at the root |
| 875 { |
| 876 connectionMatrix: [][]int{ |
| 877 {1}, // 0 -> 1 |
| 878 {2}, // 1 -> 2 |
| 879 {3}, // 2 -> 3 |
| 880 {0}, // 3 -> 0 |
| 881 }, |
| 882 |
| 883 squares: []int{0}, |
| 884 |
| 885 expectedFirstA: "Node0", |
| 886 expectedLastA: "Node3", |
| 887 expectedPathA: "Node0, Node1, Node2, Node3", |
| 888 expectedDebugDataA: expectedDebugData{ |
| 889 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3"}, |
| 890 initialFoundationSet: []string{}, |
| 891 }, |
| 892 |
| 893 expectedFirstB: "Node1", |
| 894 expectedLastB: "Node0", |
| 895 expectedPathB: "Node1, Node2, Node3, Node0", |
| 896 expectedDebugDataB: expectedDebugData{ |
| 897 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3"}, |
| 898 initialFoundationSet: []string{}, |
| 899 }, |
| 900 }, |
| 901 |
| 902 // Case: Loop of length 4 with 2 squares |
| 903 { |
| 904 connectionMatrix: [][]int{ |
| 905 {1}, // 0 -> 1 |
| 906 {2}, // 1 -> 2 |
| 907 {3}, // 2 -> 3 |
| 908 {0}, // 3 -> 0 |
| 909 }, |
| 910 |
| 911 squares: []int{1, 2}, |
| 912 |
| 913 expectedFirstA: "Node0", |
| 914 expectedLastA: "Node3", |
| 915 expectedPathA: "Node0, Node1, Node2, Node3", |
| 916 expectedDebugDataA: expectedDebugData{ |
| 917 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3"}, |
| 918 initialFoundationSet: []string{}, |
| 919 }, |
| 920 |
| 921 expectedFirstB: "Node1", |
| 922 expectedLastB: "Node0", |
| 923 expectedPathB: "Node1, Node2, Node3, Node0", |
| 924 expectedDebugDataB: expectedDebugData{ |
| 925 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3"}, |
| 926 initialFoundationSet: []string{}, |
| 927 }, |
| 928 }, |
| 929 |
| 930 // Case: Loop through left and right branches |
| 931 // |
| 932 // |--> [0] <--| |
| 933 // |--1 2--| |
| 934 { |
| 935 connectionMatrix: [][]int{ |
| 936 {1, 2}, // 0 |
| 937 {0}, // 1 |
| 938 {0}, // 2 |
| 939 }, |
| 940 squares: []int{0}, |
| 941 |
| 942 expectedFirstA: "Node0", |
| 943 expectedLastA: "Node1", |
| 944 expectedPathA: "Node0, Node1", |
| 945 expectedDebugDataA: expectedDebugData{ |
| 946 initialPendingSet: []string{"Node0", "Node1",
"Node2"}, |
| 947 initialFoundationSet: []string{}, |
| 948 }, |
| 949 |
| 950 expectedFirstB: "Node1", |
| 951 expectedLastB: "Node0", |
| 952 expectedPathB: "Node1, Node0", |
| 953 expectedDebugDataB: expectedDebugData{ |
| 954 initialPendingSet: []string{"Node0", "Node1",
"Node2"}, |
| 955 initialFoundationSet: []string{}, |
| 956 }, |
| 957 }, |
| 958 |
| 959 // Case: Loop through left and right branches below the root |
| 960 // |
| 961 // |----> 0 <---| |
| 962 // | [1] | |
| 963 // |-- 2 3--| |
| 964 { |
| 965 connectionMatrix: [][]int{ |
| 966 {1}, // 0 |
| 967 {2, 3}, // 1 |
| 968 {0}, // 2 |
| 969 {0}, // 3 |
| 970 }, |
| 971 squares: []int{1}, |
| 972 |
| 973 expectedFirstA: "Node0", |
| 974 expectedLastA: "Node2", |
| 975 expectedPathA: "Node0, Node1, Node2", |
| 976 expectedDebugDataA: expectedDebugData{ |
| 977 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3"}, |
| 978 initialFoundationSet: []string{}, |
| 979 }, |
| 980 |
| 981 expectedFirstB: "Node1", |
| 982 expectedLastB: "Node0", |
| 983 expectedPathB: "Node1, Node2, Node0", |
| 984 expectedDebugDataB: expectedDebugData{ |
| 985 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3"}, |
| 986 initialFoundationSet: []string{}, |
| 987 }, |
| 988 }, |
| 989 |
| 990 // Case: Self loop at one node below a square |
| 991 // |
| 992 // [0] |
| 993 // 1 2--| |
| 994 // ^ | |
| 995 // | | |
| 996 // ---- |
| 997 { |
| 998 connectionMatrix: [][]int{ |
| 999 {1, 2}, // 0 |
| 1000 {}, // 1 |
| 1001 {2}, // 2 |
| 1002 }, |
| 1003 squares: []int{0}, |
| 1004 |
| 1005 expectedFirstA: "Node2", |
| 1006 expectedLastA: "Node2", |
| 1007 expectedPathA: "Node2", |
| 1008 expectedDebugDataA: expectedDebugData{ |
| 1009 initialPendingSet: []string{"Node2"}, |
| 1010 initialFoundationSet: []string{}, |
| 1011 }, |
| 1012 }, |
| 1013 |
| 1014 // Case: Self loop at one node below a square, other side |
| 1015 // |
| 1016 // [0] |
| 1017 // 2 1--| |
| 1018 // ^ | |
| 1019 // | | |
| 1020 // ---- |
| 1021 { |
| 1022 connectionMatrix: [][]int{ |
| 1023 {1, 2}, // 0 |
| 1024 {1}, // 1 |
| 1025 {}, // 2 |
| 1026 }, |
| 1027 squares: []int{0}, |
| 1028 |
| 1029 expectedFirstA: "Node1", |
| 1030 expectedLastA: "Node1", |
| 1031 expectedPathA: "Node1", |
| 1032 expectedDebugDataA: expectedDebugData{ |
| 1033 initialPendingSet: []string{"Node1"}, |
| 1034 initialFoundationSet: []string{}, |
| 1035 }, |
| 1036 |
| 1037 expectedFirstB: "Node1", |
| 1038 expectedLastB: "Node1", |
| 1039 expectedPathB: "Node1", |
| 1040 expectedDebugDataB: expectedDebugData{ |
| 1041 initialPendingSet: []string{"Node1"}, |
| 1042 initialFoundationSet: []string{}, |
| 1043 }, |
| 1044 }, |
| 1045 |
| 1046 // Case: Self loop off of one branch of a square. |
| 1047 // |
| 1048 // [0] |
| 1049 // 1 2 |
| 1050 // 3 -| |
| 1051 // ^ | |
| 1052 // |--- |
| 1053 { |
| 1054 connectionMatrix: [][]int{ |
| 1055 {1, 2}, // 0 |
| 1056 {3}, // 1 |
| 1057 {}, // 2 |
| 1058 {3}, // 3 |
| 1059 }, |
| 1060 squares: []int{0}, |
| 1061 |
| 1062 expectedFirstA: "Node3", |
| 1063 expectedLastA: "Node3", |
| 1064 expectedPathA: "Node3", |
| 1065 expectedDebugDataA: expectedDebugData{ |
| 1066 initialPendingSet: []string{"Node1", "Node3"}
, |
| 1067 initialFoundationSet: []string{}, |
| 1068 }, |
| 1069 |
| 1070 expectedFirstB: "Node3", |
| 1071 expectedLastB: "Node3", |
| 1072 expectedPathB: "Node3", |
| 1073 expectedDebugDataB: expectedDebugData{ |
| 1074 initialPendingSet: []string{"Node1", "Node3"}
, |
| 1075 initialFoundationSet: []string{}, |
| 1076 }, |
| 1077 }, |
| 1078 |
| 1079 // Case: Hard loop off of one branch of a square. |
| 1080 // |
| 1081 // [0] |
| 1082 // --> 1 2 |
| 1083 // | 3 |
| 1084 // |---4 |
| 1085 { |
| 1086 connectionMatrix: [][]int{ |
| 1087 {1, 2}, // 0 |
| 1088 {3}, // 1 |
| 1089 {}, // 2 |
| 1090 {4}, // 3 |
| 1091 {1}, // 4 |
| 1092 }, |
| 1093 squares: []int{0}, |
| 1094 |
| 1095 expectedFirstA: "Node1", |
| 1096 expectedLastA: "Node4", |
| 1097 expectedPathA: "Node1, Node3, Node4", |
| 1098 expectedDebugDataA: expectedDebugData{ |
| 1099 initialPendingSet: []string{"Node1", "Node3",
"Node4"}, |
| 1100 initialFoundationSet: []string{}, |
| 1101 }, |
| 1102 |
| 1103 expectedFirstB: "Node1", |
| 1104 expectedLastB: "Node4", |
| 1105 expectedPathB: "Node1, Node3, Node4", |
| 1106 expectedDebugDataB: expectedDebugData{ |
| 1107 initialPendingSet: []string{"Node1", "Node3",
"Node4"}, |
| 1108 initialFoundationSet: []string{}, |
| 1109 }, |
| 1110 }, |
| 1111 |
| 1112 // Case: Graph below 0 is well-founded and 1 is well-founded but
not the graph below 1. |
| 1113 // |
| 1114 // [1] |
| 1115 // 2 -| 0 |
| 1116 // ^ | |
| 1117 // |--| |
| 1118 // |
| 1119 // |
| 1120 { |
| 1121 connectionMatrix: [][]int{ |
| 1122 {}, // 0 |
| 1123 {0, 2}, // 1 |
| 1124 {2}, // 2 |
| 1125 }, |
| 1126 squares: []int{1}, |
| 1127 |
| 1128 expectedFirstB: "Node2", |
| 1129 expectedLastB: "Node2", |
| 1130 expectedPathB: "Node2", |
| 1131 expectedDebugDataB: expectedDebugData{ |
| 1132 initialPendingSet: []string{"Node2"}, |
| 1133 initialFoundationSet: []string{}, |
| 1134 }, |
| 1135 }, |
| 1136 |
| 1137 // Case: Different loops through both branches sharing nodes. |
| 1138 // |
| 1139 // 0 <------| |
| 1140 // 1 | |
| 1141 // [2] | |
| 1142 // 3 4 | |
| 1143 // \ 5 | |
| 1144 // \----> 6 | |
| 1145 // 7 --| |
| 1146 { |
| 1147 connectionMatrix: [][]int{ |
| 1148 {1}, // 0 |
| 1149 {2}, // 1 |
| 1150 {3, 4}, // 2 |
| 1151 {6}, // 3 |
| 1152 {5}, // 4 |
| 1153 {6}, // 5 |
| 1154 {7}, // 6 |
| 1155 {0}, // 7 |
| 1156 }, |
| 1157 squares: []int{2}, |
| 1158 |
| 1159 expectedFirstA: "Node0", |
| 1160 expectedLastA: "Node7", |
| 1161 expectedPathA: "Node0, Node1, Node2, Node3, Node6, Node
7", |
| 1162 expectedDebugDataA: expectedDebugData{ |
| 1163 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3", "Node4", "Node5", "Node6", "Node7"}, |
| 1164 initialFoundationSet: []string{}, |
| 1165 }, |
| 1166 |
| 1167 expectedFirstB: "Node1", |
| 1168 expectedLastB: "Node0", |
| 1169 expectedPathB: "Node1, Node2, Node3, Node6, Node7, Node
0", |
| 1170 expectedDebugDataB: expectedDebugData{ |
| 1171 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3", "Node4", "Node5", "Node6", "Node7"}, |
| 1172 initialFoundationSet: []string{}, |
| 1173 }, |
| 1174 }, |
| 1175 |
| 1176 // Case: Different loops through both branches sharing nodes--sw
itch sides. |
| 1177 // |
| 1178 // 0 <------| |
| 1179 // 1 | |
| 1180 // [2] | |
| 1181 // 4 3 | |
| 1182 // \ 5 | |
| 1183 // \----> 6 | |
| 1184 // 7 --| |
| 1185 { |
| 1186 connectionMatrix: [][]int{ |
| 1187 {1}, // 0 |
| 1188 {2}, // 1 |
| 1189 {3, 4}, // 2 |
| 1190 {5}, // 3 |
| 1191 {6}, // 4 |
| 1192 {6}, // 5 |
| 1193 {7}, // 6 |
| 1194 {0}, // 7 |
| 1195 }, |
| 1196 squares: []int{2}, |
| 1197 |
| 1198 expectedFirstA: "Node0", |
| 1199 expectedLastA: "Node7", |
| 1200 expectedPathA: "Node0, Node1, Node2, Node3, Node5, Node
6, Node7", |
| 1201 expectedDebugDataA: expectedDebugData{ |
| 1202 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3", "Node4", "Node5", "Node6", "Node7"}, |
| 1203 initialFoundationSet: []string{}, |
| 1204 }, |
| 1205 |
| 1206 expectedFirstB: "Node1", |
| 1207 expectedLastB: "Node0", |
| 1208 expectedPathB: "Node1, Node2, Node3, Node5, Node6, Node
7, Node0", |
| 1209 expectedDebugDataB: expectedDebugData{ |
| 1210 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3", "Node4", "Node5", "Node6", "Node7"}, |
| 1211 initialFoundationSet: []string{}, |
| 1212 }, |
| 1213 }, |
| 1214 |
| 1215 // Case: Not Well-founded becuase of 8 becuase 4 is a circle |
| 1216 // 0 |
| 1217 // 1 |
| 1218 // 2 <-- |
| 1219 // 3 | |
| 1220 // 8 <-- 4 | |
| 1221 // 5 | |
| 1222 // 6---| |
| 1223 // 7 |
| 1224 { |
| 1225 connectionMatrix: [][]int{ |
| 1226 {1}, // 0 |
| 1227 {2}, // 1 |
| 1228 {3}, // 2 |
| 1229 {4}, // 3 |
| 1230 {5, 8}, // 4 |
| 1231 {6}, // 5 |
| 1232 {2, 7}, // 6 |
| 1233 {}, // 7 |
| 1234 {}, // 8 |
| 1235 }, |
| 1236 squares: []int{}, |
| 1237 |
| 1238 expectedFirstA: "Node2", |
| 1239 expectedLastA: "Node6", |
| 1240 expectedPathA: "Node2, Node3, Node4, Node5, Node6", |
| 1241 expectedDebugDataA: expectedDebugData{ |
| 1242 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3", "Node4", "Node5", "Node6"}, |
| 1243 initialFoundationSet: []string{}, |
| 1244 }, |
| 1245 |
| 1246 expectedFirstB: "Node2", |
| 1247 expectedLastB: "Node6", |
| 1248 expectedPathB: "Node2, Node3, Node4, Node5, Node6", |
| 1249 expectedDebugDataB: expectedDebugData{ |
| 1250 initialPendingSet: []string{"Node1", "Node2",
"Node3", "Node4", "Node5", "Node6"}, |
| 1251 initialFoundationSet: []string{}, |
| 1252 }, |
| 1253 }, |
| 1254 |
| 1255 // Case: Not Well-founded becuase of 8 becuase there is no 8 |
| 1256 // 0 |
| 1257 // 1 |
| 1258 // 2 <-- |
| 1259 // 3 | |
| 1260 // [4] | |
| 1261 // 5 | |
| 1262 // 6---| |
| 1263 // 7 |
| 1264 { |
| 1265 connectionMatrix: [][]int{ |
| 1266 {1}, // 0 |
| 1267 {2}, // 1 |
| 1268 {3}, // 2 |
| 1269 {4}, // 3 |
| 1270 {5}, // 4 |
| 1271 {6}, // 5 |
| 1272 {2, 7}, // 6 |
| 1273 {}, // 7 |
| 1274 }, |
| 1275 squares: []int{4}, |
| 1276 |
| 1277 expectedFirstA: "Node2", |
| 1278 expectedLastA: "Node6", |
| 1279 expectedPathA: "Node2, Node3, Node4, Node5, Node6", |
| 1280 expectedDebugDataA: expectedDebugData{ |
| 1281 initialPendingSet: []string{"Node0", "Node1",
"Node2", "Node3", "Node4", "Node5", "Node6"}, |
| 1282 initialFoundationSet: []string{}, |
| 1283 }, |
| 1284 |
| 1285 expectedFirstB: "Node2", |
| 1286 expectedLastB: "Node6", |
| 1287 expectedPathB: "Node2, Node3, Node4, Node5, Node6", |
| 1288 expectedDebugDataB: expectedDebugData{ |
| 1289 initialPendingSet: []string{"Node1", "Node2",
"Node3", "Node4", "Node5", "Node6"}, |
| 1290 initialFoundationSet: []string{}, |
| 1291 }, |
| 1292 }, |
| 1293 } |
| 1294 |
| 1295 for i, c := range cases { |
| 1296 graph := buildTestGraph(c.connectionMatrix, c.squares) |
| 1297 // Test from root=Node0 |
| 1298 dbgData := debugData{} |
| 1299 cycleDescription := checkWellFounded(graph[0], &dbgData) |
| 1300 if err := compareDebugData(&c.expectedDebugDataA, &dbgData); err
!= nil { |
| 1301 t.Fatalf("Case %dA: %s", i, err.Error()) |
| 1302 } |
| 1303 if len(c.expectedPathA) == 0 { |
| 1304 if cycleDescription != nil { |
| 1305 t.Fatalf("Case %dA: Detected a cycle: %s", i, cy
cleDescription) |
| 1306 } |
| 1307 } else { |
| 1308 if cycleDescription == nil { |
| 1309 t.Fatalf("Case %d: Expected a cycle.", i) |
| 1310 } |
| 1311 if !strings.Contains(cycleDescription.String(), fmt.Spri
ntf("first:%s", c.expectedFirstA)) { |
| 1312 t.Fatalf("Case %d: got=%s expectedFirst=%q", i,
cycleDescription.String(), c.expectedFirstA) |
| 1313 } |
| 1314 if !strings.Contains(cycleDescription.String(), fmt.Spri
ntf("last:%s", c.expectedLastA)) { |
| 1315 t.Fatalf("Case %d: got=%s expectedLast=%q", i, c
ycleDescription.String(), c.expectedLastA) |
| 1316 } |
| 1317 if !strings.Contains(cycleDescription.String(), fmt.Spri
ntf("{%s}", c.expectedPathA)) { |
| 1318 t.Fatalf("Case %d: got=%s expectedPath=%q", i, c
ycleDescription.String(), c.expectedPathA) |
| 1319 } |
| 1320 } |
| 1321 |
| 1322 // Test from root=Node1 |
| 1323 if len(graph) > 1 { |
| 1324 dbgData := debugData{} |
| 1325 cycleDescription := checkWellFounded(graph[1], &dbgData) |
| 1326 if err := compareDebugData(&c.expectedDebugDataB, &dbgDa
ta); err != nil { |
| 1327 t.Fatalf("Case %dB: %s", i, err.Error()) |
| 1328 } |
| 1329 if len(c.expectedPathB) == 0 { |
| 1330 if cycleDescription != nil { |
| 1331 t.Fatalf("Case %dB: Detected a cycle: %s
", i, cycleDescription) |
| 1332 } |
| 1333 } else { |
| 1334 if cycleDescription == nil { |
| 1335 t.Fatalf("Case %dB: Expected a cycle.",
i) |
| 1336 } |
| 1337 if !strings.Contains(cycleDescription.String(),
fmt.Sprintf("first:%s", c.expectedFirstB)) { |
| 1338 t.Fatalf("Case %dB: got=%s expectedFirst
=%q", i, cycleDescription.String(), c.expectedFirstB) |
| 1339 } |
| 1340 if !strings.Contains(cycleDescription.String(),
fmt.Sprintf("last:%s", c.expectedLastB)) { |
| 1341 t.Fatalf("Case %dB: got=%s expectedLast=
%q", i, cycleDescription.String(), c.expectedLastB) |
| 1342 } |
| 1343 if !strings.Contains(cycleDescription.String(),
fmt.Sprintf("{%s}", c.expectedPathB)) { |
| 1344 t.Fatalf("Case %dB: got=%s expectedPath=
%q", i, cycleDescription.String(), c.expectedPathB) |
| 1345 } |
| 1346 } |
| 1347 } |
| 1348 } |
| 1349 } |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 1908273003:
Mojom frontend: An algorithm for detecting ill-founded nodes in a graph. (Closed)
Base URL: https://github.com/domokit/mojo.git@master