graph.go

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

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