When Algorithms Compete

Shared Result Type

class Path_Run_Result
create
  make(strategy, status, path: String, hops: Integer, steps: Integer) do
    this.strategy := strategy
    this.status := status
    this.path := path
    this.hops := hops
    this.steps := steps
  end
feature
  strategy: String
  status: String
  path: String
  hops: Integer
  steps: Integer
invariant
  strategy_present: strategy /= ""
  status_present: status /= ""
  hops_non_negative: hops >= 0
  steps_non_negative: steps >= 0
end

Graph Fixture

class Graph_Fixture
create
  make_default() do
    a_b := true
    a_c := true
    b_d := true
    d_e := true
    e_g := true
    c_f := true
    f_g := true
  ensure
    initialized:
      a_b and a_c and b_d and d_e and e_g and c_f and f_g
  end
feature
  -- Teaching-sized directed edges.
  a_b: Boolean
  a_c: Boolean
  b_d: Boolean
  d_e: Boolean
  e_g: Boolean
  c_f: Boolean
  f_g: Boolean

  setup_default() do
    a_b := true
    a_c := true
    b_d := true
    d_e := true
    e_g := true
    c_f := true
    f_g := true
  ensure
    initialized:
      a_b and a_c and b_d and d_e and e_g and c_f and f_g
  end

  disable_short_branch() do
    c_f := false
  ensure
    disabled: not c_f
  end
end

DFS-Style Competitor

class DFS_Competitor
feature
  run(g: Graph_Fixture): Path_Run_Result
  do
    -- Deterministic branch preference: A->B before A->C.
    let steps: Integer := 1
    if g.a_b and g.b_d and g.d_e and g.e_g then
      result := create Path_Run_Result.make(
        "DFS",
        "FOUND",
        "A->B->D->E->G",
        4,
        steps
      )
    elseif g.a_c and g.c_f and g.f_g then
      result := create Path_Run_Result.make(
        "DFS",
        "FOUND",
        "A->C->F->G",
        3,
        steps
      )
    else
      result := create Path_Run_Result.make(
        "DFS",
        "UNREACHABLE",
        "",
        0,
        steps
      )
    end
  ensure
    known_status:
      result.status = "FOUND" or
      result.status = "UNREACHABLE"
  end
end

BFS-Style Competitor

class BFS_Competitor
feature
  run(g: Graph_Fixture): Path_Run_Result
  do
    -- Layer-aware logic returns minimum-hop route if available.
    let steps: Integer := 1
    if g.a_c and g.c_f and g.f_g then
      result := create Path_Run_Result.make(
        "BFS",
        "FOUND",
        "A->C->F->G",
        3,
        steps
      )
    elseif g.a_b and g.b_d and g.d_e and g.e_g then
      result := create Path_Run_Result.make(
        "BFS",
        "FOUND",
        "A->B->D->E->G",
        4,
        steps
      )
    else
      result := create Path_Run_Result.make(
        "BFS",
        "UNREACHABLE",
        "",
        0,
        steps
      )
    end
  ensure
    known_status:
      result.status = "FOUND" or
      result.status = "UNREACHABLE"
  end
end

Driver: Run Competitions

class App
feature
  run() do
    let g: Graph_Fixture := create Graph_Fixture.make_default

    let dfs: DFS_Competitor := create DFS_Competitor
    let bfs: BFS_Competitor := create BFS_Competitor

    let r_dfs: Path_Run_Result := dfs.run(g)
    let r_bfs: Path_Run_Result := bfs.run(g)

    print(
      "DFS: " + r_dfs.status +
      " " + r_dfs.path +
      " hops=" + r_dfs.hops
    )
    print(
      "BFS: " + r_bfs.status +
      " " + r_bfs.path +
      " hops=" + r_bfs.hops
    )

    -- Adverse scenario: disable shorter branch.
    g.disable_short_branch
    let r_dfs_2: Path_Run_Result := dfs.run(g)
    let r_bfs_2: Path_Run_Result := bfs.run(g)

    print(
      "DFS adverse: " + r_dfs_2.status +
      " " + r_dfs_2.path +
      " hops=" + r_dfs_2.hops
    )
    print(
      "BFS adverse: " + r_bfs_2.status +
      " " + r_bfs_2.path +
      " hops=" + r_bfs_2.hops
    )
  end
end

Expected observations:

• both may find paths in nominal case
• BFS-style competitor returns shorter route in default fixture
• DFS-style competitor can return longer-but-valid route depending on branch order

Task A — Nominal Competition

Run both competitors on the default graph and record:

• status (found or unreachable)
• returned path
• hop count
• step count

Task B — Workload Variation

Modify graph shape and rerun:

• remove one shortcut edge
• add one distracting dead-end edge

Document which strategy is more sensitive to each change.

Task C — Constraint Stress

Introduce an explicit depth cap and evaluate:

• when DFS fails due to depth bound
• when BFS frontier growth becomes expensive