11 // Graph is used to represent a dependency graph.
15 downEdges map[interface{}]*Set
16 upEdges map[interface{}]*Set
18 // JSON encoder for recording debug information
22 // Subgrapher allows a Vertex to be a Graph itself, by returning a Grapher.
23 type Subgrapher interface {
27 // A Grapher is any type that returns a Grapher, mainly used to identify
28 // dag.Graph and dag.AcyclicGraph. In the case of Graph and AcyclicGraph, they
30 type Grapher interface {
31 DirectedGraph() Grapher
34 // Vertex of the graph.
35 type Vertex interface{}
37 // NamedVertex is an optional interface that can be implemented by Vertex
38 // to give it a human-friendly name that is used for outputting the graph.
39 type NamedVertex interface {
44 func (g *Graph) DirectedGraph() Grapher {
48 // Vertices returns the list of all the vertices in the graph.
49 func (g *Graph) Vertices() []Vertex {
50 list := g.vertices.List()
51 result := make([]Vertex, len(list))
52 for i, v := range list {
53 result[i] = v.(Vertex)
59 // Edges returns the list of all the edges in the graph.
60 func (g *Graph) Edges() []Edge {
61 list := g.edges.List()
62 result := make([]Edge, len(list))
63 for i, v := range list {
70 // EdgesFrom returns the list of edges from the given source.
71 func (g *Graph) EdgesFrom(v Vertex) []Edge {
74 for _, e := range g.Edges() {
75 if hashcode(e.Source()) == from {
76 result = append(result, e)
83 // EdgesTo returns the list of edges to the given target.
84 func (g *Graph) EdgesTo(v Vertex) []Edge {
87 for _, e := range g.Edges() {
88 if hashcode(e.Target()) == search {
89 result = append(result, e)
96 // HasVertex checks if the given Vertex is present in the graph.
97 func (g *Graph) HasVertex(v Vertex) bool {
98 return g.vertices.Include(v)
101 // HasEdge checks if the given Edge is present in the graph.
102 func (g *Graph) HasEdge(e Edge) bool {
103 return g.edges.Include(e)
106 // Add adds a vertex to the graph. This is safe to call multiple time with
108 func (g *Graph) Add(v Vertex) Vertex {
115 // Remove removes a vertex from the graph. This will also remove any
116 // edges with this vertex as a source or target.
117 func (g *Graph) Remove(v Vertex) Vertex {
118 // Delete the vertex itself
122 // Delete the edges to non-existent things
123 for _, target := range g.DownEdges(v).List() {
124 g.RemoveEdge(BasicEdge(v, target))
126 for _, source := range g.UpEdges(v).List() {
127 g.RemoveEdge(BasicEdge(source, v))
133 // Replace replaces the original Vertex with replacement. If the original
134 // does not exist within the graph, then false is returned. Otherwise, true
136 func (g *Graph) Replace(original, replacement Vertex) bool {
137 // If we don't have the original, we can't do anything
138 if !g.vertices.Include(original) {
142 defer g.debug.BeginOperation("Replace", "").End("")
144 // If they're the same, then don't do anything
145 if original == replacement {
149 // Add our new vertex, then copy all the edges
151 for _, target := range g.DownEdges(original).List() {
152 g.Connect(BasicEdge(replacement, target))
154 for _, source := range g.UpEdges(original).List() {
155 g.Connect(BasicEdge(source, replacement))
158 // Remove our old vertex, which will also remove all the edges
164 // RemoveEdge removes an edge from the graph.
165 func (g *Graph) RemoveEdge(edge Edge) {
167 g.debug.RemoveEdge(edge)
169 // Delete the edge from the set
172 // Delete the up/down edges
173 if s, ok := g.downEdges[hashcode(edge.Source())]; ok {
174 s.Delete(edge.Target())
176 if s, ok := g.upEdges[hashcode(edge.Target())]; ok {
177 s.Delete(edge.Source())
181 // DownEdges returns the outward edges from the source Vertex v.
182 func (g *Graph) DownEdges(v Vertex) *Set {
184 return g.downEdges[hashcode(v)]
187 // UpEdges returns the inward edges to the destination Vertex v.
188 func (g *Graph) UpEdges(v Vertex) *Set {
190 return g.upEdges[hashcode(v)]
193 // Connect adds an edge with the given source and target. This is safe to
194 // call multiple times with the same value. Note that the same value is
195 // verified through pointer equality of the vertices, not through the
196 // value of the edge itself.
197 func (g *Graph) Connect(edge Edge) {
199 g.debug.Connect(edge)
201 source := edge.Source()
202 target := edge.Target()
203 sourceCode := hashcode(source)
204 targetCode := hashcode(target)
206 // Do we have this already? If so, don't add it again.
207 if s, ok := g.downEdges[sourceCode]; ok && s.Include(target) {
211 // Add the edge to the set
215 s, ok := g.downEdges[sourceCode]
218 g.downEdges[sourceCode] = s
223 s, ok = g.upEdges[targetCode]
226 g.upEdges[targetCode] = s
231 // String outputs some human-friendly output for the graph structure.
232 func (g *Graph) StringWithNodeTypes() string {
235 // Build the list of node names and a mapping so that we can more
236 // easily alphabetize the output to remain deterministic.
237 vertices := g.Vertices()
238 names := make([]string, 0, len(vertices))
239 mapping := make(map[string]Vertex, len(vertices))
240 for _, v := range vertices {
241 name := VertexName(v)
242 names = append(names, name)
247 // Write each node in order...
248 for _, name := range names {
250 targets := g.downEdges[hashcode(v)]
252 buf.WriteString(fmt.Sprintf("%s - %T\n", name, v))
254 // Alphabetize dependencies
255 deps := make([]string, 0, targets.Len())
256 targetNodes := make(map[string]Vertex)
257 for _, target := range targets.List() {
258 dep := VertexName(target)
259 deps = append(deps, dep)
260 targetNodes[dep] = target
264 // Write dependencies
265 for _, d := range deps {
266 buf.WriteString(fmt.Sprintf(" %s - %T\n", d, targetNodes[d]))
273 // String outputs some human-friendly output for the graph structure.
274 func (g *Graph) String() string {
277 // Build the list of node names and a mapping so that we can more
278 // easily alphabetize the output to remain deterministic.
279 vertices := g.Vertices()
280 names := make([]string, 0, len(vertices))
281 mapping := make(map[string]Vertex, len(vertices))
282 for _, v := range vertices {
283 name := VertexName(v)
284 names = append(names, name)
289 // Write each node in order...
290 for _, name := range names {
292 targets := g.downEdges[hashcode(v)]
294 buf.WriteString(fmt.Sprintf("%s\n", name))
296 // Alphabetize dependencies
297 deps := make([]string, 0, targets.Len())
298 for _, target := range targets.List() {
299 deps = append(deps, VertexName(target))
303 // Write dependencies
304 for _, d := range deps {
305 buf.WriteString(fmt.Sprintf(" %s\n", d))
312 func (g *Graph) init() {
313 if g.vertices == nil {
314 g.vertices = new(Set)
319 if g.downEdges == nil {
320 g.downEdges = make(map[interface{}]*Set)
322 if g.upEdges == nil {
323 g.upEdges = make(map[interface{}]*Set)
327 // Dot returns a dot-formatted representation of the Graph.
328 func (g *Graph) Dot(opts *DotOpts) []byte {
329 return newMarshalGraph("", g).Dot(opts)
332 // MarshalJSON returns a JSON representation of the entire Graph.
333 func (g *Graph) MarshalJSON() ([]byte, error) {
334 dg := newMarshalGraph("root", g)
335 return json.MarshalIndent(dg, "", " ")
338 // SetDebugWriter sets the io.Writer where the Graph will record debug
339 // information. After this is set, the graph will immediately encode itself to
340 // the stream, and continue to record all subsequent operations.
341 func (g *Graph) SetDebugWriter(w io.Writer) {
342 g.debug = &encoder{w: w}
343 g.debug.Encode(newMarshalGraph("root", g))
346 // DebugVertexInfo encodes arbitrary information about a vertex in the graph
348 func (g *Graph) DebugVertexInfo(v Vertex, info string) {
349 va := newVertexInfo(typeVertexInfo, v, info)
353 // DebugEdgeInfo encodes arbitrary information about an edge in the graph debug
355 func (g *Graph) DebugEdgeInfo(e Edge, info string) {
356 ea := newEdgeInfo(typeEdgeInfo, e, info)
360 // DebugVisitInfo records a visit to a Vertex during a walk operation.
361 func (g *Graph) DebugVisitInfo(v Vertex, info string) {
362 vi := newVertexInfo(typeVisitInfo, v, info)
366 // DebugOperation marks the start of a set of graph transformations in
367 // the debug log, and returns a DebugOperationEnd func, which marks the end of
368 // the operation in the log. Additional information can be added to the log via
369 // the info parameter.
371 // The returned func's End method allows this method to be called from a single
373 // defer g.DebugOperationBegin("OpName", "operating").End("")
375 // The returned function must be called to properly close the logical operation
377 func (g *Graph) DebugOperation(operation string, info string) DebugOperationEnd {
378 return g.debug.BeginOperation(operation, info)
381 // VertexName returns the name of a vertex.
382 func VertexName(raw Vertex) string {
383 switch v := raw.(type) {
387 return fmt.Sprintf("%s", v)
389 return fmt.Sprintf("%v", v)