Default
Default
In-browser search
Settings
Choreo turns every diagram into a graph, then runs classic graph algorithms on it to answer practical questions: "Will this deployment order work?", "What breaks if this service fails?", "Where are the cycles?", and so on.
This guide catalogs the analysis functions in each diagram module, what question they answer, and the underlying algorithm they use. The implementations live in lib/choreo/analysis.ex, lib/choreo/internal.ex, the lib/choreo/*/analysis.ex modules, and lib/choreo/analysis/tracing.ex.
Most functions build on the yog_ex
Supported diagram types Core / cross-cutting analysis These functions operate on the general Choreo
Function Purpose Algorithm used mst/2Cheapest way to connect all services MST — Kruskal (default), Prim, or Borůvka on an undirected simple graphtopological_sort/1Deployment or execution order Topological sort via Yog.Traversal.topological_sort/1cyclic?/1Detect feedback loops Cycle detection via Yog.cyclic?/1dag?/1Check if the graph is acyclic Acyclicity check via Yog.acyclic?/1strongly_connected_components/1Find mutually dependent services Strongly Connected Components (SCC) via Yog.Connectivitysingle_points_of_failure/1Find articulation points and bridge edges Tarjan's articulation-point/bridge algorithm on an undirected viewcut_vertices/1Nodes whose removal disconnects the graph Tarjan's articulation points impact_analysis/2What breaks if a node fails BFS on the transposed graph shortest_path/4Cheapest/fastest route between services Dijkstra / shortest path with semiring support (cost, latency, custom metrics)path/4Domain-specific pathfinding Dijkstra / widest path with measures :shortest, :latency, :throughput, :risk, :weightedcentrality/2Most critical or coupled nodes Degree / betweenness / closeness / PageRank centrality via Yog.Centralitycore_numbers/1K-core decomposition K-core decomposition via Yog.Connectivity.core_numbers/1reduce_transitive/1Remove redundant edges while preserving reachability Transitive reduction isolated_nodes/1Find orphan services In-degree + out-degree check heatmap/2Color nodes by centrality or score Centrality → min-max normalization → color scale validate/1Structural health check Composite: isolated nodes, SPOF, cycles, bridges
Function Purpose Algorithm used impact_analysis/2Nodes transitively impacted via trace edges BFS on the transposed trace-only graph trace_path/3Shortest trace path between two nodes Dijkstra on the trace-only graphanalyze/3Nested cross-domain analysis along a trace path Path reconstruction + domain metadata classification
Choreo.Internal — shared graph primitivesFunction Purpose Algorithm used bfs_reachable/2Reachable nodes from seed nodes Breadth-First Search (BFS) transitive_reduction/1Redundant edges implied by longer paths BFS reachability from alternate successorscompute_dp/3Longest-path DP table Dynamic programming over a topological order find_best_end_path/2Best predecessor chain Linear scan of the DP table reconstruct_path/2Reconstruct a path from DP predecessors Backtracking dfs_cycles/1All elementary cycles in a multigraph Depth-First Search (DFS) with recursion-stack trackingunsatisfied_contract/3Missing functions for a contract Set difference on function name/arity
Diagram-specific analysis Function Purpose Algorithm used isolated_nodes/1Elements with no relationships In-degree + out-degree on a simple graph missing_parents/1Containers/components without parents Metadata filter missing_descriptions/1Nodes lacking descriptions Metadata filter missing_technology/1Containers/components without technology labels Metadata filter missing_relationship_labels/1Relationships lacking labels Edge metadata filter parents_without_relationships/1Parent nodes with children but no edges Degree + parent metadata check validate/1Full C4 model validation Composite rule check
Function Purpose Algorithm used validate/1Security audit (internet-to-private, DB placement, LB placement, etc.) Rule-based set membership checks on node/edge metadata warnings/1Audit warnings Rule-based set membership checks
Function Purpose Algorithm used reachable_states/1States reachable from the initial state BFS dead_states/1States with no path to a final state Reverse BFS from final stateslivelock_states/1Reachable non-accepting loop states Intersection of reachable/dead + BFS self-reachability accepts?/2Simulate input string acceptance Deterministic walk shortest_accepting_path/1Minimum input to reach acceptance BFS accepted_strings/2All accepted strings up to length N BFS level-order expansion alphabet/1Distinct input symbols Set construction complete?/1Whether every state handles every symbol Set subset check generate_test_cases/2Input sequences for state/transition coverage BFS shortest paths to all statesequivalent?/2Check if two FSMs accept the same language Product automaton BFS minimize/1Minimize a DFA Moore's partition refinement violates_invariant?/2Forbidden state sequence exists Edge existence check validate/1Structural FSM validation Composite checks
Function Purpose Algorithm used sources/1 / sinks/1Identify source/sink nodes Node type filter cyclic?/1Feedback-loop detection Cycle detection on the normal-edge subgraph topological_sort/1Stage execution order Topological sort orphan_nodes/1Nodes unreachable from any source BFS from sources + set differencedead_ends/1Nodes that cannot reach any sink BFS on the transposed graph from sinksfan_hubs/1High in-degree + out-degree stages Degree threshold longest_path/1Critical path (longest source→sink chain) DP over topological order capacity_bottlenecks/1Stages where in_rate > capacity Throughput simulation via topological propagationsimulate/1Steady-state throughput simulation Topological-order traversal + rate summationbackpressure_points/1Nodes with inbound flow above threshold Simulation result filter upstream_lineage/1 / downstream_impact/1Ancestors/descendants BFS (transposed for upstream)upstream_sources/1 / downstream_sinks/1Source/sink subsets of lineage BFS + set intersection heatmap/2Throughput heatmap Simulation → color scale validate/1Pipeline structural validation Composite checks
Function Purpose Algorithm used cyclic_dependencies/1All circular dependency chains SCC + DFS cycle extractionaffected_by/2Components that break if the target changes BFS on the transposed graph depends_on/2Components the target depends on BFS layer_violations/2Edges violating layered architecture Edge + layer-index comparison centrality/2Most coupled components Degree centrality (in + out) leaves/1 / roots/1Nodes with no dependents / no dependencies In-degree / out-degree filter transitive_reduction/1Redundant explicit dependencies Transitive reduction instability/1Instability metric per component Ce / (Ca + Ce)isolated_subsystems/1Disconnected component groups Weakly connected components longest_dependency_chain/1Deepest dependency chain DP over topological order validate/1Dependency graph validation Composite checks
Function Purpose Algorithm used decide/2Evaluate tree against feature values Tree walk paths/1All root-to-leaf paths DFS enumeration paths_with_conditions/1Paths with branch conditions DFS enumeration depth/1 / breadth/1Tree depth / leaf count Recursive traversal / count feature_importance/1Feature split frequency Group-by + count reachable_outcomes/1Reachable outcome classes BFS orphan_nodes/1Unreachable declared nodes BFS + set differencerules/1Extract IF-THEN rules Path-to-conditions mapping generate_test_cases/1Feature maps covering every leaf Path conditions missing_branches/2Expected feature values not covered Set difference inconsistent_paths/1Logically impossible paths Path condition grouping prune_redundant/1Remove redundant decision nodes Post-order tree traversal validate/1Tree structural validation Composite checks
Function Purpose Algorithm used stride_threats/2Generate STRIDE threats Rule-based generation by element type threat_summary/1Threat distribution by category/severity Aggregation risk_score/2Total weighted risk score Weighted sum by severity cross_boundary_flows/1Data flows crossing trust boundaries Boundary comparison exposed_data_stores/1Data stores reachable from external entities BFS from external entitiesattack_paths/1Paths from externals to data stores DFS path enumeration high_risk_processes/1Low-trust processes accessing sensitive stores BFS + risk/trust checksunencrypted_boundary_flows/1Unencrypted cross-boundary flows Edge metadata + boundary check heatmap/2Threat density heatmap Threat count → color scale validate/1Threat model validation Composite checks
Function Purpose Algorithm used reachable_tasks/1Tasks reachable from start nodes BFS orphan_tasks/1Tasks not reachable from starts BFS + set differencedead_ends/1Tasks that cannot reach an end node BFS on the transposed graph from endscritical_path/1Longest latency path start→end DP over topological order parallelizable_tasks/1Tasks that can run in parallel Topological levels compensable_tasks/1Tasks with compensation edges Edge metadata check uncompensated_paths/1Failing tasks without valid compensation BFS on the compensation subgraphmissing_compensations/1Retry-configured tasks lacking compensations Metadata check bottlenecks/2High-latency / high-retry tasks Threshold filter simulate/1Estimated latency per task Topological-order latency propagation heatmap/2Cumulative latency heatmap Simulation → color scale validate/1Workflow structural validation Composite checks
Function Purpose Algorithm used ready/1Tasks whose dependencies are done Status + dependency resolution blocked/1Tasks with unresolved dependencies Status + dependency resolution orphans/1Tasks not in any milestone Parent metadata check critical_path/2Longest dependency chain by estimate DP over topological order bottlenecks/1Tasks ranked by transitive downstream impact BFS reachability count validate/1Structural integrity checks Composite: cycles, unassigned tasks, orphans, empty milestones
Function Purpose Algorithm used depth/1Maximum depth from root DFS with cycle guardbreadth/1 / leaves/1Leaf count / leaf nodes Out-degree filter orphan_nodes/1Nodes not reachable from root BFS on branch edgesmax_width/1Widest level BFS level counting paths/1All root-to-leaf paths DFS enumeration type_frequencies/1Node type composition Group-by + count cyclic?/1Cycle in hierarchy Cycle detection suggest_merges/2Candidate node pairs to merge Jaccard similarity of neighborhoodsvalidate/1Structural validation Composite checks
Function Purpose Algorithm used shortest_join_path/3Optimal join sequence Path finding on an undirected simple graph cycles/1Circular foreign-key references DFS cycle detection orphans/1Tables with no relationships Degree check table_degrees/1In/out/total coupling per table Degree metrics affected_by/2Tables that reference target transitively BFS on the transposed graph depends_on/2Tables the target depends on BFS transitive_reduction/1Redundant relationships Transitive reduction longest_dependency_chain/1Deepest FK cascade DP over topological order normalization_score/2Schema quality score Heuristic penalty scoring validate/1ERD structural validation Composite checks
Function Purpose Algorithm used cycles/1Circular dependency loops DFS cycle detection broken_contracts/1Incomplete interface/behavior realizations Contract function comparison coupling_metrics/1Afferent/efferent coupling and instability In/out degree + Ce/(Ca+Ce) law_of_demeter_violations/1Structural Law of Demeter violations Triplet enumeration (A→B, B→C, A→C) affected_by/2Classes that depend on target BFS on the transposed graph depends_on/2Classes target depends on BFS transitive_reduction/1Redundant relationships Transitive reduction validate/1UML structural validation Composite checks
Function Purpose Algorithm used validate/1 / warnings/1Semantic validation of events/commands/policies Rule-based adjacency-map checks ubiquitous_language/1Markdown glossary from nodes Sort + format
Function Purpose Algorithm used validate/1Full sequence diagram validation Composite checks isolated_participants/1Participants with no messages Set difference missing_labels/1Messages without labels Metadata filter unknown_participants/1References to undeclared participants Set membership check unbalanced_activations/1Unmatched activate/deactivate pairs Stack balance unclosed_fragments/1Fragments opened but not closed Stack balance on reversed events
Function Purpose Algorithm used orphan_requirements/1Requirements with no relationships Set difference unsatisfied/1 / unverified/1Requirements missing satisfies/verifies edges Edge metadata check coverage/1Coverage ratios Set operations traceability_matrix/1Requirements → components/tests/stakeholders Edge aggregation requirements_for/2 / components_for/2Related nodes by edge type Edge traversal high_risk_gaps/1High-risk requirements not satisfied/verified Set intersection risk_propagation/1Inherited risk from ancestors Recursive ancestor traversal unmitigated_risks/1High-risk items without lower-risk children Risk-level comparison impact_of/2Upstream + downstream affected nodes BFS in both directions circular_dependencies/1Cycles among requirement relationships Tarjan's SCC validate/1Requirements validation Composite checks
Algorithm index A quick lookup of which algorithms appear where.
Algorithm Used by BFS Choreo.Analysis.impact_analysis/2Choreo.DataflowChoreo.Dependency.affected_by/2, Choreo.ERD.affected_by/2, Choreo.UML.affected_by/2, Choreo.FSMChoreo.WorkflowChoreo.MindMapChoreo.ThreatModel.exposed_data_stores/1, Choreo.Requirement.impact_of/2, Choreo.Internal.bfs_reachable/2DFS Choreo.ERD.cycles/1, Choreo.UML.cycles/1, Choreo.MindMap.paths/1, Choreo.DecisionTree.paths/1, Choreo.ThreatModel.attack_paths/1, Choreo.Internal.dfs_cycles/1Topological sort Choreo.Analysis.topological_sort/1Choreo.DataflowChoreo.Dependency.longest_dependency_chain/1, Choreo.ERD.longest_dependency_chain/1, Choreo.Workflow.critical_path/1, Choreo.Planner.critical_path/2, Choreo.Dataflow.simulate/1SCC (Tarjan) Choreo.Analysis.strongly_connected_components/1Choreo.Dependency.cyclic_dependencies/1, Choreo.Requirement.circular_dependencies/1Articulation points / bridges Choreo.Analysis.single_points_of_failure/1Choreo.Analysis.cut_vertices/1Yog.Connectivity.analyze/1Shortest path (Dijkstra) Choreo.Analysis.shortest_path/4Choreo.Analysis.path/4Choreo.Analysis.Tracing.trace_path/3Widest path Choreo.Analysis.path/4:throughput, :weighted)MST (Kruskal/Prim/Borůvka) Choreo.Analysis.mst/2Longest path in DAG Choreo.Dataflow.longest_path/1, Choreo.Dependency.longest_dependency_chain/1, Choreo.ERD.longest_dependency_chain/1, Choreo.Workflow.critical_path/1, Choreo.Planner.critical_path/2 via Choreo.Internal.compute_dp/3Transitive reduction Choreo.Analysis.reduce_transitive/1Choreo.Dependency.transitive_reduction/1, Choreo.ERD.transitive_reduction/1, Choreo.UML.transitive_reduction/1, Choreo.Internal.transitive_reduction/1Centrality Choreo.Analysis.centrality/2K-core decomposition Choreo.Analysis.core_numbers/1Weakly connected components Choreo.Dependency.isolated_subsystems/1DFA minimization (Moore's partition refinement) Choreo.FSM.Analysis.minimize/1Product automaton BFS Choreo.FSM.Analysis.equivalent?/2Jaccard similarity Choreo.MindMap.Analysis.suggest_merges/2Instability metric Choreo.Dependency.instability/1, Choreo.UML.coupling_metrics/1
Implementation notes Most path and impact analyses work on a simple graph view produced by to_simple_graph/1 or Yog.Multi.to_simple_graph/1 Topological-order DP (Choreo.Internal.compute_dp/3) is the shared implementation for longest/critical path calculations across Dataflow, Dependency, ERD, Workflow, and Planner.Transitive reduction is implemented centrally in Choreo.Internal.transitive_reduction/1 and reused by Dependency, ERD, and UML.BFS reachability (Choreo.Internal.bfs_reachable/2) is the shared primitive for downstream/upstream impact analysis across nearly all diagram types.