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 5package graph 6 7// Node is a graph node. It returns a graph-unique integer ID. 8type Node interface { 9 ID() int64 10} 11 12// Edge is a graph edge. In directed graphs, the direction of the 13// edge is given from -> to, otherwise the edge is semantically 14// unordered. 15type Edge interface { 16 // From returns the from node of the edge. 17 From() Node 18 19 // To returns the to node of the edge. 20 To() Node 21 22 // ReversedEdge returns the edge reversal of the receiver 23 // if a reversal is valid for the data type. 24 // When a reversal is valid an edge of the same type as 25 // the receiver with nodes of the receiver swapped should 26 // be returned, otherwise the receiver should be returned 27 // unaltered. 28 ReversedEdge() Edge 29} 30 31// WeightedEdge is a weighted graph edge. In directed graphs, the direction 32// of the edge is given from -> to, otherwise the edge is semantically 33// unordered. 34type WeightedEdge interface { 35 Edge 36 Weight() float64 37} 38 39// Graph is a generalized graph. 40type Graph interface { 41 // Node returns the node with the given ID if it exists 42 // in the graph, and nil otherwise. 43 Node(id int64) Node 44 45 // Nodes returns all the nodes in the graph. 46 // 47 // Nodes must not return nil. 48 Nodes() Nodes 49 50 // From returns all nodes that can be reached directly 51 // from the node with the given ID. 52 // 53 // From must not return nil. 54 From(id int64) Nodes 55 56 // HasEdgeBetween returns whether an edge exists between 57 // nodes with IDs xid and yid without considering direction. 58 HasEdgeBetween(xid, yid int64) bool 59 60 // Edge returns the edge from u to v, with IDs uid and vid, 61 // if such an edge exists and nil otherwise. The node v 62 // must be directly reachable from u as defined by the 63 // From method. 64 Edge(uid, vid int64) Edge 65} 66 67// Weighted is a weighted graph. 68type Weighted interface { 69 Graph 70 71 // WeightedEdge returns the weighted edge from u to v 72 // with IDs uid and vid if such an edge exists and 73 // nil otherwise. The node v must be directly 74 // reachable from u as defined by the From method. 75 WeightedEdge(uid, vid int64) WeightedEdge 76 77 // Weight returns the weight for the edge between 78 // x and y with IDs xid and yid if Edge(xid, yid) 79 // returns a non-nil Edge. 80 // If x and y are the same node or there is no 81 // joining edge between the two nodes the weight 82 // value returned is implementation dependent. 83 // Weight returns true if an edge exists between 84 // x and y or if x and y have the same ID, false 85 // otherwise. 86 Weight(xid, yid int64) (w float64, ok bool) 87} 88 89// Undirected is an undirected graph. 90type Undirected interface { 91 Graph 92 93 // EdgeBetween returns the edge between nodes x and y 94 // with IDs xid and yid. 95 EdgeBetween(xid, yid int64) Edge 96} 97 98// WeightedUndirected is a weighted undirected graph. 99type WeightedUndirected interface { 100 Weighted 101 102 // WeightedEdgeBetween returns the edge between nodes 103 // x and y with IDs xid and yid. 104 WeightedEdgeBetween(xid, yid int64) WeightedEdge 105} 106 107// Directed is a directed graph. 108type Directed interface { 109 Graph 110 111 // HasEdgeFromTo returns whether an edge exists 112 // in the graph from u to v with IDs uid and vid. 113 HasEdgeFromTo(uid, vid int64) bool 114 115 // To returns all nodes that can reach directly 116 // to the node with the given ID. 117 // 118 // To must not return nil. 119 To(id int64) Nodes 120} 121 122// WeightedDirected is a weighted directed graph. 123type WeightedDirected interface { 124 Weighted 125 126 // HasEdgeFromTo returns whether an edge exists 127 // in the graph from u to v with the IDs uid and 128 // vid. 129 HasEdgeFromTo(uid, vid int64) bool 130 131 // To returns all nodes that can reach directly 132 // to the node with the given ID. 133 // 134 // To must not return nil. 135 To(id int64) Nodes 136} 137 138// NodeAdder is an interface for adding arbitrary nodes to a graph. 139type NodeAdder interface { 140 // NewNode returns a new Node with a unique 141 // arbitrary ID. 142 NewNode() Node 143 144 // AddNode adds a node to the graph. AddNode panics if 145 // the added node ID matches an existing node ID. 146 AddNode(Node) 147} 148 149// NodeRemover is an interface for removing nodes from a graph. 150type NodeRemover interface { 151 // RemoveNode removes the node with the given ID 152 // from the graph, as well as any edges attached 153 // to it. If the node is not in the graph it is 154 // a no-op. 155 RemoveNode(id int64) 156} 157 158// EdgeAdder is an interface for adding edges to a graph. 159type EdgeAdder interface { 160 // NewEdge returns a new Edge from the source to the destination node. 161 NewEdge(from, to Node) Edge 162 163 // SetEdge adds an edge from one node to another. 164 // If the graph supports node addition the nodes 165 // will be added if they do not exist, otherwise 166 // SetEdge will panic. 167 // The behavior of an EdgeAdder when the IDs 168 // returned by e.From() and e.To() are equal is 169 // implementation-dependent. 170 // Whether e, e.From() and e.To() are stored 171 // within the graph is implementation dependent. 172 SetEdge(e Edge) 173} 174 175// WeightedEdgeAdder is an interface for adding edges to a graph. 176type WeightedEdgeAdder interface { 177 // NewWeightedEdge returns a new WeightedEdge from 178 // the source to the destination node. 179 NewWeightedEdge(from, to Node, weight float64) WeightedEdge 180 181 // SetWeightedEdge adds an edge from one node to 182 // another. If the graph supports node addition 183 // the nodes will be added if they do not exist, 184 // otherwise SetWeightedEdge will panic. 185 // The behavior of a WeightedEdgeAdder when the IDs 186 // returned by e.From() and e.To() are equal is 187 // implementation-dependent. 188 // Whether e, e.From() and e.To() are stored 189 // within the graph is implementation dependent. 190 SetWeightedEdge(e WeightedEdge) 191} 192 193// EdgeRemover is an interface for removing nodes from a graph. 194type EdgeRemover interface { 195 // RemoveEdge removes the edge with the given end 196 // IDs, leaving the terminal nodes. If the edge 197 // does not exist it is a no-op. 198 RemoveEdge(fid, tid int64) 199} 200 201// Builder is a graph that can have nodes and edges added. 202type Builder interface { 203 NodeAdder 204 EdgeAdder 205} 206 207// WeightedBuilder is a graph that can have nodes and weighted edges added. 208type WeightedBuilder interface { 209 NodeAdder 210 WeightedEdgeAdder 211} 212 213// UndirectedBuilder is an undirected graph builder. 214type UndirectedBuilder interface { 215 Undirected 216 Builder 217} 218 219// UndirectedWeightedBuilder is an undirected weighted graph builder. 220type UndirectedWeightedBuilder interface { 221 Undirected 222 WeightedBuilder 223} 224 225// DirectedBuilder is a directed graph builder. 226type DirectedBuilder interface { 227 Directed 228 Builder 229} 230 231// DirectedWeightedBuilder is a directed weighted graph builder. 232type DirectedWeightedBuilder interface { 233 Directed 234 WeightedBuilder 235} 236 237// Copy copies nodes and edges as undirected edges from the source to the destination 238// without first clearing the destination. Copy will panic if a node ID in the source 239// graph matches a node ID in the destination. 240// 241// If the source is undirected and the destination is directed both directions will 242// be present in the destination after the copy is complete. 243func Copy(dst Builder, src Graph) { 244 nodes := src.Nodes() 245 for nodes.Next() { 246 dst.AddNode(nodes.Node()) 247 } 248 nodes.Reset() 249 for nodes.Next() { 250 u := nodes.Node() 251 uid := u.ID() 252 to := src.From(uid) 253 for to.Next() { 254 v := to.Node() 255 dst.SetEdge(src.Edge(uid, v.ID())) 256 } 257 } 258} 259 260// CopyWeighted copies nodes and edges as undirected edges from the source to the destination 261// without first clearing the destination. Copy will panic if a node ID in the source 262// graph matches a node ID in the destination. 263// 264// If the source is undirected and the destination is directed both directions will 265// be present in the destination after the copy is complete. 266// 267// If the source is a directed graph, the destination is undirected, and a fundamental 268// cycle exists with two nodes where the edge weights differ, the resulting destination 269// graph's edge weight between those nodes is undefined. If there is a defined function 270// to resolve such conflicts, an UndirectWeighted may be used to do this. 271func CopyWeighted(dst WeightedBuilder, src Weighted) { 272 nodes := src.Nodes() 273 for nodes.Next() { 274 dst.AddNode(nodes.Node()) 275 } 276 nodes.Reset() 277 for nodes.Next() { 278 u := nodes.Node() 279 uid := u.ID() 280 to := src.From(uid) 281 for to.Next() { 282 v := to.Node() 283 dst.SetWeightedEdge(src.WeightedEdge(uid, v.ID())) 284 } 285 } 286} 287