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_test
6
7import (
8	"fmt"
9
10	"gonum.org/v1/gonum/graph"
11	"gonum.org/v1/gonum/graph/iterator"
12	"gonum.org/v1/gonum/graph/simple"
13	"gonum.org/v1/gonum/graph/topo"
14)
15
16// GraphNode is a node in an implicit graph.
17type GraphNode struct {
18	id        int64
19	neighbors []graph.Node
20	roots     []*GraphNode
21}
22
23// NewGraphNode returns a new GraphNode.
24func NewGraphNode(id int64) *GraphNode {
25	return &GraphNode{id: id}
26}
27
28// Node allows GraphNode to satisfy the graph.Graph interface.
29func (g *GraphNode) Node(id int64) graph.Node {
30	if id == g.id {
31		return g
32	}
33
34	seen := map[int64]struct{}{g.id: {}}
35	for _, root := range g.roots {
36		if root.ID() == id {
37			return root
38		}
39
40		if root.has(seen, id) {
41			return root
42		}
43	}
44
45	for _, n := range g.neighbors {
46		if n.ID() == id {
47			return n
48		}
49
50		if gn, ok := n.(*GraphNode); ok {
51			if gn.has(seen, id) {
52				return gn
53			}
54		}
55	}
56
57	return nil
58}
59
60func (g *GraphNode) has(seen map[int64]struct{}, id int64) bool {
61	for _, root := range g.roots {
62		if _, ok := seen[root.ID()]; ok {
63			continue
64		}
65
66		seen[root.ID()] = struct{}{}
67		if root.ID() == id {
68			return true
69		}
70
71		if root.has(seen, id) {
72			return true
73		}
74
75	}
76
77	for _, n := range g.neighbors {
78		if _, ok := seen[n.ID()]; ok {
79			continue
80		}
81
82		seen[n.ID()] = struct{}{}
83		if n.ID() == id {
84			return true
85		}
86
87		if gn, ok := n.(*GraphNode); ok {
88			if gn.has(seen, id) {
89				return true
90			}
91		}
92	}
93
94	return false
95}
96
97// Nodes allows GraphNode to satisfy the graph.Graph interface.
98func (g *GraphNode) Nodes() graph.Nodes {
99	nodes := []graph.Node{g}
100	seen := map[int64]struct{}{g.id: {}}
101
102	for _, root := range g.roots {
103		nodes = append(nodes, root)
104		seen[root.ID()] = struct{}{}
105
106		nodes = root.nodes(nodes, seen)
107	}
108
109	for _, n := range g.neighbors {
110		nodes = append(nodes, n)
111		seen[n.ID()] = struct{}{}
112
113		if gn, ok := n.(*GraphNode); ok {
114			nodes = gn.nodes(nodes, seen)
115		}
116	}
117
118	return iterator.NewOrderedNodes(nodes)
119}
120
121func (g *GraphNode) nodes(dst []graph.Node, seen map[int64]struct{}) []graph.Node {
122	for _, root := range g.roots {
123		if _, ok := seen[root.ID()]; ok {
124			continue
125		}
126		seen[root.ID()] = struct{}{}
127		dst = append(dst, graph.Node(root))
128
129		dst = root.nodes(dst, seen)
130	}
131
132	for _, n := range g.neighbors {
133		if _, ok := seen[n.ID()]; ok {
134			continue
135		}
136
137		dst = append(dst, n)
138		if gn, ok := n.(*GraphNode); ok {
139			dst = gn.nodes(dst, seen)
140		}
141	}
142
143	return dst
144}
145
146// From allows GraphNode to satisfy the graph.Graph interface.
147func (g *GraphNode) From(id int64) graph.Nodes {
148	if id == g.ID() {
149		return iterator.NewOrderedNodes(g.neighbors)
150	}
151
152	seen := map[int64]struct{}{g.id: {}}
153	for _, root := range g.roots {
154		seen[root.ID()] = struct{}{}
155
156		if result := root.findNeighbors(id, seen); result != nil {
157			return iterator.NewOrderedNodes(result)
158		}
159	}
160
161	for _, n := range g.neighbors {
162		seen[n.ID()] = struct{}{}
163
164		if gn, ok := n.(*GraphNode); ok {
165			if result := gn.findNeighbors(id, seen); result != nil {
166				return iterator.NewOrderedNodes(result)
167			}
168		}
169	}
170
171	return nil
172}
173
174func (g *GraphNode) findNeighbors(id int64, seen map[int64]struct{}) []graph.Node {
175	if id == g.ID() {
176		return g.neighbors
177	}
178
179	for _, root := range g.roots {
180		if _, ok := seen[root.ID()]; ok {
181			continue
182		}
183		seen[root.ID()] = struct{}{}
184
185		if result := root.findNeighbors(id, seen); result != nil {
186			return result
187		}
188	}
189
190	for _, n := range g.neighbors {
191		if _, ok := seen[n.ID()]; ok {
192			continue
193		}
194		seen[n.ID()] = struct{}{}
195
196		if gn, ok := n.(*GraphNode); ok {
197			if result := gn.findNeighbors(id, seen); result != nil {
198				return result
199			}
200		}
201	}
202
203	return nil
204}
205
206// HasEdgeBetween allows GraphNode to satisfy the graph.Graph interface.
207func (g *GraphNode) HasEdgeBetween(uid, vid int64) bool {
208	return g.EdgeBetween(uid, vid) != nil
209}
210
211// Edge allows GraphNode to satisfy the graph.Graph interface.
212func (g *GraphNode) Edge(uid, vid int64) graph.Edge {
213	return g.EdgeBetween(uid, vid)
214}
215
216// EdgeBetween allows GraphNode to satisfy the graph.Graph interface.
217func (g *GraphNode) EdgeBetween(uid, vid int64) graph.Edge {
218	if uid == g.id || vid == g.id {
219		for _, n := range g.neighbors {
220			if n.ID() == uid || n.ID() == vid {
221				return simple.Edge{F: g, T: n}
222			}
223		}
224		return nil
225	}
226
227	seen := map[int64]struct{}{g.id: {}}
228	for _, root := range g.roots {
229		seen[root.ID()] = struct{}{}
230		if result := root.edgeBetween(uid, vid, seen); result != nil {
231			return result
232		}
233	}
234
235	for _, n := range g.neighbors {
236		seen[n.ID()] = struct{}{}
237		if gn, ok := n.(*GraphNode); ok {
238			if result := gn.edgeBetween(uid, vid, seen); result != nil {
239				return result
240			}
241		}
242	}
243
244	return nil
245}
246
247func (g *GraphNode) edgeBetween(uid, vid int64, seen map[int64]struct{}) graph.Edge {
248	if uid == g.id || vid == g.id {
249		for _, n := range g.neighbors {
250			if n.ID() == uid || n.ID() == vid {
251				return simple.Edge{F: g, T: n}
252			}
253		}
254		return nil
255	}
256
257	for _, root := range g.roots {
258		if _, ok := seen[root.ID()]; ok {
259			continue
260		}
261		seen[root.ID()] = struct{}{}
262		if result := root.edgeBetween(uid, vid, seen); result != nil {
263			return result
264		}
265	}
266
267	for _, n := range g.neighbors {
268		if _, ok := seen[n.ID()]; ok {
269			continue
270		}
271
272		seen[n.ID()] = struct{}{}
273		if gn, ok := n.(*GraphNode); ok {
274			if result := gn.edgeBetween(uid, vid, seen); result != nil {
275				return result
276			}
277		}
278	}
279
280	return nil
281}
282
283// ID allows GraphNode to satisfy the graph.Node interface.
284func (g *GraphNode) ID() int64 {
285	return g.id
286}
287
288// AddMeighbor adds an edge between g and n.
289func (g *GraphNode) AddNeighbor(n *GraphNode) {
290	g.neighbors = append(g.neighbors, graph.Node(n))
291}
292
293// AddRoot adds provides an entrance into the graph g from n.
294func (g *GraphNode) AddRoot(n *GraphNode) {
295	g.roots = append(g.roots, n)
296}
297
298func Example_implicit() {
299	// This example shows the construction of the following graph
300	// using the implicit graph type above.
301	//
302	// The visual representation of the graph can be seen at
303	// https://graphviz.gitlab.io/_pages/Gallery/undirected/fdpclust.html
304	//
305	// graph G {
306	// 	e
307	// 	subgraph clusterA {
308	// 		a -- b
309	// 		subgraph clusterC {
310	// 			C -- D
311	// 		}
312	// 	}
313	// 	subgraph clusterB {
314	// 		d -- f
315	// 	}
316	// 	d -- D
317	// 	e -- clusterB
318	// 	clusterC -- clusterB
319	// }
320
321	// graph G {
322	G := NewGraphNode(0)
323	// 	e
324	e := NewGraphNode(1)
325
326	// 	subgraph clusterA {
327	clusterA := NewGraphNode(2)
328	// 		a -- b
329	a := NewGraphNode(3)
330	b := NewGraphNode(4)
331	a.AddNeighbor(b)
332	b.AddNeighbor(a)
333	clusterA.AddRoot(a)
334	clusterA.AddRoot(b)
335
336	// 		subgraph clusterC {
337	clusterC := NewGraphNode(5)
338	// 			C -- D
339	C := NewGraphNode(6)
340	D := NewGraphNode(7)
341	C.AddNeighbor(D)
342	D.AddNeighbor(C)
343
344	clusterC.AddRoot(C)
345	clusterC.AddRoot(D)
346	// 		}
347	clusterA.AddRoot(clusterC)
348	// 	}
349
350	// 	subgraph clusterB {
351	clusterB := NewGraphNode(8)
352	// 		d -- f
353	d := NewGraphNode(9)
354	f := NewGraphNode(10)
355	d.AddNeighbor(f)
356	f.AddNeighbor(d)
357	clusterB.AddRoot(d)
358	clusterB.AddRoot(f)
359	// 	}
360
361	// 	d -- D
362	d.AddNeighbor(D)
363	D.AddNeighbor(d)
364
365	// 	e -- clusterB
366	e.AddNeighbor(clusterB)
367	clusterB.AddNeighbor(e)
368
369	// 	clusterC -- clusterB
370	clusterC.AddNeighbor(clusterB)
371	clusterB.AddNeighbor(clusterC)
372
373	G.AddRoot(e)
374	G.AddRoot(clusterA)
375	G.AddRoot(clusterB)
376	// }
377
378	if topo.IsPathIn(G, []graph.Node{C, D, d, f}) {
379		fmt.Println("C--D--d--f is a path in G.")
380	}
381
382	// Output:
383	//
384	// C--D--d--f is a path in G.
385}
386