graph
Status: planned (wave 3). There is no repository and no code yet, and graph is a working name. These pages describe the plan, not a release.
Graph algorithms that gonum/graph lacks, behind a MATLAB-style graph and digraph facade.
What it will provide
| facade | graph and digraph with adjacency, incidence and Laplacian matrices, over gonum/graph |
| matching | Hopcroft-Karp (bipartite) and blossom (general) |
| isomorphism | VF2, and canonical labelling |
| cuts and flows | minimum-cut extraction; push-relabel if gonum’s Dinic is not enough |
| centrality | the remaining centralities |
| reused, not rewritten | shortest paths, spanning trees, strongly connected components, Brandes betweenness, PageRank, HITS, Louvain and Leiden, which gonum/graph already provides |
References
The algorithms and the theory the package will start from, as the roadmap’s bibliography lists them:
| Reference | Cite |
|---|---|
| Hopcroft, Karp, An n^(5/2) algorithm for maximum matchings in bipartite graphs, SIAM J. Comput. 2(4):225-231, 1973 | doi:10.1137/0202019 |
| Edmonds, Paths, trees, and flowers, Can. J. Math. 17:449-467, 1965 | doi:10.4153/CJM-1965-045-4 |
| Cordella, Foggia, Sansone, Vento, A (sub)graph isomorphism algorithm for matching large graphs, IEEE TPAMI 26(10):1367-1372, 2004 | doi:10.1109/TPAMI.2004.75 |
| McKay, Piperno, Practical graph isomorphism, II, J. Symb. Comput. 60:94-112, 2014 | doi:10.1016/j.jsc.2013.09.003 |
| Goldberg, Tarjan, A new approach to the maximum-flow problem, JACM 35(4):921-940, 1988 | doi:10.1145/48014.61051 |
| Brandes, A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2):163-177, 2001 | doi:10.1080/0022250X.2001.9990249 |
| Tarjan, Depth-first search and linear graph algorithms, SIAM J. Comput. 1(2):146-160, 1972 | doi:10.1137/0201010 |
Reference implementations and licences
What exists, under which licence, and what that allows:
| Implementation | Licence and use |
|---|---|
gonum/gonum graph/... | BSD-3-Clause; imported directly (https://github.com/gonum/gonum). It has Dinic maximum flow, Brandes betweenness, PageRank, HITS, Louvain and Leiden; it has no matching, no push-relabel and no Sugiyama layout |
| NetworkX | BSD-3-Clause; the oracle for every graph algorithm, driven from Go with node-link JSON |
| Boost.Graph | BSL-1.0; permissive, usable as a reference |
| igraph C core | GPL-2.0: an oracle only |
GPL, LGPL, AGPL and non-free code is never ported: it is only run as an oracle, as an external program.
How it will be validated
- Exact equality for integer-weight shortest paths, flow values, matching sizes and component partitions.
- Modularity within a tolerance for community detection, with the seed fixed; labels are not compared.
- Corpora: SNAP and the DIMACS implementation challenges.
Depends on
gonum/graph. The organization extends or wraps gonum and does not duplicate it; the maintainers’ stance on adding matching upstream is an open question in the plan.
Scope notes
Graph layout is not part of this organization: it belongs to go-graphdrawing (https://github.com/go-graphdrawing), which is empty today and depends on this one.
Where the plan lives
PLAN.md, STATUS.md and the bibliography in the go-scikit roadmap.
Created on by tannevaled
Modified on by tannevaled