16777740336

Committed 06 Aug 2025 01:04PM UTC coverage: 54.85% (-12.1%) from 66.954%

Build # 16777740336

Build Type

Pull #10135

github

Committed by

web-flow

Commit Message

Merge 429aa830c into e512770f1

Pull Request Pull Request #10135: docs: move v0.19.3 items to correct file

Run Details

108702 of 198181 relevant lines covered (54.85%)

22045.97 hits per line

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

96.84

/autopilot/simple_graph.go

package autopilot

import "context"

// 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 Node) int {
                key := NodeID(node.PubKey())
                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.ForEachNode(ctx, func(ctx context.Context, node Node) error {
                u := getNodeIndex(node)

                return node.ForEachChannel(
                        ctx, func(_ context.Context,
                                edge ChannelEdge) error {

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

lightningnetwork / lnd / 16777740336

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