Skip to content

ALGORITHMS.md

Latest commit

 

History

History
326 lines (272 loc) · 21.9 KB

ALGORITHMS.md

File metadata and controls

326 lines (272 loc) · 21.9 KB
Raw

Choreo Analysis Algorithms Reference

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 graph library, which provides BFS/DFS, topological sort, strongly connected components, shortest paths, MST, centrality, and connectivity primitives.

Supported diagram types

Diagram type Main module Analysis module Typical use
System architecture Choreo Choreo.Analysis Services, databases, caches, queues
C4 model Choreo.C4 Choreo.C4.Analysis Software architecture views
Cloud infrastructure Choreo.Infrastructure Choreo.Infrastructure.Analysis VPC/subnet/security audits
Finite-state machines Choreo.FSM Choreo.FSM.Analysis State machines and automata
Dataflow / pipelines Choreo.Dataflow Choreo.Dataflow.Analysis Streaming/data pipelines
Dependency graphs Choreo.Dependency Choreo.Dependency.Analysis Module/library dependencies
Decision trees Choreo.DecisionTree Choreo.DecisionTree.Analysis Classification trees
Threat models Choreo.ThreatModel Choreo.ThreatModel.Analysis STRIDE threat modeling
Workflows Choreo.Workflow Choreo.Workflow.Analysis BPMN/saga workflows
Planner / tasks Choreo.Planner Choreo.Planner.Analysis Project/task planning
Mind maps Choreo.MindMap Choreo.MindMap.Analysis Hierarchical idea maps
Entity-relationship diagrams Choreo.ERD Choreo.ERD.Analysis Database schemas
UML class diagrams Choreo.UML Choreo.UML.Analysis Software design
Domain / event storming Choreo.Domain Choreo.Domain.Analysis Domain-driven design
Sequence diagrams Choreo.Sequence Choreo.Sequence.Analysis Message sequence validation
Requirements Choreo.Requirement Choreo.Requirement.Analysis Requirements traceability
Cross-diagram tracing — Choreo.Analysis.Tracing Trace edges across diagrams

Core / cross-cutting analysis

Choreo.Analysis — system architecture

These functions operate on the general Choreo architecture graph. Many of them are re-used or mirrored by diagram-specific modules.

Function Purpose Algorithm used
mst/2 Cheapest way to connect all services MST — Kruskal (default), Prim, or Borůvka on an undirected simple graph
topological_sort/1 Deployment or execution order Topological sort via Yog.Traversal.topological_sort/1 (Kahn / DFS-based)
cyclic?/1 Detect feedback loops Cycle detection via Yog.cyclic?/1
dag?/1 Check if the graph is acyclic Acyclicity check via Yog.acyclic?/1
strongly_connected_components/1 Find mutually dependent services Strongly Connected Components (SCC) via Yog.Connectivity
single_points_of_failure/1 Find articulation points and bridge edges Tarjan's articulation-point/bridge algorithm on an undirected view
cut_vertices/1 Nodes whose removal disconnects the graph Tarjan's articulation points
impact_analysis/2 What breaks if a node fails BFS on the transposed graph
shortest_path/4 Cheapest/fastest route between services Dijkstra / shortest path with semiring support (cost, latency, custom metrics)
path/4 Domain-specific pathfinding Dijkstra / widest path with measures :shortest, :latency, :throughput, :risk, :weighted
centrality/2 Most critical or coupled nodes Degree / betweenness / closeness / PageRank centrality via Yog.Centrality
core_numbers/1 K-core decomposition K-core decomposition via Yog.Connectivity.core_numbers/1
reduce_transitive/1 Remove redundant edges while preserving reachability Transitive reduction
isolated_nodes/1 Find orphan services In-degree + out-degree check
heatmap/2 Color nodes by centrality or score Centrality → min-max normalization → color scale
validate/1 Structural health check Composite: isolated nodes, SPOF, cycles, bridges

Choreo.Analysis.Tracing — cross-diagram tracing

Function Purpose Algorithm used
impact_analysis/2 Nodes transitively impacted via trace edges BFS on the transposed trace-only graph
trace_path/3 Shortest trace path between two nodes Dijkstra on the trace-only graph
analyze/3 Nested cross-domain analysis along a trace path Path reconstruction + domain metadata classification

Internal shared graph primitives

Function Purpose Algorithm used
bfs_reachable/2 Reachable nodes from seed nodes Breadth-First Search (BFS)
transitive_reduction/1 Redundant edges implied by longer paths BFS reachability from alternate successors
compute_dp/3 Longest-path DP table Dynamic programming over a topological order
find_best_end_path/2 Best predecessor chain Linear scan of the DP table
reconstruct_path/2 Reconstruct a path from DP predecessors Backtracking
dfs_cycles/1 All elementary cycles in a multigraph Depth-First Search (DFS) with recursion-stack tracking
unsatisfied_contract/3 Missing functions for a contract Set difference on function name/arity

Diagram-specific analysis

Choreo.C4.Analysis — C4 architecture model validation

Function Purpose Algorithm used
isolated_nodes/1 Elements with no relationships In-degree + out-degree on a simple graph
missing_parents/1 Containers/components without parents Metadata filter
missing_descriptions/1 Nodes lacking descriptions Metadata filter
missing_technology/1 Containers/components without technology labels Metadata filter
missing_relationship_labels/1 Relationships lacking labels Edge metadata filter
parents_without_relationships/1 Parent nodes with children but no edges Degree + parent metadata check
validate/1 Full C4 model validation Composite rule check

Choreo.Infrastructure.Analysis — cloud topology audits

Function Purpose Algorithm used
validate/1 Security audit (internet-to-private, DB placement, LB placement, etc.) Rule-based set membership checks on node/edge metadata
warnings/1 Audit warnings Rule-based set membership checks

Choreo.FSM.Analysis — finite-state machines

Function Purpose Algorithm used
reachable_states/1 States reachable from the initial state BFS
dead_states/1 States with no path to a final state Reverse BFS from final states
livelock_states/1 Reachable non-accepting loop states Intersection of reachable/dead + BFS self-reachability
accepts?/2 Simulate input string acceptance Deterministic walk
shortest_accepting_path/1 Minimum input to reach acceptance BFS
accepted_strings/2 All accepted strings up to length N BFS level-order expansion
alphabet/1 Distinct input symbols Set construction
complete?/1 Whether every state handles every symbol Set subset check
generate_test_cases/2 Input sequences for state/transition coverage BFS shortest paths to all states
equivalent?/2 Check if two FSMs accept the same language Product automaton BFS
minimize/1 Minimize a DFA Moore's partition refinement
violates_invariant?/2 Forbidden state sequence exists Edge existence check
validate/1 Structural FSM validation Composite checks

Choreo.Dataflow.Analysis — streaming/data pipelines

Function Purpose Algorithm used
sources/1 / sinks/1 Identify source/sink nodes Node type filter
cyclic?/1 Feedback-loop detection Cycle detection on the normal-edge subgraph
topological_sort/1 Stage execution order Topological sort
orphan_nodes/1 Nodes unreachable from any source BFS from sources + set difference
dead_ends/1 Nodes that cannot reach any sink BFS on the transposed graph from sinks
fan_hubs/1 High in-degree + out-degree stages Degree threshold
longest_path/1 Critical path (longest source→sink chain) DP over topological order
capacity_bottlenecks/1 Stages where in_rate > capacity Throughput simulation via topological propagation
simulate/1 Steady-state throughput simulation Topological-order traversal + rate summation
backpressure_points/1 Nodes with inbound flow above threshold Simulation result filter
upstream_lineage/1 / downstream_impact/1 Ancestors/descendants BFS (transposed for upstream)
upstream_sources/1 / downstream_sinks/1 Source/sink subsets of lineage BFS + set intersection
heatmap/2 Throughput heatmap Simulation → color scale
validate/1 Pipeline structural validation Composite checks

Choreo.Dependency.Analysis — dependency graphs

Function Purpose Algorithm used
cyclic_dependencies/1 All circular dependency chains SCC + DFS cycle extraction
affected_by/2 Components that break if the target changes BFS on the transposed graph
depends_on/2 Components the target depends on BFS
layer_violations/2 Edges violating layered architecture Edge + layer-index comparison
centrality/2 Most coupled components Degree centrality (in + out)
leaves/1 / roots/1 Nodes with no dependents / no dependencies In-degree / out-degree filter
transitive_reduction/1 Redundant explicit dependencies Transitive reduction
instability/1 Instability metric per component Ce / (Ca + Ce)
isolated_subsystems/1 Disconnected component groups Weakly connected components
longest_dependency_chain/1 Deepest dependency chain DP over topological order
validate/1 Dependency graph validation Composite checks

Choreo.DecisionTree.Analysis — decision trees

Function Purpose Algorithm used
decide/2 Evaluate tree against feature values Tree walk
paths/1 All root-to-leaf paths DFS enumeration
paths_with_conditions/1 Paths with branch conditions DFS enumeration
depth/1 / breadth/1 Tree depth / leaf count Recursive traversal / count
feature_importance/1 Feature split frequency Group-by + count
reachable_outcomes/1 Reachable outcome classes BFS
orphan_nodes/1 Unreachable declared nodes BFS + set difference
rules/1 Extract IF-THEN rules Path-to-conditions mapping
generate_test_cases/1 Feature maps covering every leaf Path conditions
missing_branches/2 Expected feature values not covered Set difference
inconsistent_paths/1 Logically impossible paths Path condition grouping
prune_redundant/1 Remove redundant decision nodes Post-order tree traversal
validate/1 Tree structural validation Composite checks

Choreo.ThreatModel.Analysis — STRIDE threat modeling

Function Purpose Algorithm used
stride_threats/2 Generate STRIDE threats Rule-based generation by element type
threat_summary/1 Threat distribution by category/severity Aggregation
risk_score/2 Total weighted risk score Weighted sum by severity
cross_boundary_flows/1 Data flows crossing trust boundaries Boundary comparison
exposed_data_stores/1 Data stores reachable from external entities BFS from external entities
attack_paths/1 Paths from externals to data stores DFS path enumeration
high_risk_processes/1 Low-trust processes accessing sensitive stores BFS + risk/trust checks
unencrypted_boundary_flows/1 Unencrypted cross-boundary flows Edge metadata + boundary check
heatmap/2 Threat density heatmap Threat count → color scale
validate/1 Threat model validation Composite checks

Choreo.Workflow.Analysis — workflows and orchestration

Function Purpose Algorithm used
reachable_tasks/1 Tasks reachable from start nodes BFS
orphan_tasks/1 Tasks not reachable from starts BFS + set difference
dead_ends/1 Tasks that cannot reach an end node BFS on the transposed graph from ends
critical_path/1 Longest latency path start→end DP over topological order
parallelizable_tasks/1 Tasks that can run in parallel Topological levels
compensable_tasks/1 Tasks with compensation edges Edge metadata check
uncompensated_paths/1 Failing tasks without valid compensation BFS on the compensation subgraph
missing_compensations/1 Retry-configured tasks lacking compensations Metadata check
bottlenecks/2 High-latency / high-retry tasks Threshold filter
simulate/1 Estimated latency per task Topological-order latency propagation
heatmap/2 Cumulative latency heatmap Simulation → color scale
validate/1 Workflow structural validation Composite checks

Choreo.Planner.Analysis — project/task planning

Function Purpose Algorithm used
ready/1 Tasks whose dependencies are done Status + dependency resolution
blocked/1 Tasks with unresolved dependencies Status + dependency resolution
orphans/1 Tasks not in any milestone Parent metadata check
critical_path/2 Longest dependency chain by estimate DP over topological order
bottlenecks/1 Tasks ranked by transitive downstream impact BFS reachability count
validate/1 Structural integrity checks Composite: cycles, unassigned tasks, orphans, empty milestones

Choreo.MindMap.Analysis — mind maps

Function Purpose Algorithm used
depth/1 Maximum depth from root DFS with cycle guard
breadth/1 / leaves/1 Leaf count / leaf nodes Out-degree filter
orphan_nodes/1 Nodes not reachable from root BFS on branch edges
max_width/1 Widest level BFS level counting
paths/1 All root-to-leaf paths DFS enumeration
type_frequencies/1 Node type composition Group-by + count
cyclic?/1 Cycle in hierarchy Cycle detection
suggest_merges/2 Candidate node pairs to merge Jaccard similarity of neighborhoods
validate/1 Structural validation Composite checks

Choreo.ERD.Analysis — database schemas

Function Purpose Algorithm used
shortest_join_path/3 Optimal join sequence Path finding on an undirected simple graph
cycles/1 Circular foreign-key references DFS cycle detection
orphans/1 Tables with no relationships Degree check
table_degrees/1 In/out/total coupling per table Degree metrics
affected_by/2 Tables that reference target transitively BFS on the transposed graph
depends_on/2 Tables the target depends on BFS
transitive_reduction/1 Redundant relationships Transitive reduction
longest_dependency_chain/1 Deepest FK cascade DP over topological order
normalization_score/2 Schema quality score Heuristic penalty scoring
validate/1 ERD structural validation Composite checks

Choreo.UML.Analysis — UML class diagrams

Function Purpose Algorithm used
cycles/1 Circular dependency loops DFS cycle detection
broken_contracts/1 Incomplete interface/behavior realizations Contract function comparison
coupling_metrics/1 Afferent/efferent coupling and instability In/out degree + Ce/(Ca+Ce)
law_of_demeter_violations/1 Structural Law of Demeter violations Triplet enumeration (A→B, B→C, A→C)
affected_by/2 Classes that depend on target BFS on the transposed graph
depends_on/2 Classes target depends on BFS
transitive_reduction/1 Redundant relationships Transitive reduction
validate/1 UML structural validation Composite checks

Choreo.Domain.Analysis — event storming / domain models

Function Purpose Algorithm used
validate/1 / warnings/1 Semantic validation of events/commands/policies Rule-based adjacency-map checks
ubiquitous_language/1 Markdown glossary from nodes Sort + format

Choreo.Sequence.Analysis — sequence diagrams

Function Purpose Algorithm used
validate/1 Full sequence diagram validation Composite checks
isolated_participants/1 Participants with no messages Set difference
missing_labels/1 Messages without labels Metadata filter
unknown_participants/1 References to undeclared participants Set membership check
unbalanced_activations/1 Unmatched activate/deactivate pairs Stack balance
unclosed_fragments/1 Fragments opened but not closed Stack balance on reversed events

Choreo.Requirement.Analysis — requirements traceability

Function Purpose Algorithm used
orphan_requirements/1 Requirements with no relationships Set difference
unsatisfied/1 / unverified/1 Requirements missing satisfies/verifies edges Edge metadata check
coverage/1 Coverage ratios Set operations
traceability_matrix/1 Requirements → components/tests/stakeholders Edge aggregation
requirements_for/2 / components_for/2 Related nodes by edge type Edge traversal
high_risk_gaps/1 High-risk requirements not satisfied/verified Set intersection
risk_propagation/1 Inherited risk from ancestors Recursive ancestor traversal
unmitigated_risks/1 High-risk items without lower-risk children Risk-level comparison
impact_of/2 Upstream + downstream affected nodes BFS in both directions
circular_dependencies/1 Cycles among requirement relationships Tarjan's SCC
validate/1 Requirements validation Composite checks

Algorithm index

A quick lookup of which algorithms appear where.

Algorithm Used by
BFS Choreo.Analysis.impact_analysis/2, Choreo.Dataflow reachability/lineage, Choreo.Dependency.Analysis.affected_by/2, Choreo.ERD.Analysis.affected_by/2, Choreo.UML.Analysis.affected_by/2, Choreo.FSM, Choreo.Workflow, Choreo.MindMap, Choreo.ThreatModel.Analysis.exposed_data_stores/1, Choreo.Requirement.Analysis.impact_of/2, Choreo.Internal.bfs_reachable/2
DFS Choreo.ERD.Analysis.cycles/1, Choreo.UML.Analysis.cycles/1, Choreo.MindMap.Analysis.paths/1, Choreo.DecisionTree.Analysis.paths/1, Choreo.ThreatModel.Analysis.attack_paths/2, Choreo.Internal.dfs_cycles/1
Topological sort Choreo.Analysis.topological_sort/1, Choreo.Dataflow, Choreo.Dependency.Analysis.longest_dependency_chain/1, Choreo.ERD.Analysis.longest_dependency_chain/1, Choreo.Workflow.Analysis.critical_path/1, Choreo.Planner.Analysis.critical_path/2, Choreo.Dataflow.Analysis.simulate/1
SCC (Tarjan) Choreo.Analysis.strongly_connected_components/1, Choreo.Dependency.Analysis.cyclic_dependencies/1, Choreo.Requirement.Analysis.circular_dependencies/1
Articulation points / bridges Choreo.Analysis.single_points_of_failure/1, Choreo.Analysis.cut_vertices/1 via Yog.Connectivity.analyze/1
Shortest path (Dijkstra) Choreo.Analysis.shortest_path/4, Choreo.Analysis.path/4, Choreo.Analysis.Tracing.trace_path/3
Widest path Choreo.Analysis.path/4 (:throughput, :weighted)
MST (Kruskal/Prim/Borůvka) Choreo.Analysis.mst/2
Longest path in DAG Choreo.Dataflow.Analysis.longest_path/1, Choreo.Dependency.Analysis.longest_dependency_chain/1, Choreo.ERD.Analysis.longest_dependency_chain/1, Choreo.Workflow.Analysis.critical_path/1, Choreo.Planner.Analysis.critical_path/2 via Choreo.Internal.compute_dp/3
Transitive reduction Choreo.Analysis.reduce_transitive/1, Choreo.Dependency.Analysis.transitive_reduction/1, Choreo.ERD.Analysis.transitive_reduction/1, Choreo.UML.Analysis.transitive_reduction/1, Choreo.Internal.transitive_reduction/1
Centrality Choreo.Analysis.centrality/2 (degree, betweenness, closeness, PageRank)
K-core decomposition Choreo.Analysis.core_numbers/1
Weakly connected components Choreo.Dependency.Analysis.isolated_subsystems/1
DFA minimization (Moore's partition refinement) Choreo.FSM.Analysis.minimize/1
Product automaton BFS Choreo.FSM.Analysis.equivalent?/2
Jaccard similarity Choreo.MindMap.Analysis.suggest_merges/2
Instability metric Choreo.Dependency.Analysis.instability/1, Choreo.UML.Analysis.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, which collapses parallel edges.
  • 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.