Skip to content

Latest commit

 

History

History
106 lines (90 loc) · 4.47 KB

ROADMAP.md

File metadata and controls

106 lines (90 loc) · 4.47 KB

Graphina Feature Roadmap

This document includes the roadmap for the Graphina project. It outlines features to be implemented and their current status.

Important

This roadmap is a work in progress and is subject to change.

  • Core Library

    • Directed and undirected graph types (weighted and unweighted).
    • NodeId and EdgeId wrappers, NodeMap, EdgeMap, and OrderedNodeMap.
    • Graph builders.
    • Validation utilities (connectivity, DAG, bipartite, negative weights, and self-loops).
    • Simple IO: edge and adjacency list formats.
    • Serialization: JSON, binary, and GraphML.
    • Experimental memory pooling utilities.

  • Shortest Paths and Traversal

    • Dijkstra (single-source) and Dijkstra path tracing.
    • Bellman–Ford (negative weights) and path tracing.
    • Floyd–Warshall (all-pairs).
    • Johnson's algorithm (all-pairs on sparse graphs).
    • A* and IDA*.
    • BFS, DFS, IDDFS, and bidirectional search.

  • Centrality (Node/Edge Importance)

    • Degree, closeness, betweenness (node and edge).
    • Eigenvector, PageRank, Katz, and harmonic centralities.
    • Personalized PageRank (vector plus NodeMap facade API).
    • Local and global reaching centralities.
    • Laplacian centrality.
    • VoteRank (seed selector).
    • Percolation centrality.

  • Community Detection and Clustering

    • Label propagation.
    • Louvain method.
    • Girvan–Newman.
    • Spectral embeddings and spectral clustering.
    • Infomap (simplified version).
    • Personalized PageRank (community usage).
    • Connected components.

  • Minimum Spanning Trees (MST)

    • Prim's algorithm.
    • Kruskal's algorithm.
    • Borůvka's algorithm.

  • Subgraphs and Links

    • Subgraph extraction (induced, ego graph, and k-hop).
    • Filter nodes and edges; get the component subgraph.
    • Link prediction (RA, Jaccard, Adamic–Adar, CN, SH variants, WIC, and CNC).

  • Approximation and Heuristics

    • Maximum independent set (greedy).
    • Maximum clique (greedy heuristic), clique removal.
    • Large clique size.
    • Approx. clustering coefficient (sampling).
    • Densest subgraph (greedy peeling).
    • Diameter lower bound.
    • Minimum vertex cover (greedy).
    • Minimum maximal matching (greedy).
    • Ramsey R(2, t) approximation.
    • TSP approximations (greedy, SA, TA, and Christofides).
    • Treewidth decompositions (min-degree and min fill-in).

  • Parallel Algorithms

    • Parallel BFS.
    • Parallel degree and clustering coefficients.
    • Parallel triangles counting.
    • Parallel PageRank.
    • Parallel shortest paths.
    • Parallel connected components.

  • Visualization

    • ASCII visualization.
    • Force-directed, circular, grid, hierarchical layouts.
    • HTML generation, SVG export, PNG export.
    • D3.js JSON.

  • API and Developer Experience

    • Unified error handling via GraphinaError and Result returns (community and many centrality algorithms).
    • Public re-exports and facades for consistent entry points (like personalized PageRank).
    • Gate low-level modules (like core::pool) behind feature flags; marked experimental.
    • Crate-level documentation summarizing modules, features, and conventions.
    • Expanded conversion helpers (vector <-> NodeMap, typed adapters) across modules.
    • Finer-grained error variants for convergence vs invalid argument.
    • Stability policy and semver guarantees for public APIs.

  • Ecosystem and Bindings

    • Python bindings (PyGraphina) with community and centrality coverage.
    • Ensure parity and ergonomic exceptions across bindings.
    • Interoperability helpers (like import and export formats compatible with NetworkX and rustworkx).
    • WebAssembly support.

  • Data and Real-World Graphs

    • Integration tests referencing public datasets.
    • Optional dataset helper scripts with docs for getting the test datasets.

  • Benchmarks and Performance

    • Benchmarks for algorithms, graphs, and project-level scenarios.
    • Micro-benchmarks for pooling and hot paths under --features pool.
    • Profiling guides and performance tuning tips in docs.

  • Code Quality, CI, and Documentation

    • CI for builds and tests; code coverage reporting.