OLD | NEW |
1 // Copyright 2016 The Chromium Authors. All rights reserved. | 1 // Copyright 2016 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 package utils | 5 package utils |
6 | 6 |
7 import ( | 7 import ( |
8 "bytes" | 8 "bytes" |
9 "fmt" | 9 "fmt" |
10 ) | 10 ) |
11 | 11 |
12 // This file contains an implementation of an algorithm to check the well-founde
dness | 12 // This file contains an implementation of an algorithm to check the well-founde
dness |
13 // of two-sorted directed graphs. See the paper | 13 // of two-sorted directed graphs. See the paper |
14 // "Well-Founded Two-Sorted Directed Graphs" (https://goo.gl/ipxFKu) for backgro
und | 14 // "Well-Founded Two-Sorted Directed Graphs" (https://goo.gl/YrLmfY) for backgro
und |
15 // and detailed definitions. Here we give only a high-level overview. | 15 // and detailed definitions. Here we give only a high-level overview. |
16 // | 16 // |
17 // A two-sorted graph is a directed graph that contains two sorts of nodes calle
d circle nodes and | 17 // A two-sorted graph is a directed graph that contains two sorts of nodes calle
d circle nodes and |
18 // square nodes. A node in a two-sorted graph is *well-founded* iff it satisfies
the | 18 // square nodes. A node in a two-sorted graph is *well-founded* iff it satisfies
the |
19 // following recursive definition: | 19 // following recursive definition: |
20 // (i) Leaf nodes are well-founded | 20 // (i) Leaf nodes are well-founded |
21 // (ii) A circle node is well-founded iff all of its children are well-founded | 21 // (ii) A circle node is well-founded iff all of its children are well-founded |
22 // (iii) A non-leaf square node is well-founded iff at least one of its children
is well-founded. | 22 // (iii) A non-leaf square node is well-founded iff at least one of its children
is well-founded. |
23 // (See the paper for a more logically correct definition.) | 23 // (See the paper for a more logically correct definition.) |
24 // | 24 // |
(...skipping 587 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
612 for _, element := range path { | 612 for _, element := range path { |
613 if len(description.Path) > 0 || element.node == cycleStart { | 613 if len(description.Path) > 0 || element.node == cycleStart { |
614 description.Path = append(description.Path, element.edge
) | 614 description.Path = append(description.Path, element.edge
) |
615 } | 615 } |
616 } | 616 } |
617 if description.Path[len(description.Path)-1].Target != cycleStart { | 617 if description.Path[len(description.Path)-1].Target != cycleStart { |
618 panic(fmt.Sprintf("%s != %s", description.Path[len(description.P
ath)-1].Target.Name(), cycleStart.Name())) | 618 panic(fmt.Sprintf("%s != %s", description.Path[len(description.P
ath)-1].Target.Name(), cycleStart.Name())) |
619 } | 619 } |
620 return &description | 620 return &description |
621 } | 621 } |
OLD | NEW |