14193549836

Committed 01 Apr 2025 10:40AM UTC coverage: 69.046% (+0.007%) from 69.039%

Build # 14193549836

Build Type

Pull #9665

github

Committed by

web-flow

Commit Message

Merge e8825f209 into b01f4e514

Pull Request Pull Request #9665: kvdb: bump etcd libs to v3.5.12

Run Details

133439 of 193262 relevant lines covered (69.05%)

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

lightningnetwork / lnd / 14193549836

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