dependencygraph.go

Documentation: github.com/GoogleCloudPlatform/k8s-config-connector/scripts/resource-autogen/sampleconversion

     1  // Copyright 2023 Google LLC
     2  //
     3  // Licensed under the Apache License, Version 2.0 (the "License");
     4  // you may not use this file except in compliance with the License.
     5  // You may obtain a copy of the License at
     6  //
     7  //      http://www.apache.org/licenses/LICENSE-2.0
     8  //
     9  // Unless required by applicable law or agreed to in writing, software
    10  // distributed under the License is distributed on an "AS IS" BASIS,
    11  // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    12  // See the License for the specific language governing permissions and
    13  // limitations under the License.
    14  
    15  package sampleconversion
    16  
    17  import (
    18  	"sort"
    19  
    20  	"github.com/GoogleCloudPlatform/k8s-config-connector/pkg/util/slice"
    21  )
    22  
    23  type DependencyGraph struct {
    24  	// edges is the map of directed edges from the vertex (key of the map) to
    25  	// the list of adjacent vertices (value of the map) in the graph.
    26  	edges map[string][]string
    27  }
    28  
    29  func NewDependencyGraph() *DependencyGraph {
    30  	edges := make(map[string][]string)
    31  	return &DependencyGraph{edges: edges}
    32  }
    33  
    34  // AddDependencyWithTFRefVal adds an edge in the dependency graph using the
    35  // referencer's TF type, and the referencee's "TF Reference Value" in the format
    36  // of `[referenced_tf_type].[referenced_resource_name].[referenced_field_name]`.
    37  func (d *DependencyGraph) AddDependencyWithTFRefVal(tfRefValOfReferencee, referencer string) {
    38  	referencee, _ := extractReferencedTFTypeAndField(tfRefValOfReferencee)
    39  	d.addDependency(referencee, referencer)
    40  }
    41  
    42  // addDependency adds an edge in the dependency graph using the referencer's TF
    43  // type, and the referencee's TF type.
    44  func (d *DependencyGraph) addDependency(referencee, referencer string) {
    45  	referencerList := make([]string, 0)
    46  	if _, ok := d.edges[referencee]; ok {
    47  		referencerList = d.edges[referencee]
    48  	}
    49  	referencerList = append(referencerList, referencer)
    50  	d.edges[referencee] = referencerList
    51  }
    52  
    53  func (d *DependencyGraph) TopologicalSort() []string {
    54  	visited := make(map[string]bool)
    55  	referencees := make([]string, 0)
    56  	result := make([]string, 0)
    57  
    58  	for referencee, _ := range d.edges {
    59  		visited[referencee] = false
    60  		referencees = append(referencees, referencee)
    61  	}
    62  	sort.Strings(referencees)
    63  
    64  	// Iterate the referencees following the alphabetical order.
    65  	for _, referencee := range referencees {
    66  		result = topologicalSort(referencee, d.edges, visited, result)
    67  	}
    68  
    69  	slice.Reverse(result)
    70  	return result
    71  }
    72  
    73  func topologicalSort(vertex string, edges map[string][]string, visited map[string]bool, result []string) (updatedResult []string) {
    74  	// If the vertex has been visited, or if the vertex doesn't have any
    75  	// outgoing edges (thus not covered by the "visited" map), skip the
    76  	// topological sorting for the vertex.
    77  	if isVisited, ok := visited[vertex]; isVisited || !ok {
    78  		return result
    79  	}
    80  	visited[vertex] = true
    81  	adjacentList, ok := edges[vertex]
    82  	if !ok || len(adjacentList) == 0 {
    83  		result = append(result, vertex)
    84  		return result
    85  	}
    86  	for _, adjacentVertex := range adjacentList {
    87  		result = topologicalSort(adjacentVertex, edges, visited, result)
    88  	}
    89  	result = append(result, vertex)
    90  	return result
    91  }
    92
View as plain text