15561477203

Committed 10 Jun 2025 01:54PM UTC coverage: 58.351% (-10.1%) from 68.487%

Build # 15561477203

Build Type

Pull #9356

github

Committed by

web-flow

Commit Message

Merge 6440b25db into c6d6d4c0b

Pull Request Pull Request #9356: lnrpc: add incoming/outgoing channel ids filter to forwarding history request

Run Details

33 of 36 new or added lines in 2 files covered. (91.67%)

28366 existing lines in 455 files now uncovered.

97715 of 167461 relevant lines covered (58.35%)

1.81 hits per line

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

28.21

/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 {	3✔
31	metric, err := NewBetweennessCentralityMetric(	3✔
32	runtime.NumCPU(),	3✔
33	)	3✔
34	if err != nil {	3✔
35	panic(err)	×
36	}
37
38	return &TopCentrality{	3✔
39	centralityMetric: metric,	3✔
40	}	3✔
41	}
42
43	// Name returns the name of the heuristic.
44	func (g *TopCentrality) Name() string {	3✔
45	return "top_centrality"	3✔
46	}	3✔
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,
UNCOV 56	nodes map[NodeID]struct{}) (map[NodeID]*NodeScore, error) {	×
UNCOV 57		×
UNCOV 58	// Calculate betweenness centrality for the whole graph.	×
UNCOV 59	if err := g.centralityMetric.Refresh(ctx, graph); err != nil {	×
60	return nil, err	×
61	}	×
62
UNCOV 63	normalize := true	×
UNCOV 64	centrality := g.centralityMetric.GetMetric(normalize)	×
UNCOV 65		×
UNCOV 66	// Create a map of the existing peers for faster filtering.	×
UNCOV 67	existingPeers := make(map[NodeID]struct{})	×
UNCOV 68	for _, c := range chans {	×
UNCOV 69	existingPeers[c.Node] = struct{}{}	×
UNCOV 70	}	×
71
UNCOV 72	result := make(map[NodeID]*NodeScore, len(nodes))	×
UNCOV 73	for nodeID := range nodes {	×
UNCOV 74	// Skip nodes we already have channel with.	×
UNCOV 75	if _, ok := existingPeers[nodeID]; ok {	×
UNCOV 76	continue	×
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.
UNCOV 82	score, ok := centrality[nodeID]	×
UNCOV 83	if !ok {	×
84	continue	×
85	}
86
UNCOV 87	result[nodeID] = &NodeScore{	×
UNCOV 88	NodeID: nodeID,	×
UNCOV 89	Score: score,	×
UNCOV 90	}	×
91	}
92
UNCOV 93	return result, nil	×
94	}

lightningnetwork / lnd / 15561477203

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