Found by two independent senior-model code reviews (Codex + Claude), each verified by execution against the affected functions before any fix landed.
johnson never applied the Bellman-Ford reweighting correction, silently
returning wrong all-pairs shortest-path distances for any weighted graph
(all-pairs-shortest-paths dispatches here). The existing test fixture
asserted the wrong values - corrected alongside the fix.betweenness-centrality silently ignored edge weights (plain BFS
hop-counting even on weighted input) and was cubic. Rewritten using
Brandes' algorithm: correct on weighted graphs, O(VE) instead of O(V^3).weight* on multigraphs NPE'd on plain [u v] edge vectors, or picked an
arbitrary parallel edge instead of the minimum, breaking every weighted
algorithm (dijkstra/astar/johnson/bellman-ford/max-flow) on multidigraphs.remove-edges on a multigraph deleted every parallel edge instead of the
one targeted by edge-key.astar-path returned non-shortest paths for admissible-but-inconsistent
heuristics; fixed via standard node reopening.bf-path returned nil for start = end instead of the zero-hop path,
inconsistent with bf-path-bi/dijkstra-path.network-simplex/solve misreported an unbounded negative-cost cycle as a
finite optimum, and its "infinity" sentinel silently became 0 on an
all-zero-magnitude graph (Clojure's 0 is truthy, so (or (* 3 (max ...)) 1) never fell through).articulation-points/bridges/tarjan-blocks/digraph-all-cycles used
direct recursion, stack-overflowing on graphs beyond a few thousand nodes.
Converted to an explicit-stack iterative walk.remove-attr was asymmetric on undirected graphs; multigraph edge
attributes were split-brain across two storage keys; subgraph bypassed
attribute pruning; remove-multi-nodes added a spurious :in key on
undirected multigraphs.clustering-coefficient threw on weighted graphs; bellman-ford threw on
FlyGraph; clustering-coefficient/density divided by zero on
empty/singleton graphs.pagerank was O(iterations x V x (V+E)) instead of O(iterations x
(V+E)) - measured 51-142x speedup after precomputing reverse adjacency.compliance_tester.cljc now also exercises multigraph/multidigraph against
the shared protocol contracts, the root cause behind several of the above.
loom.io readers and writers for GraphML, GEXF, edge lists, and adjacency
JSON, plus a DOT reader. Matching writer/reader pairs preserve directedness,
weights, node values, and Loom attributes.multigraph and multidigraph constructors with stable parallel
edge identities, per-edge weights, and attribute support through
edges-with-ids.loom.flow/min-cost-flow exposes the existing network-simplex solver as a
graph-level operation over node demand and edge capacity/cost attributes,
returning [flow-map total-cost] consistently with max-flow.loom.gen is now portable to ClojureScript with a cross-platform seeded
PRNG; seeded graph generators now produce identical results on the JVM
and JS.ex-info validation for missing algorithm nodes, negative
weights passed to Dijkstra/A*, and malformed maximum-flow capacities and
source/sink constraints.This is a backward-compatible minor release: existing simple-graph protocol
implementations and endpoint-shaped edges behavior are unchanged.
add-attrs-to-all no longer invents bogus attributes: it treated the flat
key/value list as a sliding window (partition 2 1), writing a spurious
entry keyed by each value. It now pairs keys with values (partition 2).New:
loom.gen/gen-circle and loom.gen/gen-newman-watts - ring and small-world
(Newman & Watts 1999) graph generators, seeded for reproducibility. Closes #106.loom.gen/gen-barabasi-albert - scale-free graph generator via preferential
attachment (Barabasi & Albert 1999), seeded. Reworks #105 (whose attachment
probability was inverted).loom.alg/clustering-coefficient - local and average clustering coefficient
(Watts & Strogatz 1998).New:
loom.alg/simple-paths - all simple paths between two nodes, with an optional
:max-depth. Closes #111.loom.alg/digraph-all-cycles - all simple cycles in a directed graph
(Johnson's algorithm). Closes #126.Performance:
degeneracy-ordering decrements neighbor degrees directly instead of building
an intermediate map. Closes #108.pre-traverse pushes successors lazily, avoiding O(E) stack growth on dense
graphs (preorder unchanged). Closes #120.First release of the maintained fork, published as net.clojars.savya/loom.
Platform:
deps.edn so loom is usable as a git dependency and via clojure -X:test.Bug fixes:
transpose returned an empty graph under ClojureScript, breaking scc,
strongly-connected?, and every transpose-based operation. Fixes #131.remove-nodes / subgraph threw a null error on digraphs under ClojureScript.
Fixes #134.bf-path-bi ran its two searches in racing threads and could return a
non-shortest path; it is now deterministic.bipartite-color ignored edge direction on digraphs, giving non-deterministic
results for nodes with no outgoing edges. Fixes #118.maximal-cliques on a digraph now throws instead of returning silently-wrong
results. Fixes #128.remove-nodes now prunes the removed nodes' attributes. Fixes #93.weight on an edge dispatches to (weight* g e), honoring the protocol for
graphs whose edges are not determined by their endpoints. Fixes #141.(graph {})) no longer throws.
Fixes #137.Closed issues:
Merged pull requests:
Closed issues:
Merged pull requests:
Closed issues:
Merged pull requests:
Closed issues:
Merged pull requests:
Closed issues:
\(scc ...\) dies with a StackOverflow on large directed graphs #5Closed issues:
Closed issues:
* This Change Log was automatically generated by github_changelog_generator
Can you improve this documentation? These fine people already did:
Savyasachi & AysyluEdit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |