13035292482

Committed 29 Jan 2025 03:59PM UTC coverage: 49.3% (-9.5%) from 58.777%

Build # 13035292482

Build Type

Pull #9456

github

Committed by

mohamedawnallah

Commit Message

docs: update release-notes-0.19.0.md

In this commit, we warn users about the removal
of RPCs `SendToRoute`, `SendToRouteSync`, `SendPayment`,
and `SendPaymentSync` in the next release 0.20.

Pull Request Pull Request #9456: lnrpc+docs: deprecate warning `SendToRoute`, `SendToRouteSync`, `SendPayment`, and `SendPaymentSync` in Release 0.19

Run Details

100634 of 204126 relevant lines covered (49.3%)

1.54 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

3.66

/autopilot/betweenness_centrality.go

package autopilot

import (
        "fmt"
        "sync"
)

// stack is a simple int stack to help with readability of Brandes'
// betweenness centrality implementation below.
type stack struct {
        stack []int
}

func (s *stack) push(v int) {
        s.stack = append(s.stack, v)
}

func (s *stack) top() int {
        return s.stack[len(s.stack)-1]
}

func (s *stack) pop() {
        s.stack = s.stack[:len(s.stack)-1]
}

func (s *stack) empty() bool {
        return len(s.stack) == 0
}

// queue is a simple int queue to help with readability of Brandes'
// betweenness centrality implementation below.
type queue struct {
        queue []int
}

func (q *queue) push(v int) {
        q.queue = append(q.queue, v)
}

func (q *queue) front() int {
        return q.queue[0]
}

func (q *queue) pop() {
        q.queue = q.queue[1:]
}

func (q *queue) empty() bool {
        return len(q.queue) == 0
}

// BetweennessCentrality is a NodeMetric that calculates node betweenness
// centrality using Brandes' algorithm. Betweenness centrality for each node
// is the number of shortest paths passing through that node, not counting
// shortest paths starting or ending at that node. This is a useful metric
// to measure control of individual nodes over the whole network.
type BetweennessCentrality struct {
        // workers number of goroutines are used to parallelize
        // centrality calculation.
        workers int

        // centrality stores original (not normalized) centrality values for
        // each node in the graph.
        centrality map[NodeID]float64

        // min is the minimum centrality in the graph.
        min float64

        // max is the maximum centrality in the graph.
        max float64
}

// NewBetweennessCentralityMetric creates a new BetweennessCentrality instance.
// Users can specify the number of workers to use for calculating centrality.
func NewBetweennessCentralityMetric(workers int) (*BetweennessCentrality, error) {
        // There should be at least one worker.
        if workers < 1 {
                return nil, fmt.Errorf("workers must be positive")
        }
        return &BetweennessCentrality{
                workers: workers,
        }, nil
}

// Name returns the name of the metric.
func (bc *BetweennessCentrality) Name() string {
        return "betweenness_centrality"
}

// betweennessCentrality is the core of Brandes' algorithm.
// We first calculate the shortest paths from the start node s to all other
// nodes with BFS, then update the betweenness centrality values by using
// Brandes' dependency trick.
// For detailed explanation please read:
// https://www.cl.cam.ac.uk/teaching/1617/MLRD/handbook/brandes.html
func betweennessCentrality(g *SimpleGraph, s int, centrality []float64) {
        // pred[w] is the list of nodes that immediately precede w on a
        // shortest path from s to t for each node t.
        pred := make([][]int, len(g.Nodes))

        // sigma[t] is the number of shortest paths between nodes s and t
        // for each node t.
        sigma := make([]int, len(g.Nodes))
        sigma[s] = 1

        // dist[t] holds the distance between s and t for each node t.
        // We initialize this to -1 (meaning infinity) for each t != s.
        dist := make([]int, len(g.Nodes))
        for i := range dist {
                dist[i] = -1
        }

        dist[s] = 0

        var (
                st stack
                q  queue
        )
        q.push(s)

        // BFS to calculate the shortest paths (sigma and pred)
        // from s to t for each node t.
        for !q.empty() {
                v := q.front()
                q.pop()
                st.push(v)

                for _, w := range g.Adj[v] {
                        // If distance from s to w is infinity (-1)
                        // then set it and enqueue w.
                        if dist[w] < 0 {
                                dist[w] = dist[v] + 1
                                q.push(w)
                        }

                        // If w is on a shortest path the update
                        // sigma and add v to w's predecessor list.
                        if dist[w] == dist[v]+1 {
                                sigma[w] += sigma[v]
                                pred[w] = append(pred[w], v)
                        }
                }
        }

        // delta[v] is the ratio of the shortest paths between s and t that go
        // through v and the total number of shortest paths between s and t.
        // If we have delta then the betweenness centrality is simply the sum
        // of delta[w] for each w != s.
        delta := make([]float64, len(g.Nodes))

        for !st.empty() {
                w := st.top()
                st.pop()

                // pred[w] is the list of nodes that immediately precede w on a
                // shortest path from s.
                for _, v := range pred[w] {
                        // Update delta using Brandes' equation.
                        delta[v] += (float64(sigma[v]) / float64(sigma[w])) * (1.0 + delta[w])
                }

                if w != s {
                        // As noted above centrality is simply the sum
                        // of delta[w] for each w != s.
                        centrality[w] += delta[w]
                }
        }
}

// Refresh recalculates and stores centrality values.
func (bc *BetweennessCentrality) Refresh(graph ChannelGraph) error {
        cache, err := NewSimpleGraph(graph)
        if err != nil {
                return err
        }

        var wg sync.WaitGroup
        work := make(chan int)
        partials := make(chan []float64, bc.workers)

        // Each worker will compute a partial result.
        // This partial result is a sum of centrality updates
        // on roughly N / workers nodes.
        worker := func() {
                defer wg.Done()
                partial := make([]float64, len(cache.Nodes))

                // Consume the next node, update centrality
                // parital to avoid unnecessary synchronization.
                for node := range work {
                        betweennessCentrality(cache, node, partial)
                }
                partials <- partial
        }

        // Now start the N workers.
        wg.Add(bc.workers)
        for i := 0; i < bc.workers; i++ {
                go worker()
        }

        // Distribute work amongst workers.
        // Should be fair when the graph is sufficiently large.
        for node := range cache.Nodes {
                work <- node
        }

        close(work)
        wg.Wait()
        close(partials)

        // Collect and sum partials for final result.
        centrality := make([]float64, len(cache.Nodes))
        for partial := range partials {
                for i := 0; i < len(partial); i++ {
                        centrality[i] += partial[i]
                }
        }

        // Get min/max to be able to normalize
        // centrality values between 0 and 1.
        bc.min = 0
        bc.max = 0
        if len(centrality) > 0 {
                for _, v := range centrality {
                        if v < bc.min {
                                bc.min = v
                        } else if v > bc.max {
                                bc.max = v
                        }
                }
        }

        // Divide by two as this is an undirected graph.
        bc.min /= 2.0
        bc.max /= 2.0

        bc.centrality = make(map[NodeID]float64)
        for u, value := range centrality {
                // Divide by two as this is an undirected graph.
                bc.centrality[cache.Nodes[u]] = value / 2.0
        }

        return nil
}

// GetMetric returns the current centrality values for each node indexed
// by node id.
func (bc *BetweennessCentrality) GetMetric(normalize bool) map[NodeID]float64 {
        // Normalization factor.
        var z float64
        if (bc.max - bc.min) > 0 {
                z = 1.0 / (bc.max - bc.min)
        }

        centrality := make(map[NodeID]float64)
        for k, v := range bc.centrality {
                if normalize {
                        v = (v - bc.min) * z
                }
                centrality[k] = v
        }

        return centrality
}

1	package autopilot
2
3	import (
4	"fmt"
5	"sync"
6	)
7
8	// stack is a simple int stack to help with readability of Brandes'
9	// betweenness centrality implementation below.
10	type stack struct {
11	stack []int
12	}
13
14	func (s *stack) push(v int) {	×
15	s.stack = append(s.stack, v)	×
16	}	×
17
18	func (s *stack) top() int {	×
19	return s.stack[len(s.stack)-1]	×
20	}	×
21
22	func (s *stack) pop() {	×
23	s.stack = s.stack[:len(s.stack)-1]	×
24	}	×
25
26	func (s *stack) empty() bool {	×
27	return len(s.stack) == 0	×
28	}	×
29
30	// queue is a simple int queue to help with readability of Brandes'
31	// betweenness centrality implementation below.
32	type queue struct {
33	queue []int
34	}
35
36	func (q *queue) push(v int) {	×
37	q.queue = append(q.queue, v)	×
38	}	×
39
40	func (q *queue) front() int {	×
41	return q.queue[0]	×
42	}	×
43
44	func (q *queue) pop() {	×
45	q.queue = q.queue[1:]	×
46	}	×
47
48	func (q *queue) empty() bool {	×
49	return len(q.queue) == 0	×
50	}	×
51
52	// BetweennessCentrality is a NodeMetric that calculates node betweenness
53	// centrality using Brandes' algorithm. Betweenness centrality for each node
54	// is the number of shortest paths passing through that node, not counting
55	// shortest paths starting or ending at that node. This is a useful metric
56	// to measure control of individual nodes over the whole network.
57	type BetweennessCentrality struct {
58	// workers number of goroutines are used to parallelize
59	// centrality calculation.
60	workers int
61
62	// centrality stores original (not normalized) centrality values for
63	// each node in the graph.
64	centrality map[NodeID]float64
65
66	// min is the minimum centrality in the graph.
67	min float64
68
69	// max is the maximum centrality in the graph.
70	max float64
71	}
72
73	// NewBetweennessCentralityMetric creates a new BetweennessCentrality instance.
74	// Users can specify the number of workers to use for calculating centrality.
75	func NewBetweennessCentralityMetric(workers int) (*BetweennessCentrality, error) {	3✔
76	// There should be at least one worker.	3✔
77	if workers < 1 {	3✔
78	return nil, fmt.Errorf("workers must be positive")	×
79	}	×
80	return &BetweennessCentrality{	3✔
81	workers: workers,	3✔
82	}, nil	3✔
83	}
84
85	// Name returns the name of the metric.
86	func (bc *BetweennessCentrality) Name() string {	×
87	return "betweenness_centrality"	×
88	}	×
89
90	// betweennessCentrality is the core of Brandes' algorithm.
91	// We first calculate the shortest paths from the start node s to all other
92	// nodes with BFS, then update the betweenness centrality values by using
93	// Brandes' dependency trick.
94	// For detailed explanation please read:
95	// https://www.cl.cam.ac.uk/teaching/1617/MLRD/handbook/brandes.html
96	func betweennessCentrality(g *SimpleGraph, s int, centrality []float64) {	×
97	// pred[w] is the list of nodes that immediately precede w on a	×
98	// shortest path from s to t for each node t.	×
99	pred := make([][]int, len(g.Nodes))	×
100		×
101	// sigma[t] is the number of shortest paths between nodes s and t	×
102	// for each node t.	×
103	sigma := make([]int, len(g.Nodes))	×
104	sigma[s] = 1	×
105		×
106	// dist[t] holds the distance between s and t for each node t.	×
107	// We initialize this to -1 (meaning infinity) for each t != s.	×
108	dist := make([]int, len(g.Nodes))	×
109	for i := range dist {	×
110	dist[i] = -1	×
111	}	×
112
113	dist[s] = 0	×
114		×
115	var (	×
116	st stack	×
117	q queue	×
118	)	×
119	q.push(s)	×
120		×
121	// BFS to calculate the shortest paths (sigma and pred)	×
122	// from s to t for each node t.	×
123	for !q.empty() {	×
124	v := q.front()	×
125	q.pop()	×
126	st.push(v)	×
127		×
128	for _, w := range g.Adj[v] {	×
129	// If distance from s to w is infinity (-1)	×
130	// then set it and enqueue w.	×
131	if dist[w] < 0 {	×
132	dist[w] = dist[v] + 1	×
133	q.push(w)	×
134	}	×
135
136	// If w is on a shortest path the update
137	// sigma and add v to w's predecessor list.
138	if dist[w] == dist[v]+1 {	×
139	sigma[w] += sigma[v]	×
140	pred[w] = append(pred[w], v)	×
141	}	×
142	}
143	}
144
145	// delta[v] is the ratio of the shortest paths between s and t that go
146	// through v and the total number of shortest paths between s and t.
147	// If we have delta then the betweenness centrality is simply the sum
148	// of delta[w] for each w != s.
149	delta := make([]float64, len(g.Nodes))	×
150		×
151	for !st.empty() {	×
152	w := st.top()	×
153	st.pop()	×
154		×
155	// pred[w] is the list of nodes that immediately precede w on a	×
156	// shortest path from s.	×
157	for _, v := range pred[w] {	×
158	// Update delta using Brandes' equation.	×
159	delta[v] += (float64(sigma[v]) / float64(sigma[w])) * (1.0 + delta[w])	×
160	}	×
161
162	if w != s {	×
163	// As noted above centrality is simply the sum	×
164	// of delta[w] for each w != s.	×
165	centrality[w] += delta[w]	×
166	}	×
167	}
168	}
169
170	// Refresh recalculates and stores centrality values.
171	func (bc *BetweennessCentrality) Refresh(graph ChannelGraph) error {	×
172	cache, err := NewSimpleGraph(graph)	×
173	if err != nil {	×
174	return err	×
175	}	×
176
177	var wg sync.WaitGroup	×
178	work := make(chan int)	×
179	partials := make(chan []float64, bc.workers)	×
180		×
181	// Each worker will compute a partial result.	×
182	// This partial result is a sum of centrality updates	×
183	// on roughly N / workers nodes.	×
184	worker := func() {	×
185	defer wg.Done()	×
186	partial := make([]float64, len(cache.Nodes))	×
187		×
188	// Consume the next node, update centrality	×
189	// parital to avoid unnecessary synchronization.	×
190	for node := range work {	×
191	betweennessCentrality(cache, node, partial)	×
192	}	×
193	partials <- partial	×
194	}
195
196	// Now start the N workers.
197	wg.Add(bc.workers)	×
198	for i := 0; i < bc.workers; i++ {	×
199	go worker()	×
200	}	×
201
202	// Distribute work amongst workers.
203	// Should be fair when the graph is sufficiently large.
204	for node := range cache.Nodes {	×
205	work <- node	×
206	}	×
207
208	close(work)	×
209	wg.Wait()	×
210	close(partials)	×
211		×
212	// Collect and sum partials for final result.	×
213	centrality := make([]float64, len(cache.Nodes))	×
214	for partial := range partials {	×
215	for i := 0; i < len(partial); i++ {	×
216	centrality[i] += partial[i]	×
217	}	×
218	}
219
220	// Get min/max to be able to normalize
221	// centrality values between 0 and 1.
222	bc.min = 0	×
223	bc.max = 0	×
224	if len(centrality) > 0 {	×
225	for _, v := range centrality {	×
226	if v < bc.min {	×
227	bc.min = v	×
228	} else if v > bc.max {	×
229	bc.max = v	×
230	}	×
231	}
232	}
233
234	// Divide by two as this is an undirected graph.
235	bc.min /= 2.0	×
236	bc.max /= 2.0	×
237		×
238	bc.centrality = make(map[NodeID]float64)	×
239	for u, value := range centrality {	×
240	// Divide by two as this is an undirected graph.	×
241	bc.centrality[cache.Nodes[u]] = value / 2.0	×
242	}	×
243
244	return nil	×
245	}
246
247	// GetMetric returns the current centrality values for each node indexed
248	// by node id.
249	func (bc *BetweennessCentrality) GetMetric(normalize bool) map[NodeID]float64 {	×
250	// Normalization factor.	×
251	var z float64	×
252	if (bc.max - bc.min) > 0 {	×
253	z = 1.0 / (bc.max - bc.min)	×
254	}	×
255
256	centrality := make(map[NodeID]float64)	×
257	for k, v := range bc.centrality {	×
258	if normalize {	×
259	v = (v - bc.min) * z	×
260	}	×
261	centrality[k] = v	×
262	}
263
264	return centrality	×
265	}

lightningnetwork / lnd / 13035292482

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous