19155841408

Committed 07 Nov 2025 02:03AM UTC coverage: 66.675% (-0.04%) from 66.712%

Build # 19155841408

Build Type

Pull #10352

github

Committed by

web-flow

Commit Message

Merge e4313eba8 into 096ab65b1

Pull Request Pull Request #10352: [WIP] chainrpc: return Unavailable while notifier starts

Run Details

137328 of 205965 relevant lines covered (66.68%)

21333.36 hits per line

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

89.74

/autopilot/top_centrality.go

package autopilot

import (
        "context"
        "runtime"

        "github.com/btcsuite/btcd/btcutil"
)

// TopCentrality is a simple greedy technique to create connections to nodes
// with the top betweenness centrality value. This algorithm is usually
// referred to as TopK in the literature. The idea is that by opening channels
// to nodes with top betweenness centrality we also increase our own betweenness
// centrality (given we already have at least one channel, or create at least
// two new channels).
// A different and much better approach is instead of selecting nodes with top
// centrality value, we extend the graph in a loop by inserting a new non
// existing edge and recalculate the betweenness centrality of each node. This
// technique is usually referred to as "greedy" algorithm and gives better
// results than TopK but is considerably slower too.
type TopCentrality struct {
        centralityMetric *BetweennessCentrality
}

// A compile time assertion to ensure TopCentrality meets the
// AttachmentHeuristic interface.
var _ AttachmentHeuristic = (*TopCentrality)(nil)

// NewTopCentrality constructs and returns a new TopCentrality heuristic.
func NewTopCentrality() *TopCentrality {
        metric, err := NewBetweennessCentralityMetric(
                runtime.NumCPU(),
        )
        if err != nil {
                panic(err)
        }

        return &TopCentrality{
                centralityMetric: metric,
        }
}

// Name returns the name of the heuristic.
func (g *TopCentrality) Name() string {
        return "top_centrality"
}

// NodeScores will return a [0,1] normalized map of scores for the given nodes
// except for the ones we already have channels with. The scores will simply
// be the betweenness centrality values of the nodes.
// As our current implementation of betweenness centrality is non-incremental,
// NodeScores will recalculate the centrality values on every call, which is
// slow for large graphs.
func (g *TopCentrality) NodeScores(ctx context.Context, graph ChannelGraph,
        chans []LocalChannel, chanSize btcutil.Amount,
        nodes map[NodeID]struct{}) (map[NodeID]*NodeScore, error) {

        // Calculate betweenness centrality for the whole graph.
        if err := g.centralityMetric.Refresh(ctx, graph); err != nil {
                return nil, err
        }

        normalize := true
        centrality := g.centralityMetric.GetMetric(normalize)

        // Create a map of the existing peers for faster filtering.
        existingPeers := make(map[NodeID]struct{})
        for _, c := range chans {
                existingPeers[c.Node] = struct{}{}
        }

        result := make(map[NodeID]*NodeScore, len(nodes))
        for nodeID := range nodes {
                // Skip nodes we already have channel with.
                if _, ok := existingPeers[nodeID]; ok {
                        continue
                }

                // Skip passed nodes not in the graph. This could happen if
                // the graph changed before computing the centrality values as
                // the nodes we iterate are prefiltered by the autopilot agent.
                score, ok := centrality[nodeID]
                if !ok {
                        continue
                }

                result[nodeID] = &NodeScore{
                        NodeID: nodeID,
                        Score:  score,
                }
        }

        return result, nil
}

1	package autopilot
2
3	import (
4	"context"
5	"runtime"
6
7	"github.com/btcsuite/btcd/btcutil"
8	)
9
10	// TopCentrality is a simple greedy technique to create connections to nodes
11	// with the top betweenness centrality value. This algorithm is usually
12	// referred to as TopK in the literature. The idea is that by opening channels
13	// to nodes with top betweenness centrality we also increase our own betweenness
14	// centrality (given we already have at least one channel, or create at least
15	// two new channels).
16	// A different and much better approach is instead of selecting nodes with top
17	// centrality value, we extend the graph in a loop by inserting a new non
18	// existing edge and recalculate the betweenness centrality of each node. This
19	// technique is usually referred to as "greedy" algorithm and gives better
20	// results than TopK but is considerably slower too.
21	type TopCentrality struct {
22	centralityMetric *BetweennessCentrality
23	}
24
25	// A compile time assertion to ensure TopCentrality meets the
26	// AttachmentHeuristic interface.
27	var _ AttachmentHeuristic = (*TopCentrality)(nil)
28
29	// NewTopCentrality constructs and returns a new TopCentrality heuristic.
30	func NewTopCentrality() *TopCentrality {	34✔
31	metric, err := NewBetweennessCentralityMetric(	34✔
32	runtime.NumCPU(),	34✔
33	)	34✔
34	if err != nil {	34✔
35	panic(err)	×
36	}
37
38	return &TopCentrality{	34✔
39	centralityMetric: metric,	34✔
40	}	34✔
41	}
42
43	// Name returns the name of the heuristic.
44	func (g *TopCentrality) Name() string {	14✔
45	return "top_centrality"	14✔
46	}	14✔
47
48	// NodeScores will return a [0,1] normalized map of scores for the given nodes
49	// except for the ones we already have channels with. The scores will simply
50	// be the betweenness centrality values of the nodes.
51	// As our current implementation of betweenness centrality is non-incremental,
52	// NodeScores will recalculate the centrality values on every call, which is
53	// slow for large graphs.
54	func (g *TopCentrality) NodeScores(ctx context.Context, graph ChannelGraph,
55	chans []LocalChannel, chanSize btcutil.Amount,
56	nodes map[NodeID]struct{}) (map[NodeID]*NodeScore, error) {	200✔
57		200✔
58	// Calculate betweenness centrality for the whole graph.	200✔
59	if err := g.centralityMetric.Refresh(ctx, graph); err != nil {	200✔
60	return nil, err	×
61	}	×
62
63	normalize := true	200✔
64	centrality := g.centralityMetric.GetMetric(normalize)	200✔
65		200✔
66	// Create a map of the existing peers for faster filtering.	200✔
67	existingPeers := make(map[NodeID]struct{})	200✔
68	for _, c := range chans {	1,100✔
69	existingPeers[c.Node] = struct{}{}	900✔
70	}	900✔
71
72	result := make(map[NodeID]*NodeScore, len(nodes))	200✔
73	for nodeID := range nodes {	1,100✔
74	// Skip nodes we already have channel with.	900✔
75	if _, ok := existingPeers[nodeID]; ok {	1,470✔
76	continue	570✔
77	}
78
79	// Skip passed nodes not in the graph. This could happen if
80	// the graph changed before computing the centrality values as
81	// the nodes we iterate are prefiltered by the autopilot agent.
82	score, ok := centrality[nodeID]	330✔
83	if !ok {	330✔
84	continue	×
85	}
86
87	result[nodeID] = &NodeScore{	330✔
88	NodeID: nodeID,	330✔
89	Score: score,	330✔
90	}	330✔
91	}
92
93	return result, nil	200✔
94	}

lightningnetwork / lnd / 19155841408

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