# path_analysis URL: /api/analysis/path_analysis/ Section: analysis -------------------------------------------------------------------------------- path_analysis - Bengal window.BENGAL_THEME_DEFAULTS = { appearance: 'dark', palette: 'snow-lynx' }; // Progressive Enhancement System Configuration window.Bengal = window.Bengal || {}; window.Bengal.enhanceBaseUrl = '/bengal/assets/js/enhancements'; window.Bengal.watchDom = true; window.Bengal.debug = false; (function () { try { var defaults = window.BENGAL_THEME_DEFAULTS || { appearance: 'system', palette: '' }; var defaultAppearance = defaults.appearance; if (defaultAppearance === 'system') { defaultAppearance = (window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches) ? 'dark' : 'light'; } var storedTheme = localStorage.getItem('bengal-theme'); var storedPalette = localStorage.getItem('bengal-palette'); var theme = storedTheme ? (storedTheme === 'system' ? defaultAppearance : storedTheme) : defaultAppearance; var palette = storedPalette ?? defaults.palette; document.documentElement.setAttribute('data-theme', theme); if (palette) { document.documentElement.setAttribute('data-palette', palette); } } catch (e) { document.documentElement.setAttribute('data-theme', 'light'); } })(); Skip to main content Magnifying Glass ESC Recent Clear Magnifying Glass No results for "" Try different keywords or check your spelling Start typing to search... ↑↓ Navigate ↵ Open ESC Close Powered by Lunr ᓚᘏᗢ Documentation Info About Arrow Clockwise Get Started Note Tutorials File Text Content Palette Theming Settings Building Starburst Extending Bookmark Reference Learning Tracks Releases Dev GitHub API Reference bengal CLI Magnifying Glass Search ⌘K Palette Appearance Chevron Down Mode Monitor System Sun Light Moon Dark Palette Snow Lynx Brown Bengal Silver Bengal Charcoal Bengal Blue Bengal List ᓚᘏᗢ Magnifying Glass Search X Close Documentation Info About Arrow Clockwise Get Started Note Tutorials File Text Content Palette Theming Settings Building Starburst Extending Bookmark Reference Learning Tracks Releases Dev GitHub API Reference bengal CLI Palette Appearance Chevron Down Mode Monitor System Sun Light Moon Dark Palette Snow Lynx Brown Bengal Silver Bengal Charcoal Bengal Blue Bengal API Reference __main__ bengal Caret Right Folder Analysis community_detection graph_analysis graph_reporting graph_visualizer knowledge_graph link_suggestions link_types page_rank path_analysis performance_advisor results Caret Right Folder Assets manifest pipeline Caret Right Folder Autodoc base config docstring_parser utils virtual_orchestrator Caret Right Folder Extractors cli openapi python Caret Right Folder Models cli common openapi python Caret Right Folder Cache asset_dependency_map cache_store cacheable compression dependency_tracker page_discovery_cache query_index query_index_registry taxonomy_index utils Caret Right Folder Build Cache autodoc_tracking core file_tracking fingerprint parsed_content_cache rendered_output_cache taxonomy_index_mixin validation_cache Caret Right Folder Indexes author_index category_index date_range_index section_index Caret Right Folder Cli __main__ base site_templates utils Caret Right Folder Commands assets build clean collections config debug explain fix health init perf project serve site skeleton sources theme utils validate Caret Right Folder Graph __main__ bridges communities orphans pagerank report suggest Caret Right Folder New config presets scaffolds site wizard Caret Right Folder Helpers cli_app_loader cli_output config_validation error_handling menu_config metadata progress site_loader traceback validation Caret Right Folder Skeleton hydrator schema Caret Right Folder Templates base registry Caret Right Folder Blog template Caret Right Folder Changelog template Caret Right Folder Default template Caret Right Folder Docs template Caret Right Folder Landing template Caret Right Folder Portfolio template Caret Right Folder Resume template Caret Right Folder Collections errors loader schemas validator Caret Right Folder Config defaults deprecation directory_loader env_overrides environment feature_mappings hash loader merge origin_tracker validators Caret Right Folder Content Layer entry loaders manager source Caret Right Folder Sources github local notion rest Caret Right Folder Content Types base registry strategies Caret Right Folder Core build_context cascade_engine menu section theme Caret Right Folder Asset asset_core css_transforms Caret Right Folder Page computed content metadata navigation operations page_core proxy relationships utils Caret Right Folder Site core data discovery factories page_caches properties section_registry theme Caret Right Folder Debug base config_inspector content_migrator delta_analyzer dependency_visualizer explainer incremental_debugger models reporter shortcode_sandbox Caret Right Folder Discovery asset_discovery content_discovery Caret Right Folder Fonts downloader generator Caret Right Folder Health autofix base health_check report Caret Right Folder Linkcheck async_checker ignore_policy internal_checker models orchestrator Caret Right Folder Validators anchors assets cache config connectivity cross_ref fonts links menu navigation output performance rendering rss sitemap taxonomy tracks Caret Right Folder Directives analysis checkers constants Caret Right Folder Orchestration asset content full_to_incremental incremental menu postprocess related_posts render section static streaming taxonomy Caret Right Folder Postprocess html_output redirects rss sitemap special_pages Caret Right Folder Output Formats index_generator json_generator llm_generator lunr_index_generator txt_generator utils Caret Right Folder Rendering api_doc_enhancer asset_extractor errors jinja_utils link_transformer link_validator pygments_cache renderer template_context template_profiler validator Caret Right Folder Parsers base factory mistune native_html pygments_patch python_markdown Caret Right Folder Pipeline core output thread_local toc transforms Caret Right Folder Plugins badges cross_references inline_icon term variable_substitution Caret Right Folder Directives _icons admonitions badge base button cache cards checklist code_tabs container contracts data_table dropdown embed errors example_label fenced figure glossary icon include list_table literalinclude marimo navigation options rubric steps tabs target term terminal tokens utils validator video Caret Right Folder Template Engine asset_url core environment manifest menu url_helpers Caret Right Folder Template Functions advanced_collections advanced_strings autodoc collections content crossref data dates debug files get_page i18n icons images math_functions navigation pagination_helpers seo strings tables taxonomies theme urls Caret Right Folder Server build_handler component_preview constants dev_server live_reload pid_manager reload_controller request_handler request_logger resource_manager utils Caret Right Folder Services validation Caret Right Folder Themes config Caret Right Folder Utils atomic_write autodoc build_context build_stats build_summary cli_output css_minifier dates dotdict error_handlers file_io file_lock hashing incremental_constants js_bundler live_progress logger metadata observability page_initializer pagination path_resolver paths performance_collector performance_report profile progress retry rich_console sections swizzle text theme_registry theme_resolution thread_local traceback_config traceback_renderer url_normalization url_strategy API Reference Analysis ᗢ Caret Down Link Copy URL External Open LLM text Copy Copy LLM text Share with AI Ask Claude Ask ChatGPT Ask Gemini Ask Copilot Module analysis.path_analysis Path Analysis for Bengal SSG. Implements algorithms for understanding navigation patterns and page accessibility: Shortest paths between pages (BFS-based) Betweenness centrality (identifies bridge pages) Closeness centrality (measures accessibility) These metrics help optimize navigation structure and identify critical pages. For large sites (>500 pages), pivot-based approximation is used automatically to maintain O(k*N) complexity instead of O(N²). References: Brandes, U. (2001). A faster algorithm for betweenness centrality. Journal of Mathematical Sociology. Bader, D. A., et al. (2007). Approximating betweenness centrality. Algorithms and Models for the Web-Graph. View source 3 Classes 1 Function Classes PathAnalysisResults dataclass Results from path analysis and centrality computations. Contains centrality metrics that identify … 4 Caret Right Results from path analysis and centrality computations. Contains centrality metrics that identify important pages in the site's link structure. High betweenness indicates bridge pages, high closeness indicates easily accessible pages. Attributes Name Type Description betweenness_centrality dict[Page, float] Map of pages to betweenness scores (0.0-1.0) closeness_centrality dict[Page, float] Map of pages to closeness scores (0.0-1.0) avg_path_length float Average shortest path length between all page pairs diameter int Network diameter (longest shortest path) is_approximate bool True if approximation was used (for large sites) pivots_used int Number of pivot nodes used (if approximate) Methods 4 get_top_bridges Get pages with highest betweenness centrality (bridge pages). 1 list[tuple[Page, float]] Caret Right def get_top_bridges(self, limit: int = 20) -> list[tuple[Page, float]] Get pages with highest betweenness centrality (bridge pages). Parameters 1 limit int Number of pages to return Returns list[tuple[Page, float]] — List of (page, centrality) tuples sorted by centrality descending get_most_accessible Get most accessible pages (highest closeness centrality). 1 list[tuple[Page, float]] Caret Right def get_most_accessible(self, limit: int = 20) -> list[tuple[Page, float]] Get most accessible pages (highest closeness centrality). Parameters 1 limit int Number of pages to return Returns list[tuple[Page, float]] — List of (page, centrality) tuples sorted by centrality descending get_betweenness Get betweenness centrality for specific page. 1 float Caret Right def get_betweenness(self, page: Page) -> float Get betweenness centrality for specific page. Parameters 1 page Page Returns float get_closeness Get closeness centrality for specific page. 1 float Caret Right def get_closeness(self, page: Page) -> float Get closeness centrality for specific page. Parameters 1 page Page Returns float PathSearchResult dataclass Result from find_all_paths including metadata about the search. 0 Caret Right Result from find_all_paths including metadata about the search. Attributes Name Type Description paths list[list[Page]] List of paths found (each path is a list of pages) complete bool True if search completed, False if terminated early termination_reason str | None Reason for early termination (if any) PathAnalyzer Analyze navigation paths and page accessibility. Computes centrality metrics to identify: - Bridge… 8 Caret Right Analyze navigation paths and page accessibility. Computes centrality metrics to identify: Bridge pages (high betweenness): Pages that connect different parts of the site Accessible pages (high closeness): Pages that are easy to reach from anywhere Navigation bottlenecks: Critical pages for site navigation For large sites (>500 pages by default), uses pivot-based approximation to achieve O(k*N) complexity instead of O(N²). This provides ~100x speedup for 10k page sites while maintaining accurate relative rankings. Methods 4 find_shortest_path Find shortest path between two pages using BFS. 2 list[Page] | None Caret Right def find_shortest_path(self, source: Page, target: Page) -> list[Page] | None Find shortest path between two pages using BFS. Parameters 2 source Page Starting page target Page Destination page Returns list[Page] | None — List of pages representing the path, or None if no path exists analyze Compute path-based centrality metrics. Computes: - Betweenness centrality: How… 1 PathAnalysisResults Caret Right def analyze(self, progress_callback: ProgressCallback | None = None) -> PathAnalysisResults Compute path-based centrality metrics. Computes: Betweenness centrality: How often a page appears on shortest paths Closeness centrality: How close a page is to all other pages Network diameter: Longest shortest path Average path length For large sites, automatically uses pivot-based approximation for O(k*N) complexity instead of O(N²). Parameters 1 progress_callback ProgressCallback | None Optional callback for progress updates. Called as callback(current, total, phase) where phase is "betweenness" or "closeness". Returns PathAnalysisResults — PathAnalysisResults with all metrics find_all_paths Find all simple paths between two pages with safety limits. This operation can… 5 PathSearchResult Caret Right def find_all_paths(self, source: Page, target: Page, max_length: int = 10, max_paths: int = 1000, timeout_seconds: float | None = 30.0) -> PathSearchResult Find all simple paths between two pages with safety limits. This operation can be expensive for highly connected graphs. Safety limits prevent runaway computation: max_length: Maximum path length to consider max_paths: Stop after finding this many paths timeout_seconds: Stop after this many seconds Parameters 5 source Page Starting page target Page Destination page max_length int Maximum path length to search (default: 10) max_paths int Maximum number of paths to find (default: 1000) timeout_seconds float | None Maximum time in seconds (default: 30.0, None for no limit) Returns PathSearchResult — PathSearchResult with paths found and completion status find_all_paths_simple Find all simple paths between two pages (legacy API). This is the original API… 3 list[list[Page]] Caret Right def find_all_paths_simple(self, source: Page, target: Page, max_length: int = 10) -> list[list[Page]] Find all simple paths between two pages (legacy API). This is the original API preserved for backward compatibility. For new code, prefer find_all_paths() which includes safety limits. Parameters 3 source Page Starting page target Page Destination page max_length int Maximum path length to search Returns list[list[Page]] — List of paths (each path is a list of pages) Internal Methods 4 Caret Right __init__ Initialize path analyzer. 4 None Caret Right def __init__(self, graph: KnowledgeGraph, k_pivots: int = DEFAULT_K_PIVOTS, seed: int = DEFAULT_SEED, auto_approximate_threshold: int = DEFAULT_AUTO_THRESHOLD) Initialize path analyzer. Parameters 4 graph KnowledgeGraph KnowledgeGraph with page connections k_pivots int Number of pivot nodes to use for approximation (default: 100) seed int Random seed for deterministic pivot selection (default: 42) auto_approximate_threshold int Use exact algorithm if page count <= this (default: 500) _compute_betweenness_centrality Compute betweenness centrality using Brandes' algorithm. Betweenness measures … 3 dict[Page, float] Caret Right def _compute_betweenness_centrality(self, pages: list[Page], use_approximate: bool, progress_callback: ProgressCallback | None = None) -> dict[Page, float] Compute betweenness centrality using Brandes' algorithm. Betweenness measures how often a page appears on shortest paths between other pages. High betweenness indicates a "bridge" page. For large sites, uses pivot-based approximation: only compute from k randomly selected source nodes and scale results. Parameters 3 pages list[Page] List of pages to analyze use_approximate bool If True, use pivot-based approximation progress_callback ProgressCallback | None Optional progress callback Returns dict[Page, float] — Dictionary mapping pages to betweenness centrality scores _compute_closeness_centrality Compute closeness centrality and network metrics. Closeness measures how close… 3 tuple[dict[Page, fl… Caret Right def _compute_closeness_centrality(self, pages: list[Page], use_approximate: bool, progress_callback: ProgressCallback | None = None) -> tuple[dict[Page, float], float, int] Compute closeness centrality and network metrics. Closeness measures how close a page is to all other pages. Higher closeness = more accessible. For large sites, uses pivot-based approximation: only compute distances from k randomly selected source nodes. Parameters 3 pages list[Page] List of pages to analyze use_approximate bool If True, use pivot-based approximation progress_callback ProgressCallback | None Optional progress callback Returns tuple[dict[Page, float], float, int] — Tuple of (closeness_dict, avg_path_length, diameter) _bfs_distances Compute shortest path distances from source to all other pages. 2 dict[Page, int] Caret Right def _bfs_distances(self, source: Page, pages: list[Page]) -> dict[Page, int] Compute shortest path distances from source to all other pages. Parameters 2 source Page pages list[Page] Returns dict[Page, int] Functions analyze_paths Convenience function for path analysis. 5 PathAnalysisResults Caret Right def analyze_paths(graph: KnowledgeGraph, k_pivots: int = PathAnalyzer.DEFAULT_K_PIVOTS, seed: int = PathAnalyzer.DEFAULT_SEED, auto_approximate_threshold: int = PathAnalyzer.DEFAULT_AUTO_THRESHOLD, progress_callback: ProgressCallback | None = None) -> PathAnalysisResults Convenience function for path analysis. Parameters 5 Name Type Default Description graph KnowledgeGraph — KnowledgeGraph with page connections k_pivots int PathAnalyzer.DEFAULT_K_PIVOTS Number of pivot nodes for approximation (default: 100) seed int PathAnalyzer.DEFAULT_SEED Random seed for deterministic results (default: 42) auto_approximate_threshold int PathAnalyzer.DEFAULT_AUTO_THRESHOLD Use exact if pages <= this (default: 500) progress_callback ProgressCallback | None None Optional progress callback Returns PathAnalysisResults — PathAnalysisResults with centrality metrics ← Previous page_rank Next → performance_advisor List © 2025 Bengal ᓚᘏᗢ window.BENGAL_LAZY_ASSETS = { tabulator: '/bengal/assets/js/tabulator.min.js', dataTable: '/bengal/assets/js/data-table.js', mermaidToolbar: '/bengal/assets/js/mermaid-toolbar.9de5abba.js', mermaidTheme: '/bengal/assets/js/mermaid-theme.344822c5.js', graphMinimap: '/bengal/assets/js/graph-minimap.cc7e42e3.js', graphContextual: '/bengal/assets/js/graph-contextual.440e59c6.js' }; window.BENGAL_ICONS = { close: '/bengal/assets/icons/close.911d4fe1.svg', enlarge: '/bengal/assets/icons/enlarge.652035e5.svg', copy: '/bengal/assets/icons/copy.3d56e945.svg', 'download-svg': '/bengal/assets/icons/download.04f07e1b.svg', 'download-png': '/bengal/assets/icons/image.c34dfd40.svg', 'zoom-in': '/bengal/assets/icons/zoom-in.237b4a83.svg', 'zoom-out': '/bengal/assets/icons/zoom-out.38857c77.svg', reset: '/bengal/assets/icons/reset.d26dba29.svg' }; Arrow Up X -------------------------------------------------------------------------------- Metadata: - Author: lbliii - Word Count: 2243 - Reading Time: 11 minutes