13566028875

Committed 27 Feb 2025 12:09PM UTC coverage: 49.396% (-9.4%) from 58.748%

Build # 13566028875

Build Type

Pull #9555

github

Committed by

ellemouton

Commit Message

graph/db: populate the graph cache in Start instead of during construction

In this commit, we move the graph cache population logic out of the
ChannelGraph constructor and into its Start method instead.

Pull Request Pull Request #9555: graph: extract cache from CRUD [6]

Run Details

34 of 54 new or added lines in 4 files covered. (62.96%)

27464 existing lines in 436 files now uncovered.

101095 of 204664 relevant lines covered (49.4%)

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

lightningnetwork / lnd / 13566028875

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