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 graph 6 7 // Node is a graph node. It returns a graph-unique integer ID. 8 type Node interface { 9 ID() int 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. 15 type Edge interface { 16 From() Node 17 To() Node 18 Weight() float64 19 } 20 21 // Graph is a generalized graph. 22 type Graph interface { 23 // Has returns whether the node exists within the graph. 24 Has(Node) bool 25 26 // Nodes returns all the nodes in the graph. 27 Nodes() []Node 28 29 // From returns all nodes that can be reached directly 30 // from the given node. 31 From(Node) []Node 32 33 // HasEdgeBeteen returns whether an edge exists between 34 // nodes x and y without considering direction. 35 HasEdgeBetween(x, y Node) bool 36 37 // Edge returns the edge from u to v if such an edge 38 // exists and nil otherwise. The node v must be directly 39 // reachable from u as defined by the From method. 40 Edge(u, v Node) Edge 41 } 42 43 // Undirected is an undirected graph. 44 type Undirected interface { 45 Graph 46 47 // EdgeBetween returns the edge between nodes x and y. 48 EdgeBetween(x, y Node) Edge 49 } 50 51 // Directed is a directed graph. 52 type Directed interface { 53 Graph 54 55 // HasEdgeFromTo returns whether an edge exists 56 // in the graph from u to v. 57 HasEdgeFromTo(u, v Node) bool 58 59 // To returns all nodes that can reach directly 60 // to the given node. 61 To(Node) []Node 62 } 63 64 // Weighter defines graphs that can report edge weights. 65 type Weighter interface { 66 // Weight returns the weight for the edge between 67 // x and y if Edge(x, y) returns a non-nil Edge. 68 // If x and y are the same node or there is no 69 // joining edge between the two nodes the weight 70 // value returned is implementation dependent. 71 // Weight returns true if an edge exists between 72 // x and y or if x and y have the same ID, false 73 // otherwise. 74 Weight(x, y Node) (w float64, ok bool) 75 } 76 77 // NodeAdder is an interface for adding arbitrary nodes to a graph. 78 type NodeAdder interface { 79 // NewNodeID returns a new unique arbitrary ID. 80 NewNodeID() int 81 82 // Adds a node to the graph. AddNode panics if 83 // the added node ID matches an existing node ID. 84 AddNode(Node) 85 } 86 87 // NodeRemover is an interface for removing nodes from a graph. 88 type NodeRemover interface { 89 // RemoveNode removes a node from the graph, as 90 // well as any edges attached to it. If the node 91 // is not in the graph it is a no-op. 92 RemoveNode(Node) 93 } 94 95 // EdgeSetter is an interface for adding edges to a graph. 96 type EdgeSetter interface { 97 // SetEdge adds an edge from one node to another. 98 // If the graph supports node addition the nodes 99 // will be added if they do not exist, otherwise 100 // SetEdge will panic. 101 // If the IDs returned by e.From and e.To are 102 // equal, SetEdge will panic. 103 SetEdge(e Edge) 104 } 105 106 // EdgeRemover is an interface for removing nodes from a graph. 107 type EdgeRemover interface { 108 // RemoveEdge removes the given edge, leaving the 109 // terminal nodes. If the edge does not exist it 110 // is a no-op. 111 RemoveEdge(Edge) 112 } 113 114 // Builder is a graph that can have nodes and edges added. 115 type Builder interface { 116 NodeAdder 117 EdgeSetter 118 } 119 120 // UndirectedBuilder is an undirected graph builder. 121 type UndirectedBuilder interface { 122 Undirected 123 Builder 124 } 125 126 // DirectedBuilder is a directed graph builder. 127 type DirectedBuilder interface { 128 Directed 129 Builder 130 } 131 132 // Copy copies nodes and edges as undirected edges from the source to the destination 133 // without first clearing the destination. Copy will panic if a node ID in the source 134 // graph matches a node ID in the destination. 135 // 136 // If the source is undirected and the destination is directed both directions will 137 // be present in the destination after the copy is complete. 138 // 139 // If the source is a directed graph, the destination is undirected, and a fundamental 140 // cycle exists with two nodes where the edge weights differ, the resulting destination 141 // graph's edge weight between those nodes is undefined. If there is a defined function 142 // to resolve such conflicts, an Undirect may be used to do this. 143 func Copy(dst Builder, src Graph) { 144 nodes := src.Nodes() 145 for _, n := range nodes { 146 dst.AddNode(n) 147 } 148 for _, u := range nodes { 149 for _, v := range src.From(u) { 150 dst.SetEdge(src.Edge(u, v)) 151 } 152 } 153 } 154