---
name: wikifita-site-graph-construction
type: analysis
title: "Link Graph Construction"
description: "How nodes (pages) and edges (links) are built from wiki content: link extraction, resolution cascade, backlink computation, and the D3-force graph visualization layout."
tags: [wikifita, graph, links, backlinks, d3-force, resolution, wiki-links]
timestamp: 2026-07-21
---

# Link Graph Construction

The Wikifita Atlas constructs a directed graph from the wiki corpus where pages are nodes and inter-page links are edges. This graph powers three systems: PageRank computation, search proximity boosting, and the interactive D3 force-directed visualization.

The graph construction happens during Phase 5 of the corpus pipeline [[wikifita-site-corpus-pipeline]], after frontmatter parsing and title resolution, and before PageRank computation [[wikifita-site-pagerank]].

---

## Graph Structure

### Nodes

Every `.md` or `.mdx` file in the corpus (excluding `AGENTS.md`) becomes a graph node. Nodes are identified by their POSIX-normalized file path (e.g., `memorias/MEMORY.md`).

```mermaid
flowchart TD
    A[RawWikiFile[]] -->|filter .md/.mdx, exclude AGENTS.md| B[Graph Nodes]
    B --> C["Node = WikiPage (path, title, category, pagerank)"]
```

### Edges

Edges are **directed** links from one page to another, extracted from the page's markdown content. Each edge represents a deliberate authorial reference -- a link written by the wiki author pointing to another page.

```mermaid
flowchart LR
    A["Page A (source)"] -->|"WIKI_LINK_TARGET_LABEL"| B["Page B (target)"]
    A -->|"[text](target.md)"| B
    A -->|"![alt](image.png)"| C["Image/Asset"]
```

Self-links (edges from a page to itself) are **filtered out** during outlink construction. This prevents a page from boosting its own PageRank or appearing in its own backlinks.

---

## Link Extraction

Links are extracted from the markdown AST using `unist-util-visit` over the parsed remark tree. Three origin kinds are detected:

### 1. Markdown Links (`kind: "markdown"`)

Standard markdown link syntax. The extractor visits `link` AST nodes and extracts the `url` field.

```markdown
[Link text](target.md)
[Link text](target.md#section)
[Link text](https://external.com)
```

| Component | Extraction |
|-----------|-----------|
| `target` | `node.url` from the AST |
| `label` | Concatenation of all child text nodes |
| `fragment` | Everything after `#` in the URL |

### 2. Wiki Links (`kind: "wiki"`)

Double-bracket wiki-style links found in raw text nodes. The extractor visits `text` AST nodes and applies a regex:

```
Pattern: /\[\[([^\]|#]+(?:#[^\]|]+)?)(?:\|([^\]]+))?\]\]/g
```

This matches:
- `target` -- simple wiki link
- `WIKI_LINK_TARGET_LABEL` -- wiki link with display text
- `target-fragment` -- wiki link with anchor
- `WIKI_LINK_TARGET_FRAGMENT_LABEL` -- wiki link with anchor and display text

| Component | Extraction |
|-----------|-----------|
| `target` | First capture group (before `\|`) |
| `label` | Second capture group (after `\|`), or target if absent |
| `fragment` | Everything after `#` in the target |

Wiki links inside code fences are **not extracted** because `unist-util-visit` does not visit text nodes within `code` or `inlineCode` AST elements.

### 3. Image References (`kind: "image"`)

Markdown image syntax. The extractor visits `image` AST nodes.

```markdown
![Alt text](image.png)
![Alt text](https://cdn.example.com/photo.jpg)
```

| Component | Extraction |
|-----------|-----------|
| `target` | `node.url` from the AST |
| `label` | `node.alt` (alt text) |
| `fragment` | Parsed from URL |

### Code Fence Exclusion

A critical design property: links inside code blocks are **automatically excluded** from extraction. The remark parser treats code blocks as atomic `code` nodes. The `unist-util-visit` function does not descend into their children, so any `triple-dot` patterns or markdown links inside fenced code are invisible to the link extractor.

This is essential for a wiki about code -- pages frequently contain example markdown syntax that should not be treated as actual links.

---

## Link Resolution Cascade

Each extracted raw link target goes through a multi-stage resolution pipeline (`resolveLinkTarget`). The stages form a cascade: if resolution succeeds at any stage, later stages are skipped.

### Stage 1: Fragment Extraction

```
Input:  "path/to/page#section"
Output: pathTarget = "path/to/page"
        fragment   = "section"
```

The target is split at the first `#`. If there is no `#`, the fragment is undefined.

### Stage 2: External URL Detection

If the target matches the external URL pattern, it is immediately classified as external:

```
Pattern: /^(?:[a-z][a-z0-9+.-]*:|\/\/)/i
```

This matches absolute URLs (`https://...`, `http://...`, `ftp://...`) and protocol-relative URLs (`//...`).

| Input | Result |
|-------|--------|
| `https://example.com` | `state: "external"` |
| `http://example.com` | `state: "external"` |
| `//cdn.example.com/img.png` | `state: "external"` |
| `mailto:user@example.com` | `state: "external"` |

### Stage 3: Fragment-Only Links

If the path target is empty but a fragment exists (e.g., `#section`), the link resolves to the source page itself with the given fragment:

```
Input:  "#introduction" (on page "docs/guide.md")
Result: destination = "docs/guide.md", state = "resolved"
```

### Stage 4: Exact Match

The path target is normalized (POSIX paths, stripped leading `../`, `./`, `/`) and checked against the set of all page paths:

```
1. Try exact match:     "memorias/MEMORY.md"  -> check allPaths
2. Try with .md:        "memorias/MEMORY"      -> check "memorias/MEMORY.md"
3. Try with .mdx:       "memorias/MEMORY"      -> check "memorias/MEMORY.mdx"
```

If any variant matches, the link resolves with `state: "resolved"`.

### Stage 5: Relative Path Resolution

If the target is not root-relative (does not start with `/`), it is resolved relative to the source page's directory:

```
Source:  "docs/guide/setup.md"
Target: "../config/options"
Result:  path.posix.join("docs/guide", "../config/options") = "docs/config/options"
```

The joined path is then checked with the same exact-match and extension-variant logic as Stage 4.

### Stage 6: Fuzzy Slug Matching

If all previous stages fail, the system performs a fuzzy match on the last path component (the "slug"):

```
Target slug: "MEMORY"
Candidate slugs: ["memory.md", "MEMORY.md", "Memory.mdx"]
```

The matching uses:
- **Case-insensitive comparison** with `pt-BR` locale (`slug.localeCompare(candidate, "pt-BR", { sensitivity: "base" })`)
- **Full route path comparison** as a fallback (the entire path, not just the slug)

| Matches Found | Result |
|--------------|--------|
| Exactly 1 | `state: "resolved"`, destination = matched page |
| More than 1 | `state: "ambiguous"` |
| 0 | `state: "missing"` |

The ambiguity case is important: if two pages have the same filename in different directories (e.g., `docs/config.md` and `wiki/config.md`), a link to `config` is flagged as ambiguous rather than arbitrarily choosing one.

### Resolution Cascade Summary

```mermaid
flowchart TD
    A[Raw Link Target] --> B{Fragment?}
    B -->|"path#frag"| C[Split path and fragment]
    B -->|"#frag only"| D["state: resolved (self)"]
    B -->|no fragment| C
    C --> E{External URL?}
    E -->|yes| F["state: external"]
    E -->|no| G{Exact match in allPaths?}
    G -->|yes| H["state: resolved"]
    G -->|no| I{Relative resolution?}
    I -->|match| H
    I -->|no match| J{Fuzzy slug match?}
    J -->|1 match| H
    J -->|">1 match"| K["state: ambiguous"]
    J -->|0 matches| L["state: missing"]
```

---

## Backlink Computation

After all pages have their outgoing links resolved, backlinks are computed as the inverse mapping. This is a single pass over all pages:

```
For each page in corpus:
    outlinks = unique resolved destinations (excluding self-links)
    For each outlink target:
        backlinksByPath[target].push(page.path)
```

### Properties

- **Symmetric by construction**: If page A has an outlink to page B, then A appears in B's backlinks
- **Deduplication**: If page A links to page B multiple times, A appears only once in B's backlinks (outlinks are deduplicated)
- **Self-exclusion**: A page never appears in its own backlinks
- **Directed**: Backlinks are computed from directed outlinks, but the backlinks array itself represents the reverse direction

### Usage

Backlinks are used in three contexts:
1. **Search proximity boost**: The BFS graph distance uses both outlinks and backlinks as undirected edges [[wikifita-site-search-system]]
2. **Context rail sidebar**: The document view shows which pages link to the current page
3. **LLM endpoint**: The per-page `/llms.txt` endpoint includes a backlinks section [[wikifita-site-llm-integration]]

---

## Graph Edge List

The final graph edge list is a flat array of `{source, target}` pairs, derived directly from outlinks:

```typescript
links = basePages.flatMap(page =>
  page.outlinks.map(target => ({ source: page.path, target }))
)
```

This is a directed edge list. Each edge represents a resolved, non-self link from one page to another. The edge list is stored on the `WikiCorpus.links` field and serialized to the client for graph visualization.

---

## D3 Force-Directed Graph Layout

The graph is visualized using `d3-force` in the client-side `AtlasClient.tsx` component. The layout applies physics simulation to position nodes in a way that reveals the wiki's structure.

### Force Configuration

| Force | Type | Parameters | Purpose |
|-------|------|-----------|---------|
| `forceLink` | Link | distance: 72, strength: 0.16 | Pulls connected nodes toward a target distance |
| `forceManyBody` | Charge | strength: -92 (global), -56 (background) | Repels all nodes from each other |
| `forceCollide` | Collision | radius: nodeRadius + 10, strength: 0.8 | Prevents node overlap |
| `forceX` | Position | per-community X target | Pulls nodes toward category-based columns |
| `forceY` | Position | center Y, strength: 0.04 | Gentle vertical centering |
| `forceCenter` | Center | canvas center | Centers the entire graph |

### Seeded Randomness

The simulation uses a deterministic seeded random number generator for node initial positions. This ensures the same corpus produces the same layout across renders, given the same commit SHA and page count.

The layout is cached by the key `{commit}:{variant}:{selectedPath}:{pageCount}:{linkCount}`:
- `commit`: Git SHA (changes when content changes)
- `variant`: `"global"` (full graph) or `"background"` (dimmed background)
- `selectedPath`: Currently focused page (affects forceX targets)
- `pageCount` and `linkCount`: Graph dimensions

### Community-Based X-Positioning

The `forceX` pull organizes nodes into vertical columns by category:

| Category | X Target | Visual Position |
|----------|----------|-----------------|
| `memory` | Left column | Left side |
| `project` | Left-center | |
| `research` | Center | Center |
| `directive` | Right-center | |
| `person` | Right column | Right side |
| `other` | Far right | Right edge |

This creates a natural visual clustering where related pages are near each other horizontally, even if they are not directly linked. The `forceLink` attraction works within and across clusters, creating the final layout.

### Simulation Lifecycle

```
1. Initialize nodes with seeded random positions
2. Configure forces
3. Run simulation:
   - Global mode: 240 ticks (full computation)
   - Background mode: 180 ticks (reduced computation for dimmed graph)
4. Stop simulation
5. Cache layout positions
6. Render nodes and edges on canvas
```

### Node Rendering

Each node is rendered as a circle on an HTML5 canvas:

| Property | Formula |
|----------|---------|
| Radius | $5 + \sqrt{\frac{\text{pagerank}}{\text{maxRank}}} \times 18$ |
| Color | Category base color mixed with tag-derived accent (FNV-1a hash) |
| Label | Title text, rendered below the node |
| Opacity | 1.0 for selected/highlighted, 0.3-0.6 for background |

### Edge Rendering

Edges are rendered as lines with:
- Direction indicated by arrowheads (optional)
- Color derived from source node color at reduced opacity
- Curved paths when multiple edges exist between the same node pair

### Undirected Adjacency for Client

The directed `{source, target}` edge list is converted to an undirected adjacency map on the client for graph traversal:

```typescript
adjacency = new Map()
for (const { source, target } of links) {
  adjacency.get(source).push(target)
  adjacency.get(target).push(source)  // reverse direction
}
```

This undirected adjacency is used for the BFS proximity computation in search [[wikifita-site-search-system]].

---

## Self-Link Filtering

Self-links are filtered at two levels:

### Outlink Construction

When building a page's `outlinks` array, any resolved destination that equals the page's own path is excluded:

```typescript
outlinks = resolvedLinks
  .filter(link => link.destination !== page.path)
  .map(link => link.destination)
  .unique()
```

### Backlink Computation

Since backlinks are derived from outlinks, self-exclusion propagates automatically. A page that links to itself will not appear in its own backlinks because the self-link was already removed from outlinks.

### Why Self-Links Are Excluded

Without filtering:
- A page could artificially inflate its own PageRank
- The backlinks section would show the page itself (confusing)
- The graph would have self-loops (visually noisy and mechanically meaningless)

---

## Link Resolution Diagnostics

The resolution cascade produces diagnostics that are available for debugging and quality assurance:

| State | Meaning | Action |
|-------|---------|--------|
| `resolved` | Link target found in corpus | Render as clickable link |
| `external` | Link points outside the wiki | Render as external link (may open in new tab) |
| `missing` | No matching page found | Render with `unresolved` CSS class |
| `ambiguous` | Multiple pages match the slug | Render with `unresolved ambiguous` CSS class |

The rendering pipeline [[wikifita-site-rendering-pipeline]] uses these states to add CSS classes and `data-link-state` attributes, enabling visual feedback for broken links.

---

## Corpus Impact

The link graph has measurable structural properties that affect the wiki's usability:

### Connectivity Metrics

| Metric | Description | Typical Value |
|--------|-------------|---------------|
| Edge count | Total resolved directed links | 2-5x page count |
| Density | $\frac{|E|}{|V|(|V|-1)}$ | Very sparse (< 0.1) |
| Dangling nodes | Pages with 0 outlinks | 5-15% of pages |
| Isolated nodes | Pages with 0 inlinks and 0 outlinks | Rare (< 5%) |
| Average outdegree | Mean outlinks per page | 2-6 |

### Structural Patterns

- **Hub pages**: Index pages, CLAUDE.md files, and memory indexes tend to have high outdegree (many links to other pages)
- **Authority pages**: Key concept pages and popular research topics accumulate high indegree (many backlinks)
- **Bridge pages**: Pages that link across categories (e.g., a research page linking to infrastructure docs) act as bridges in the PageRank computation
- **Leaf pages**: Pages with no incoming links are discoverable only through search or manual navigation

---

## Related Pages

- [[wikifita-site-pagerank]] -- How PageRank consumes the graph structure
- [[wikifita-site-search-system]] -- BFS proximity boost using the graph
- [[wikifita-site-corpus-pipeline]] -- The 7-phase pipeline where graph construction happens
- [[wikifita-site-rendering-pipeline]] -- How link states affect HTML rendering
- [[wikifita-site-architecture]] -- Full technical architecture