# Graph Schema
This document describes the data model used by Arbor to represent code structure.
## Nodes
Every code entity is represented as a node in the graph.
### Node Structure
```json
{
"id": "unique_node_identifier",
"name": "FunctionName",
"qualifiedName": "ModuleName.ClassName.FunctionName",
"kind": "function",
"file": "src/services/user.ts",
"lineStart": 45,
"lineEnd": 78,
"column": 2,
"signature": "async validateUser(id: string): Promise<User>",
"visibility": "public",
"attributes": {
"async": true,
"static": false,
"exported": true
},
"docstring": "Validates a user by their ID.",
"centrality": 0.75
}
```
### Node Kinds
| Kind | Description | Languages |
|------|-------------|-----------|
| `function` | Standalone function | All |
| `method` | Class method | All |
| `class` | Class definition | All |
| `interface` | Interface/protocol/trait | TS, Rust |
| `struct` | Struct definition | Rust |
| `enum` | Enum definition | All |
| `variable` | Module-level variable | All |
| `constant` | Constant definition | All |
| `type_alias` | Type alias | TS, Rust |
| `module` | File/module boundary | All |
| `import` | Import statement | All |
| `export` | Export declaration | TS |
### Node IDs
Node IDs are generated deterministically from:
- File path (relative to project root)
- Node qualified name
- Node kind
This ensures the same node always gets the same ID, enabling incremental updates.
```
id = hash(file_path + ":" + qualified_name + ":" + kind)
```
## Edges
Edges represent relationships between nodes.
### Edge Structure
```json
{
"from": "source_node_id",
"to": "target_node_id",
"kind": "calls",
"location": {
"file": "src/services/user.ts",
"line": 52,
"column": 8
}
}
```
### Edge Kinds
| Kind | Description | From → To |
|------|-------------|-----------|
| `calls` | Function invocation | function → function |
| `imports` | Import statement | module → module |
| `exports` | Re-export | module → symbol |
| `extends` | Class inheritance | class → class |
| `implements` | Interface implementation | class → interface |
| `uses_type` | Type reference | any → type/interface |
| `references` | General symbol reference | any → any |
| `contains` | Nesting relationship | class → method |
| `returns` | Return type | function → type |
| `parameter` | Parameter type | function → type |
## Graph Structure
The graph is stored using an adjacency list representation:
```
nodes: HashMap<NodeId, Node>
edges_out: HashMap<NodeId, Vec<Edge>>
edges_in: HashMap<NodeId, Vec<Edge>>
```
Both incoming and outgoing edges are indexed for fast traversal in either direction.
## Indexes
For fast lookups, we maintain several indexes:
### Name Index
```
name_index: HashMap<String, Vec<NodeId>>
```
Maps symbol names to node IDs. Used for text search.
### File Index
```
file_index: HashMap<PathBuf, Vec<NodeId>>
```
Maps file paths to all nodes defined in that file. Used for incremental updates.
### Kind Index
```
kind_index: HashMap<NodeKind, Vec<NodeId>>
```
Maps node kinds to IDs. Used for filtering by type.
## Serialization
The graph can be serialized to JSON for export or persistence:
```json
{
"version": "1.0",
"projectRoot": "/path/to/project",
"timestamp": "2024-01-15T10:30:00Z",
"stats": {
"nodeCount": 1542,
"edgeCount": 4820
},
"nodes": [
{ "id": "...", "name": "...", ... }
],
"edges": [
{ "from": "...", "to": "...", "kind": "..." }
]
}
```
## Language-Specific Mappings
### TypeScript
| AST Node | Arbor Kind |
|----------|------------|
| `function_declaration` | function |
| `method_definition` | method |
| `class_declaration` | class |
| `interface_declaration` | interface |
| `type_alias_declaration` | type_alias |
| `variable_declaration` | variable |
| `import_statement` | import |
| `export_statement` | export |
### Rust
| AST Node | Arbor Kind |
|----------|------------|
| `function_item` | function |
| `impl_item` → `function_item` | method |
| `struct_item` | struct |
| `enum_item` | enum |
| `trait_item` | interface |
| `use_declaration` | import |
| `mod_item` | module |
### Python
| AST Node | Arbor Kind |
|----------|------------|
| `function_definition` | function |
| `class_definition.function_definition` | method |
| `class_definition` | class |
| `import_statement` | import |
| `import_from_statement` | import |
## Centrality Algorithm
Arbor uses a simplified PageRank variant to compute node importance:
1. Initialize all nodes with score 1/N
2. For each iteration:
- Each node distributes its score to nodes it calls
- Damping factor of 0.85 prevents score concentration
3. Converge after ~10-20 iterations
Nodes with high centrality scores are architecturally significant (many dependents) and prioritized in context windows.
