christiangeorgelucas/graph-tools

package nodes

import (
	"context"
	"math"
	"sort"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/network"
	"gonum.org/v1/gonum/graph/path"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Scores every vertex by structural importance under the requested measure:
//
//	"degree"       — the number of incident edges (in plus out for a directed
//	                 graph); a self-loop counts 2, per the usual convention.
//	"betweenness"  — how many shortest paths run through the vertex, counted
//	                 over unordered pairs. Computed on the UNWEIGHTED topology
//	                 (hop counts); edge weights are ignored for this measure.
//	"closeness"    — the reciprocal of the summed distance FROM every vertex
//	                 that can reach it (the standard incoming convention).
//	                 Rejects graphs with zero-weight edges, which would put a
//	                 distinct vertex at distance 0 and make the value infinite.
//	"eccentricity" — the distance to the farthest vertex this vertex can REACH
//	                 (the outgoing convention).
//	"harmonic"     — the sum of reciprocal distances FROM every vertex that can
//	                 reach it (the standard incoming convention). Rejects
//	                 zero-weight edges, for the same reason as closeness.
//
// Defaults to "degree". Every measure except "degree" needs an all-pairs
// shortest-path computation and therefore rejects negative edge weights and
// graphs beyond the documented all-pairs size bounds. Scores are always finite:
// a vertex with no reachable peers scores 0 rather than infinity.
func Centrality(ctx context.Context, ax axiom.Context, input *gen.CentralityRequest) (*gen.CentralityResult, error) {
	if input == nil {
		return &gen.CentralityResult{Error: "request is required"}, nil
	}
	b, err := buildGraph(input.Graph)
	if err != nil {
		return &gen.CentralityResult{Error: err.Error()}, nil
	}

	measure := input.Measure
	if measure == "" {
		measure = "degree"
	}

	scores := map[int64]float64{}
	switch measure {
	case "degree":
		for _, id := range b.ids {
			vid := b.idOf[id]
			n := 0
			it := b.directedView().From(vid)
			for it.Next() {
				n++
			}
			if b.directed {
				in := b.directedView().To(vid)
				for in.Next() {
					n++
				}
			}
			// Self-loops live outside the gonum structures, so add them back
			// here. A self-loop contributes 2 either way: twice to an
			// undirected vertex's degree, and once each to its in- and
			// out-degree when directed.
			scores[vid] = float64(n + 2*b.selfLoopOf[id])
		}

	case "betweenness", "closeness", "harmonic", "eccentricity":
		if err := b.requireQuadraticBudget(measure + " centrality"); err != nil {
			return &gen.CentralityResult{Error: err.Error()}, nil
		}
		if b.hasNeg {
			return &gen.CentralityResult{Error: measure + " centrality requires non-negative edge weights"}, nil
		}
		// closeness and harmonic divide BY the distance, so a zero-weight edge
		// puts a distinct vertex at distance 0 and the true value is infinite.
		// Reporting that as 0 (the clamp used for a vertex with no reachable
		// peers) would INVERT the ranking — the most central vertex would score
		// like an isolated one — so reject rather than guess. The other
		// measures never divide by a distance and are unaffected.
		if b.hasZero && (measure == "closeness" || measure == "harmonic") {
			return &gen.CentralityResult{Error: measure +
				" centrality is undefined when an edge has zero weight, because a distinct vertex then sits at distance 0; remove the zero-weight edges or use a different measure"}, nil
		}
		if err := ctx.Err(); err != nil {
			return &gen.CentralityResult{Error: "cancelled before computing " + measure + ": " + err.Error()}, nil
		}
		g := b.weightedGraph()

		computed, budgetErr := runBounded(ctx, measure+" centrality", func() map[int64]float64 {
			return computeAllPairs(measure, g, b)
		})
		if budgetErr != nil {
			return &gen.CentralityResult{Error: budgetErr.Error()}, nil
		}
		scores = computed

	default:
		return &gen.CentralityResult{Error: "unknown measure " + quote(input.Measure) +
			"; expected one of: degree, betweenness, closeness, harmonic, eccentricity"}, nil
	}

	out := &gen.CentralityResult{Measure: measure}
	for _, id := range b.ids {
		// gonum omits zero-valued entries from some of its maps, so a missing
		// key is a genuine zero. It also yields +Inf for a vertex with no
		// reachable peers (the closeness of an isolated vertex is 1/0). An
		// infinity is not representable as a JSON number — it serialises as the
		// STRING "Infinity" out of a double field — and would poison any
		// downstream arithmetic, so it is reported as 0, the standard
		// convention for a vertex with nothing to be close to.
		s := scores[b.idOf[id]]
		if math.IsInf(s, 0) || math.IsNaN(s) {
			s = 0
		}
		out.Scores = append(out.Scores, &gen.CentralityScore{Node: id, Score: s})
	}
	sort.Slice(out.Scores, func(i, j int) bool { return out.Scores[i].Node < out.Scores[j].Node })
	return out, nil
}

// computeAllPairs runs the requested all-pairs measure. It is split out so the
// whole computation can be driven under a single wall-clock budget.
func computeAllPairs(measure string, g graph.Graph, b *built) map[int64]float64 {
	switch measure {
	case "betweenness":
		// Always the unweighted Brandes algorithm, never the weighted form.
		// gonum's BetweennessWeighted enumerates EVERY shortest path via
		// AllShortest, which is exponential when shortest paths tie — a
		// 600-vertex graph with uniform weights does not finish in 45s and
		// allocates gigabytes, and no size cap can bound that safely. Brandes
		// is O(V*E) with no path enumeration: the same graph takes 351ms. The
		// cost is that betweenness reflects hop-count topology rather than edge
		// weights, which the docs state explicitly.
		raw := network.Betweenness(g)
		out := make(map[int64]float64, len(raw))
		for k, v := range raw {
			// gonum accumulates over ORDERED pairs, so an undirected graph
			// comes out at twice the conventional (Brandes / networkx /
			// textbook) unnormalised value. Halve it so a caller
			// cross-checking against a standard tool gets the same number.
			if !b.directed {
				v /= 2
			}
			out[k] = v
		}
		return out
	case "closeness":
		return network.Closeness(g, path.DijkstraAllPaths(g))
	case "harmonic":
		return network.Harmonic(g, path.DijkstraAllPaths(g))
	case "eccentricity":
		// gonum's Eccentricity uses INCOMING paths, i.e. max over u of d(u,v).
		// The documented and conventional meaning is the outgoing one — how far
		// this vertex can reach — so it is computed on the TRANSPOSED graph,
		// which turns every incoming path into an outgoing one. For an
		// undirected graph the transpose is the graph itself, a no-op.
		tg := b.transposedWeightedGraph()
		return network.Eccentricity(tg, path.DijkstraAllPaths(tg))
	}
	return nil
}

package nodes

import (
	"context"
	"sort"

	"gonum.org/v1/gonum/graph/topo"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Partitions a graph into groups of mutually-reachable vertices. For an
// undirected graph these are the connected components; for a directed graph
// they are the strongly connected components (Tarjan's algorithm), and
// strongly_connected is set to true. Components and their members are sorted
// by vertex id.
func ConnectedComponents(ctx context.Context, ax axiom.Context, input *gen.Graph) (*gen.ComponentsResult, error) {
	b, err := buildGraph(input)
	if err != nil {
		return &gen.ComponentsResult{Error: err.Error()}, nil
	}
	if err := ctx.Err(); err != nil {
		return &gen.ComponentsResult{Error: "cancelled: " + err.Error()}, nil
	}

	var groups [][]string
	if b.directed {
		for _, comp := range topo.TarjanSCC(b.directedView()) {
			groups = append(groups, b.sortedNames(comp))
		}
		sort.Slice(groups, func(i, j int) bool { return groups[i][0] < groups[j][0] })
	} else {
		groups = b.weakComponents()
	}

	out := &gen.ComponentsResult{
		Count:             int32(len(groups)),
		StronglyConnected: b.directed,
	}
	for _, g := range groups {
		out.Components = append(out.Components, &gen.Component{Nodes: g})
	}
	return out, nil
}

package nodes

import (
	"context"

	"gonum.org/v1/gonum/graph/topo"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Summarises the structure of a graph: vertex and edge counts, edge density,
// mean degree, self-loop count, total edge weight, connectivity, component
// count, and whether a directed graph is acyclic. Connectivity and
// component_count use weak connectivity (edge direction ignored) for directed
// input. Piping a MinimumSpanningTree result in here is how you weigh the tree.
func Describe(ctx context.Context, ax axiom.Context, input *gen.Graph) (*gen.GraphStats, error) {
	b, err := buildGraph(input)
	if err != nil {
		return &gen.GraphStats{Error: err.Error()}, nil
	}
	if err := ctx.Err(); err != nil {
		return &gen.GraphStats{Error: "cancelled: " + err.Error()}, nil
	}

	n := len(b.ids)
	m := b.edgeCount
	out := &gen.GraphStats{
		NodeCount:     int32(n),
		EdgeCount:     int32(m),
		Directed:      b.directed,
		SelfLoopCount: int32(b.selfLoops),
		TotalWeight:   b.totalWeight,
	}

	comps := b.weakComponents()
	out.ComponentCount = int32(len(comps))
	out.IsConnected = n > 0 && len(comps) == 1

	// Mean TOTAL degree, counting in+out for a directed graph. Summing every
	// vertex's degree gives 2*|E| either way, so this is 2|E|/|V| in both
	// cases — and it is exactly the mean of what Centrality's "degree" measure
	// reports per vertex, so the two nodes cannot disagree about a graph.
	if n > 0 {
		out.AverageDegree = 2 * float64(m) / float64(n)
	}

	// Density counts only the simple (non-self-loop) edges a simple graph can
	// hold: n*(n-1) ordered pairs when directed, half that when undirected.
	if n > 1 {
		maxEdges := float64(n) * float64(n-1)
		if !b.directed {
			maxEdges /= 2
		}
		out.Density = float64(m-b.selfLoops) / maxEdges
	}

	if b.directed && b.selfLoops == 0 {
		if _, err := topo.Sort(b.directedView()); err == nil {
			out.IsDag = true
		}
	}

	return out, nil
}

package nodes

import (
	"context"
	"math"

	"gonum.org/v1/gonum/graph/path"
	"gonum.org/v1/gonum/graph/simple"
	"gonum.org/v1/gonum/graph/topo"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Reports whether a graph contains a cycle and returns one concrete example.
// For a directed graph a cycle is a strongly connected component with more than
// one vertex (or a self-loop), and cycle_count is the number of such components
// PLUS the number of self-loops. For an undirected graph cycle_count is the circuit rank
// |E| - |V| + (number of components), the number of independent cycles. The
// returned example cycle repeats its first vertex id at the end to close it.
func DetectCycle(ctx context.Context, ax axiom.Context, input *gen.Graph) (*gen.CycleResult, error) {
	b, err := buildGraph(input)
	if err != nil {
		return &gen.CycleResult{Error: err.Error()}, nil
	}
	if err := ctx.Err(); err != nil {
		return &gen.CycleResult{Error: "cancelled: " + err.Error()}, nil
	}

	out := &gen.CycleResult{}

	// A self-loop is the shortest possible cycle and is always reported first.
	selfLoopNode := b.firstSelfLoop(input)

	if b.directed {
		cyclic := 0
		var best []string
		for _, comp := range topo.TarjanSCC(b.dg) {
			if len(comp) > 1 {
				cyclic++
				names := b.sortedNames(comp)
				if best == nil || names[0] < best[0] {
					best = names
				}
			}
		}
		out.CycleCount = int32(cyclic + b.selfLoops)
		out.HasCycle = out.CycleCount > 0
		if selfLoopNode != "" {
			out.Cycle = []string{selfLoopNode, selfLoopNode}
		} else if best != nil {
			out.Cycle = b.directedCycleWitness(best)
		}
		return out, nil
	}

	// Undirected: circuit rank = |E| - |V| + components.
	nonLoopEdges := b.edgeCount - b.selfLoops
	comps := len(b.weakComponents())
	rank := nonLoopEdges - len(b.ids) + comps
	if rank < 0 {
		rank = 0
	}
	out.CycleCount = int32(rank + b.selfLoops)
	out.HasCycle = out.CycleCount > 0
	if selfLoopNode != "" {
		out.Cycle = []string{selfLoopNode, selfLoopNode}
	} else if rank > 0 {
		out.Cycle = b.undirectedCycleWitness()
	}
	return out, nil
}

// firstSelfLoop returns the lexicographically smallest vertex carrying a
// self-loop, or "" when there is none.
func (b *built) firstSelfLoop(g *gen.Graph) string {
	best := ""
	for _, e := range g.GetEdges() {
		if e.From == e.To && (best == "" || e.From < best) {
			best = e.From
		}
	}
	return best
}

// directedCycleWitness returns one elementary directed cycle inside a strongly
// connected component. It anchors on the component's smallest vertex u, uses a
// shortest (hop-count) path search from u, and closes the cycle through the
// in-neighbour of u that is nearest to u. Because the search is unweighted the
// path is simple, so appending u yields an elementary cycle.
func (b *built) directedCycleWitness(comp []string) []string {
	in := make(map[string]bool, len(comp))
	for _, id := range comp {
		in[id] = true
	}
	sub := simple.NewDirectedGraph()
	for _, id := range comp {
		sub.AddNode(simple.Node(b.idOf[id]))
	}
	for _, id := range comp {
		it := b.directedView().From(b.idOf[id])
		for it.Next() {
			if in[b.nameOf[it.Node().ID()]] {
				sub.SetEdge(simple.Edge{F: simple.Node(b.idOf[id]), T: simple.Node(it.Node().ID())})
			}
		}
	}

	u := b.idOf[comp[0]]
	sp := path.DijkstraFrom(simple.Node(u), orderedD{sub})

	// Choose the closing in-neighbour by WEIGHT first, then materialise exactly
	// ONE path. Calling sp.To() for every in-neighbour would allocate a full
	// path per candidate, making the witness search O(indegree * diameter): a
	// 20000-vertex "broom" (a long chain with a back-edge from every vertex)
	// churned 13 GB of allocation to emit a three-element cycle. WeightTo is
	// O(1) and needs no allocation.
	var bestY int64
	bestW := math.Inf(1)
	found := false
	it := orderedD{sub}.To(u)
	for it.Next() {
		y := it.Node().ID()
		w := sp.WeightTo(y)
		if math.IsInf(w, 1) {
			continue
		}
		// Ties break on the caller's id so the witness stays deterministic.
		if !found || w < bestW || (w == bestW && b.nameOf[y] < b.nameOf[bestY]) {
			bestY, bestW, found = y, w, true
		}
	}
	if !found {
		return nil
	}
	p, _ := sp.To(bestY)
	if len(p) == 0 {
		return nil
	}
	cycle := b.names(p)
	return append(cycle, comp[0])
}

// undirectedCycleWitness returns one elementary undirected cycle. It builds a
// spanning forest with Kruskal's algorithm, picks an input edge the forest did
// not take (adding such an edge to a forest always closes exactly one cycle),
// and walks the unique tree path between that edge's endpoints.
func (b *built) undirectedCycleWitness() []string {
	// Kruskal populates the destination with every vertex itself; pre-adding
	// them would make it panic.
	forest := simple.NewWeightedUndirectedGraph(0, math.Inf(1))
	path.Kruskal(forest, b.weightedUndirectedView())

	var extras []edgePair
	edges := b.weightedUndirectedView().WeightedEdges()
	for edges.Next() {
		e := edges.WeightedEdge()
		uid, vid := e.From().ID(), e.To().ID()
		if forest.HasEdgeBetween(uid, vid) {
			continue
		}
		u, v := b.nameOf[uid], b.nameOf[vid]
		if v < u {
			u, v = v, u
		}
		extras = append(extras, edgePair{u, v})
	}
	if len(extras) == 0 {
		return nil
	}
	sortPairs(extras)
	chosen := extras[0]

	// The witness needs only the UNIQUE tree path between the endpoints, so
	// edge weights are irrelevant — and running Dijkstra over the weighted
	// forest PANICS ("dijkstra: negative edge weight") whenever the graph has a
	// negative weight, which is a supported input class. Search an unweighted
	// copy of the forest instead, where every edge costs 1.
	plain := simple.NewUndirectedGraph()
	for _, id := range b.ids {
		plain.AddNode(simple.Node(b.idOf[id]))
	}
	fe := forest.Edges()
	for fe.Next() {
		e := fe.Edge()
		plain.SetEdge(simple.Edge{F: simple.Node(e.From().ID()), T: simple.Node(e.To().ID())})
	}

	sp := path.DijkstraFrom(simple.Node(b.idOf[chosen.a]), orderedU{plain})
	p, _ := sp.To(b.idOf[chosen.b])
	if len(p) == 0 {
		return nil
	}
	cycle := b.names(p)
	return append(cycle, chosen.a)
}

package nodes

import (
	"context"
	"math"
	"sort"

	"gonum.org/v1/gonum/graph/path"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Computes the shortest-path distance from one source vertex to every other
// vertex in the graph, returning the reachable vertices with their total cost
// and hop count, plus the list of vertices that cannot be reached. Uses
// Dijkstra's algorithm, switching to Bellman-Ford for graphs with negative
// edge weights.
func Distances(ctx context.Context, ax axiom.Context, input *gen.DistancesRequest) (*gen.DistancesResult, error) {
	if input == nil {
		return &gen.DistancesResult{Error: "request is required"}, nil
	}
	b, err := buildGraph(input.Graph)
	if err != nil {
		return &gen.DistancesResult{Error: err.Error()}, nil
	}
	if err := ctx.Err(); err != nil {
		return &gen.DistancesResult{Error: "cancelled: " + err.Error()}, nil
	}
	fromID, ok := b.idOf[input.From]
	if !ok {
		return &gen.DistancesResult{Error: "unknown source node id " + quote(input.From)}, nil
	}

	sp, errMsg := b.shortestFrom(ctx, fromID)
	if errMsg != "" {
		return &gen.DistancesResult{Error: errMsg}, nil
	}

	// The hop-count walk below is O(V+E) (see distancesFrom), but still runs
	// under the shared wall-clock budget as a backstop.
	out, budgetErr := runBounded(ctx, "Distances", func() *gen.DistancesResult {
		return distancesFrom(b, sp, fromID)
	})
	if budgetErr != nil {
		return &gen.DistancesResult{Error: budgetErr.Error()}, nil
	}
	return out, nil
}

// distancesFrom turns a computed shortest-path tree into the result message.
//
// Hop counts come from a breadth-first search over the SHORTEST-PATH DAG — the
// sub-graph of edges (u,v) satisfying dist[u] + w(u,v) == dist[v] — which is
// O(V+E) and depends on neither the graph's diameter nor its tie structure.
//
// The obvious implementation, calling sp.To(v) per vertex and reading len(path),
// is O(V * diameter) because each call materialises the whole path. Resolving
// the farthest vertices first and memoising helps only when distances are
// DISTINCT: give every edge an explicit zero weight, or hang many leaves off the
// end of a long chain, and every vertex ties, the ordering degenerates, and the
// quadratic behaviour returns — a 20000-vertex zero-weight chain cost 3.8s and
// churned 14 GB. The DAG walk has no such branch.
//
// The float equality test is exact by construction, not approximate: the search
// computed dist[v] AS dist[u] + w(u,v) for whichever predecessor it chose, and
// recomputing that same IEEE sum reproduces the same bits, so at least one
// in-edge always matches.
func distancesFrom(b *built, sp path.Shortest, source int64) *gen.DistancesResult {
	out := &gen.DistancesResult{}

	dist := make(map[int64]float64, len(b.ids))
	for _, id := range b.ids {
		vid := b.idOf[id]
		dist[vid] = sp.WeightTo(vid)
	}

	wg := b.weightedLister()
	hops := make(map[int64]int32, len(b.ids))
	hops[source] = 0
	queue := make([]int64, 0, len(b.ids))
	queue = append(queue, source)

	for len(queue) > 0 {
		u := queue[0]
		queue = queue[1:]
		it := wg.From(u) // ordered wrapper: deterministic neighbour order
		for it.Next() {
			v := it.Node().ID()
			if _, seen := hops[v]; seen {
				continue
			}
			w, ok := wg.Weight(u, v)
			if !ok {
				continue
			}
			if dist[u]+w == dist[v] {
				hops[v] = hops[u] + 1
				queue = append(queue, v)
			}
		}
	}

	for _, id := range b.ids {
		vid := b.idOf[id]
		h, reachable := hops[vid]
		// A vertex is unreachable exactly when the search never assigned it a
		// finite distance; buildGraph has already ruled out weight overflow as
		// a cause.
		if !reachable || math.IsInf(dist[vid], 1) {
			out.Unreachable = append(out.Unreachable, id)
			continue
		}
		out.Distances = append(out.Distances, &gen.Distance{
			Node:     id,
			Weight:   dist[vid],
			HopCount: h,
		})
	}
	sort.Slice(out.Distances, func(i, j int) bool { return out.Distances[i].Node < out.Distances[j].Node })
	sort.Strings(out.Unreachable)
	return out
}

package nodes

import (
	"context"
	"math"

	"gonum.org/v1/gonum/graph/path"
	"gonum.org/v1/gonum/graph/simple"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Selects the cheapest set of edges that connects every vertex without forming
// a cycle, using Kruskal's algorithm. The result is returned as a plain Graph —
// the package's canonical envelope — so it feeds straight into Describe,
// DetectCycle, ConnectedComponents or TopologicalSort with an identity edge and
// no adapter. Pipe it into Describe to recover the tree's total weight. When
// the input is disconnected the result is a minimum spanning forest rather than
// an error. Requires an undirected graph.
func MinimumSpanningTree(ctx context.Context, ax axiom.Context, input *gen.Graph) (*gen.Graph, error) {
	b, err := buildGraph(input)
	if err != nil {
		// Graph carries no error field, so a rejected request surfaces as a Go
		// error and the platform reports it as a node failure.
		return nil, err
	}
	if b.directed {
		return nil, errUndirectedRequired("MinimumSpanningTree")
	}
	if err := ctx.Err(); err != nil {
		return nil, err
	}

	// Kruskal panics if dst already holds nodes that exist in g; it populates
	// dst with every vertex itself, including isolated ones.
	dst := simple.NewWeightedUndirectedGraph(0, math.Inf(1))
	path.Kruskal(dst, b.weightedUndirectedView())

	tree := &gen.Graph{Directed: false}
	for _, id := range b.ids {
		tree.Nodes = append(tree.Nodes, &gen.GraphNode{Id: id, Label: b.labelOf[id]})
	}
	var picked []edgePair
	edges := orderedWU{dst}.WeightedEdges()
	for edges.Next() {
		e := edges.WeightedEdge()
		u, v := b.nameOf[e.From().ID()], b.nameOf[e.To().ID()]
		if v < u {
			u, v = v, u
		}
		picked = append(picked, edgePair{u, v})
	}
	// Deterministic edge ordering in the emitted graph.
	sortPairs(picked)
	for _, p := range picked {
		w := b.wug.WeightedEdge(b.idOf[p.a], b.idOf[p.b]).Weight()
		tree.Edges = append(tree.Edges, &gen.GraphEdge{
			From:               p.a,
			To:                 p.b,
			Weight:             w,
			ExplicitZeroWeight: w == 0,
		})
	}
	return tree, nil
}

package nodes

import (
	"context"
	"sort"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Flips a graph's edge direction — a directed graph in yields an undirected
// graph out, and vice versa. It takes and returns the plain Graph envelope, so
// it chains from and into every other Graph-shaped node with no adapter.
//
// This is the bridge across the package's directed/undirected split:
// MinimumSpanningTree requires an undirected graph and TopologicalSort requires
// a directed one, so without this node a directed graph could never reach the
// former and an undirected graph could never reach the latter inside a flow.
// Because the direction is read from the input graph's own `directed` field
// rather than from a separate parameter, the node needs no configuration and
// composes mid-flow.
//
// Directed -> UNDIRECTED collapses any pair of opposing edges into a single
// edge carrying the smaller of the two weights — a directed a->b of 5 and b->a
// of 2 become one a-b of 2 — because an undirected graph cannot hold both and
// silently keeping an arbitrary one would be a guess.
//
// Undirected -> DIRECTED replaces each undirected edge with a pair of opposing
// edges, which preserves reachability exactly. Note that this makes the result
// cyclic by construction, so a topological sort of it will report is_dag=false
// unless the original had no edges, and that it doubles the edge count.
//
// Self-loops and vertex labels are preserved in every case.
func Orient(ctx context.Context, ax axiom.Context, input *gen.Graph) (*gen.Graph, error) {
	b, err := buildGraph(input)
	if err != nil {
		return nil, err
	}
	if err := ctx.Err(); err != nil {
		return nil, err
	}

	// The output direction is the opposite of the input's.
	out := &gen.Graph{Directed: !b.directed}
	for _, id := range b.ids {
		out.Nodes = append(out.Nodes, &gen.GraphNode{Id: id, Label: b.labelOf[id]})
	}

	if out.Directed {
		// Undirected -> directed: each edge becomes an opposing pair. A
		// self-loop is already its own reverse, so it is emitted once.
		for _, e := range input.Edges {
			out.Edges = append(out.Edges, cloneEdge(e))
			if e.From != e.To {
				rev := cloneEdge(e)
				rev.From, rev.To = e.To, e.From
				out.Edges = append(out.Edges, rev)
			}
		}
		sortEdges(out.Edges)
		return out, nil
	}

	// Directed -> undirected: collapse opposing pairs, keeping the smaller
	// weight so the result is deterministic and never loses the cheaper route.
	type key struct{ a, b string }
	best := map[key]*gen.GraphEdge{}
	var order []key
	for _, e := range input.Edges {
		k := key{e.From, e.To}
		if e.To < e.From {
			k = key{e.To, e.From}
		}
		cand := cloneEdge(e)
		cand.From, cand.To = k.a, k.b
		prev, seen := best[k]
		if !seen {
			best[k] = cand
			order = append(order, k)
			continue
		}
		if resolveWeight(cand.Weight, cand.ExplicitZeroWeight) <
			resolveWeight(prev.Weight, prev.ExplicitZeroWeight) {
			best[k] = cand
		}
	}
	for _, k := range order {
		out.Edges = append(out.Edges, best[k])
	}
	sortEdges(out.Edges)
	return out, nil
}

func cloneEdge(e *gen.GraphEdge) *gen.GraphEdge {
	return &gen.GraphEdge{
		From:               e.From,
		To:                 e.To,
		Weight:             e.Weight,
		ExplicitZeroWeight: e.ExplicitZeroWeight,
	}
}

// sortEdges gives the emitted edge list a deterministic order.
func sortEdges(es []*gen.GraphEdge) {
	sort.SliceStable(es, func(i, j int) bool {
		if es[i].From != es[j].From {
			return es[i].From < es[j].From
		}
		return es[i].To < es[j].To
	})
}

package nodes

import (
	"context"
	"fmt"
	"math"
	"sort"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Ranks vertices by link importance using the PageRank power iteration: a
// vertex is important when important vertices point at it. Self-loops are
// honoured, since a self-loop is a genuine rank sink that changes every score.
// An undirected graph is treated as a directed graph with each edge present in
// both directions. Edge weights are ignored — the ranking is computed on the
// link topology only. Scores sum to 1 and are rounded to 6 decimal places. The
// power iteration runs from a fixed uniform start vector and accumulates in a
// fixed order, so the result is bit-for-bit reproducible before rounding as
// well as after — see pagerank_iter.go for why the recurrence is run here
// rather than by gonum.
func PageRank(ctx context.Context, ax axiom.Context, input *gen.PageRankRequest) (*gen.PageRankResult, error) {
	if input == nil {
		return &gen.PageRankResult{Error: "request is required"}, nil
	}
	b, err := buildGraph(input.Graph)
	if err != nil {
		return &gen.PageRankResult{Error: err.Error()}, nil
	}
	if len(b.ids) == 0 {
		return &gen.PageRankResult{Error: "graph has no nodes"}, nil
	}

	damping := input.Damping
	// NaN must be rejected BEFORE the range check. Every comparison against a
	// NaN is false, so `damping <= 0 || damping >= 1` lets NaN through, and the
	// power iteration's convergence test then never becomes true — an infinite
	// loop driven by one caller-supplied field.
	if math.IsNaN(damping) || math.IsInf(damping, 0) {
		return &gen.PageRankResult{Error: "damping must be a finite value strictly between 0 and 1"}, nil
	}
	if damping == 0 {
		damping = 0.85
	}
	// The upper bound is 0.99, not 1. The power iteration needs roughly
	// log(tolerance)/log(damping) steps, so the cost grows without limit as
	// damping approaches 1: at 0.99 a full-size graph converges in ~0.3s, but
	// at 0.9999999999 it does not return at all — an unbounded CPU burn from a
	// single caller-supplied float.
	if damping <= 0 || damping > maxPageRankDamping {
		return &gen.PageRankResult{Error: fmt.Sprintf(
			"damping must be greater than 0 and at most %g; values nearer 1 make the power iteration converge arbitrarily slowly",
			maxPageRankDamping)}, nil
	}

	if err := ctx.Err(); err != nil {
		return &gen.PageRankResult{Error: "cancelled before computing PageRank: " + err.Error()}, nil
	}

	// The convergence tolerance is pinned rather than caller-supplied, so a
	// caller cannot drive the iteration count. It is a PER-VERTEX target:
	// deterministicPageRank compares the L1 residual against tol*n, because an
	// L1 sum over n vertices has a noise floor that grows with n and a
	// size-independent target is unreachable on large graphs. At 20000
	// vertices the resulting worst-case error per score is about 2e-7, which
	// stays under the 6-decimal rounding applied below.
	const pageRankTolerance = 1e-13
	const pageRankDecimals = 6

	// deterministicPageRank, not gonum's network.PageRank/PageRankSparse: gonum
	// seeds its iteration from a random vector, which made this node's output
	// nondeterministic at rounding boundaries. The in-package iteration is also
	// sparse — O(V+E) per step — so the dense-matrix blow-up gonum's PageRank
	// would incur at the vertex limit does not arise either.
	view := b.pageRankView(input.Graph)
	ids := make([]int64, 0, len(b.ids))
	for _, id := range b.ids {
		ids = append(ids, b.idOf[id])
	}

	type prResult struct {
		scores map[int64]float64
		err    error
	}
	res, budgetErr := runBounded(ctx, "PageRank", func() prResult {
		sc, err := deterministicPageRank(view, ids, damping, pageRankTolerance)
		return prResult{sc, err}
	})
	if budgetErr != nil {
		return &gen.PageRankResult{Error: budgetErr.Error()}, nil
	}
	if res.err != nil {
		return &gen.PageRankResult{Error: res.err.Error()}, nil
	}
	scores := res.scores

	out := &gen.PageRankResult{Damping: damping}
	for _, id := range b.ids {
		out.Scores = append(out.Scores, &gen.PageRankScore{
			Node:  id,
			Score: roundTo(scores[b.idOf[id]], pageRankDecimals),
		})
	}
	sort.Slice(out.Scores, func(i, j int) bool { return out.Scores[i].Node < out.Scores[j].Node })
	return out, nil
}

package nodes

import (
	"context"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Finds the lowest-cost path between two vertices of a graph and returns the
// ordered vertex ids, the total weight and the hop count. Uses Dijkstra's
// algorithm, automatically switching to Bellman-Ford when the graph contains
// negative edge weights; a negative-weight cycle is reported as an error.
func ShortestPath(ctx context.Context, ax axiom.Context, input *gen.ShortestPathRequest) (*gen.ShortestPathResult, error) {
	if input == nil {
		return &gen.ShortestPathResult{Error: "request is required"}, nil
	}
	b, err := buildGraph(input.Graph)
	if err != nil {
		return &gen.ShortestPathResult{Error: err.Error()}, nil
	}
	if err := ctx.Err(); err != nil {
		return &gen.ShortestPathResult{Error: "cancelled: " + err.Error()}, nil
	}
	fromID, ok := b.idOf[input.From]
	if !ok {
		return &gen.ShortestPathResult{Error: "unknown source node id " + quote(input.From)}, nil
	}
	toID, ok := b.idOf[input.To]
	if !ok {
		return &gen.ShortestPathResult{Error: "unknown target node id " + quote(input.To)}, nil
	}

	sp, errMsg := b.shortestFrom(ctx, fromID)
	if errMsg != "" {
		return &gen.ShortestPathResult{Error: errMsg}, nil
	}

	p, w := sp.To(toID)
	// An unreachable target is signalled by an EMPTY path. buildGraph has
	// already guaranteed that no reachable total can overflow to +Inf, so an
	// empty path here means genuine unreachability and nothing else.
	if len(p) == 0 {
		return &gen.ShortestPathResult{Found: false}, nil
	}
	return &gen.ShortestPathResult{
		Found:       true,
		Path:        b.names(p),
		TotalWeight: w,
		HopCount:    int32(len(p) - 1),
	}, nil
}

package nodes

import (
	"context"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Extracts the subgraph induced by a set of vertices: keeps exactly those
// vertices and every edge whose endpoints are both kept. The result is returned
// as a plain Graph — the package's canonical envelope — so it chains straight
// into any graph-consuming node with an identity edge and no adapter. A
// requested vertex id that is not in the source graph is rejected rather than
// silently ignored; an empty selection yields an empty graph.
func Subgraph(ctx context.Context, ax axiom.Context, input *gen.SubgraphRequest) (*gen.Graph, error) {
	if input == nil {
		return nil, errRequestRequired()
	}
	b, err := buildGraph(input.Graph)
	if err != nil {
		return nil, err
	}
	if err := ctx.Err(); err != nil {
		return nil, err
	}

	keep := make(map[string]bool, len(input.Nodes))
	for _, id := range input.Nodes {
		if _, ok := b.idOf[id]; !ok {
			return nil, errUnknownNode(id)
		}
		keep[id] = true
	}

	out := &gen.Graph{Directed: input.Graph.Directed}
	for _, id := range b.ids {
		if keep[id] {
			out.Nodes = append(out.Nodes, &gen.GraphNode{Id: id, Label: b.labelOf[id]})
		}
	}
	for _, e := range input.Graph.Edges {
		if keep[e.From] && keep[e.To] {
			out.Edges = append(out.Edges, &gen.GraphEdge{
				From:               e.From,
				To:                 e.To,
				Weight:             e.Weight,
				ExplicitZeroWeight: e.ExplicitZeroWeight,
			})
		}
	}
	return out, nil
}

package nodes

import (
	"context"
	"sort"

	"gonum.org/v1/gonum/graph"
	"gonum.org/v1/gonum/graph/topo"

	"christiangeorgelucas/graph-tools/axiom"
	gen "christiangeorgelucas/graph-tools/gen"
)

// Orders the vertices of a directed acyclic graph so that every edge points
// from an earlier vertex to a later one — the standard dependency/build order.
// The ordering is a deterministic function of the input: the same graph always
// yields the same order. It is NOT guaranteed to be the lexicographically
// smallest valid order — vertex ids seed the traversal, but the result is not a
// lexicographic Kahn ordering. Reports
// is_dag=false with an empty order when the graph contains a cycle. Requires a
// directed graph.
func TopologicalSort(ctx context.Context, ax axiom.Context, input *gen.Graph) (*gen.TopoSortResult, error) {
	b, err := buildGraph(input)
	if err != nil {
		return &gen.TopoSortResult{Error: err.Error()}, nil
	}
	if err := ctx.Err(); err != nil {
		return &gen.TopoSortResult{Error: "cancelled: " + err.Error()}, nil
	}
	if !b.directed {
		return &gen.TopoSortResult{Error: "TopologicalSort requires a directed graph; set `directed` to true"}, nil
	}
	if b.selfLoops > 0 {
		// A self-loop is a cycle, but it is excluded from the gonum structure,
		// so report it explicitly rather than returning a bogus ordering.
		return &gen.TopoSortResult{IsDag: false}, nil
	}

	// SortStabilized with a lexical comparator makes the ordering a pure
	// function of the input rather than of gonum's internal map iteration
	// order. Note the comparator orders gonum's DFS roots, not Kahn's ready
	// set, so the result is stable but not lexicographically minimal.
	sorted, err := topo.SortStabilized(b.directedView(), func(nodes []graph.Node) {
		sort.Slice(nodes, func(i, j int) bool {
			return b.nameOf[nodes[i].ID()] < b.nameOf[nodes[j].ID()]
		})
	})
	if err != nil {
		return &gen.TopoSortResult{IsDag: false}, nil
	}
	return &gen.TopoSortResult{IsDag: true, Order: b.names(sorted)}, nil
}