# google/graph-mining architecture

> Architecture diagram of the GitHub repository google/graph-mining, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2025-06-30). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/google/graph-mining
- Repository: https://github.com/google/graph-mining

## Overview

##### Project type and purpose
- This is an open-source, shared-memory, highly-parallel C++ library for graph mining and clustering.
- It provides in-memory graph representations, a scheduler for parallel execution, and a suite of graph algorithms (clustering, connected components, shortest paths, triangle counting, etc.).

##### File structure
- Top-level:
- BUILD.* & WORKSPACE.bazel – Bazel build configuration
- .bazelrc, .gitignore, LICENSE, CONTRIBUTING.md, docs/ – repository metadata and contribution guidelines
- examples/ – quickstart/demo code
- utils/ – common utilities (containers, math, status, timers, Bazel macros)
- sketching/ – point-cloud encoding module
- in_memory/ – core graph abstractions + algorithm packages
- in_memory/ substructure:
- parallel/ – scheduler, parallel utilities
- clustering/ – dozens of subpackages (affinity, hac, correlation, parline, etc.), each with its own BUILD, .cc/.h, .proto, tests
- connected_components, generation, shortest_paths, tree_partitioner, triangle_counting – other algorithm suites
- status_macros.h – error/status handling

##### Extract README insights
- Mission: “most scalable library for graph algorithms”
- Focus today on clustering, with pointers to research papers
- Build & run via Bazel; Protobuf used for “.proto” config in each algorithm

1. Build & Tooling Layer
- Bazel (BUILD files, WORKSPACE)
- Protobuf compiler (for .proto → .cc/.h)
2. Utility Layer
- utils/ (containers, math, status, timer, build_defs.bzl)
3. Core Graph & Parallel Engine
- in_memory/graph.*, in_memory/parallel/ (scheduler, parallel_graph_utils)
- in_memory/status_macros.h
4. Algorithm Modules
- Clustering packages (affinity, hac, correlation, parline, etc.)
- Other algorithms (connected_components, shortest_paths, triangle_counting, generation, tree_partitioner)
5. Sketching Module
- sketching/point_cloud
6. Examples & Demos
- examples/quickstart.cc
- Build & Tooling → compiles Utilities, Core, Algorithms, Sketching, Examples
- Utilities → Core Graph & Parallel Engine (utility functions imported here)
- Core Graph & Parallel Engine → Algorithm Modules (graph data structures + parallel scheduler consumed by algorithms)
- Algorithm Modules → Examples (examples link against selected algorithms)
- Algorithm Modules (.proto) ↔ Protobuf compiler (code-gen step)
c. Architectural Patterns & Principles
- Layered architecture: clear separation of concerns (Utilities → Core → Algorithms → Consumers)
- Modular plugin style: each clustering algorithm is its own Bazel target, with well-defined interfaces (.proto definitions)
- High cohesion & low coupling: algorithms depend only on core abstractions and utils
d. Key Technologies & Frameworks
- C++17 (source files: .cc/.h)
- Bazel build system
- Protocol Buffers (.proto → code-gen)
- Eigen, farmhash (via utils/eigen.BUILD, utils/farmhash.BUILD)

## Diagram (Mermaid)

```mermaid
flowchart TB
    %% Build & Tooling Layer
    subgraph "Build & Tooling" 
        BRC[".bazelrc"] 
        BOSS["BUILD.oss"] 
        WBZ["WORKSPACE.bazel"] 
        BDB["build_defs.bzl"] 
    end
    class BRC,BOSS,WBZ,BDB build

    %% Utility Layer
    subgraph "Utility Layer"
        UBLD["/utils/BUILD"]
        UCONT["container/"] 
        UMATHCC["math.cc"] 
        UMATHH["math.h"] 
        UPPTH1["parse_text_proto.h"] 
        UPPTH2["parse_text_proto_internal.h"] 
        USTS["thread_safe_status.h"] 
        UTIMER["timer.h"]
    end
    class UBLD,UCONT,UMATHCC,UMATHH,UPPTH1,UPPTH2,USTS,UTIMER util

    %% Core Graph & Parallel Engine
    subgraph "Core Graph & Parallel Engine"
        IMBUILD["/in_memory/BUILD"]
        SCHCC["scheduler.cc"] 
        SCHH["scheduler.h"] 
        PGC["parallel_graph_utils.cc"] 
        PGH["parallel_graph_utils.h"] 
        PSO["parallel_sequence_ops.h"] 
        PW["per_worker.h"] 
        STMAC["status_macros.h"]
    end
    class IMBUILD,SCHCC,SCHH,PGC,PGH,PSO,PW,STMAC core

    %% Protobuf Compiler
    PROTO["Protobuf Compiler"]:::core

    %% Algorithm Modules
    subgraph "Algorithm Modules"
        subgraph "Clustering Modules"
            CLBUILD["clustering/BUILD"]
            CLUTILCC["clustering_utils.cc"]
            CLUTILH["clustering_utils.h"]
            AFF["affinity/"]
            CLIQ["clique_container/"]
            COCON["coconductance/"]
            CORR["correlation/"]
            HAC["hac/"]
            DHAC["dynamic/hac/"]
            LP["label_propagation/"]
            PL["parline/"]
            MISC["misc utilities/types"]
        end
        subgraph "Connected Components"
            CCBUILD["connected_components/BUILD"]
            CCUF["asynchronous_union_find.h"]
        end
        subgraph "Shortest Paths"
            DIJCC["dijkstra.cc"]
            DIJH["dijkstra.h"]
        end
        subgraph "Triangle Counting"
            TCPC["parallel_triangle_counting.cc"]
            TCPH["parallel_triangle_counting.h"]
        end
        subgraph "Graph Generation"
            GBUILD["generation/BUILD"]
            BA["barabasi_albert.cc"]
            ER["erdos_renyi.cc"]
            AW["add_edge_weights.cc"]
        end
        subgraph "Tree Partitioner"
            TPC["min_size_tree_partitioning.cc"]
            TPH["min_size_tree_partitioning.h"]
        end
    end
    class CLBUILD,CLUTILCC,CLUTILH,AFF,CLIQ,COCON,CORR,HAC,DHAC,LP,PL,MISC,CCBUILD,CCUF,DIJCC,DIJH,TCPC,TCPH,GBUILD,BA,ER,AW,TPC,TPH algo

    %% Sketching Module
    subgraph "Sketching Module"
        SCCC["fixed_dimensional_encoding.cc"]
        SCHH2["fixed_dimensional_encoding.h"]
        SCONFIG["fixed_dimensional_encoding_config.proto"]
    end
    class SCCC,SCHH2,SCONFIG sketch

    %% Examples & Demos
    subgraph "Examples & Demos"
        EXBUILD["/examples/BUILD"]
        EXQ["quickstart.cc"]
    end
    class EXBUILD,EXQ example

    %% Relationships
    BRC -->|builds| UBLD
    BRC -->|builds| IMBUILD
    BRC -->|builds| CLBUILD
    BRC -->|builds| SCCC
    BRC -->|builds| EXBUILD

    UBLD -->|provides utilities| IMBUILD
    UCONT -->|provides utilities| IMBUILD
    UMATHCC -->|provides math| IMBUILD
    UMATHH -->|provides math| IMBUILD
    USTS -->|provides status| IMBUILD
    UTIMER -->|provides timer| IMBUILD

    IMBUILD -->|core engine| CLBUILD
    IMBUILD -->|core engine| CCBUILD
    IMBUILD -->|core engine| DIJCC
    IMBUILD -->|core engine| TCPC
    IMBUILD -->|core engine| GBUILD
    IMBUILD -->|core engine| TPC

    PROTO -->|generates code| CLUTILCC
    PROTO -->|generates code| SCONFIG

    CLBUILD -->|used by| EXQ
    CCBUILD -->|used by| EXQ
    DIJCC -->|used by| EXQ
    TCPC -->|used by| EXQ

    %% Click Events
    click BRC "https://github.com/google/graph-mining/blob/main/.bazelrc"
    click BOSS "https://github.com/google/graph-mining/blob/main/BUILD.oss"
    click WBZ "https://github.com/google/graph-mining/blob/main/WORKSPACE.bazel"
    click BDB "https://github.com/google/graph-mining/blob/main/utils/build_defs.bzl"
    click UBLD "https://github.com/google/graph-mining/tree/main/utils/BUILD"
    click UCONT "https://github.com/google/graph-mining/tree/main/utils/container/"
    click UMATHCC "https://github.com/google/graph-mining/blob/main/utils/math.cc"
    click UMATHH "https://github.com/google/graph-mining/blob/main/utils/math.h"
    click UPPTH1 "https://github.com/google/graph-mining/blob/main/utils/parse_proto/parse_text_proto.h"
    click UPPTH2 "https://github.com/google/graph-mining/blob/main/utils/parse_proto/parse_text_proto_internal.h"
    click USTS "https://github.com/google/graph-mining/blob/main/utils/status/thread_safe_status.h"
    click UTIMER "https://github.com/google/graph-mining/blob/main/utils/timer.h"
    click IMBUILD "https://github.com/google/graph-mining/tree/main/in_memory/BUILD"
    click SCHCC "https://github.com/google/graph-mining/blob/main/in_memory/parallel/scheduler.cc"
    click SCHH "https://github.com/google/graph-mining/blob/main/in_memory/parallel/scheduler.h"
    click PGC "https://github.com/google/graph-mining/blob/main/in_memory/parallel/parallel_graph_utils.cc"
    click PGH "https://github.com/google/graph-mining/blob/main/in_memory/parallel/parallel_graph_utils.h"
    click PSO "https://github.com/google/graph-mining/blob/main/in_memory/parallel/parallel_sequence_ops.h"
    click PW "https://github.com/google/graph-mining/blob/main/in_memory/parallel/per_worker.h"
    click STMAC "https://github.com/google/graph-mining/blob/main/in_memory/status_macros.h"
    click CLBUILD "https://github.com/google/graph-mining/tree/main/in_memory/clustering/BUILD"
    click CLUTILCC "https://github.com/google/graph-mining/blob/main/in_memory/clustering/clustering_utils.cc"
    click CLUTILH "https://github.com/google/graph-mining/blob/main/in_memory/clustering/clustering_utils.h"
    click AFF "https://github.com/google/graph-mining/tree/main/in_memory/clustering/affinity/"
    click CLIQ "https://github.com/google/graph-mining/tree/main/in_memory/clustering/clique_container/"
    click COCON "https://github.com/google/graph-mining/tree/main/in_memory/clustering/coconductance/"
    click CORR "https://github.com/google/graph-mining/tree/main/in_memory/clustering/correlation/"
    click HAC "https://github.com/google/graph-mining/tree/main/in_memory/clustering/hac/"
    click DHAC "https://github.com/google/graph-mining/tree/main/in_memory/clustering/dynamic/hac/"
    click LP "https://github.com/google/graph-mining/tree/main/in_memory/clustering/label_propagation/"
    click PL "https://github.com/google/graph-mining/tree/main/in_memory/clustering/parline/"
    click CCBUILD "https://github.com/google/graph-mining/tree/main/in_memory/connected_components/BUILD"
    click CCUF "https://github.com/google/graph-mining/blob/main/in_memory/connected_components/asynchronous_union_find.h"
    click DIJCC "https://github.com/google/graph-mining/blob/main/in_memory/shortest_paths/dijkstra.cc"
    click DIJH "https://github.com/google/graph-mining/blob/main/in_memory/shortest_paths/dijkstra.h"
    click TCPC "https://github.com/google/graph-mining/blob/main/in_memory/triangle_counting/parallel_triangle_counting.cc"
    click TCPH "https://github.com/google/graph-mining/blob/main/in_memory/triangle_counting/parallel_triangle_counting.h"
    click GBUILD "https://github.com/google/graph-mining/tree/main/in_memory/generation/BUILD"
    click BA "https://github.com/google/graph-mining/blob/main/in_memory/generation/barabasi_albert.cc"
    click ER "https://github.com/google/graph-mining/blob/main/in_memory/generation/erdos_renyi.cc"
    click AW "https://github.com/google/graph-mining/blob/main/in_memory/generation/add_edge_weights.cc"
    click TPC "https://github.com/google/graph-mining/blob/main/in_memory/tree_partitioner/min_size_tree_partitioning.cc"
    click TPH "https://github.com/google/graph-mining/blob/main/in_memory/tree_partitioner/min_size_tree_partitioning.h"
    click SCCC "https://github.com/google/graph-mining/blob/main/sketching/point_cloud/fixed_dimensional_encoding.cc"
    click SCHH2 "https://github.com/google/graph-mining/blob/main/sketching/point_cloud/fixed_dimensional_encoding.h"
    click SCONFIG "https://github.com/google/graph-mining/blob/main/sketching/point_cloud/fixed_dimensional_encoding_config.proto"
    click EXBUILD "https://github.com/google/graph-mining/tree/main/examples/BUILD"
    click EXQ "https://github.com/google/graph-mining/blob/main/examples/quickstart.cc"

    %% Styles
    classDef build fill:#d3d3d3,stroke:#333,stroke-width:1px
    classDef util fill:#87CEFA,stroke:#333,stroke-width:1px
    classDef core fill:#90EE90,stroke:#333,stroke-width:1px
    classDef algo fill:#FFA500,stroke:#333,stroke-width:1px
    classDef sketch fill:#20B2AA,stroke:#333,stroke-width:1px
    classDef example fill:#9370DB,stroke:#333,stroke-width:1px
```
