algorithm

package
v0.9.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Nov 25, 2025 License: MIT Imports: 6 Imported by: 0

Documentation

Overview

Package algorithm provides graph algorithms for network analysis.

Package config provides configuration settings for the graph algorithms.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func AllShortestPathLength 

func AllShortestPathLength(g *graph.Graph, cfg *Config) graph.PathLength

AllShortestPathLength returns all-pairs unweighted shortest path lengths. - For each source u, the inner map contains v -> dist(u,v) for all reachable v (including u with 0). - Unreachable targets are omitted from the inner map. - Uses a worker pool sized by cfg.Workers (or NumCPU when <=0).

func AllShortestPaths 

func AllShortestPaths(g *graph.Graph, cfg *Config) graph.Paths

AllShortestPaths computes all-pairs shortest paths while keeping the same return structure (graph.Paths). Performance improvements over the (s,t)-pair BFS approach:

  • Run exactly one BFS per source node (O(n*(m+n)) instead of O(n^2*(m+n)) in the worst case).
  • Reconstruct all shortest paths to every target using predecessors (no repeated BFS).
  • Use memoization to enumerate all s->u shortest paths once and reuse for all targets.

Notes:

  • For undirected graphs we fill symmetric entries [t][s] with the SAME slice reference as [s][t] (matching prior behavior and saving work). If you need reversed node order per entry, that can be changed, but be aware of the extra cost.
  • Self paths [u][u] are set to a single self path.

func AutoCacheClear 

func AutoCacheClear(tick time.Duration)

AutoCacheClear starts a goroutine that clears the cache at regular intervals defined by tick.

func BetweennessCentrality 

func BetweennessCentrality(g *graph.Graph, cfg *Config) map[graph.NodeID]float64

BetweennessCentrality computes betweenness centrality using cached all shortest paths. - Uses AllShortestPaths(g, cfg) (assumed cached/fast) to enumerate all shortest paths. - For each pair (s,t), each interior node on a shortest path gets 1/|SP(s,t)| credit. - Undirected graphs enqueue only i<j pairs (no double counting). - Normalization matches NetworkX: undirected => 2/((n-1)(n-2)), directed => 1/((n-1)(n-2)).

func CacheClear 

func CacheClear()

CacheClear clears the cached shortest paths and their lengths.

func ClosenessCentrality 

func ClosenessCentrality(g *graph.Graph, cfg *Config) map[graph.NodeID]float64

ClosenessCentrality computes NetworkX-compatible closeness centrality.

Semantics:

  • Directed + Reverse=false => OUT-closeness on G (matches nx.closeness_centrality(G))
  • Directed + Reverse=true => IN-closeness on G (matches nx.closeness_centrality(G.reverse()))
  • Undirected => standard closeness.

Distances are unweighted (#edges) and come from cached all-pairs shortest paths.

Requirements: - AllShortestPaths(g, cfg) must respect directedness of g. - cfg.Closeness.WfImproved follows NetworkX default (true) unless overridden.

func ClusteringCoefficient 

func ClusteringCoefficient(g *graph.Graph, cfg *Config) map[graph.NodeID]float64

ClusteringCoefficientAll computes local clustering coefficients for all nodes. - If g.IsBidirectional()==false (directed): Fagiolo (2007) directed clustering (matches NetworkX). - If g.IsBidirectional()==true (undirected): standard undirected clustering. Returns map[graph.NodeID]float64 with a value for every node in g.

func DegreeAssortativityCoefficient 

func DegreeAssortativityCoefficient(g *graph.Graph, cfg *Config) float64

DegreeAssortativityCoefficient computes Newman's degree assortativity coefficient (Pearson correlation) between degrees at the two ends of each edge/arc, with behavior controlled by cfg.Assortativity.

Assumptions / Notes: - For undirected graphs, it counts each edge once using upper-triangle filtering by node index. - For directed graphs:

  • Mode "projected": ignores direction and uses undirected degrees on both ends.
  • Mode "out-in": j = out(u), k = in(v) over arcs u->v
  • Mode "out-out": j = out(u), k = out(v)
  • Mode "in-in": j = in(u), k = in(v)
  • Mode "in-out": j = in(u), k = out(v)

- Self-loops are ignored by default (configurable). - Replace neighbor getters with your Graph's actual API if different.

func DegreeCentrality 

func DegreeCentrality(g *graph.Graph, cfg *Config) map[graph.NodeID]float64

DegreeCentrality computes degree-based centrality with NetworkX-compatible semantics. - Undirected: deg(u)/(n-1). - Directed (default "total"): (in(u)+out(u))/(n-1). Use "in"/"out" for the specific variants. Self-loops are ignored for centrality.

func Diameter 

func Diameter(g *graph.Graph, cfg *Config) int

Diameter computes the diameter of the graph using all-pairs shortest paths.

func EdgeBetweennessCentrality 

func EdgeBetweennessCentrality(g *graph.Graph, cfg *Config) map[graph.NodeID]map[graph.NodeID]float64

EdgeBetweennessCentrality computes edge betweenness centrality (unweighted) compatible with NetworkX's nx.edge_betweenness_centrality.

Algorithm:

  • Brandes (2001) single-source shortest paths with dependency accumulation, extended for edges.

Parallelization:

  • Sources (s) are split across a worker pool (cfg.Workers).

Normalization (normalized=true):

  • Directed: multiply by 1 / ((n-1)*(n-2))
  • Undirected: multiply by 2 / ((n-1)*(n-2))

Additionally, undirected results are divided by 2 to correct for double counting in Brandes accumulation (same practice as NetworkX).

Returns:

  • map[graph.NodeID]map[graph.NodeID]float64 where:
  • Undirected: key is canonical [min(u,v), max(u,v)]
  • Directed: key is (u,v) ordered

func EigenvectorCentrality 

func EigenvectorCentrality(g *graph.Graph, cfg *Config) map[graph.NodeID]float64

EigenvectorCentrality computes eigenvector centrality using parallel power iteration. Semantics match NetworkX by default:

  • Undirected graphs: neighbors are used (symmetric).
  • Directed graphs: by default (Reverse=false) we use predecessors/in-edges (left eigenvector). Set Reverse=true to use successors/out-edges (right eigenvector).

Unweighted edges are assumed. The result vector is L2-normalized (sum of squares == 1).

func GreedyModularityCommunitiesNX 

func GreedyModularityCommunitiesNX(g *graph.Graph) map[graph.NodeID]int

GreedyModularityCommunitiesNX implements the Clauset–Newman–Moore greedy modularity maximization, aligned with NetworkX conventions: - work on an undirected projection - m = number_of_undirected_edges - inv2m = 1/(2m); each undirected edge contributes inv2m twice (symmetrically) Returns a partition map: nodeID -> compact community label.

func Modularity 

func Modularity(g *graph.Graph, cfg *Config) float64

Modularity computes Newman-Girvan modularity Q. If cfg.Modularity.Partition == nil, it runs greedy CNM to obtain a partition first. All computations are performed on an undirected projection (to match NetworkX).

func PageRank 

func PageRank(g *graph.Graph, cfg *Config) map[graph.NodeID]float64

PageRank computes PageRank using a parallel power-iteration that mirrors NetworkX semantics:

  • Teleport and dangling redistribution match NetworkX (personalization used for both by default).
  • Convergence check uses L1 error before any per-iteration normalization: sum(|x - x_last|) < n*tol.
  • Result is L1-normalized once after convergence (or after max-iter).
  • For directed graphs, Reverse=false is the standard PageRank (incoming influence). Reverse=true flips direction (treat in-neighbors as outs).
  • For undirected graphs, neighbors are used as outs (degree-based normalization).

func ShortestPaths 

func ShortestPaths(g *graph.Graph, start, end graph.NodeID) []graph.Path

ShortestPaths finds all shortest paths between two nodes in a graph.

Types

type AssortativityCoefficientConfig 

type AssortativityCoefficientConfig struct {
	// Mode selects which degree pairing to use.
	// Defaults:
	//   - If graph is undirected: "projected"
	//   - If graph is directed:   "out-in"
	Mode AssortativityMode

	// IgnoreSelfLoops controls whether to ignore self loops (u==v).
	// Default: true
	IgnoreSelfLoops bool
}

AssortativityCoefficientConfig holds the configuration settings for the assortativity coefficient algorithm.

type AssortativityMode 

type AssortativityMode string

AssortativityMode defines how degree pairs (j,k) are taken on each edge/arc. - Projected: ignore direction; use undirected degrees on both ends. - OutIn: use out-degree(u) and in-degree(v) for each arc u->v - OutOut: out-degree(u) and out-degree(v) - InIn: in-degree(u) and in-degree(v) - InOut: in-degree(u) and out-degree(v) 

const (
	AssortativityProjected AssortativityMode = "projected"
	AssortativityOutIn     AssortativityMode = "out-in"
	AssortativityOutOut    AssortativityMode = "out-out"
	AssortativityInIn      AssortativityMode = "in-in"
	AssortativityInOut     AssortativityMode = "in-out"
)

type BetweennessCentralityConfig 

type BetweennessCentralityConfig struct {
	Normalized bool
}

BetweennessCentralityConfig holds the configuration settings for the edge betweenness centrality algorithm.

type ClosenessCentralityConfig 

type ClosenessCentralityConfig struct {
	Reverse    bool
	WfImproved bool
}

ClosenessCentralityConfig holds the configuration settings for the closeness centrality algorithm.

type Config 

type Config struct {
	Workers         int
	Betweenness     *BetweennessCentralityConfig
	Closeness       *ClosenessCentralityConfig
	Degree          *DegreeCentralityConfig
	EdgeBetweenness *EdgeBetweennessCentralityConfig
	Eigenvector     *EigenvectorCentralityConfig
	PageRank        *PageRankConfig
	Assortativity   *AssortativityCoefficientConfig
	Modularity      *ModularityConfig
}

Config holds the configuration settings for the graph algorithms.

func Default 

func Default() *Config

Default returns the default configuration for the graph algorithms.

type DegreeCentralityConfig 

type DegreeCentralityConfig struct {
	Mode DegreeCentralityMode
}

DegreeCentralityConfig holds the configuration settings for the degree centrality algorithm.

type DegreeCentralityMode added in v0.8.2 

type DegreeCentralityMode string
const (
	DegreeCentralityTotal DegreeCentralityMode = "total"
	DegreeCentralityIn    DegreeCentralityMode = "in"
	DegreeCentralityOut   DegreeCentralityMode = "out"
)

type EdgeBetweennessCentralityConfig 

type EdgeBetweennessCentralityConfig struct {
	Normalized bool
}

EdgeBetweennessCentralityConfig holds the configuration settings for the edge betweenness centrality algorithm.

type EigenvectorCentralityConfig 

type EigenvectorCentralityConfig struct {
	MaxIter int
	Tol     float64
	Reverse bool
	NStart  *map[graph.NodeID]float64 // initial vector; if nil, uniform distribution
}

EigenvectorCentralityConfig holds the configuration settings for the eigenvector centrality algorithm.

type ModularityConfig 

type ModularityConfig struct {
	// Partition maps each node to its community ID.
	// If nil, algorithm will compute greedy modularity communities automatically.
	Partition map[graph.NodeID]int
}

ModularityConfig holds the configuration settings for the modularity calculation.

type PageRankConfig 

type PageRankConfig struct {
	Alpha           float64                   // damping, default 0.85
	MaxIter         int                       // default 100
	Tol             float64                   // L1 error, default 1e-6
	Personalization *map[graph.NodeID]float64 // p(u); if nil is uniform
	Dangling        *map[graph.NodeID]float64 // d(u); if nil p(u)
	Reverse         bool
}

PageRankConfig holds the configuration settings for the PageRank algorithm.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.