YogEx Algorithm Selector

Mix.install([
  # For Hex publication/readers:
  {:choreo, "~> 0.14.1"},
  # {:choreo, path: Path.expand("../..", __DIR__), force: true},
  {:kino_vizjs, "~> 0.9.0"}
])

Section

Interactive algorithm picker: This notebook builds a Choreo.DecisionTree that guides you to the right YogEx algorithm based on the graph problem you are trying to solve.

The Decision Tree

import Choreo.Lab.DSL.DecisionTree
alias Choreo.DecisionTree
alias Choreo.DecisionTree.Analysis

selector =
  decision_tree do
    # Root
    problem = root("What problem are you solving?")

    # Pathfinding branch
    path_weights = decision("Edge weights?")
    path_pairs = decision("Single pair or all pairs?")
    graph_density = decision("Graph density?")
    bfs = outcome("BFS / Bidirectional BFS", class: "pathfinding")
    dijkstra = outcome("Dijkstra", class: "pathfinding")
    johnson = outcome("Johnson's", class: "pathfinding")
    floyd = outcome("Floyd-Warshall", class: "pathfinding")
    bellman_ford = outcome("Bellman-Ford", class: "pathfinding")
    astar = outcome("A*", class: "pathfinding")

    # Flow branch
    flow_problem = decision("Which flow problem?")
    mincost_size = decision("Instance size?")
    dinic_ek = outcome("Dinic's / Edmonds-Karp", class: "flow")
    ssp = outcome("Successive Shortest Path", class: "flow")
    network_simplex = outcome("Network Simplex", class: "flow")
    stoer_wagner = outcome("Stoer-Wagner", class: "flow")

    # Spanning tree branch
    st_type = decision("What kind of spanning tree?")
    prims = outcome("Prim's", class: "tree")
    kruskals = outcome("Kruskal's", class: "tree")
    edmonds = outcome("Edmonds' (arborescence)", class: "tree")
    max_st = outcome("Max Spanning Tree", class: "tree")

    # Matching branch
    matching_type = decision("What kind of matching?")
    hopcroft_karp = outcome("Hopcroft-Karp", class: "matching")
    hungarian = outcome("Hungarian", class: "matching")
    blossom = outcome("Blossom", class: "matching")

    # Community branch
    community_goal = decision("Priority?")
    label_prop = outcome("Label Propagation", class: "community")
    leiden = outcome("Leiden", class: "community")
    louvain = outcome("Louvain", class: "community")
    clique_perc = outcome("Clique Percolation", class: "community")

    # Centrality branch
    centrality_goal = decision("What to measure?")
    degree = outcome("Degree Centrality", class: "centrality")
    closeness = outcome("Closeness / Harmonic", class: "centrality")
    betweenness = outcome("Betweenness", class: "centrality")
    pagerank = outcome("PageRank", class: "centrality")

    # Connectivity branch
    connectivity_type = decision("What structure?")
    scc = outcome("Tarjan's / Kosaraju's SCC", class: "connectivity")
    components = outcome("Connected Components", class: "connectivity")
    bridges = outcome("Tarjan's Bridges", class: "connectivity")
    articulation = outcome("Tarjan's Articulation", class: "connectivity")

    # Traversal branch
    traversal_type = decision("Traversal order?")
    bfs_trav = outcome("BFS", class: "traversal")
    dfs_trav = outcome("DFS", class: "traversal")
    topsort = outcome("Topological Sort", class: "traversal")

    # Branches: problem type
    problem ~> path_weights |> when_("Shortest path")
    problem ~> flow_problem |> when_("Flow / cuts")
    problem ~> st_type |> when_("Spanning tree")
    problem ~> matching_type |> when_("Matching")
    problem ~> community_goal |> when_("Community detection")
    problem ~> centrality_goal |> when_("Centrality")
    problem ~> connectivity_type |> when_("Connectivity")
    problem ~> traversal_type |> when_("Traversal")

    # Branches: pathfinding
    path_weights ~> bfs |> when_("Unweighted")
    path_weights ~> astar |> when_("Heuristic available")
    path_weights ~> path_pairs |> when_("Non-negative weights")
    path_weights ~> bellman_ford |> when_("Negative weights")
    path_pairs ~> dijkstra |> when_("Single pair")
    path_pairs ~> graph_density |> when_("All pairs")
    graph_density ~> johnson |> when_("Sparse")
    graph_density ~> floyd |> when_("Dense")

    # Branches: flow
    flow_problem ~> dinic_ek |> when_("Max flow")
    flow_problem ~> mincost_size |> when_("Min-cost flow")
    flow_problem ~> stoer_wagner |> when_("Global min cut")
    mincost_size ~> ssp |> when_("Small / medium")
    mincost_size ~> network_simplex |> when_("Large")

    # Branches: spanning tree
    st_type ~> prims |> when_("Dense graph")
    st_type ~> kruskals |> when_("Sparse graph")
    st_type ~> edmonds |> when_("Directed")
    st_type ~> max_st |> when_("Maximum weight")

    # Branches: matching
    matching_type ~> hopcroft_karp |> when_("Bipartite unweighted")
    matching_type ~> hungarian |> when_("Bipartite weighted")
    matching_type ~> blossom |> when_("General graph")

    # Branches: community
    community_goal ~> label_prop |> when_("Speed")
    community_goal ~> leiden |> when_("Quality guarantee")
    community_goal ~> louvain |> when_("Modularity")
    community_goal ~> clique_perc |> when_("Overlapping")

    # Branches: centrality
    centrality_goal ~> degree |> when_("Simple importance")
    centrality_goal ~> closeness |> when_("Distance-based")
    centrality_goal ~> betweenness |> when_("Bridge detection")
    centrality_goal ~> pagerank |> when_("Link quality")

    # Branches: connectivity
    connectivity_type ~> scc |> when_("Strongly connected components")
    connectivity_type ~> components |> when_("Connected components")
    connectivity_type ~> bridges |> when_("Bridge edges")
    connectivity_type ~> articulation |> when_("Articulation points")

    # Branches: traversal
    traversal_type ~> bfs_trav |> when_("Level-order")
    traversal_type ~> dfs_trav |> when_("Depth-first")
    traversal_type ~> topsort |> when_("DAG ordering")
  end

mermaid = Choreo.DecisionTree.to_mermaid(selector, direction: :lr)

Choreo.Lab.Siren.new(mermaid, height: "1800px")

Extracted Rules

Convert every root-to-leaf path into a readable IF-THEN rule:

Analysis.rules(selector)
|> Enum.each(fn %{conditions: conditions, outcome: outcome} ->
  conds = Enum.map(conditions, fn {f, v} -> "#{f} = #{v}" end) |> Enum.join(" AND ")
  IO.puts("IF #{conds} THEN #{outcome.label}")
end)

Interactive Evaluation

# Example: I need a min-cost flow algorithm for a large network.
Analysis.decide(selector, %{
  "What problem are you solving?" => "Flow / cuts",
  "Which flow problem?" => "Min-cost flow",
  "Instance size?" => "Large"
})

Validation

Analysis.validate(selector)
|> Enum.each(fn {sev, msg} ->
  icon = if sev == :error, do: "❌", else: "⚠️"
  IO.puts("#{icon} #{msg}")
end)