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
    -- Teaching-sized directed graph. Neighbor order is
    -- fixed, so both searches are deterministic.
    edges := {
      "A": ["B", "C"],
      "B": ["D"],
      "C": ["F"],
      "D": ["E"],
      "E": ["G"],
      "F": ["G"],
      "G": []
    }
  ensure
    short_branch_open: has_edge("C", "F")
  end
feature
  edges: Map[String, Array[String]]

  has_edge(from_node, to_node: String): Boolean do
    result := edges.contains_key(from_node)
              and edges.get(from_node).contains(to_node)
  end

  disable_short_branch() do
    let out := edges.get("C")
    if out.contains("F") then
      out.remove(out.index_of("F"))
    end
  ensure
    disabled: not has_edge("C", "F")
  end

  -- Rebuild the path to goal from the node each 
  -- node was first reached from.
  trace(came_from: Map[String, String], 
        goal: String): String do
    result := goal
    from let prev := came_from.get(goal) 
    until prev = "" do
      result := prev + "->" + result
      prev := came_from.get(prev)
    end
  end
end

DFS-Style Competitor

class DFS_Competitor
feature
  steps: Integer
  came_from: Map[String, String]

  run(g: Graph_Fixture): Path_Run_Result
  do
    steps := 0
    came_from := {}
    came_from.put("A", "")
    if visit(g, "A", "G") then
      let path := g.trace(came_from, "G")
      result := create Path_Run_Result.make(
        "DFS", "FOUND", path, 
        path.split("->").length - 1, steps
      )
    else
      result := create Path_Run_Result.make(
        "DFS", "UNREACHABLE", "", 0, steps
      )
    end
  ensure
    known_status:
      result.status = "FOUND" or
      result.status = "UNREACHABLE"
  end

  -- Go as deep as possible along the first unvisited
  -- neighbor before trying the next one.
  visit(g: Graph_Fixture, node, goal: String): Boolean
  do
    steps := steps + 1
    if node = goal then
      result := true
    else
      result := false
      across g.edges.get(node) as next do
        if not result 
           and not came_from.contains_key(next) then
          came_from.put(next, node)
          result := visit(g, next, goal)
        end
      end
    end
  end
end

BFS-Style Competitor

class BFS_Competitor
feature
  run(g: Graph_Fixture): Path_Run_Result
  do
    -- Expand nodes in the order they were discovered,
    -- so every node one hop out is expanded before any
    -- node two hops out.
    let steps: Integer := 0
    let came_from: Map[String, String] := {}
    came_from.put("A", "")
    let frontier: Array[String] := ["A"]
    from let i := 0
    until i >= frontier.length 
          or came_from.contains_key("G") do
      steps := steps + 1
      across g.edges.get(frontier.get(i)) as next do
        if not came_from.contains_key(next) then
          came_from.put(next, frontier.get(i))
          frontier.add(next)
        end
      end
      i := i + 1
    end
    if came_from.contains_key("G") then
      let path := g.trace(came_from, "G")
      result := create Path_Run_Result.make(
        "BFS", "FOUND", path, 
        path.split("->").length - 1, 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 +
      " steps=" + r_dfs.steps
    )
    print(
      "BFS: " + r_bfs.status +
      " " + r_bfs.path +
      " hops=" + r_bfs.hops +
      " steps=" + r_bfs.steps
    )

    -- 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 +
      " steps=" + r_dfs_2.steps
    )
    print(
      "BFS adverse: " + r_bfs_2.status +
      " " + r_bfs_2.path +
      " hops=" + r_bfs_2.hops +
      " steps=" + r_bfs_2.steps
    )
  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