Repository: lightningnetwork/lnd (language: go)

Issue:
Add graph diameter calculation to GetNetworkInfo
The response of the `GetNetworkInfo` RPC contains the following fields:
```proto
message NetworkInfo {
    uint32 graph_diameter = 1;
    double avg_out_degree = 2;
    uint32 max_out_degree = 3;
    uint32 num_nodes = 4;
    uint32 num_channels = 5;
    int64 total_network_capacity = 6;
    double avg_channel_size = 7;
    int64 min_channel_size = 8;
    int64 max_channel_size = 9;
}
```

Currently, all fields _except_ the `graph_diameter` field are populated. The [graph diameter](http://mathworld.wolfram.com/GraphDiameter.html) is to represent the diameter, or the worst-case path length from one node to another within the channel graph. 



Discussion / hints:
I'll take a look at this issue.
Hi phlip9, Im actually already working on this issue and have a PR open for it.

I need to fix a bug though, so maybe if you'd liketo takea look at the PR that would be cool
Ahh I didn't see that. I'll check out your PR.
If this task hasn't completed and nobody is working on it, I'd like try to finish it.
Hey man, feel free to work on it :)
Hey aferdigo, I actually just noticed that my PR is almost done. My bad... Been kinda swamped lately. I will upload the PR later today
Ok, I will take another one :)
I’ll take this up :)
@nalinbhardwaj: are you still working on this? if not, I can finish it. 
@mlerner I have the work done already but I think I may have misunderstood the task(which is why I was holding off a PR), is the graph diameter to be found using the same `EdgeWeight()` as `routing/pathfinding.go` or should edge weights be taken as 1?
PR #417 contains quite a lot of code and discussions, and the main issue seems to be performance (the graph is quite large). If you want to work on this, please have a look at the (closed) PR first.

Fix patch:
diff --git a/autopilot/graph.go b/autopilot/graph.go
index e630f8d35d..ced7ed2e94 100644
--- a/autopilot/graph.go
+++ b/autopilot/graph.go
@@ -455,6 +455,96 @@ func (m *memChannelGraph) addRandNode() (*btcec.PublicKey, error) {
 	return newPub, nil
 }
 
+// databaseChannelGraphCached wraps a channeldb.ChannelGraph instance with the
+// necessary API to properly implement the autopilot.ChannelGraph interface.
+type databaseChannelGraphCached struct {
+	db *channeldb.ChannelGraph
+}
+
+// A compile time assertion to ensure databaseChannelGraphCached meets the
+// autopilot.ChannelGraph interface.
+var _ ChannelGraph = (*databaseChannelGraphCached)(nil)
+
+// ChannelGraphFromCachedDatabase returns an instance of the
+// autopilot.ChannelGraph backed by a live, open channeldb instance.
+func ChannelGraphFromCachedDatabase(db *channeldb.ChannelGraph) ChannelGraph {
+	return &databaseChannelGraphCached{
+		db: db,
+	}
+}
+
+// dbNodeCached is a wrapper struct around a database transaction for a
+// channeldb.LightningNode. The wrapper methods implement the autopilot.Node
+// interface.
+type dbNodeCached struct {
+	node     route.Vertex
+	channels map[uint64]*channeldb.DirectedChannel
+}
+
+// A compile time assertion to ensure dbNodeCached meets the autopilot.Node
+// interface.
+var _ Node = (*dbNodeCached)(nil)
+
+// PubKey is the identity public key of the node.
+//
+// NOTE: Part of the autopilot.Node interface.
+func (nc dbNodeCached) PubKey() [33]byte {
+	return nc.node
+}
+
+// Addrs returns a slice of publicly reachable public TCP addresses that the
+// peer is known to be listening on.
+//
+// NOTE: Part of the autopilot.Node interface.
+func (nc dbNodeCached) Addrs() []net.Addr {
+	// TODO: Add addresses to be usable by autopilot.
+	return []net.Addr{}
+}
+
+// ForEachChannel is a higher-order function that will be used to iterate
+// through all edges emanating from/to the target node. For each active
+// channel, this function should be called with the populated ChannelEdge that
+// describes the active channel.
+//
+// NOTE: Part of the autopilot.Node interface.
+func (nc dbNodeCached) ForEachChannel(cb func(ChannelEdge) error) error {
+	for cid, channel := range nc.channels {
+		edge := ChannelEdge{
+			ChanID:   lnwire.NewShortChanIDFromInt(cid),
+			Capacity: channel.Capacity,
+			Peer: dbNodeCached{
+				node: channel.OtherNode,
+			},
+		}
+
+		if err := cb(edge); err != nil {
+			return err
+		}
+	}
+
+	return nil
+}
+
+// ForEachNode is a higher-order function that should be called once for each
+// connected node within the channel graph. If the passed callback returns an
+// error, then execution should be terminated.
+//
+// NOTE: Part of the autopilot.ChannelGraph interface.
+func (dc *databaseChannelGraphCached) ForEachNode(cb func(Node) error) error {
+	return dc.db.ForEachNodeCached(func(n route.Vertex,
+		channels map[uint64]*channeldb.DirectedChannel) error {
+
+		if len(channels) > 0 {
+			node := dbNodeCached{
+				node:     n,
+				channels: channels,
+			}
+			return cb(node)
+		}
+		return nil
+	})
+}
+
 // memNode is a purely in-memory implementation of the autopilot.Node
 // interface.
 type memNode struct {
diff --git a/autopilot/simple_graph.go b/autopilot/simple_graph.go
index 208a784e9f..f7bf4c12c9 100644
--- a/autopilot/simple_graph.go
+++ b/autopilot/simple_graph.go
@@ -1,5 +1,12 @@
 package autopilot
 
+// 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 simplifed adj graph of a channel graph to speed
 // up graph processing by eliminating all unnecessary hashing and map access.
 type SimpleGraph struct {
@@ -62,5 +69,162 @@ func NewSimpleGraph(g ChannelGraph) (*SimpleGraph, error) {
 		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 {
+		if maxValue < value {
+			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)
+
+	// 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)
+}
diff --git a/docs/release-notes/release-notes-0.15.0.md b/docs/release-notes/release-notes-0.15.0.md
index 301f41e026..a95f208ba1 100644
--- a/docs/release-notes/release-notes-0.15.0.md
+++ b/docs/release-notes/release-notes-0.15.0.md
@@ -75,6 +75,8 @@
   `remote_balance`](https://github.com/lightningnetwork/lnd/pull/5931) in
   `pending_force_closing_channels` under `pendingchannels` whereas before was
   empty(zero).
+* The graph's [diameter is calculated](https://github.com/lightningnetwork/lnd/pull/6066)
+  and added to the `getnetworkinfo` output.
 
 * [Add dev only RPC subserver and the devrpc.ImportGraph
   call](https://github.com/lightningnetwork/lnd/pull/6149)
@@ -131,6 +133,7 @@ gRPC performance metrics (latency to process `GetInfo`, etc)](https://github.com
 * 3nprob
 * Andreas Schjønhaug
 * asvdf
+* bitromortac
 * BTCparadigm
 * Carla Kirk-Cohen
 * Carsten Otto
@@ -151,4 +154,4 @@ gRPC performance metrics (latency to process `GetInfo`, etc)](https://github.com
 * Thebora Kompanioni
 * Torkel Rogstad
 * Vsevolod Kaganovych
-* Yong Yu
+* Yong Yu
\ No newline at end of file
diff --git a/rpcserver.go b/rpcserver.go
index 453e7c1937..15f2fc04e7 100644
--- a/rpcserver.go
+++ b/rpcserver.go
@@ -5904,10 +5904,20 @@ func (r *rpcServer) GetNetworkInfo(ctx context.Context,
 		minChannelSize = 0
 	}
 
-	// TODO(roasbeef): graph diameter
+	// Graph diameter.
+	channelGraph := autopilot.ChannelGraphFromCachedDatabase(graph)
+	simpleGraph, err := autopilot.NewSimpleGraph(channelGraph)
+	if err != nil {
+		return nil, err
+	}
+	start := time.Now()
+	diameter := simpleGraph.DiameterRadialCutoff()
+	rpcsLog.Infof("elapsed time for diameter (%d) calculation: %v", diameter,
+		time.Since(start))
 
 	// TODO(roasbeef): also add oldest channel?
 	netInfo := &lnrpc.NetworkInfo{
+		GraphDiameter:        diameter,
 		MaxOutDegree:         maxChanOut,
 		AvgOutDegree:         float64(2*numChannels) / float64(numNodes),
 		NumNodes:             numNodes,


Test patch:
diff --git a/autopilot/simple_graph_test.go b/autopilot/simple_graph_test.go
new file mode 100644
index 0000000000..03fb2ed902
--- /dev/null
+++ b/autopilot/simple_graph_test.go
@@ -0,0 +1,94 @@
+package autopilot
+
+import (
+	"testing"
+
+	"github.com/stretchr/testify/require"
+)
+
+var (
+	testShortestPathLengths = map[int]uint32{
+		0: 0,
+		1: 1,
+		2: 1,
+		3: 1,
+		4: 2,
+		5: 2,
+		6: 3,
+		7: 3,
+		8: 4,
+	}
+	testNodeEccentricities = map[int]uint32{
+		0: 4,
+		1: 5,
+		2: 4,
+		3: 3,
+		4: 3,
+		5: 3,
+		6: 4,
+		7: 4,
+		8: 5,
+	}
+)
+
+// NewTestSimpleGraph is a helper that generates a SimpleGraph from a test
+// graph description.
+// Assumes that the graph description is internally consistent, i.e. edges are
+// not repeatedly defined.
+func NewTestSimpleGraph(graph testGraphDesc) SimpleGraph {
+	// We convert the test graph description into an adjacency list.
+	adjList := make([][]int, graph.nodes)
+	for node, neighbors := range graph.edges {
+		for _, neighbor := range neighbors {
+			adjList[node] = append(adjList[node], neighbor)
+			adjList[neighbor] = append(adjList[neighbor], node)
+		}
+	}
+
+	return SimpleGraph{Adj: adjList}
+}
+
+func TestShortestPathLengths(t *testing.T) {
+	simpleGraph := NewTestSimpleGraph(centralityTestGraph)
+
+	// Test the shortest path lengths from node 0 to all other nodes.
+	shortestPathLengths := simpleGraph.shortestPathLengths(0)
+	require.Equal(t, shortestPathLengths, testShortestPathLengths)
+}
+
+func TestEccentricities(t *testing.T) {
+	simpleGraph := NewTestSimpleGraph(centralityTestGraph)
+
+	// Test the node eccentricities for all nodes.
+	nodes := make([]int, len(simpleGraph.Adj))
+	for a := range nodes {
+		nodes[a] = a
+	}
+	nodeEccentricities := simpleGraph.nodeEccentricities(nodes)
+	require.Equal(t, nodeEccentricities, testNodeEccentricities)
+}
+
+func TestDiameterExact(t *testing.T) {
+	simpleGraph := NewTestSimpleGraph(centralityTestGraph)
+
+	// Test the diameter in a brute-force manner.
+	diameter := simpleGraph.Diameter()
+	require.Equal(t, uint32(5), diameter)
+}
+
+func TestDiameterCutoff(t *testing.T) {
+	simpleGraph := NewTestSimpleGraph(centralityTestGraph)
+
+	// Test the diameter by cutting out the inside of the graph.
+	diameter := simpleGraph.DiameterRadialCutoff()
+	require.Equal(t, uint32(5), diameter)
+}
+
+func BenchmarkShortestPathOpt(b *testing.B) {
+	// TODO: a method that generates a huge graph is needed
+	simpleGraph := NewTestSimpleGraph(centralityTestGraph)
+
+	for n := 0; n < b.N; n++ {
+		_ = simpleGraph.shortestPathLengths(0)
+	}
+}