alg.go

     1  // Copyright 2022 The Go 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 dag
     6  
     7  // Transpose reverses all edges in g.
     8  func (g *Graph) Transpose() {
     9  	old := g.edges
    10  
    11  	g.edges = make(map[string]map[string]bool)
    12  	for _, n := range g.Nodes {
    13  		g.edges[n] = make(map[string]bool)
    14  	}
    15  
    16  	for from, tos := range old {
    17  		for to := range tos {
    18  			g.edges[to][from] = true
    19  		}
    20  	}
    21  }
    22  
    23  // Topo returns a topological sort of g. This function is deterministic.
    24  func (g *Graph) Topo() []string {
    25  	topo := make([]string, 0, len(g.Nodes))
    26  	marks := make(map[string]bool)
    27  
    28  	var visit func(n string)
    29  	visit = func(n string) {
    30  		if marks[n] {
    31  			return
    32  		}
    33  		for _, to := range g.Edges(n) {
    34  			visit(to)
    35  		}
    36  		marks[n] = true
    37  		topo = append(topo, n)
    38  	}
    39  	for _, root := range g.Nodes {
    40  		visit(root)
    41  	}
    42  	for i, j := 0, len(topo)-1; i < j; i, j = i+1, j-1 {
    43  		topo[i], topo[j] = topo[j], topo[i]
    44  	}
    45  	return topo
    46  }
    47  
    48  // TransitiveReduction removes edges from g that are transitively
    49  // reachable. g must be transitively closed.
    50  func (g *Graph) TransitiveReduction() {
    51  	// For i -> j -> k, if i -> k exists, delete it.
    52  	for _, i := range g.Nodes {
    53  		for _, j := range g.Nodes {
    54  			if g.HasEdge(i, j) {
    55  				for _, k := range g.Nodes {
    56  					if g.HasEdge(j, k) {
    57  						g.DelEdge(i, k)
    58  					}
    59  				}
    60  			}
    61  		}
    62  	}
    63  }
    64
View as plain text