Repository: gonum/gonum
Pull request #2038 (2025-03-25 10:23:24)

graph/network: add eccentricity measurement
Please take a look.

Closes: #2037

<!--
Checklist:

- API changes have been discussed
- code is goformated correctly (goimports)
- packages with generated code have had code generation run
- tests pass locally
- linked to relevant issues

Please make sure your commit message summary line and pull request
title match the Go convention; a one-line summary of the change,
prefixed by the primary affected package that should complete the
sentence, "This change modifies Gonum to _____."

Do not delete any of this templated text in the PR description, but
feel free to add additional context.
-->


kortschak: > It seems that this test is indeed flaky, I can reproduce this failure quite reliably by running it a lot of times

Thanks. I can see why that is and I'll send a fix. In the meantime this looks good. Please also send another PR with the commit message "A+C: add Nicolas Peugnet" adding yourself to AUTHORS and CONTRIBUTORS.

Patch:
diff --git a/graph/network/distance.go b/graph/network/distance.go
index 25a0c0c2..a71ccdd8 100644
--- a/graph/network/distance.go
+++ b/graph/network/distance.go
@@ -40,6 +40,35 @@ func Closeness(g graph.Graph, p path.AllShortest) map[int64]float64 {
 	return c
 }
 
+// Eccentricity returns the eccentricity for nodes in the graph g used to
+// construct the given shortest paths.
+//
+//	E(v) = \max_u d(u,v)
+//
+// For directed graphs the incoming paths are used. Infinite distances are
+// not considered.
+func Eccentricity(g graph.Graph, p path.AllShortest) map[int64]float64 {
+	nodes := graph.NodesOf(g.Nodes())
+	e := make(map[int64]float64, len(nodes))
+	for _, u := range nodes {
+		uid := u.ID()
+		var dmax float64
+		for _, v := range nodes {
+			vid := v.ID()
+			// The ordering here is not relevant for
+			// undirected graphs, but we make sure we
+			// are counting incoming paths.
+			d := p.Weight(vid, uid)
+			if math.IsInf(d, 0) {
+				continue
+			}
+			dmax = max(d, dmax)
+		}
+		e[u.ID()] = dmax
+	}
+	return e
+}
+
 // Farness returns the farness for nodes in the graph g used to construct
 // the given shortest paths.
 //


Test patch:
diff --git a/graph/network/distance_test.go b/graph/network/distance_test.go
index 38e77b23..1e1a27b0 100644
--- a/graph/network/distance_test.go
+++ b/graph/network/distance_test.go
@@ -16,9 +16,10 @@ import (
 var undirectedCentralityTests = []struct {
 	g []set
 
-	farness  map[int64]float64
-	harmonic map[int64]float64
-	residual map[int64]float64
+	eccentricity map[int64]float64
+	farness      map[int64]float64
+	harmonic     map[int64]float64
+	residual     map[int64]float64
 }{
 	{
 		g: []set{
@@ -27,6 +28,11 @@ var undirectedCentralityTests = []struct {
 			C: nil,
 		},
 
+		eccentricity: map[int64]float64{
+			A: 2,
+			B: 1,
+			C: 2,
+		},
 		farness: map[int64]float64{
 			A: 1 + 2,
 			B: 1 + 1,
@@ -52,6 +58,13 @@ var undirectedCentralityTests = []struct {
 			E: nil,
 		},
 
+		eccentricity: map[int64]float64{
+			A: 4,
+			B: 3,
+			C: 2,
+			D: 3,
+			E: 4,
+		},
 		farness: map[int64]float64{
 			A: 1 + 2 + 3 + 4,
 			B: 1 + 1 + 2 + 3,
@@ -83,6 +96,13 @@ var undirectedCentralityTests = []struct {
 			E: linksTo(C),
 		},
 
+		eccentricity: map[int64]float64{
+			A: 2,
+			B: 2,
+			C: 1,
+			D: 2,
+			E: 2,
+		},
 		farness: map[int64]float64{
 			A: 2 + 2 + 1 + 2,
 			B: 2 + 1 + 2 + 2,
@@ -114,6 +134,13 @@ var undirectedCentralityTests = []struct {
 			E: nil,
 		},
 
+		eccentricity: map[int64]float64{
+			A: 1,
+			B: 1,
+			C: 1,
+			D: 1,
+			E: 1,
+		},
 		farness: map[int64]float64{
 			A: 1 + 1 + 1 + 1,
 			B: 1 + 1 + 1 + 1,
@@ -174,6 +201,14 @@ func TestDistanceCentralityUndirected(t *testing.T) {
 			}
 		}
 
+		got = Eccentricity(g, p)
+		for n := range test.g {
+			if !scalar.EqualWithinAbsOrRel(got[int64(n)], test.eccentricity[int64(n)], tol, tol) {
+				t.Errorf("unexpected eccentricity for test %d:\ngot: %v\nwant:%v",
+					i, orderedFloats(got, prec), orderedFloats(test.eccentricity, prec))
+				break
+			}
+		}
 		got = Farness(g, p)
 		for n := range test.g {
 			if !scalar.EqualWithinAbsOrRel(got[int64(n)], test.farness[int64(n)], tol, tol) {
diff --git a/lapack/testlapack/dlaln2.go b/lapack/testlapack/dlaln2.go
index 4caddd5e..93300d02 100644
--- a/lapack/testlapack/dlaln2.go
+++ b/lapack/testlapack/dlaln2.go
@@ -41,9 +41,9 @@ func testDlaln2(t *testing.T, impl Dlaln2er, trans bool, na, nw, extra int, rnd
 
 	var w complex128
 	if nw == 1 {
-		w = complex(rand.NormFloat64(), 0)
+		w = complex(rnd.NormFloat64(), 0)
 	} else {
-		w = complex(rand.NormFloat64(), rand.NormFloat64())
+		w = complex(rnd.NormFloat64(), rnd.NormFloat64())
 	}
 	smin := dlamchP * (math.Abs(real(w)) + math.Abs(imag(w)))