graph.go

Documentation: sigs.k8s.io/cli-utils/pkg/object/graph

     1  // Copyright 2020 The Kubernetes Authors.
     2  // SPDX-License-Identifier: Apache-2.0
     3  
     4  // This package provides a graph data struture
     5  // and graph functionality using ObjMetadata as
     6  // vertices in the graph.
     7  package graph
     8  
     9  import (
    10  	"sort"
    11  
    12  	"sigs.k8s.io/cli-utils/pkg/object"
    13  	"sigs.k8s.io/cli-utils/pkg/object/validation"
    14  	"sigs.k8s.io/cli-utils/pkg/ordering"
    15  )
    16  
    17  // Graph is contains a directed set of edges, implemented as
    18  // an adjacency list (map key is "from" vertex, slice are "to"
    19  // vertices).
    20  type Graph struct {
    21  	// map "from" vertex -> list of "to" vertices
    22  	edges map[object.ObjMetadata]object.ObjMetadataSet
    23  	// map "to" vertex -> list of "from" vertices
    24  	reverseEdges map[object.ObjMetadata]object.ObjMetadataSet
    25  }
    26  
    27  // New returns a pointer to an empty Graph data structure.
    28  func New() *Graph {
    29  	g := &Graph{}
    30  	g.edges = make(map[object.ObjMetadata]object.ObjMetadataSet)
    31  	g.reverseEdges = make(map[object.ObjMetadata]object.ObjMetadataSet)
    32  	return g
    33  }
    34  
    35  // AddVertex adds an ObjMetadata vertex to the graph, with
    36  // an initial empty set of edges from added vertex.
    37  func (g *Graph) AddVertex(v object.ObjMetadata) {
    38  	if _, exists := g.edges[v]; !exists {
    39  		g.edges[v] = object.ObjMetadataSet{}
    40  	}
    41  	if _, exists := g.reverseEdges[v]; !exists {
    42  		g.reverseEdges[v] = object.ObjMetadataSet{}
    43  	}
    44  }
    45  
    46  // edgeMapKeys returns a sorted set of unique vertices in the graph.
    47  func edgeMapKeys(edgeMap map[object.ObjMetadata]object.ObjMetadataSet) object.ObjMetadataSet {
    48  	keys := make(object.ObjMetadataSet, len(edgeMap))
    49  	i := 0
    50  	for k := range edgeMap {
    51  		keys[i] = k
    52  		i++
    53  	}
    54  	sort.Sort(ordering.SortableMetas(keys))
    55  	return keys
    56  }
    57  
    58  // AddEdge adds a edge from one ObjMetadata vertex to another. The
    59  // direction of the edge is "from" -> "to".
    60  func (g *Graph) AddEdge(from object.ObjMetadata, to object.ObjMetadata) {
    61  	// Add "from" vertex if it doesn't already exist.
    62  	if _, exists := g.edges[from]; !exists {
    63  		g.edges[from] = object.ObjMetadataSet{}
    64  	}
    65  	if _, exists := g.reverseEdges[from]; !exists {
    66  		g.reverseEdges[from] = object.ObjMetadataSet{}
    67  	}
    68  	// Add "to" vertex if it doesn't already exist.
    69  	if _, exists := g.edges[to]; !exists {
    70  		g.edges[to] = object.ObjMetadataSet{}
    71  	}
    72  	if _, exists := g.reverseEdges[to]; !exists {
    73  		g.reverseEdges[to] = object.ObjMetadataSet{}
    74  	}
    75  	// Add edge "from" -> "to" if it doesn't already exist
    76  	// into the adjacency list.
    77  	if !g.isAdjacent(from, to) {
    78  		g.edges[from] = append(g.edges[from], to)
    79  		g.reverseEdges[to] = append(g.reverseEdges[to], from)
    80  	}
    81  }
    82  
    83  // edgeMapToList returns a sorted slice of directed graph edges (vertex pairs).
    84  func edgeMapToList(edgeMap map[object.ObjMetadata]object.ObjMetadataSet) []Edge {
    85  	edges := []Edge{}
    86  	for from, toList := range edgeMap {
    87  		for _, to := range toList {
    88  			edge := Edge{From: from, To: to}
    89  			edges = append(edges, edge)
    90  		}
    91  	}
    92  	sort.Sort(SortableEdges(edges))
    93  	return edges
    94  }
    95  
    96  // isAdjacent returns true if an edge "from" vertex -> "to" vertex exists;
    97  // false otherwise.
    98  func (g *Graph) isAdjacent(from object.ObjMetadata, to object.ObjMetadata) bool {
    99  	// If "from" vertex does not exist, it is impossible edge exists; return false.
   100  	if _, exists := g.edges[from]; !exists {
   101  		return false
   102  	}
   103  	// Iterate through adjacency list to see if "to" vertex is adjacent.
   104  	for _, vertex := range g.edges[from] {
   105  		if vertex == to {
   106  			return true
   107  		}
   108  	}
   109  	return false
   110  }
   111  
   112  // Size returns the number of vertices in the graph.
   113  func (g *Graph) Size() int {
   114  	return len(g.edges)
   115  }
   116  
   117  // removeVertex removes the passed vertex as well as any edges into the vertex.
   118  func removeVertex(edges map[object.ObjMetadata]object.ObjMetadataSet, r object.ObjMetadata) {
   119  	// First, remove the object from all adjacency lists.
   120  	for v, adj := range edges {
   121  		edges[v] = adj.Remove(r)
   122  	}
   123  	// Finally, remove the vertex
   124  	delete(edges, r)
   125  }
   126  
   127  // Dependencies returns the objects that this object depends on.
   128  func (g *Graph) Dependencies(from object.ObjMetadata) object.ObjMetadataSet {
   129  	edgesFrom, exists := g.edges[from]
   130  	if !exists {
   131  		return nil
   132  	}
   133  	c := make(object.ObjMetadataSet, len(edgesFrom))
   134  	copy(c, edgesFrom)
   135  	return c
   136  }
   137  
   138  // Dependents returns the objects that depend on this object.
   139  func (g *Graph) Dependents(to object.ObjMetadata) object.ObjMetadataSet {
   140  	edgesTo, exists := g.reverseEdges[to]
   141  	if !exists {
   142  		return nil
   143  	}
   144  	c := make(object.ObjMetadataSet, len(edgesTo))
   145  	copy(c, edgesTo)
   146  	return c
   147  }
   148  
   149  // Sort returns the ordered set of vertices after a topological sort.
   150  func (g *Graph) Sort() ([]object.ObjMetadataSet, error) {
   151  	// deep copy edge map to avoid destructive sorting
   152  	edges := make(map[object.ObjMetadata]object.ObjMetadataSet, len(g.edges))
   153  	for vertex, deps := range g.edges {
   154  		c := make(object.ObjMetadataSet, len(deps))
   155  		copy(c, deps)
   156  		edges[vertex] = c
   157  	}
   158  
   159  	sorted := []object.ObjMetadataSet{}
   160  	for len(edges) > 0 {
   161  		// Identify all the leaf vertices.
   162  		leafVertices := object.ObjMetadataSet{}
   163  		for v, adj := range edges {
   164  			if len(adj) == 0 {
   165  				leafVertices = append(leafVertices, v)
   166  			}
   167  		}
   168  		// No leaf vertices means cycle in the directed graph,
   169  		// where remaining edges define the cycle.
   170  		if len(leafVertices) == 0 {
   171  			// Error can be ignored, so return the full set list
   172  			return sorted, validation.NewError(CyclicDependencyError{
   173  				Edges: edgeMapToList(edges),
   174  			}, edgeMapKeys(edges)...)
   175  		}
   176  		// Remove all edges to leaf vertices.
   177  		for _, v := range leafVertices {
   178  			removeVertex(edges, v)
   179  		}
   180  		sorted = append(sorted, leafVertices)
   181  	}
   182  	return sorted, nil
   183  }
   184
View as plain text