mirror of
https://github.com/hanzoai/skills.git
synced 2026-11-19 00:47:36 +00:00
Every page now loads /webmcp.js, scripts/webmcp.ts with its types stripped (npm run webmcp). Where the browser has document.modelContext it registers two read-only tools: search_skills over the published skills index, and get_skill, which returns a skill's markdown checked against the index digest. The markdown alternate link moves from build.py to site.py, so CI holds every page to it. The API catalog gains the site itself (llms.txt and the skills index) and hanzo.ai/agents; the live discovery check now fetches every catalog link. tests/site.mjs drives the tools through a recording modelContext, and checks a browser without one loads clean.
771 lines
32 KiB
HTML
771 lines
32 KiB
HTML
<!doctype html>
|
||
<html lang="en"><head>
|
||
<meta charset="utf-8"><meta name="viewport" content="width=device-width,initial-scale=1">
|
||
<title>advanced-graph-algorithms</title>
|
||
<meta name="color-scheme" content="dark">
|
||
<style>
|
||
/* Committed to one visual world: a dark instrument panel. No light variant —
|
||
the dot field and the hairline rules only read on black, and a naive
|
||
inversion would wash both out. Every colour is painted explicitly so the page
|
||
never borrows a host background. */
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen';src:url('/fonts/Zen-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Variable.woff2') format('woff2');font-weight:100 900;font-style:normal;font-display:swap}
|
||
@font-face{font-family:'Zen Mono';src:url('/fonts/ZenMono-Italic-Variable.woff2') format('woff2');font-weight:100 900;font-style:italic;font-display:swap}
|
||
@font-face{font-family:'Zen Pixel Square';src:url('/fonts/ZenPixel-Square.woff2') format('woff2');font-style:normal;font-display:swap}
|
||
|
||
:root{
|
||
--ink:#f4f4f2; --soft:#9c9c98; --faint:#6a6a66; --ground:#000; --panel:#0a0a0a;
|
||
--line:#232323; --line-hi:#3a3a3a; --accent:#f4f4f2;
|
||
--font-zen-sans:'Zen',-apple-system,BlinkMacSystemFont,"Segoe UI",Helvetica,Arial,sans-serif;
|
||
--font-zen-mono:'Zen Mono',ui-monospace,"SF Mono",SFMono-Regular,Menlo,Consolas,monospace;
|
||
--font-zen-pixel-square:'Zen Pixel Square',monospace;
|
||
--mono:var(--font-zen-mono);
|
||
--sans:var(--font-zen-sans);
|
||
/* Controls are pills and surfaces are soft, as on hanzo.ai. */
|
||
--r:999px; --r-soft:14px;
|
||
}
|
||
*{box-sizing:border-box}
|
||
html{-webkit-text-size-adjust:100%}
|
||
body{margin:0;background:var(--ground);color:var(--ink);font-family:var(--sans);
|
||
font-size:16px;line-height:1.65;-webkit-font-smoothing:antialiased}
|
||
.wrap{max-width:60rem;margin:0 auto;padding:0 1.75rem}
|
||
|
||
/* The dot field. A halftone made of one repeating radial-gradient, faded out
|
||
along the diagonal by a mask so it reads as a wave rather than wallpaper. */
|
||
/* No overflow clip here: the dot field is inset to the box already, and a clip
|
||
would cut off the copy-prompt menu. */
|
||
.hero{position:relative;border-bottom:1px solid var(--line)}
|
||
.hero::before{content:"";position:absolute;inset:0;
|
||
background-image:radial-gradient(var(--line-hi) 1px, transparent 1px);
|
||
background-size:7px 7px;
|
||
-webkit-mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
mask-image:linear-gradient(115deg,#000 0%,rgba(0,0,0,.55) 38%,transparent 72%);
|
||
pointer-events:none}
|
||
.hero .wrap{position:relative;padding-top:5.5rem;padding-bottom:4rem}
|
||
|
||
nav{border-bottom:1px solid var(--line)}
|
||
nav .in{max-width:60rem;margin:0 auto;padding:1.1rem 1.75rem;display:flex;
|
||
justify-content:space-between;align-items:center;gap:1rem}
|
||
.brand{font-family:var(--mono);font-size:.85rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--ink);text-decoration:none;
|
||
display:inline-flex;align-items:center;gap:.6rem}
|
||
.brand i{font-style:normal;color:var(--faint)}
|
||
.mark{width:1.15em;height:1.15em;display:block;flex:0 0 auto}
|
||
nav a.up{font-family:var(--mono);font-size:.72rem;letter-spacing:.14em;
|
||
text-transform:uppercase;color:var(--soft);text-decoration:none}
|
||
nav a.up:hover{color:var(--ink)}
|
||
|
||
h1{font-family:var(--mono);font-size:clamp(2rem,5.4vw,3.4rem);line-height:1.12;
|
||
letter-spacing:-.02em;margin:0 0 1.1rem;font-weight:500;text-wrap:balance}
|
||
h1 em{font-style:normal;color:var(--faint)}
|
||
.lede{color:var(--soft);font-size:1.05rem;max-width:52ch;margin:0 0 2.25rem}
|
||
|
||
.btns{display:flex;flex-wrap:wrap;gap:.7rem;margin:0 0 .5rem;align-items:center}
|
||
.btn{display:inline-flex;align-items:center;gap:.5rem;font-family:var(--mono);
|
||
font-size:.72rem;letter-spacing:.14em;text-transform:uppercase;
|
||
padding:.8rem 1.4rem;border:1px solid var(--line-hi);border-radius:var(--r);
|
||
color:var(--ink);text-decoration:none;background:transparent;cursor:pointer;
|
||
line-height:1.2;font-weight:400}
|
||
.btn:hover{background:#141414;text-decoration:none;border-color:var(--soft)}
|
||
.btn.solid{background:var(--ink);color:#000;border-color:var(--ink)}
|
||
.btn.solid:hover{background:#d8d8d4}
|
||
.btn .chev{width:.7em;height:.7em;flex:0 0 auto;transition:transform .15s ease}
|
||
.btn[aria-expanded="true"] .chev{transform:rotate(180deg)}
|
||
|
||
/* Copy-prompt selector. Each row copies the prompt for its own target. */
|
||
.copy{position:relative;display:inline-flex}
|
||
.menu{position:absolute;top:calc(100% + .5rem);left:0;z-index:20;min-width:21rem;
|
||
background:var(--panel);border:1px solid var(--line-hi);border-radius:var(--r-soft);
|
||
padding:.4rem;display:flex;flex-direction:column;
|
||
box-shadow:0 12px 32px rgba(0,0,0,.75)}
|
||
.menu[hidden]{display:none}
|
||
.mi{display:flex;align-items:center;gap:.7rem;width:100%;text-align:left;
|
||
padding:.62rem .8rem;border:0;border-radius:calc(var(--r-soft) - .35rem);
|
||
background:transparent;color:var(--ink);font-family:var(--mono);font-size:.76rem;
|
||
letter-spacing:.04em;text-decoration:none;cursor:pointer;line-height:1.3;
|
||
white-space:nowrap}
|
||
.mi:hover,.mi:focus-visible{background:#181818;outline:none}
|
||
.mi .mark{width:1.05rem;height:1.05rem;color:var(--soft)}
|
||
.mi:hover .mark{color:var(--ink)}
|
||
.mi u{margin-left:auto;color:var(--faint);text-decoration:none;font-size:.68rem;
|
||
letter-spacing:.1em;text-transform:uppercase}
|
||
|
||
/* Works-with bar: one scrolling row, name and mark per agent. */
|
||
.strip{border-bottom:1px solid var(--line);background:var(--panel)}
|
||
.strip .in{max-width:60rem;margin:0 auto;padding:.9rem 1.75rem;display:flex;
|
||
align-items:center;gap:1.25rem;font-family:var(--mono);font-size:.72rem;
|
||
letter-spacing:.1em;text-transform:uppercase;color:var(--faint)}
|
||
.strip b{color:var(--soft);font-weight:400;flex:0 0 auto;
|
||
border-right:1px solid var(--line);padding-right:1.25rem;align-self:stretch;
|
||
display:flex;align-items:center}
|
||
.bar{display:flex;align-items:center;gap:.5rem;flex:1 1 auto;min-width:0;
|
||
overflow-x:auto;scrollbar-width:none;scroll-snap-type:x proximity;
|
||
-webkit-overflow-scrolling:touch;
|
||
-webkit-mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent);
|
||
mask-image:linear-gradient(90deg,#000 calc(100% - 3rem),transparent)}
|
||
.bar::-webkit-scrollbar{display:none}
|
||
.agent{display:inline-flex;align-items:center;gap:.45rem;flex:0 0 auto;
|
||
padding:.4rem .85rem;border:1px solid var(--line);border-radius:var(--r);
|
||
color:var(--soft);white-space:nowrap;scroll-snap-align:start;
|
||
text-decoration:none;background:var(--ground)}
|
||
.agent:hover{color:var(--ink);border-color:var(--line-hi);text-decoration:none}
|
||
.agent .mark{width:.95rem;height:.95rem}
|
||
|
||
h2{font-family:var(--mono);font-size:1.1rem;letter-spacing:-.01em;margin:2.75rem 0 .75rem;font-weight:500}
|
||
h3{font-size:1rem;margin:2rem 0 .5rem;font-weight:600}
|
||
h4,h5,h6{font-size:.94rem;margin:1.5rem 0 .5rem;font-weight:600}
|
||
p{margin:0 0 1rem;max-width:70ch}
|
||
ul,ol{margin:0 0 1rem;padding-left:1.35rem;max-width:70ch}
|
||
li{margin:.22rem 0}
|
||
a{color:var(--ink);text-decoration:underline;text-underline-offset:3px;
|
||
text-decoration-color:var(--line-hi)}
|
||
a:hover{text-decoration-color:var(--ink)}
|
||
a:focus-visible{outline:1px solid var(--ink);outline-offset:3px}
|
||
code{font-family:var(--mono);font-size:.85em;background:var(--panel);
|
||
border:1px solid var(--line);border-radius:5px;padding:.1em .36em}
|
||
pre{background:var(--panel);border:1px solid var(--line);padding:1rem 1.1rem;
|
||
border-radius:var(--r-soft);overflow-x:auto;margin:0 0 1.25rem}
|
||
pre code{background:none;border:0;padding:0;font-size:.82rem;line-height:1.7}
|
||
blockquote{margin:0 0 1rem;padding-left:1rem;border-left:1px solid var(--line-hi);color:var(--soft)}
|
||
hr{border:0;border-top:1px solid var(--line);margin:2.5rem 0}
|
||
table{border-collapse:collapse;width:100%;margin:0 0 1.25rem;font-size:.92rem;
|
||
display:block;overflow-x:auto}
|
||
th,td{border:1px solid var(--line);padding:.5rem .7rem;text-align:left}
|
||
|
||
.curl{display:block;background:var(--panel);border:1px solid var(--line);
|
||
border-radius:var(--r-soft);padding:.95rem 1.1rem;font-family:var(--mono);
|
||
font-size:.8rem;color:var(--soft);overflow-x:auto;margin:0 0 2.5rem;
|
||
white-space:pre;line-height:1.9}
|
||
.curl b{color:var(--ink);font-weight:400}
|
||
.curl i{font-style:normal;color:var(--faint)}
|
||
|
||
/* index */
|
||
#q{width:100%;padding:.85rem 1.2rem;font-family:var(--mono);font-size:.85rem;color:var(--ink);
|
||
background:var(--panel);border:1px solid var(--line);border-radius:var(--r);margin:0 0 .6rem}
|
||
#q::placeholder{color:var(--faint);text-transform:uppercase;letter-spacing:.1em;font-size:.72rem}
|
||
#q:focus{outline:none;border-color:var(--soft)}
|
||
#count{color:var(--faint);font-family:var(--mono);font-size:.72rem;letter-spacing:.1em;
|
||
text-transform:uppercase;margin:0 0 2rem}
|
||
.cat{margin:2.5rem 0 .5rem;font-family:var(--mono);font-size:.7rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);border-bottom:1px solid var(--line);
|
||
padding-bottom:.45rem}
|
||
.row{display:block;padding:.6rem .9rem;margin:0 -.9rem;border-bottom:1px solid var(--line);
|
||
border-radius:var(--r-soft);text-decoration:none}
|
||
.row:hover{background:#0a0a0a}
|
||
.nm{font-family:var(--mono);font-size:.84rem;color:var(--ink);display:block}
|
||
.ds{color:var(--soft);font-size:.9rem;display:block;margin-top:.12rem}
|
||
footer{margin-top:4rem;padding:2rem 0 4rem;border-top:1px solid var(--line);
|
||
color:var(--faint);font-size:.85rem}
|
||
footer a{color:var(--soft)}
|
||
.fmap{display:grid;gap:1.75rem;grid-template-columns:repeat(auto-fit,minmax(11rem,1fr));
|
||
margin:0 0 2rem;font-size:.85rem}
|
||
.fmap b{display:block;font-family:var(--mono);font-size:.68rem;letter-spacing:.16em;
|
||
text-transform:uppercase;color:var(--faint);font-weight:400;margin:0 0 .6rem;
|
||
border-bottom:1px solid var(--line);padding-bottom:.4rem}
|
||
.fmap a{display:inline-block;color:var(--ink);text-decoration:none;margin:.3rem .35rem 0 0}
|
||
.fmap a:hover{text-decoration:underline}
|
||
.fmap div{color:var(--faint);line-height:1.5}
|
||
.fend{border-top:1px solid var(--line);padding-top:1.25rem;font-size:.82rem}
|
||
|
||
@media (max-width:640px){
|
||
.hero .wrap{padding-top:3.25rem;padding-bottom:2.75rem}
|
||
.btns{gap:.5rem}
|
||
.btn{padding:.75rem 1.15rem;font-size:.68rem}
|
||
.copy,.copy .btn{width:100%;justify-content:center}
|
||
.menu{left:0;right:0;min-width:0}
|
||
.strip .in{flex-direction:column;align-items:flex-start;gap:.6rem;padding:.9rem 1.75rem}
|
||
.strip b{border-right:0;padding-right:0}
|
||
.bar{width:100%}
|
||
}
|
||
</style>
|
||
<link rel="icon" href="/favicon.svg">
|
||
<link rel="canonical" href="https://hanzoskills.com/advanced-graph-algorithms">
|
||
<link rel="alternate" type="text/markdown" href="/advanced-graph-algorithms.md">
|
||
<script type="module" src="/webmcp.js"></script>
|
||
</head>
|
||
<!-- Reading this with a machine? Every page here is also plain markdown.
|
||
This one: https://hanzoskills.com/advanced-graph-algorithms.md
|
||
Index: https://hanzoskills.com/llms.txt
|
||
Corpus: https://hanzoskills.com/all.md
|
||
Append .md to any path for the markdown twin. -->
|
||
<body>
|
||
<nav><div class="in">
|
||
<a class="brand" href="/"><svg class="mark" viewBox="0 0 67 67" fill="currentColor" aria-hidden="true"><path d="M22.21 67V44.6369H0V67H22.21Z"/><path d="M66.7038 22.3184H22.2534L0.0878906 44.6367H44.4634L66.7038 22.3184Z"/><path d="M22.21 0H0V22.3184H22.21V0Z"/><path d="M66.7198 0H44.5098V22.3184H66.7198V0Z"/><path d="M66.7198 67V44.6369H44.5098V67H66.7198Z"/></svg> HANZO<i>SKILLS</i></a>
|
||
<a class="up" href="/">All skills</a>
|
||
</div></nav>
|
||
|
||
<div class="wrap">
|
||
<h1>advanced-graph-algorithms</h1><p class="lede">Specialized graph algorithms including graph decomposition, vertex coloring, matching algorithms, and 2024 research advances</p><h1>Advanced Graph Algorithms</h1>
|
||
<p><strong>Last Updated</strong>: 2025-10-25</p>
|
||
<h2>When to Use This Skill</h2>
|
||
<p><strong>Activate when</strong>:</p>
|
||
<ul><li>Solving graph coloring and scheduling problems</li><li>Computing matchings in general graphs</li><li>Decomposing graphs into components</li><li>Finding cliques and independent sets</li><li>Solving vertex cover and dominating set problems</li><li>Implementing latest graph algorithm research</li></ul>
|
||
<p><strong>Prerequisites</strong>: <code>graph-theory-fundamentals.md</code>, <code>graph-data-structures.md</code>, <code>graph-traversal-algorithms.md</code>, <code>network-flow-algorithms.md</code></p>
|
||
<p><strong>Related Skills</strong>: <code>shortest-path-algorithms.md</code>, <code>minimum-spanning-tree.md</code>, <code>graph-applications.md</code></p>
|
||
<hr>
|
||
<h2>Core Algorithms</h2>
|
||
<h3>1. Graph Coloring</h3>
|
||
<p><strong>Concept</strong>: Assign colors to vertices such that no adjacent vertices share same color</p>
|
||
<p><strong>Chromatic Number</strong>: χ(G) = minimum number of colors needed</p>
|
||
<pre><code class="lang-python">from typing import Dict, Set, Optional, List
|
||
|
||
def greedy_coloring(graph: 'AdjacencyList') -> Dict[int, int]:
|
||
"""
|
||
Greedy graph coloring algorithm
|
||
|
||
Time: O(V + E)
|
||
Approximation: Uses at most Δ(G) + 1 colors where Δ = max degree
|
||
"""
|
||
coloring = {}
|
||
|
||
for v in range(graph.num_vertices):
|
||
# Find colors used by neighbors
|
||
neighbor_colors = {coloring[u] for u in graph.neighbors(v)
|
||
if u in coloring}
|
||
|
||
# Assign smallest available color
|
||
color = 0
|
||
while color in neighbor_colors:
|
||
color += 1
|
||
|
||
coloring[v] = color
|
||
|
||
return coloring
|
||
|
||
def welsh_powell_coloring(graph: 'AdjacencyList') -> Dict[int, int]:
|
||
"""
|
||
Welsh-Powell algorithm: Color vertices in degree-descending order
|
||
|
||
Often produces better coloring than simple greedy
|
||
"""
|
||
# Sort vertices by degree (descending)
|
||
vertices_by_degree = sorted(
|
||
range(graph.num_vertices),
|
||
key=lambda v: graph.degree(v),
|
||
reverse=True
|
||
)
|
||
|
||
coloring = {}
|
||
|
||
for v in vertices_by_degree:
|
||
# Find colors used by neighbors
|
||
neighbor_colors = {coloring[u] for u in graph.neighbors(v)
|
||
if u in coloring}
|
||
|
||
# Assign smallest available color
|
||
color = 0
|
||
while color in neighbor_colors:
|
||
color += 1
|
||
|
||
coloring[v] = color
|
||
|
||
return coloring
|
||
|
||
def is_valid_coloring(graph: 'AdjacencyList', coloring: Dict[int, int]) -> bool:
|
||
"""Verify that coloring is valid (no adjacent vertices same color)"""
|
||
for u in range(graph.num_vertices):
|
||
for v in graph.neighbors(u):
|
||
if coloring[u] == coloring[v]:
|
||
return False
|
||
return True
|
||
|
||
def chromatic_number_bound(graph: 'AdjacencyList') -> tuple[int, int]:
|
||
"""
|
||
Compute bounds on chromatic number
|
||
|
||
Returns: (lower_bound, upper_bound)
|
||
"""
|
||
# Lower bound: size of maximum clique
|
||
# Upper bound: Δ(G) + 1 (greedy bound)
|
||
|
||
max_degree = max(graph.degree(v) for v in range(graph.num_vertices))
|
||
upper_bound = max_degree + 1
|
||
|
||
# Simple lower bound: 2 if graph has edges, 1 otherwise
|
||
lower_bound = 2 if graph.edge_count() > 0 else 1
|
||
|
||
return lower_bound, upper_bound
|
||
|
||
# Example usage
|
||
from graph_data_structures import AdjacencyList
|
||
|
||
graph = AdjacencyList(5, directed=False)
|
||
graph.add_edge(0, 1)
|
||
graph.add_edge(0, 2)
|
||
graph.add_edge(1, 2)
|
||
graph.add_edge(1, 3)
|
||
graph.add_edge(2, 3)
|
||
graph.add_edge(3, 4)
|
||
|
||
coloring = welsh_powell_coloring(graph)
|
||
num_colors = max(coloring.values()) + 1
|
||
print(f"Coloring uses {num_colors} colors")
|
||
print(f"Valid: {is_valid_coloring(graph, coloring)}")</code></pre>
|
||
<p><strong>Edge Coloring</strong>:</p>
|
||
<pre><code class="lang-python">def edge_coloring_vizing(graph: 'AdjacencyList') -> Dict[tuple[int, int], int]:
|
||
"""
|
||
Edge coloring using Vizing's algorithm
|
||
|
||
Vizing's Theorem: χ'(G) ∈ {Δ(G), Δ(G) + 1}
|
||
where χ'(G) = edge chromatic number, Δ(G) = max degree
|
||
|
||
Time: O(V × E)
|
||
"""
|
||
if graph.directed:
|
||
raise ValueError("Edge coloring for undirected graphs only")
|
||
|
||
edge_colors = {}
|
||
max_degree = max(graph.degree(v) for v in range(graph.num_vertices))
|
||
|
||
# Process edges one by one
|
||
edges = graph.all_edges()
|
||
|
||
for u, v, _ in edges:
|
||
edge = tuple(sorted([u, v]))
|
||
|
||
# Find colors used at u and v
|
||
colors_at_u = {edge_colors.get(tuple(sorted([u, w])))
|
||
for w in graph.neighbors(u)
|
||
if tuple(sorted([u, w])) in edge_colors}
|
||
|
||
colors_at_v = {edge_colors.get(tuple(sorted([v, w])))
|
||
for w in graph.neighbors(v)
|
||
if tuple(sorted([v, w])) in edge_colors}
|
||
|
||
# Assign smallest color not used at u or v
|
||
used_colors = colors_at_u | colors_at_v
|
||
color = 0
|
||
while color in used_colors:
|
||
color += 1
|
||
|
||
edge_colors[edge] = color
|
||
|
||
return edge_colors</code></pre>
|
||
<h3>2. Maximum Matching (General Graphs)</h3>
|
||
<p><strong>Concept</strong>: Maximum set of edges with no shared vertices</p>
|
||
<p><strong>Blossom Algorithm</strong> (Edmonds, 1965): Polynomial-time maximum matching for general graphs</p>
|
||
<pre><code class="lang-python">class BlossomMatching:
|
||
"""
|
||
Edmonds' blossom algorithm for maximum matching
|
||
|
||
Simplified implementation - full version is complex
|
||
|
||
Time: O(V² × E)
|
||
"""
|
||
|
||
def __init__(self, graph: 'AdjacencyList'):
|
||
if graph.directed:
|
||
raise ValueError("Matching for undirected graphs only")
|
||
|
||
self.graph = graph
|
||
self.matching = {} # matching[u] = v if (u,v) in matching
|
||
|
||
def is_matched(self, v: int) -> bool:
|
||
"""Check if vertex is matched"""
|
||
return v in self.matching
|
||
|
||
def find_augmenting_path_simple(self) -> Optional[List[int]]:
|
||
"""
|
||
Find augmenting path (simple version, doesn't handle blossoms)
|
||
|
||
Augmenting path: Path with alternating unmatched/matched edges
|
||
starting and ending at unmatched vertices
|
||
"""
|
||
# Start from unmatched vertex
|
||
for start in range(self.graph.num_vertices):
|
||
if self.is_matched(start):
|
||
continue
|
||
|
||
# BFS to find augmenting path
|
||
from collections import deque
|
||
queue = deque([(start, [start])])
|
||
visited = {start}
|
||
|
||
while queue:
|
||
u, path = queue.popleft()
|
||
|
||
for v in self.graph.neighbors(u):
|
||
if v == start:
|
||
continue
|
||
|
||
if v in visited:
|
||
continue
|
||
|
||
new_path = path + [v]
|
||
|
||
# Check if path alternates between matched/unmatched
|
||
if len(new_path) % 2 == 0:
|
||
# Even length - should be matched edge
|
||
if self.matching.get(u) == v:
|
||
visited.add(v)
|
||
queue.append((v, new_path))
|
||
else:
|
||
# Odd length - should be unmatched edge
|
||
if self.matching.get(u) != v:
|
||
if not self.is_matched(v):
|
||
# Found augmenting path!
|
||
return new_path
|
||
|
||
visited.add(v)
|
||
queue.append((v, new_path))
|
||
|
||
return None
|
||
|
||
def augment_along_path(self, path: List[int]):
|
||
"""Flip matched/unmatched edges along path"""
|
||
for i in range(0, len(path) - 1, 2):
|
||
u, v = path[i], path[i + 1]
|
||
# Add edge to matching
|
||
self.matching[u] = v
|
||
self.matching[v] = u
|
||
|
||
def maximum_matching(self) -> Set[tuple[int, int]]:
|
||
"""
|
||
Compute maximum matching (simplified, no blossom contraction)
|
||
|
||
Full blossom algorithm handles odd cycles (blossoms)
|
||
"""
|
||
# Repeatedly find and augment along augmenting paths
|
||
while True:
|
||
path = self.find_augmenting_path_simple()
|
||
|
||
if path is None:
|
||
break # No more augmenting paths
|
||
|
||
self.augment_along_path(path)
|
||
|
||
# Convert to set of edges
|
||
matching_edges = set()
|
||
seen = set()
|
||
|
||
for u in self.matching:
|
||
if u not in seen:
|
||
v = self.matching[u]
|
||
matching_edges.add(tuple(sorted([u, v])))
|
||
seen.add(u)
|
||
seen.add(v)
|
||
|
||
return matching_edges
|
||
|
||
# Example usage
|
||
graph_match = AdjacencyList(6, directed=False)
|
||
graph_match.add_edge(0, 1)
|
||
graph_match.add_edge(0, 2)
|
||
graph_match.add_edge(1, 3)
|
||
graph_match.add_edge(2, 3)
|
||
graph_match.add_edge(3, 4)
|
||
graph_match.add_edge(4, 5)
|
||
|
||
blossom = BlossomMatching(graph_match)
|
||
matching = blossom.maximum_matching()
|
||
print(f"Maximum matching: {matching}")
|
||
print(f"Matching size: {len(matching)}")</code></pre>
|
||
<h3>3. Vertex Cover</h3>
|
||
<p><strong>Concept</strong>: Minimum set of vertices such that every edge has at least one endpoint in set</p>
|
||
<p><strong>NP-Complete</strong>: No polynomial exact algorithm (unless P=NP)</p>
|
||
<pre><code class="lang-python">def vertex_cover_approximation(graph: 'AdjacencyList') -> Set[int]:
|
||
"""
|
||
2-approximation for minimum vertex cover
|
||
|
||
Algorithm: Maximal matching gives 2-approximation
|
||
(Include both endpoints of each matching edge)
|
||
|
||
Time: O(E)
|
||
Approximation ratio: 2
|
||
"""
|
||
if graph.directed:
|
||
raise ValueError("Vertex cover for undirected graphs")
|
||
|
||
cover = set()
|
||
remaining_edges = set(graph.all_edges())
|
||
|
||
while remaining_edges:
|
||
# Pick arbitrary edge
|
||
u, v, _ = remaining_edges.pop()
|
||
|
||
# Add both endpoints to cover
|
||
cover.add(u)
|
||
cover.add(v)
|
||
|
||
# Remove all edges incident to u or v
|
||
remaining_edges = {(a, b, w) for a, b, w in remaining_edges
|
||
if a != u and a != v and b != u and b != v}
|
||
|
||
return cover
|
||
|
||
def is_vertex_cover(graph: 'AdjacencyList', cover: Set[int]) -> bool:
|
||
"""Verify that cover is valid"""
|
||
for u in range(graph.num_vertices):
|
||
for v in graph.neighbors(u):
|
||
if u not in cover and v not in cover:
|
||
return False
|
||
return True
|
||
|
||
# Example
|
||
graph_vc = AdjacencyList(5, directed=False)
|
||
graph_vc.add_edge(0, 1)
|
||
graph_vc.add_edge(0, 2)
|
||
graph_vc.add_edge(1, 3)
|
||
graph_vc.add_edge(2, 3)
|
||
graph_vc.add_edge(3, 4)
|
||
|
||
cover = vertex_cover_approximation(graph_vc)
|
||
print(f"Vertex cover (size {len(cover)}): {cover}")
|
||
print(f"Valid: {is_vertex_cover(graph_vc, cover)}")</code></pre>
|
||
<h3>4. Clique Finding</h3>
|
||
<p><strong>Concept</strong>: Find maximum complete subgraph (all vertices connected)</p>
|
||
<p><strong>NP-Complete</strong>: Finding maximum clique is NP-hard</p>
|
||
<pre><code class="lang-python">def find_all_cliques_bron_kerbosch(graph: 'AdjacencyList'
|
||
) -> List[Set[int]]:
|
||
"""
|
||
Bron-Kerbosch algorithm for finding all maximal cliques
|
||
|
||
Time: O(3^(V/3)) worst case (exponential)
|
||
"""
|
||
cliques = []
|
||
|
||
def bronker bosch(R: Set[int], P: Set[int], X: Set[int]):
|
||
"""
|
||
R = current clique being built
|
||
P = candidates for extension
|
||
X = already processed vertices
|
||
"""
|
||
if not P and not X:
|
||
# R is maximal clique
|
||
cliques.append(R.copy())
|
||
return
|
||
|
||
# Choose pivot to minimize iterations
|
||
pivot = max(P | X, key=lambda v: len(set(graph.neighbors(v)) & P),
|
||
default=None)
|
||
|
||
if pivot is None:
|
||
return
|
||
|
||
pivot_neighbors = set(graph.neighbors(pivot))
|
||
|
||
# Process vertices not adjacent to pivot
|
||
for v in list(P - pivot_neighbors):
|
||
v_neighbors = set(graph.neighbors(v))
|
||
|
||
bronkerbosch(
|
||
R | {v},
|
||
P & v_neighbors,
|
||
X & v_neighbors
|
||
)
|
||
|
||
P.remove(v)
|
||
X.add(v)
|
||
|
||
# Initialize: R = empty, P = all vertices, X = empty
|
||
all_vertices = set(range(graph.num_vertices))
|
||
bronkerbosch(set(), all_vertices, set())
|
||
|
||
return cliques
|
||
|
||
def maximum_clique(graph: 'AdjacencyList') -> Set[int]:
|
||
"""Find maximum clique (largest complete subgraph)"""
|
||
all_cliques = find_all_cliques_bron_kerbosch(graph)
|
||
|
||
if not all_cliques:
|
||
return set()
|
||
|
||
return max(all_cliques, key=len)
|
||
|
||
# Example
|
||
graph_clique = AdjacencyList(5, directed=False)
|
||
graph_clique.add_edge(0, 1)
|
||
graph_clique.add_edge(0, 2)
|
||
graph_clique.add_edge(0, 3)
|
||
graph_clique.add_edge(1, 2)
|
||
graph_clique.add_edge(1, 3)
|
||
graph_clique.add_edge(2, 3)
|
||
graph_clique.add_edge(3, 4)
|
||
|
||
max_clique = maximum_clique(graph_clique)
|
||
print(f"Maximum clique: {max_clique}") # {0, 1, 2, 3}</code></pre>
|
||
<hr>
|
||
<h2>2024 Research Advances</h2>
|
||
<h3>Graph Neural Networks Integration</h3>
|
||
<pre><code class="lang-python">class GraphAttentionNetwork:
|
||
"""
|
||
Graph Attention Network (GAT) integration
|
||
|
||
2024 advances: Multi-head attention, edge features, heterogeneous graphs
|
||
"""
|
||
|
||
def __init__(self, num_features: int, num_heads: int = 4):
|
||
self.num_features = num_features
|
||
self.num_heads = num_heads
|
||
# Would integrate with PyTorch/TensorFlow in practice
|
||
|
||
def attention_coefficients(self, node_features, neighbors):
|
||
"""
|
||
Compute attention coefficients using self-attention
|
||
|
||
2024 approach: Learned edge weights for graph algorithms
|
||
"""
|
||
# Simplified - actual implementation uses neural networks
|
||
pass
|
||
|
||
def aggregate_features(self, graph, node_features):
|
||
"""
|
||
Aggregate neighbor features using attention
|
||
|
||
Applications:
|
||
- Node classification
|
||
- Link prediction
|
||
- Graph classification
|
||
"""
|
||
pass</code></pre>
|
||
<h3>Quantum-Inspired Algorithms (2024)</h3>
|
||
<pre><code class="lang-python">def quantum_inspired_max_cut(graph: 'WeightedGraph') -> tuple[Set[int], Set[int]]:
|
||
"""
|
||
Quantum-inspired approximation for maximum cut
|
||
|
||
Based on 2024 research: Classical simulation of quantum algorithms
|
||
Achieves better approximation ratios than classical methods
|
||
|
||
Max cut: Partition vertices to maximize edges between partitions
|
||
"""
|
||
# Simplified version - full implementation uses tensor networks
|
||
|
||
import random
|
||
|
||
# Initialize random partition
|
||
S = set(random.sample(range(graph.num_vertices),
|
||
graph.num_vertices // 2))
|
||
T = set(range(graph.num_vertices)) - S
|
||
|
||
improved = True
|
||
|
||
while improved:
|
||
improved = False
|
||
|
||
# Try moving each vertex
|
||
for v in range(graph.num_vertices):
|
||
current_cut = compute_cut_value(graph, S, T)
|
||
|
||
# Move v to other partition
|
||
if v in S:
|
||
S.remove(v)
|
||
T.add(v)
|
||
else:
|
||
T.remove(v)
|
||
S.add(v)
|
||
|
||
new_cut = compute_cut_value(graph, S, T)
|
||
|
||
if new_cut > current_cut:
|
||
improved = True
|
||
else:
|
||
# Move back
|
||
if v in S:
|
||
S.remove(v)
|
||
T.add(v)
|
||
else:
|
||
T.remove(v)
|
||
S.add(v)
|
||
|
||
return S, T
|
||
|
||
def compute_cut_value(graph: 'WeightedGraph', S: Set[int], T: Set[int]) -> float:
|
||
"""Compute total weight of edges crossing cut"""
|
||
cut_value = 0.0
|
||
|
||
for u in S:
|
||
for edge in graph.adj[u]:
|
||
v = edge.dest
|
||
if v in T:
|
||
cut_value += edge.weight
|
||
|
||
return cut_value</code></pre>
|
||
<hr>
|
||
<h2>Patterns</h2>
|
||
<h3>Pattern 1: NP-Hard Problem Strategies</h3>
|
||
<pre><code class="lang-python">class NPHardGraphProblems:
|
||
"""Strategies for NP-hard graph problems"""
|
||
|
||
@staticmethod
|
||
def choose_approach(problem: str, graph_size: int) -> str:
|
||
"""Select approach based on problem and size"""
|
||
|
||
if graph_size <= 20:
|
||
return "exact_exponential" # Brute force, backtracking
|
||
|
||
elif graph_size <= 100:
|
||
return "exact_bounded" # Branch and bound, ILP
|
||
|
||
elif graph_size <= 1000:
|
||
return "approximation" # Polynomial approximations
|
||
|
||
else:
|
||
return "heuristic" # Fast heuristics, local search
|
||
|
||
@staticmethod
|
||
def vertex_cover_strategy(graph):
|
||
"""Example: Choosing vertex cover approach"""
|
||
n = graph.num_vertices
|
||
|
||
if n <= 20:
|
||
return "exact_backtracking"
|
||
else:
|
||
return vertex_cover_approximation(graph)</code></pre>
|
||
<hr>
|
||
<h2>Quick Reference</h2>
|
||
<h3>Complexity Classes</h3>
|
||
<p>| Problem | Complexity | Best Algorithm | |---------|-----------|----------------| | Graph Coloring | NP-Complete | Greedy (Δ+1 colors) | | Chromatic Number | NP-Complete | Bounds + backtracking | | Maximum Matching | P | Blossom (O(V²E)) | | Vertex Cover | NP-Complete | 2-approximation | | Maximum Clique | NP-Complete | Bron-Kerbosch | | Independent Set | NP-Complete | Complement of vertex cover |</p>
|
||
<h3>Approximation Ratios</h3>
|
||
<p>| Problem | Algorithm | Ratio | |---------|-----------|-------| | Vertex Cover | Maximal matching | 2 | | Graph Coloring | Greedy | Δ + 1 | | Max Cut | Randomized | 0.5 | | TSP (metric) | Christofides | 1.5 |</p>
|
||
<hr>
|
||
<h2>Anti-Patterns</h2>
|
||
<h3>❌ Using Exponential Algorithms on Large Graphs</h3>
|
||
<pre><code class="lang-python"># WRONG: Bron-Kerbosch on large graph
|
||
large_graph = AdjacencyList(1000)
|
||
# ... add edges ...
|
||
cliques = find_all_cliques_bron_kerbosch(large_graph) # May never finish!
|
||
|
||
# CORRECT: Use heuristics or approximate for large graphs
|
||
if graph.num_vertices > 100:
|
||
# Use greedy or sampling-based approach
|
||
pass</code></pre>
|
||
<h3>❌ Assuming Optimal Solution Exists Quickly</h3>
|
||
<pre><code class="lang-python"># WRONG: Expect exact minimum vertex cover
|
||
cover = minimum_vertex_cover_exact(graph) # NP-hard!
|
||
|
||
# CORRECT: Use approximation with known bounds
|
||
cover = vertex_cover_approximation(graph) # 2-approximation</code></pre>
|
||
<hr>
|
||
<h2>Related Skills</h2>
|
||
<p><strong>Next Steps</strong>:</p>
|
||
<ul><li><code>graph-applications.md</code> → Real-world applications of these algorithms</li></ul>
|
||
<p><strong>Foundations</strong>:</p>
|
||
<ul><li><code>graph-theory-fundamentals.md</code> → Basic graph concepts</li><li><code>graph-traversal-algorithms.md</code> → BFS and DFS</li><li><code>network-flow-algorithms.md</code> → Maximum matching via flow</li></ul>
|
||
<hr>
|
||
<h2>Summary</h2>
|
||
<p>Advanced graph algorithms tackle complex combinatorial problems:</p>
|
||
<ul><li><strong>Graph Coloring</strong>: NP-complete, greedy gives Δ+1 approximation</li><li><strong>Maximum Matching</strong>: Polynomial via Edmonds' blossom algorithm</li><li><strong>Vertex Cover</strong>: NP-complete, 2-approximation via maximal matching</li><li><strong>Clique Finding</strong>: NP-complete, Bron-Kerbosch finds all maximal cliques</li><li><strong>2024 Advances</strong>: GNNs, quantum-inspired algorithms</li></ul>
|
||
<p><strong>Key takeaways</strong>:</p>
|
||
<ol><li>Many graph problems are NP-complete - use approximations</li><li>Greedy coloring uses at most Δ+1 colors</li><li>Blossom algorithm solves maximum matching in polynomial time</li><li>Vertex cover has 2-approximation, clique finding is exponential</li><li>Recent advances use machine learning and quantum-inspired methods</li></ol>
|
||
<p><strong>Next</strong>: Move to <code>graph-applications.md</code> for real-world use cases.</p>
|
||
<footer>
|
||
<div class="fmap">
|
||
<div><b>Build</b>
|
||
<a href="https://hanzo.app">hanzo.app</a> app builder
|
||
<a href="https://hanzo.codes">hanzo.codes</a> code with an agent
|
||
<a href="https://hanzoskills.com">hanzoskills.com</a> what an agent reads</div>
|
||
<div><b>Run</b>
|
||
<a href="https://console.hanzo.ai">console.hanzo.ai</a> cloud console
|
||
<a href="https://api.hanzo.ai">api.hanzo.ai</a> the API</div>
|
||
<div><b>Account</b>
|
||
<a href="https://hanzo.id">hanzo.id</a> sign in
|
||
<a href="https://pay.hanzo.ai">pay.hanzo.ai</a> top up
|
||
<a href="https://billing.hanzo.ai">billing.hanzo.ai</a> invoices and usage</div>
|
||
<div><b>Company</b>
|
||
<a href="https://hanzo.ai">hanzo.ai</a> canonical
|
||
<a href="https://hanzo.ventures">hanzo.ventures</a> ventures</div>
|
||
</div>
|
||
<div class="fend"><a href="/advanced-graph-algorithms.md">This page as plain text</a> · <a href="/llms.txt">Index for agents</a></div>
|
||
</footer>
|
||
</div></body></html> |