17027244024

Committed 17 Aug 2025 11:32PM UTC coverage: 57.287% (-9.5%) from 66.765%

Build # 17027244024

Build Type

Pull #10167

github

Committed by

web-flow

Commit Message

Merge fcb4f4303 into fb1adfc21

Pull Request Pull Request #10167: multi: bump Go to 1.24.6

Run Details

3 of 18 new or added lines in 6 files covered. (16.67%)

28537 existing lines in 457 files now uncovered.

99094 of 172978 relevant lines covered (57.29%)

1.78 hits per line

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

0.0

/autopilot/simple_graph.go

package autopilot

import (
        "context"

        "github.com/lightningnetwork/lnd/routing/route"
)

// diameterCutoff is used to discard nodes in the diameter calculation.
// It is the multiplier for the eccentricity of the highest-degree node,
// serving as a cutoff to discard all nodes with a smaller hop distance. This
// number should not be set close to 1 and is a tradeoff for computation cost,
// where 0 is maximally costly.
const diameterCutoff = 0.75

// SimpleGraph stores a simplified adj graph of a channel graph to speed
// up graph processing by eliminating all unnecessary hashing and map access.
type SimpleGraph struct {
        // Nodes is a map from node index to NodeID.
        Nodes []NodeID

        // Adj stores nodes and neighbors in an adjacency list.
        Adj [][]int
}

// NewSimpleGraph creates a simplified graph from the current channel graph.
// Returns an error if the channel graph iteration fails due to underlying
// failure.
func NewSimpleGraph(ctx context.Context, g ChannelGraph) (*SimpleGraph, error) {
        nodes := make(map[NodeID]int)
        adj := make(map[int][]int)
        nextIndex := 0

        // getNodeIndex returns the integer index of the passed node.
        // The returned index is then used to create a simplified adjacency list
        // where each node is identified by its index instead of its pubkey, and
        // also to create a mapping from node index to node pubkey.
        getNodeIndex := func(node route.Vertex) int {
                key := NodeID(node)
                nodeIndex, ok := nodes[key]

                if !ok {
                        nodes[key] = nextIndex
                        nodeIndex = nextIndex
                        nextIndex++
                }

                return nodeIndex
        }

        // Iterate over each node and each channel and update the adj and the
        // node index.
        err := g.ForEachNodesChannels(ctx, func(_ context.Context,
                node Node, channels []*ChannelEdge) error {

                u := getNodeIndex(node.PubKey())

                for _, edge := range channels {
                        v := getNodeIndex(edge.Peer)
                        adj[u] = append(adj[u], v)
                }

                return nil
        }, func() {
                clear(adj)
                clear(nodes)
                nextIndex = 0
        })
        if err != nil {
                return nil, err
        }

        graph := &SimpleGraph{
                Nodes: make([]NodeID, len(nodes)),
                Adj:   make([][]int, len(nodes)),
        }

        // Fill the adj and the node index to node pubkey mapping.
        for nodeID, nodeIndex := range nodes {
                graph.Adj[nodeIndex] = adj[nodeIndex]
                graph.Nodes[nodeIndex] = nodeID
        }

        // We prepare to give some debug output about the size of the graph.
        totalChannels := 0
        for _, channels := range graph.Adj {
                totalChannels += len(channels)
        }

        // The number of channels is double counted, so divide by two.
        log.Debugf("Initialized simple graph with %d nodes and %d "+
                "channels", len(graph.Adj), totalChannels/2)
        return graph, nil
}

// maxVal is a helper function to get the maximal value of all values of a map.
func maxVal(mapping map[int]uint32) uint32 {
        maxValue := uint32(0)
        for _, value := range mapping {
                maxValue = max(maxValue, value)
        }
        return maxValue
}

// degree determines the number of edges for a node in the graph.
func (graph *SimpleGraph) degree(node int) int {
        return len(graph.Adj[node])
}

// nodeMaxDegree determines the node with the max degree and its degree.
func (graph *SimpleGraph) nodeMaxDegree() (int, int) {
        var maxNode, maxDegree int
        for node := range graph.Adj {
                degree := graph.degree(node)
                if degree > maxDegree {
                        maxNode = node
                        maxDegree = degree
                }
        }
        return maxNode, maxDegree
}

// shortestPathLengths performs a breadth-first-search from a node to all other
// nodes, returning the lengths of the paths.
func (graph *SimpleGraph) shortestPathLengths(node int) map[int]uint32 {
        // level indicates the shell of the search around the root node.
        var level uint32
        graphOrder := len(graph.Adj)

        // nextLevel tracks which nodes should be visited in the next round.
        nextLevel := make([]int, 0, graphOrder)

        // The root node is put as a starting point for the exploration.
        nextLevel = append(nextLevel, node)

        // Seen tracks already visited nodes and tracks how far away they are.
        seen := make(map[int]uint32, graphOrder)

        // Mark the root node as seen.
        seen[node] = level

        // thisLevel contains the nodes that are explored in the round.
        thisLevel := make([]int, 0, graphOrder)

        // Abort if we have an empty graph.
        if len(graph.Adj) == 0 {
                return seen
        }

        // We discover other nodes in a ring-like structure as long as we don't
        // have more nodes to explore.
        for len(nextLevel) > 0 {
                level++

                // We swap the queues for efficient memory management.
                thisLevel, nextLevel = nextLevel, thisLevel

                // Visit all neighboring nodes of the level and mark them as
                // seen if they were not discovered before.
                for _, thisNode := range thisLevel {
                        for _, neighbor := range graph.Adj[thisNode] {
                                _, ok := seen[neighbor]
                                if !ok {
                                        nextLevel = append(nextLevel, neighbor)
                                        seen[neighbor] = level
                                }

                                // If we have seen all nodes, we return early.
                                if len(seen) == graphOrder {
                                        return seen
                                }
                        }
                }

                // Empty the queue to be used in the next level.
                thisLevel = thisLevel[:0:cap(thisLevel)]
        }

        return seen
}

// nodeEccentricity calculates the eccentricity (longest shortest path to all
// other nodes) of a node.
func (graph *SimpleGraph) nodeEccentricity(node int) uint32 {
        pathLengths := graph.shortestPathLengths(node)
        return maxVal(pathLengths)
}

// nodeEccentricities calculates the eccentricities for the given nodes.
func (graph *SimpleGraph) nodeEccentricities(nodes []int) map[int]uint32 {
        eccentricities := make(map[int]uint32, len(graph.Adj))
        for _, node := range nodes {
                eccentricities[node] = graph.nodeEccentricity(node)
        }
        return eccentricities
}

// Diameter returns the maximal eccentricity (longest shortest path
// between any node pair) in the graph.
//
// Note: This method is exact but expensive, use DiameterRadialCutoff instead.
func (graph *SimpleGraph) Diameter() uint32 {
        nodes := make([]int, len(graph.Adj))
        for a := range nodes {
                nodes[a] = a
        }
        eccentricities := graph.nodeEccentricities(nodes)
        return maxVal(eccentricities)
}

// DiameterRadialCutoff is a method to efficiently evaluate the diameter of a
// graph. The highest-degree node is usually central in the graph. We can
// determine its eccentricity (shortest-longest path length to any other node)
// and use it as an approximation for the radius of the network. We then
// use this radius to compute a cutoff. All the nodes within a distance of the
// cutoff are discarded, as they represent the inside of the graph. We then
// loop over all outer nodes and determine their eccentricities, from which we
// get the diameter.
func (graph *SimpleGraph) DiameterRadialCutoff() uint32 {
        // Determine the reference node as the node with the highest degree.
        nodeMaxDegree, _ := graph.nodeMaxDegree()

        distances := graph.shortestPathLengths(nodeMaxDegree)
        eccentricityMaxDegreeNode := maxVal(distances)

        // We use the eccentricity to define a cutoff for the interior of the
        // graph from the reference node.
        cutoff := uint32(float32(eccentricityMaxDegreeNode) * diameterCutoff)
        log.Debugf("Cutoff radius is %d hops (max-degree node's "+
                "eccentricity is %d)", cutoff, eccentricityMaxDegreeNode)

        // Remove the nodes that are close to the reference node.
        var nodes []int
        for node, distance := range distances {
                if distance > cutoff {
                        nodes = append(nodes, node)
                }
        }
        log.Debugf("Evaluated nodes: %d, discarded nodes %d",
                len(nodes), len(graph.Adj)-len(nodes))

        // Compute the diameter of the remaining nodes.
        eccentricities := graph.nodeEccentricities(nodes)
        return maxVal(eccentricities)
}

1	package autopilot
2
3	import (
4	"context"
5
6	"github.com/lightningnetwork/lnd/routing/route"
7	)
8
9	// diameterCutoff is used to discard nodes in the diameter calculation.
10	// It is the multiplier for the eccentricity of the highest-degree node,
11	// serving as a cutoff to discard all nodes with a smaller hop distance. This
12	// number should not be set close to 1 and is a tradeoff for computation cost,
13	// where 0 is maximally costly.
14	const diameterCutoff = 0.75
15
16	// SimpleGraph stores a simplified adj graph of a channel graph to speed
17	// up graph processing by eliminating all unnecessary hashing and map access.
18	type SimpleGraph struct {
19	// Nodes is a map from node index to NodeID.
20	Nodes []NodeID
21
22	// Adj stores nodes and neighbors in an adjacency list.
23	Adj [][]int
24	}
25
26	// NewSimpleGraph creates a simplified graph from the current channel graph.
27	// Returns an error if the channel graph iteration fails due to underlying
28	// failure.
UNCOV 29	func NewSimpleGraph(ctx context.Context, g ChannelGraph) (*SimpleGraph, error) {	×
UNCOV 30	nodes := make(map[NodeID]int)	×
UNCOV 31	adj := make(map[int][]int)	×
UNCOV 32	nextIndex := 0	×
UNCOV 33		×
UNCOV 34	// getNodeIndex returns the integer index of the passed node.	×
UNCOV 35	// The returned index is then used to create a simplified adjacency list	×
UNCOV 36	// where each node is identified by its index instead of its pubkey, and	×
UNCOV 37	// also to create a mapping from node index to node pubkey.	×
UNCOV 38	getNodeIndex := func(node route.Vertex) int {	×
UNCOV 39	key := NodeID(node)	×
UNCOV 40	nodeIndex, ok := nodes[key]	×
UNCOV 41		×
UNCOV 42	if !ok {	×
UNCOV 43	nodes[key] = nextIndex	×
UNCOV 44	nodeIndex = nextIndex	×
UNCOV 45	nextIndex++	×
UNCOV 46	}	×
47
UNCOV 48	return nodeIndex	×
49	}
50
51	// Iterate over each node and each channel and update the adj and the
52	// node index.
UNCOV 53	err := g.ForEachNodesChannels(ctx, func(_ context.Context,	×
UNCOV 54	node Node, channels []*ChannelEdge) error {	×
UNCOV 55		×
UNCOV 56	u := getNodeIndex(node.PubKey())	×
UNCOV 57		×
UNCOV 58	for _, edge := range channels {	×
UNCOV 59	v := getNodeIndex(edge.Peer)	×
UNCOV 60	adj[u] = append(adj[u], v)	×
UNCOV 61	}	×
62
UNCOV 63	return nil	×
UNCOV 64	}, func() {	×
UNCOV 65	clear(adj)	×
UNCOV 66	clear(nodes)	×
UNCOV 67	nextIndex = 0	×
UNCOV 68	})	×
UNCOV 69	if err != nil {	×
70	return nil, err	×
71	}	×
72
UNCOV 73	graph := &SimpleGraph{	×
UNCOV 74	Nodes: make([]NodeID, len(nodes)),	×
UNCOV 75	Adj: make([][]int, len(nodes)),	×
UNCOV 76	}	×
UNCOV 77		×
UNCOV 78	// Fill the adj and the node index to node pubkey mapping.	×
UNCOV 79	for nodeID, nodeIndex := range nodes {	×
UNCOV 80	graph.Adj[nodeIndex] = adj[nodeIndex]	×
UNCOV 81	graph.Nodes[nodeIndex] = nodeID	×
UNCOV 82	}	×
83
84	// We prepare to give some debug output about the size of the graph.
UNCOV 85	totalChannels := 0	×
UNCOV 86	for _, channels := range graph.Adj {	×
UNCOV 87	totalChannels += len(channels)	×
UNCOV 88	}	×
89
90	// The number of channels is double counted, so divide by two.
UNCOV 91	log.Debugf("Initialized simple graph with %d nodes and %d "+	×
UNCOV 92	"channels", len(graph.Adj), totalChannels/2)	×
UNCOV 93	return graph, nil	×
94	}
95
96	// maxVal is a helper function to get the maximal value of all values of a map.
UNCOV 97	func maxVal(mapping map[int]uint32) uint32 {	×
UNCOV 98	maxValue := uint32(0)	×
UNCOV 99	for _, value := range mapping {	×
UNCOV 100	maxValue = max(maxValue, value)	×
UNCOV 101	}	×
UNCOV 102	return maxValue	×
103	}
104
105	// degree determines the number of edges for a node in the graph.
UNCOV 106	func (graph *SimpleGraph) degree(node int) int {	×
UNCOV 107	return len(graph.Adj[node])	×
UNCOV 108	}	×
109
110	// nodeMaxDegree determines the node with the max degree and its degree.
UNCOV 111	func (graph *SimpleGraph) nodeMaxDegree() (int, int) {	×
UNCOV 112	var maxNode, maxDegree int	×
UNCOV 113	for node := range graph.Adj {	×
UNCOV 114	degree := graph.degree(node)	×
UNCOV 115	if degree > maxDegree {	×
UNCOV 116	maxNode = node	×
UNCOV 117	maxDegree = degree	×
UNCOV 118	}	×
119	}
UNCOV 120	return maxNode, maxDegree	×
121	}
122
123	// shortestPathLengths performs a breadth-first-search from a node to all other
124	// nodes, returning the lengths of the paths.
UNCOV 125	func (graph *SimpleGraph) shortestPathLengths(node int) map[int]uint32 {	×
UNCOV 126	// level indicates the shell of the search around the root node.	×
UNCOV 127	var level uint32	×
UNCOV 128	graphOrder := len(graph.Adj)	×
UNCOV 129		×
UNCOV 130	// nextLevel tracks which nodes should be visited in the next round.	×
UNCOV 131	nextLevel := make([]int, 0, graphOrder)	×
UNCOV 132		×
UNCOV 133	// The root node is put as a starting point for the exploration.	×
UNCOV 134	nextLevel = append(nextLevel, node)	×
UNCOV 135		×
UNCOV 136	// Seen tracks already visited nodes and tracks how far away they are.	×
UNCOV 137	seen := make(map[int]uint32, graphOrder)	×
UNCOV 138		×
UNCOV 139	// Mark the root node as seen.	×
UNCOV 140	seen[node] = level	×
UNCOV 141		×
UNCOV 142	// thisLevel contains the nodes that are explored in the round.	×
UNCOV 143	thisLevel := make([]int, 0, graphOrder)	×
UNCOV 144		×
UNCOV 145	// Abort if we have an empty graph.	×
UNCOV 146	if len(graph.Adj) == 0 {	×
147	return seen	×
148	}	×
149
150	// We discover other nodes in a ring-like structure as long as we don't
151	// have more nodes to explore.
UNCOV 152	for len(nextLevel) > 0 {	×
UNCOV 153	level++	×
UNCOV 154		×
UNCOV 155	// We swap the queues for efficient memory management.	×
UNCOV 156	thisLevel, nextLevel = nextLevel, thisLevel	×
UNCOV 157		×
UNCOV 158	// Visit all neighboring nodes of the level and mark them as	×
UNCOV 159	// seen if they were not discovered before.	×
UNCOV 160	for _, thisNode := range thisLevel {	×
UNCOV 161	for _, neighbor := range graph.Adj[thisNode] {	×
UNCOV 162	_, ok := seen[neighbor]	×
UNCOV 163	if !ok {	×
UNCOV 164	nextLevel = append(nextLevel, neighbor)	×
UNCOV 165	seen[neighbor] = level	×
UNCOV 166	}	×
167
168	// If we have seen all nodes, we return early.
UNCOV 169	if len(seen) == graphOrder {	×
UNCOV 170	return seen	×
UNCOV 171	}	×
172	}
173	}
174
175	// Empty the queue to be used in the next level.
UNCOV 176	thisLevel = thisLevel[:0:cap(thisLevel)]	×
177	}
178
179	return seen	×
180	}
181
182	// nodeEccentricity calculates the eccentricity (longest shortest path to all
183	// other nodes) of a node.
UNCOV 184	func (graph *SimpleGraph) nodeEccentricity(node int) uint32 {	×
UNCOV 185	pathLengths := graph.shortestPathLengths(node)	×
UNCOV 186	return maxVal(pathLengths)	×
UNCOV 187	}	×
188
189	// nodeEccentricities calculates the eccentricities for the given nodes.
UNCOV 190	func (graph *SimpleGraph) nodeEccentricities(nodes []int) map[int]uint32 {	×
UNCOV 191	eccentricities := make(map[int]uint32, len(graph.Adj))	×
UNCOV 192	for _, node := range nodes {	×
UNCOV 193	eccentricities[node] = graph.nodeEccentricity(node)	×
UNCOV 194	}	×
UNCOV 195	return eccentricities	×
196	}
197
198	// Diameter returns the maximal eccentricity (longest shortest path
199	// between any node pair) in the graph.
200	//
201	// Note: This method is exact but expensive, use DiameterRadialCutoff instead.
UNCOV 202	func (graph *SimpleGraph) Diameter() uint32 {	×
UNCOV 203	nodes := make([]int, len(graph.Adj))	×
UNCOV 204	for a := range nodes {	×
UNCOV 205	nodes[a] = a	×
UNCOV 206	}	×
UNCOV 207	eccentricities := graph.nodeEccentricities(nodes)	×
UNCOV 208	return maxVal(eccentricities)	×
209	}
210
211	// DiameterRadialCutoff is a method to efficiently evaluate the diameter of a
212	// graph. The highest-degree node is usually central in the graph. We can
213	// determine its eccentricity (shortest-longest path length to any other node)
214	// and use it as an approximation for the radius of the network. We then
215	// use this radius to compute a cutoff. All the nodes within a distance of the
216	// cutoff are discarded, as they represent the inside of the graph. We then
217	// loop over all outer nodes and determine their eccentricities, from which we
218	// get the diameter.
UNCOV 219	func (graph *SimpleGraph) DiameterRadialCutoff() uint32 {	×
UNCOV 220	// Determine the reference node as the node with the highest degree.	×
UNCOV 221	nodeMaxDegree, _ := graph.nodeMaxDegree()	×
UNCOV 222		×
UNCOV 223	distances := graph.shortestPathLengths(nodeMaxDegree)	×
UNCOV 224	eccentricityMaxDegreeNode := maxVal(distances)	×
UNCOV 225		×
UNCOV 226	// We use the eccentricity to define a cutoff for the interior of the	×
UNCOV 227	// graph from the reference node.	×
UNCOV 228	cutoff := uint32(float32(eccentricityMaxDegreeNode) * diameterCutoff)	×
UNCOV 229	log.Debugf("Cutoff radius is %d hops (max-degree node's "+	×
UNCOV 230	"eccentricity is %d)", cutoff, eccentricityMaxDegreeNode)	×
UNCOV 231		×
UNCOV 232	// Remove the nodes that are close to the reference node.	×
UNCOV 233	var nodes []int	×
UNCOV 234	for node, distance := range distances {	×
UNCOV 235	if distance > cutoff {	×
UNCOV 236	nodes = append(nodes, node)	×
UNCOV 237	}	×
238	}
UNCOV 239	log.Debugf("Evaluated nodes: %d, discarded nodes %d",	×
UNCOV 240	len(nodes), len(graph.Adj)-len(nodes))	×
UNCOV 241		×
UNCOV 242	// Compute the diameter of the remaining nodes.	×
UNCOV 243	eccentricities := graph.nodeEccentricities(nodes)	×
UNCOV 244	return maxVal(eccentricities)	×
245	}

lightningnetwork / lnd / 17027244024

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