1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
// Mgmt
// Copyright (C) 2013-2024+ James Shubin and the project contributors
// Written by James Shubin <james@shubin.ca> and the project contributors
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with this program. If not, see <https://www.gnu.org/licenses/>.
//
// Additional permission under GNU GPL version 3 section 7
//
// If you modify this program, or any covered work, by linking or combining it
// with embedded mcl code and modules (and that the embedded mcl code and
// modules which link with this program, contain a copy of their source code in
// the authoritative form) containing parts covered by the terms of any other
// license, the licensors of this program grant you additional permission to
// convey the resulting work. Furthermore, the licensors of this program grant
// the original author, James Shubin, additional permission to update this
// additional permission if he deems it necessary to achieve the goals of this
// additional permission.
package pgraph
// AddGraph adds the set of edges and vertices of a graph to the existing graph.
func (g *Graph) AddGraph(graph *Graph) {
g.addEdgeVertexGraphHelper(nil, graph, nil, false, false)
}
// AddEdgeVertexGraph adds a directed edge to the graph from a vertex. This is
// useful for flattening the relationship between a subgraph and an existing
// graph, without having to run the subgraph recursively. It adds the maximum
// number of edges, creating a relationship to every vertex.
func (g *Graph) AddEdgeVertexGraph(vertex Vertex, graph *Graph, edgeGenFn func(v1, v2 Vertex) Edge) {
g.addEdgeVertexGraphHelper(vertex, graph, edgeGenFn, false, false)
}
// AddEdgeVertexGraphLight adds a directed edge to the graph from a vertex. This
// is useful for flattening the relationship between a subgraph and an existing
// graph, without having to run the subgraph recursively. It adds the minimum
// number of edges, creating a relationship to the vertices with indegree equal
// to zero.
func (g *Graph) AddEdgeVertexGraphLight(vertex Vertex, graph *Graph, edgeGenFn func(v1, v2 Vertex) Edge) {
g.addEdgeVertexGraphHelper(vertex, graph, edgeGenFn, false, true)
}
// AddEdgeGraphVertex adds a directed edge to the vertex from a graph. This is
// useful for flattening the relationship between a subgraph and an existing
// graph, without having to run the subgraph recursively. It adds the maximum
// number of edges, creating a relationship from every vertex.
func (g *Graph) AddEdgeGraphVertex(graph *Graph, vertex Vertex, edgeGenFn func(v1, v2 Vertex) Edge) {
g.addEdgeVertexGraphHelper(vertex, graph, edgeGenFn, true, false)
}
// AddEdgeGraphVertexLight adds a directed edge to the vertex from a graph. This
// is useful for flattening the relationship between a subgraph and an existing
// graph, without having to run the subgraph recursively. It adds the minimum
// number of edges, creating a relationship from the vertices with outdegree
// equal to zero.
func (g *Graph) AddEdgeGraphVertexLight(graph *Graph, vertex Vertex, edgeGenFn func(v1, v2 Vertex) Edge) {
g.addEdgeVertexGraphHelper(vertex, graph, edgeGenFn, true, true)
}
// addEdgeVertexGraphHelper is a helper function to add a directed edges to the
// graph from a vertex, or vice-versa. It operates in this reverse direction by
// specifying the reverse argument as true. It is useful for flattening the
// relationship between a subgraph and an existing graph, without having to run
// the subgraph recursively. It adds the maximum number of edges, creating a
// relationship to or from every vertex if the light argument is false, and if
// it is true, it adds the minimum number of edges, creating a relationship to
// or from the vertices with an indegree or outdegree equal to zero depending on
// if we specified reverse or not.
func (g *Graph) addEdgeVertexGraphHelper(vertex Vertex, graph *Graph, edgeGenFn func(v1, v2 Vertex) Edge, reverse, light bool) {
if graph == nil {
return // if the graph is empty, there's nothing to do!
}
var degree map[Vertex]int // compute all of the in/outdegree's if needed
if light && reverse {
degree = graph.OutDegree()
} else if light { // && !reverse
degree = graph.InDegree()
}
for _, v := range graph.VerticesSorted() { // sort to help out edgeGenFn
// forward:
// we only want to add edges to indegree == 0, because every
// other vertex is a dependency of at least one of those
// reverse:
// we only want to add edges to outdegree == 0, because every
// other vertex is a pre-requisite to at least one of these
if light && degree[v] != 0 {
continue
}
g.AddVertex(v) // ensure vertex is part of the graph
if vertex != nil && reverse {
edge := edgeGenFn(v, vertex) // generate a new unique edge
g.AddEdge(v, vertex, edge)
} else if vertex != nil { // && !reverse
edge := edgeGenFn(vertex, v)
g.AddEdge(vertex, v, edge)
}
}
// also remember to suck in all of the graph's edges too!
for v1 := range graph.Adjacency() {
for v2, e := range graph.Adjacency()[v1] {
g.AddEdge(v1, v2, e)
}
}
}
|
