Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(329)

Side by Side Diff: mojom/mojom_tool/utils/wellfounded_graphs.go

Issue 2028843002: Mojom frontend: Update shortened url for latest version of graph-theory paper. (Closed) Base URL: https://github.com/domokit/mojo.git@master
Patch Set: Created 4 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « no previous file | no next file » | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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
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 }
OLDNEW
« no previous file with comments | « no previous file | no next file » | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698