undirected.go

Documentation: k8s.io/kubernetes/third_party/forked/gonum/graph/simple

     1  // Copyright ©2014 The gonum 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 simple
     6  
     7  import (
     8  	"fmt"
     9  
    10  	"golang.org/x/tools/container/intsets"
    11  
    12  	"k8s.io/kubernetes/third_party/forked/gonum/graph"
    13  )
    14  
    15  // UndirectedGraph implements a generalized undirected graph.
    16  type UndirectedGraph struct {
    17  	nodes map[int]graph.Node
    18  	edges map[int]edgeHolder
    19  
    20  	self, absent float64
    21  
    22  	freeIDs intsets.Sparse
    23  	usedIDs intsets.Sparse
    24  }
    25  
    26  // NewUndirectedGraph returns an UndirectedGraph with the specified self and absent
    27  // edge weight values.
    28  func NewUndirectedGraph(self, absent float64) *UndirectedGraph {
    29  	return &UndirectedGraph{
    30  		nodes: make(map[int]graph.Node),
    31  		edges: make(map[int]edgeHolder),
    32  
    33  		self:   self,
    34  		absent: absent,
    35  	}
    36  }
    37  
    38  // NewNodeID returns a new unique ID for a node to be added to g. The returned ID does
    39  // not become a valid ID in g until it is added to g.
    40  func (g *UndirectedGraph) NewNodeID() int {
    41  	if len(g.nodes) == 0 {
    42  		return 0
    43  	}
    44  	if len(g.nodes) == maxInt {
    45  		panic(fmt.Sprintf("simple: cannot allocate node: no slot"))
    46  	}
    47  
    48  	var id int
    49  	if g.freeIDs.Len() != 0 && g.freeIDs.TakeMin(&id) {
    50  		return id
    51  	}
    52  	if id = g.usedIDs.Max(); id < maxInt {
    53  		return id + 1
    54  	}
    55  	for id = 0; id < maxInt; id++ {
    56  		if !g.usedIDs.Has(id) {
    57  			return id
    58  		}
    59  	}
    60  	panic("unreachable")
    61  }
    62  
    63  // AddNode adds n to the graph. It panics if the added node ID matches an existing node ID.
    64  func (g *UndirectedGraph) AddNode(n graph.Node) {
    65  	if _, exists := g.nodes[n.ID()]; exists {
    66  		panic(fmt.Sprintf("simple: node ID collision: %d", n.ID()))
    67  	}
    68  	g.nodes[n.ID()] = n
    69  	g.edges[n.ID()] = &sliceEdgeHolder{self: n.ID()}
    70  
    71  	g.freeIDs.Remove(n.ID())
    72  	g.usedIDs.Insert(n.ID())
    73  }
    74  
    75  // RemoveNode removes n from the graph, as well as any edges attached to it. If the node
    76  // is not in the graph it is a no-op.
    77  func (g *UndirectedGraph) RemoveNode(n graph.Node) {
    78  	if _, ok := g.nodes[n.ID()]; !ok {
    79  		return
    80  	}
    81  	delete(g.nodes, n.ID())
    82  
    83  	g.edges[n.ID()].Visit(func(neighbor int, edge graph.Edge) {
    84  		g.edges[neighbor] = g.edges[neighbor].Delete(n.ID())
    85  	})
    86  	delete(g.edges, n.ID())
    87  
    88  	g.freeIDs.Insert(n.ID())
    89  	g.usedIDs.Remove(n.ID())
    90  
    91  }
    92  
    93  // SetEdge adds e, an edge from one node to another. If the nodes do not exist, they are added.
    94  // It will panic if the IDs of the e.From and e.To are equal.
    95  func (g *UndirectedGraph) SetEdge(e graph.Edge) {
    96  	var (
    97  		from = e.From()
    98  		fid  = from.ID()
    99  		to   = e.To()
   100  		tid  = to.ID()
   101  	)
   102  
   103  	if fid == tid {
   104  		panic("simple: adding self edge")
   105  	}
   106  
   107  	if !g.Has(from) {
   108  		g.AddNode(from)
   109  	}
   110  	if !g.Has(to) {
   111  		g.AddNode(to)
   112  	}
   113  
   114  	g.edges[fid] = g.edges[fid].Set(tid, e)
   115  	g.edges[tid] = g.edges[tid].Set(fid, e)
   116  }
   117  
   118  // RemoveEdge removes e from the graph, leaving the terminal nodes. If the edge does not exist
   119  // it is a no-op.
   120  func (g *UndirectedGraph) RemoveEdge(e graph.Edge) {
   121  	from, to := e.From(), e.To()
   122  	if _, ok := g.nodes[from.ID()]; !ok {
   123  		return
   124  	}
   125  	if _, ok := g.nodes[to.ID()]; !ok {
   126  		return
   127  	}
   128  
   129  	g.edges[from.ID()] = g.edges[from.ID()].Delete(to.ID())
   130  	g.edges[to.ID()] = g.edges[to.ID()].Delete(from.ID())
   131  }
   132  
   133  // Node returns the node in the graph with the given ID.
   134  func (g *UndirectedGraph) Node(id int) graph.Node {
   135  	return g.nodes[id]
   136  }
   137  
   138  // Has returns whether the node exists within the graph.
   139  func (g *UndirectedGraph) Has(n graph.Node) bool {
   140  	_, ok := g.nodes[n.ID()]
   141  	return ok
   142  }
   143  
   144  // Nodes returns all the nodes in the graph.
   145  func (g *UndirectedGraph) Nodes() []graph.Node {
   146  	nodes := make([]graph.Node, len(g.nodes))
   147  	i := 0
   148  	for _, n := range g.nodes {
   149  		nodes[i] = n
   150  		i++
   151  	}
   152  
   153  	return nodes
   154  }
   155  
   156  // Edges returns all the edges in the graph.
   157  func (g *UndirectedGraph) Edges() []graph.Edge {
   158  	var edges []graph.Edge
   159  
   160  	seen := make(map[[2]int]struct{})
   161  	for _, u := range g.edges {
   162  		u.Visit(func(neighbor int, e graph.Edge) {
   163  			uid := e.From().ID()
   164  			vid := e.To().ID()
   165  			if _, ok := seen[[2]int{uid, vid}]; ok {
   166  				return
   167  			}
   168  			seen[[2]int{uid, vid}] = struct{}{}
   169  			seen[[2]int{vid, uid}] = struct{}{}
   170  			edges = append(edges, e)
   171  		})
   172  	}
   173  
   174  	return edges
   175  }
   176  
   177  // From returns all nodes in g that can be reached directly from n.
   178  func (g *UndirectedGraph) From(n graph.Node) []graph.Node {
   179  	if !g.Has(n) {
   180  		return nil
   181  	}
   182  
   183  	nodes := make([]graph.Node, g.edges[n.ID()].Len())
   184  	i := 0
   185  	g.edges[n.ID()].Visit(func(neighbor int, edge graph.Edge) {
   186  		nodes[i] = g.nodes[neighbor]
   187  		i++
   188  	})
   189  
   190  	return nodes
   191  }
   192  
   193  // HasEdgeBetween returns whether an edge exists between nodes x and y.
   194  func (g *UndirectedGraph) HasEdgeBetween(x, y graph.Node) bool {
   195  	_, ok := g.edges[x.ID()].Get(y.ID())
   196  	return ok
   197  }
   198  
   199  // Edge returns the edge from u to v if such an edge exists and nil otherwise.
   200  // The node v must be directly reachable from u as defined by the From method.
   201  func (g *UndirectedGraph) Edge(u, v graph.Node) graph.Edge {
   202  	return g.EdgeBetween(u, v)
   203  }
   204  
   205  // EdgeBetween returns the edge between nodes x and y.
   206  func (g *UndirectedGraph) EdgeBetween(x, y graph.Node) graph.Edge {
   207  	// We don't need to check if neigh exists because
   208  	// it's implicit in the edges access.
   209  	if !g.Has(x) {
   210  		return nil
   211  	}
   212  
   213  	edge, _ := g.edges[x.ID()].Get(y.ID())
   214  	return edge
   215  }
   216  
   217  // Weight returns the weight for the edge between x and y if Edge(x, y) returns a non-nil Edge.
   218  // If x and y are the same node or there is no joining edge between the two nodes the weight
   219  // value returned is either the graph's absent or self value. Weight returns true if an edge
   220  // exists between x and y or if x and y have the same ID, false otherwise.
   221  func (g *UndirectedGraph) Weight(x, y graph.Node) (w float64, ok bool) {
   222  	xid := x.ID()
   223  	yid := y.ID()
   224  	if xid == yid {
   225  		return g.self, true
   226  	}
   227  	if n, ok := g.edges[xid]; ok {
   228  		if e, ok := n.Get(yid); ok {
   229  			return e.Weight(), true
   230  		}
   231  	}
   232  	return g.absent, false
   233  }
   234  
   235  // Degree returns the degree of n in g.
   236  func (g *UndirectedGraph) Degree(n graph.Node) int {
   237  	if _, ok := g.nodes[n.ID()]; !ok {
   238  		return 0
   239  	}
   240  
   241  	return g.edges[n.ID()].Len()
   242  }
   243
View as plain text