graph.go

Documentation: github.com/chaos-mesh/chaos-mesh/pkg/chaosdaemon/graph

     1  // Copyright 2021 Chaos Mesh Authors.
     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  
    16  package graph
    17  
    18  import (
    19  	"github.com/go-logr/logr"
    20  )
    21  
    22  // Edge represents an edge in graph
    23  type Edge struct {
    24  	Source uint32
    25  	Target uint32
    26  	Next   *Edge
    27  }
    28  
    29  // Graph represents a graph with link list
    30  type Graph struct {
    31  	head map[uint32]*Edge
    32  }
    33  
    34  // NewGraph creates a Graph
    35  func NewGraph() *Graph {
    36  	return &Graph{
    37  		head: make(map[uint32]*Edge),
    38  	}
    39  }
    40  
    41  // Insert inserts an Edge into a graph from source to target
    42  func (g *Graph) Insert(source uint32, target uint32) {
    43  	newEdge := Edge{
    44  		Source: source,
    45  		Target: target,
    46  		Next:   g.head[source],
    47  	}
    48  	g.head[source] = &newEdge
    49  }
    50  
    51  // IterFrom starts iterating from source node
    52  func (g *Graph) IterFrom(source uint32) *Edge {
    53  	return g.head[source]
    54  }
    55  
    56  // Flatten flattens the subtree from source (without checking whether it's a tree)
    57  func (g *Graph) Flatten(source uint32, log logr.Logger) []uint32 {
    58  	current := g.head[source]
    59  
    60  	var flatTree []uint32
    61  	for {
    62  		if current == nil {
    63  			break
    64  		}
    65  
    66  		children := g.Flatten(current.Target, log)
    67  		flatTree = append(flatTree, current.Target)
    68  		flatTree = append(flatTree, children...)
    69  
    70  		current = current.Next
    71  	}
    72  
    73  	log.Info("get flatTree", "source", source, "flatTree", flatTree)
    74  	return flatTree
    75  }
    76