;;; dag-draw-pass3-positioning.el --- Node positioning for dag-draw -*- lexical-binding: t -*-

;; Copyright (C) 2024, 2025

;; Author: Generated by Claude
;; Keywords: internal

;; This program is free software; you can redistribute it and/or modify
;; it under the terms of the GNU General Public License as published by
;; the Free Software Foundation, either version 3 of the License, or
;; (at your option) any later version.

;;; Commentary:

;; GKNV Baseline Compliance:
;;
;; This module implements Pass 3 (Positioning) of the GKNV graph drawing algorithm
;; as specified in "A Technique for Drawing Directed Graphs" (Gansner, Koutsofios,
;; North, Vo).
;;
;; GKNV Reference: Section 4.2 (lines 1398-1614), Figure 4-2
;; Decisions: D3.1 (Network simplex on auxiliary graph - NOT heuristics),
;;            D3.2 (Omega values 1,2,8), D3.3 (Separation ρ function),
;;            D3.4 (Auxiliary tree initialization), D3.5 (Node ports)
;; Algorithm: Network simplex on auxiliary graph
;;
;; Key Requirements:
;; - Use auxiliary graph method (NOT heuristics per Section 4.1)
;; - Edge weights: Ω(e) = 1 (both real), 2 (one virtual), 8 (both virtual)
;; - Separation: ρ(a,b) = (xsize(a) + xsize(b))/2 + nodesep(G)
;; - Exploit auxiliary graph structure for initial feasible tree
;; - Support X-offset node ports per Section 4.2
;;
;; Baseline Status: ✅ Compliant (Heuristic fallback removed 2025-10-13)
;;
;; GKNV Section 4.2 states: "Much simpler code and produces optimal solutions...
;; runs as fast or faster than the heuristic implementation."
;;
;; Decision D3.1 specifies: Use network simplex on auxiliary graph, NOT heuristics.
;; The heuristic function was never called and has been removed for compliance.
;;
;; See doc/implementation-decisions.md (D3.1-D3.5) for full decision rationale.

;;; Code:

(require 'dash)
(require 'ht)
(require 'cl-lib)
(require 'dag-draw)
(require 'dag-draw-core)
(require 'dag-draw-aesthetic-principles)
(require 'dag-draw-quality)

;;; Y-coordinate assignment (straightforward)

(defun dag-draw--assign-y-coordinates (graph)
  "Assign Y coordinates to nodes based on their ranks.
This is straightforward - nodes in the same rank get the same Y coordinate.
Argument GRAPH ."
  (let ((rank-separation (dag-draw-graph-rank-separation graph))
        (_max-rank (or (dag-draw-graph-max-rank graph) 0)))

    ;; Assign Y coordinates from top to bottom
    (ht-each (lambda (_node-id node)
               (let ((rank (or (dag-draw-node-rank node) 0)))
                 (setf (dag-draw-node-y-coord node)
                       (* rank rank-separation))))
             (dag-draw-graph-nodes graph))))

;;; X-coordinate assignment using auxiliary graph


(defun dag-draw--get-omega-factor (_graph from-node to-node)
  "Get omega factor for edge cost based on node types.
Real-real edges: 1, real-virtual: 2, virtual-virtual: 8
Argument GRAPH .
Argument FROM-NODE .
Argument TO-NODE ."
  (let ((from-virtual (dag-draw--is-virtual-node-p from-node))
        (to-virtual (dag-draw--is-virtual-node-p to-node)))
    (cond
     ((and (not from-virtual) (not to-virtual)) 1)   ; both real
     ((and from-virtual to-virtual) 8)               ; both virtual
     ((or from-virtual to-virtual) 2)                ; one virtual
     (t 1))))                                        ; fallback

(defun dag-draw--is-virtual-node-p (node-id)
  "Check if node is a virtual node (start with `virtual_').
Argument NODE-ID ."
  (string-match "^virtual_" (symbol-name node-id)))

(defun dag-draw--add-separation-edges (aux-graph original-graph)
  "Add separation constraint edges between adjacent nodes in same rank.
Argument AUX-GRAPH .
Argument ORIGINAL-GRAPH ."
  (let ((rank-to-nodes (ht-create)))

    ;; Group nodes by rank
    (ht-each (lambda (node-id node)
               (let ((rank (or (dag-draw-node-rank node) 0)))
                 (ht-set! rank-to-nodes rank
                          (cons node-id (ht-get rank-to-nodes rank '())))))
             (dag-draw-graph-nodes original-graph))

    ;; Add separation edges within each rank
    (ht-each (lambda (_rank node-list)
               (let ((ordered-nodes (dag-draw--get-ordered-nodes-in-rank
                                     original-graph node-list)))
                 (dotimes (i (1- (length ordered-nodes)))
                   (let ((left-node (nth i ordered-nodes))
                         (right-node (nth (1+ i) ordered-nodes)))

                     ;; Add separation edge with minimum distance constraint
                     (let ((sep-distance (dag-draw--calculate-separation
                                          original-graph left-node right-node)))
                       (let ((sep-edge (dag-draw-edge-create
                                        :from-node left-node
                                        :to-node right-node
                                        :weight 0  ; No cost, just constraint
                                        :min-length sep-distance)))  ; GKNV ρ(u,v) separation constraint
                         (push sep-edge (dag-draw-graph-edges aux-graph))))))))
             rank-to-nodes)))

(defun dag-draw--get-ordered-nodes-in-rank (graph node-list)
  "Get nodes in rank ordered by their assigned order.
Argument GRAPH .
Argument NODE-LIST ."
  (sort node-list
        (lambda (a b)
          (let ((order-a (or (dag-draw-node-order (dag-draw-get-node graph a)) 0))
                (order-b (or (dag-draw-node-order (dag-draw-get-node graph b)) 0)))
            (< order-a order-b)))))

(defun dag-draw--calculate-separation (graph left-node right-node)
  "Calculate minimum separation between two adjacent nodes using GKNV formula.
ρ(a,b) = (xsize(a) + xsize(b))/2 + nodesep(G)
Argument GRAPH .
Argument LEFT-NODE .
Argument RIGHT-NODE ."
  (let* ((left (dag-draw-get-node graph left-node))
         (right (dag-draw-get-node graph right-node))
         (left-width (dag-draw-node-x-size left))
         (right-width (dag-draw-node-x-size right))
         (base-node-sep (dag-draw-graph-node-separation graph)))

    ;; GKNV formula: ρ(a,b) = (xsize(a) + xsize(b))/2 + nodesep(G)
    (+ (/ (+ left-width right-width) 2.0) base-node-sep)))



(defun dag-draw--get-node-targets (graph node-id)
  "Get list of nodes that NODE-ID connects to (outgoing edges).
Argument GRAPH ."
  (let ((targets '()))
    (dolist (edge (dag-draw-graph-edges graph))
      (when (eq (dag-draw-edge-from-node edge) node-id)
        (push (dag-draw-edge-to-node edge) targets)))
    targets))

(defun dag-draw--get-node-sources (graph node-id)
  "Get list of nodes that connect to NODE-ID (incoming edges).
Argument GRAPH ."
  (let ((sources '()))
    (dolist (edge (dag-draw-graph-edges graph))
      (when (eq (dag-draw-edge-to-node edge) node-id)
        (push (dag-draw-edge-from-node edge) sources)))
    sources))

;; REMOVED: Heuristic positioning fallback (previously lines 131-182)
;;
;; Decision D3.1 (doc/implementation-decisions.md): Use network simplex on auxiliary
;; graph for positioning - NOT heuristics.
;;
;; Rationale from GKNV paper (Section 4.2):
;; - Heuristic approach (Section 4.1) is "complicated to program and the results
;;   are sometimes noticeably imperfect"
;; - Network simplex approach (Section 4.2) provides:
;;   * "Much simpler code"
;;   * "Produces optimal solutions"
;;   * "Runs as fast or faster than the heuristic implementation"
;;   * Reuses network simplex infrastructure from Pass 1
;;
;; The heuristic function dag-draw--position-nodes-heuristic was never called in
;; the codebase and contradicted the baseline decision. It has been removed to
;; ensure compliance with GKNV Section 4.2 as the sole positioning method.
;;
;; If positioning quality issues arise, they should be addressed by improving
;; the network simplex constraint solver, not by adding heuristic fallbacks.

;;; Network simplex solver (simplified)



;;; Main positioning function

(defun dag-draw-position-nodes (graph)
  "Assign X and Y coordinates to all nodes.

GRAPH is a `dag-draw-graph' structure with assigned ranks and ordering.

Implements GKNV Pass 3 (Section 4) using auxiliary graph construction
for optimal X-coordinate assignment and rank-based Y-coordinate placement.

Returns the modified GRAPH with x-coord and y-coord set on all nodes."

  ;; Check coordinate mode for ASCII-native behavior
  (let ((coordinate-mode (or (dag-draw-graph-coordinate-mode graph) 'high-res)))

    ;; First assign Y coordinates (with coordinate-mode awareness)
    (if (eq coordinate-mode 'ascii)
        (dag-draw--assign-y-coordinates-ascii graph)
      (dag-draw--assign-y-coordinates graph))

    ;; Use GKNV auxiliary graph method for X-coordinate positioning (Section 4.2)
    (if (eq coordinate-mode 'ascii)
        (dag-draw--position-with-auxiliary-graph-ascii graph)
      (dag-draw--position-with-auxiliary-graph graph))

    ;; Apply GKNV positioning enhancements
    (dag-draw--apply-gknv-positioning-enhancements graph)

    ;; Apply ASCII coordinate rounding if in ASCII mode
    (when (eq coordinate-mode 'ascii)
      (dag-draw--round-coordinates-for-ascii graph)))

  ;; GKNV Pass 3 Authority: Store final coordinates in protected adjusted-positions
  ;; Section 4: "The third pass finds optimal coordinates for nodes"
  ;; This prevents manual coordinate overrides from affecting rendering
  (unless (dag-draw-graph-adjusted-positions graph)
    (setf (dag-draw-graph-adjusted-positions graph) (ht-create)))
  (ht-each (lambda (node-id node)
             (let ((final-x (or (dag-draw-node-x-coord node) 0))
                   (final-y (or (dag-draw-node-y-coord node) 0))
                   (width (dag-draw-node-x-size node))
                   (height (dag-draw-node-y-size node)))
               ;; Store GKNV-assigned coordinates in protected location
               ;; Format: (x y width height) - same as collision resolution format
               (ht-set! (dag-draw-graph-adjusted-positions graph) node-id
                        (list final-x final-y width height))))
           (dag-draw-graph-nodes graph))

  ;; GKNV Section 1.1: Evaluate aesthetic principles for positioning decisions
  (let ((positioning-aesthetics (dag-draw--evaluate-positioning-aesthetics graph)))
    (when (> (plist-get positioning-aesthetics :average-edge-length) 200)
      (when dag-draw-debug-output
        (message "GKNV A3: Average edge length %.1f exceeds threshold - consider tighter layout"
                 (plist-get positioning-aesthetics :average-edge-length))))
    (when (< (plist-get positioning-aesthetics :symmetry-score) 0.5)
      (when dag-draw-debug-output
        (message "GKNV A4: Layout symmetry score %.2f - consider balance improvements"
                 (plist-get positioning-aesthetics :symmetry-score)))))

  graph)

;;; Coordinate normalization and adjustment



;;; GKNV Positioning Enhancements Integration

(defun dag-draw--apply-gknv-positioning-enhancements (graph)
  "Apply GKNV positioning enhancements: minpath() and packcut().
Based on GKNV Figure 4-1 algorithm steps 8-9 within the
iterative optimization loop.
Argument GRAPH ."
  (let ((max-iterations 3)  ; GKNV recommends iterative improvement
        (best-layout-width most-positive-fixnum)
        (best-coordinates (ht-create)))

    ;; Store initial coordinates as baseline
    (dag-draw--store-coordinates graph best-coordinates)
    (setq best-layout-width (dag-draw--calculate-layout-width graph))

    ;; Iterative GKNV positioning enhancement
    (dotimes (_iteration max-iterations)
      ;; Step 8: minpath() - straighten virtual node chains
      (dag-draw--minpath-straighten-virtual-chains graph)

      ;; Step 9: packcut() - compact layout by removing excess spacing
      (dag-draw--packcut-compact-layout graph)

      ;; Check if this iteration improved the layout
      (let ((current-width (dag-draw--calculate-layout-width graph)))
        (when (< current-width best-layout-width)
          (setq best-layout-width current-width)
          (dag-draw--store-coordinates graph best-coordinates))))

    ;; Restore best coordinates found
    (dag-draw--restore-coordinates graph best-coordinates)))

(defun dag-draw--store-coordinates (graph coordinate-store)
  "Store current node coordinates in COORDINATE-STORE hash table.
Argument GRAPH ."
  (ht-clear! coordinate-store)
  (ht-each (lambda (node-id node)
             (ht-set! coordinate-store node-id
                      (cons (dag-draw-node-x-coord node)
                            (dag-draw-node-y-coord node))))
           (dag-draw-graph-nodes graph)))

(defun dag-draw--restore-coordinates (graph coordinate-store)
  "Restore node coordinates from COORDINATE-STORE hash table.
Argument GRAPH ."
  (ht-each (lambda (node-id coords)
             (let ((node (dag-draw-get-node graph node-id)))
               (when node
                 (setf (dag-draw-node-x-coord node) (car coords))
                 (setf (dag-draw-node-y-coord node) (cdr coords)))))
           coordinate-store))

;;; GKNV minpath() Virtual Node Chain Straightening

(defun dag-draw--find-virtual-node-chains (graph)
  "Find chains of virtual nodes that can be straightened.
Returns list of virtual node chains, where each chain is a list of node IDs
that form a continuous path of virtual nodes between real nodes.
Based on GKNV paper: minpath straightens chains of virtual nodes.
Argument GRAPH ."
  (let ((chains '())
        (visited (ht-create)))

    ;; Find all virtual nodes
    (ht-each (lambda (node-id _node)
               (when (and (dag-draw--is-virtual-node-p node-id)
                          (not (ht-get visited node-id)))
                 ;; Start a new chain from this virtual node
                 (let ((chain (dag-draw--trace-virtual-chain graph node-id visited)))
                   (when (> (length chain) 0)
                     (push chain chains)))))
             (dag-draw-graph-nodes graph))

    chains))

(defun dag-draw--trace-virtual-chain (graph start-node visited)
  "Trace a chain of virtual nodes starting from START-NODE.
Marks visited nodes and returns the chain as a list of node IDs.
Argument GRAPH ."
  (let ((chain '())
        (current-node start-node))

    ;; Walk forward through virtual nodes
    (while (and current-node
                (dag-draw--is-virtual-node-p current-node)
                (not (ht-get visited current-node)))
      ;; Mark as visited
      (ht-set! visited current-node t)
      ;; Add to chain
      (push current-node chain)

      ;; Find next virtual node in chain
      (setq current-node (dag-draw--find-next-virtual-in-chain graph current-node)))

    ;; Return chain in correct order (reverse since we pushed)
    (reverse chain)))

(defun dag-draw--find-next-virtual-in-chain (graph current-node)
  "Find the next virtual node connected to CURRENT-NODE.
Returns the next virtual node ID if found, nil otherwise.
Argument GRAPH ."
  (let ((next-virtual nil))
    (dolist (edge (dag-draw-graph-edges graph))
      (when (eq (dag-draw-edge-from-node edge) current-node)
        (let ((target-node (dag-draw-edge-to-node edge)))
          (when (dag-draw--is-virtual-node-p target-node)
            (setq next-virtual target-node)))))
    next-virtual))

(defun dag-draw--minpath-straighten-virtual-chains (graph)
  "Apply GKNV minpath() algorithm to straighten virtual node chains.
Sets virtual nodes in each chain to have the same X coordinate
for straight lines.
Based on GKNV paper: `minpath straightens chains of virtual nodes
by sequentially finding sub-chains that may be assigned the same
X coordinate.'
Argument GRAPH ."
  (let ((chains (dag-draw--find-virtual-node-chains graph)))
    (dolist (chain chains)
      (when (> (length chain) 0)  ; Handle both single nodes and multi-node chains
        ;; Calculate optimal X coordinate for this chain
        (let ((optimal-x (dag-draw--calculate-optimal-chain-x-coordinate graph chain)))
          ;; Align all virtual nodes in chain to optimal X
          (dolist (node-id chain)
            (let ((node (dag-draw-get-node graph node-id)))
              (when node
                (setf (dag-draw-node-x-coord node) optimal-x)))))))))

(defun dag-draw--calculate-optimal-chain-x-coordinate (graph chain)
  "Calculate optimal X coordinate for virtual node CHAIN.
Uses median of chain endpoints and neighbor positions for best alignment.
Argument GRAPH ."
  (let ((x-coordinates '()))

    ;; Collect X coordinates of chain endpoints (real nodes connected to chain)
    (let ((first-virtual (car chain))
          (last-virtual (car (last chain))))

      ;; Find real nodes connected to first virtual node (incoming)
      (dolist (edge (dag-draw-graph-edges graph))
        (when (eq (dag-draw-edge-to-node edge) first-virtual)
          (let ((source-node (dag-draw-get-node graph (dag-draw-edge-from-node edge))))
            (when (and source-node (not (dag-draw--is-virtual-node-p (dag-draw-edge-from-node edge))))
              (push (or (dag-draw-node-x-coord source-node) 0) x-coordinates)))))

      ;; Find real nodes connected to last virtual node (outgoing)
      (dolist (edge (dag-draw-graph-edges graph))
        (when (eq (dag-draw-edge-from-node edge) last-virtual)
          (let ((target-node (dag-draw-get-node graph (dag-draw-edge-to-node edge))))
            (when (and target-node (not (dag-draw--is-virtual-node-p (dag-draw-edge-to-node edge))))
              (push (or (dag-draw-node-x-coord target-node) 0) x-coordinates))))))

    ;; Calculate median/average of collected coordinates
    (if x-coordinates
        (let ((sorted-coords (sort x-coordinates #'<)))
          (if (= (length sorted-coords) 1)
              (car sorted-coords)
            ;; Use median for better alignment
            (let ((mid-index (/ (length sorted-coords) 2)))
              (if (= (mod (length sorted-coords) 2) 0)
                  ;; Even number - average of two middle values
                  (/ (+ (nth (1- mid-index) sorted-coords)
                        (nth mid-index sorted-coords)) 2.0)
                ;; Odd number - middle value
                (nth mid-index sorted-coords)))))
      ;; Fallback if no coordinates found
      0)))

;;; GKNV packcut() Layout Compaction


(defun dag-draw--get-nodes-in-rank-sorted-by-x (graph rank)
  "Get nodes in RANK sorted by X coordinate (left to right).
Returns list of node IDs sorted by their X coordinates.
Argument GRAPH ."
  (let ((nodes-in-rank '()))
    ;; Collect nodes in this rank
    (ht-each (lambda (node-id node)
               (when (and (dag-draw-node-rank node)
                          (= (dag-draw-node-rank node) rank))
                 (push node-id nodes-in-rank)))
             (dag-draw-graph-nodes graph))

    ;; Sort by X coordinate
    (sort nodes-in-rank
          (lambda (a b)
            (let ((x-a (or (dag-draw-node-x-coord (dag-draw-get-node graph a)) 0))
                  (x-b (or (dag-draw-node-x-coord (dag-draw-get-node graph b)) 0)))
              (< x-a x-b))))))

(defun dag-draw--find-rank-compaction-opportunities (graph nodes-in-rank)
  "Find compaction opportunities within a single rank.
Returns list of compaction operations for this rank.
Argument GRAPH .
Argument NODES-IN-RANK ."
  (let ((opportunities '()))
    (when (>= (length nodes-in-rank) 2)
      ;; Check gaps between adjacent nodes
      (dotimes (i (1- (length nodes-in-rank)))
        (let* ((left-node-id (nth i nodes-in-rank))
               (right-node-id (nth (1+ i) nodes-in-rank))
               (left-node (dag-draw-get-node graph left-node-id))
               (right-node (dag-draw-get-node graph right-node-id))
               (left-x (dag-draw-node-x-coord left-node))
               (right-x (dag-draw-node-x-coord right-node))
               (current-gap (- right-x left-x))
               (min-separation (dag-draw--calculate-separation graph left-node-id right-node-id))
               (excess-space (- current-gap min-separation)))

          (when (> excess-space 5)  ; Minimum threshold for compaction
            (push (list :left-node left-node-id
                        :right-node right-node-id
                        :can-compact t
                        :savings excess-space
                        :current-gap current-gap
                        :min-separation min-separation)
                  opportunities)))))
    opportunities))

(defun dag-draw--packcut-compact-layout (graph)
  "Apply GKNV packcut() compaction algorithm to reduce layout width.
Sweeps layout from left to right, searching for blocks that can
be compacted.  Based on GKNV specification: `For each node, if all
the nodes to the right of it can be shifted to the left by some
increment without violating any positioning constraints, the shift
is performed.'
Argument GRAPH ."
  (let ((ranks (dag-draw--get-graph-ranks graph)))
    ;; Process each rank independently
    (dolist (rank ranks)
      (dag-draw--packcut-compact-rank graph rank))))

(defun dag-draw--packcut-compact-rank (graph rank)
  "Apply packcut compaction to a single RANK in GRAPH.
Implements left-to-right sweep compaction within the rank."
  (let ((nodes-in-rank (dag-draw--get-nodes-in-rank-sorted-by-x graph rank)))
    (when (>= (length nodes-in-rank) 2)
      ;; Sweep from left to right, compacting gaps
      (dotimes (i (1- (length nodes-in-rank)))
        (let* ((left-node-id (nth i nodes-in-rank))
               (right-node-id (nth (1+ i) nodes-in-rank))
               (compaction-amount (dag-draw--calculate-compaction-amount
                                   graph left-node-id right-node-id)))
          (when (> compaction-amount 0)
            ;; Shift right node and all nodes to its right
            (dag-draw--shift-nodes-right-of-position graph rank
                                                     (dag-draw-node-x-coord
                                                      (dag-draw-get-node graph right-node-id))
                                                     (- compaction-amount))))))))

(defun dag-draw--calculate-compaction-amount (graph left-node-id right-node-id)
  "Calculate how much RIGHT-NODE can be shifted left toward LEFT-NODE.
Returns the amount of compaction possible while respecting GKNV constraints.
Argument GRAPH .
Argument LEFT-NODE-ID .
Argument RIGHT-NODE-ID ."
  (let* ((left-node (dag-draw-get-node graph left-node-id))
         (right-node (dag-draw-get-node graph right-node-id))
         (left-x (dag-draw-node-x-coord left-node))
         (right-x (dag-draw-node-x-coord right-node))
         (current-gap (- right-x left-x))
         (min-separation (dag-draw--calculate-separation graph left-node-id right-node-id))
         (excess-space (- current-gap min-separation)))

    ;; Return compaction amount (positive means can compact)
    (max 0 (- excess-space 2))))  ; Leave smaller buffer for more aggressive compaction

(defun dag-draw--shift-nodes-right-of-position (graph rank x-threshold shift-amount)
  "Shift all nodes in RANK that are right of X-THRESHOLD by SHIFT-AMOUNT.
SHIFT-AMOUNT should be negative for leftward movement (compaction).
Argument GRAPH ."
  (ht-each (lambda (_node-id node)
             (when (and (dag-draw-node-rank node)
                        (= (dag-draw-node-rank node) rank)
                        (>= (dag-draw-node-x-coord node) x-threshold))
               ;; Shift this node
               (setf (dag-draw-node-x-coord node)
                     (+ (dag-draw-node-x-coord node) shift-amount))))
           (dag-draw-graph-nodes graph)))

(defun dag-draw--calculate-layout-width (graph)
  "Calculate total width of the layout from leftmost to rightmost node.
Argument GRAPH ."
  (let ((min-x most-positive-fixnum)
        (max-x most-negative-fixnum))
    (ht-each (lambda (_node-id node)
               (let ((x (dag-draw-node-x-coord node)))
                 (when x
                   (setq min-x (min min-x x))
                   (setq max-x (max max-x x)))))
             (dag-draw-graph-nodes graph))
    (if (and (< min-x most-positive-fixnum)
             (> max-x most-negative-fixnum))
        (- max-x min-x)
      0)))

;; Note: dag-draw--get-graph-ranks is defined in dag-draw-quality.el

;;; GKNV Section 4.2: Network Simplex Constraint Solver

(defun dag-draw--build-constraint-auxiliary-graph (graph)
  "Build auxiliary GRAPH for GKNV Section 4.2 constraint solver.
Per GKNV specification: `Every edge e=(u,v) in G is replaced by
two edges (n_e,u) and (n_e,v) with δ=0 and ω=ω(e)×Ω(e).  If v is
the left neighbor of w, then G' has an edge f=(v,w) with
δ(f)=ρ(v,w) and ω(f)=0.'"
  (let ((aux-graph (dag-draw-create-graph)))

    ;; Copy all original nodes to auxiliary graph
    (ht-each (lambda (node-id node)
               (dag-draw-add-node aux-graph node-id (dag-draw-node-label node))
               ;; Copy node properties
               (let ((aux-node (dag-draw-get-node aux-graph node-id)))
                 (setf (dag-draw-node-rank aux-node) (dag-draw-node-rank node))
                 (setf (dag-draw-node-x-coord aux-node) (dag-draw-node-x-coord node))
                 (setf (dag-draw-node-y-coord aux-node) (dag-draw-node-y-coord node))))
             (dag-draw-graph-nodes graph))

    ;; Create auxiliary nodes and cost edges for each original edge
    (dolist (edge (dag-draw-graph-edges graph))
      (let* ((from-node (dag-draw-edge-from-node edge))
             (to-node (dag-draw-edge-to-node edge))
             (edge-weight (or (dag-draw-edge-weight edge) 1))
             ;; GKNV Section 4.2, line 1418: Edge Cost Node n_e
             (ne-node-id (intern (format "n_e_%s_%s" from-node to-node)))
             (omega-factor (dag-draw--calculate-omega-factor from-node to-node))
             (cost-weight (* edge-weight omega-factor)))

        ;; Create n_e edge cost node per GKNV terminology
        (dag-draw-add-node aux-graph ne-node-id (format "n_e_%s_%s" from-node to-node))

        ;; Set n_e node to a separate rank to avoid separation edge conflicts
        ;; Cost nodes don't participate in rank-based separation
        (let ((ne-node (dag-draw-get-node aux-graph ne-node-id)))
          (setf (dag-draw-node-rank ne-node) -1))  ; Use rank -1 for cost nodes

        ;; GKNV Section 4.2, line 1420: Create cost encoding edges (n_e, u) and (n_e, v)
        ;; With δ=0 and ω=ω(e)×Ω(e) per GKNV specification
        (let ((attrs1 (ht-create))
              (attrs2 (ht-create)))
          (ht-set attrs1 'min-length 0)  ; GKNV δ(n_e→u) = 0 for cost encoding edges
          (ht-set attrs2 'min-length 0)  ; GKNV δ(n_e→v) = 0 for cost encoding edges
          (dag-draw-add-edge aux-graph ne-node-id from-node cost-weight nil attrs1)
          (dag-draw-add-edge aux-graph ne-node-id to-node cost-weight nil attrs2))))

    ;; Create separation edges for adjacent nodes in same rank
    (ht-each (lambda (_rank nodes-in-rank)
               (when (> (length nodes-in-rank) 1)
                 ;; Sort nodes by X coordinate to establish left-right order
                 (let ((sorted-nodes (sort (copy-sequence nodes-in-rank)
                                           (lambda (a b)
                                             (< (or (dag-draw-node-x-coord
                                                     (dag-draw-get-node aux-graph a)) 0)
                                                (or (dag-draw-node-x-coord
                                                     (dag-draw-get-node aux-graph b)) 0))))))
                   ;; Create separation edges between adjacent nodes
                   (dotimes (i (1- (length sorted-nodes)))
                     (let* ((left-node (nth i sorted-nodes))
                            (right-node (nth (1+ i) sorted-nodes))
                            (separation (dag-draw--calculate-separation aux-graph left-node right-node)))
                       ;; Create separation edge: (left, right) with δ=ρ(left,right), ω=0
                       (let ((sep-attrs (ht-create)))
                         (ht-set sep-attrs 'min-length separation)  ; GKNV δ(u,v) = ρ(u,v) separation constraint
                         (dag-draw-add-edge aux-graph left-node right-node 0 nil sep-attrs)))))))
             (dag-draw--group-nodes-by-rank aux-graph))

    aux-graph))

(defun dag-draw--calculate-omega-factor (from-node to-node)
  "Calculate Ω factor for edge cost per GKNV specification.
Edges between virtual nodes get higher weights to favor straightening.
Argument FROM-NODE .
Argument TO-NODE ."
  (let ((from-virtual (dag-draw--is-virtual-node-p from-node))
        (to-virtual (dag-draw--is-virtual-node-p to-node)))
    (cond
     ;; Both virtual nodes - highest priority for straightening
     ((and from-virtual to-virtual) 8)
     ;; One virtual, one real - medium priority
     ((or from-virtual to-virtual) 2)
     ;; Both real nodes - lowest priority (already straight)
     (t 1))))

(defun dag-draw--group-nodes-by-rank (graph)
  "Group nodes by their rank for separation edge creation.
Argument GRAPH ."
  (let ((rank-groups (ht-create)))
    (ht-each (lambda (node-id node)
               (let ((rank (or (dag-draw-node-rank node) 0)))
                 (ht-set rank-groups rank
                         (cons node-id (or (ht-get rank-groups rank) '())))))
             (dag-draw-graph-nodes graph))
    rank-groups))


(defun dag-draw--network-simplex-x-coordinates (aux-graph)
  "Apply network simplex algo to auxiliary graph for X coordinate optimization.
Reuses existing network simplex infrastructure but optimizes
X coordinates instead of ranks.
Argument AUX-GRAPH ."
  ;; For now, use a simplified approach that respects separation constraints
  ;; TODO: Full network simplex implementation for X coordinates
  (dag-draw--simple-x-coordinate-solver aux-graph))

(defun dag-draw--simple-x-coordinate-solver (aux-graph)
  "Simplified constraint solver that minimizes GKNV cost function.
Implements iterative cost minimization with separation constraint compliance.
Argument AUX-GRAPH ."
  ;; Initialize all nodes to reasonable starting positions
  (dag-draw--initialize-x-coordinates aux-graph)

  ;; Multiple iterations to converge on optimal positioning
  ;; GKNV edge straightening requires more iterations for proper convergence
  (dotimes (_iteration 30)  ; More iterations for better edge straightening
    (dag-draw--gknv-cost-minimization-iteration aux-graph))

  ;; Final cleanup to ensure separation constraints
  (dag-draw--enforce-separation-constraints aux-graph))

(defun dag-draw--initialize-x-coordinates (aux-graph)
  "Initialize X coordinates for all nodes in auxiliary graph.
Argument AUX-GRAPH ."
  (let ((current-x 0)
        (node-spacing 100))  ; Default spacing
    (ht-each (lambda (_node-id node)
               (unless (dag-draw-node-x-coord node)
                 (setf (dag-draw-node-x-coord node) current-x)
                 (setq current-x (+ current-x node-spacing))))
             (dag-draw-graph-nodes aux-graph))))

(defun dag-draw--gknv-cost-minimization-iteration (aux-graph)
  "One iteration of GKNV cost minimization across all nodes.
Updates each node's X coordinate to minimize the GKNV cost function.
Argument AUX-GRAPH ."
  ;; Update each node's position based on cost minimization
  (ht-each (lambda (node-id node)
             (let ((new-x (dag-draw--calculate-cost-minimizing-position aux-graph node-id)))
               (setf (dag-draw-node-x-coord node) new-x)))
           (dag-draw-graph-nodes aux-graph)))


(defun dag-draw--calculate-cost-minimizing-position (aux-graph node-id)
  "Calculate X position that minimizes GKNV cost function for NODE-ID.
Per GKNV Section 4.2: minimize Σ Ω(e)×ω(e)×|x_w - x_v| for L1
norm optimization.  Per GKNV line 1241: `chains may be aligned
vertically and thus straightened'.
Argument AUX-GRAPH ."
  ;; Standard cost-based positioning with enhanced edge straightening
  (let ((weighted-positions '()))
    ;; Collect all cost edges (weight > 0) connected to this node
    (dolist (edge (dag-draw-graph-edges aux-graph))
      (let ((weight (dag-draw-edge-weight edge)))
        (when (> weight 0)  ; Only cost edges, not separation edges (weight=0)
          (cond
           ;; Node is source of edge - minimize distance to target
           ((eq (dag-draw-edge-from-node edge) node-id)
            (let* ((target-id (dag-draw-edge-to-node edge))
                   (target-node (dag-draw-get-node aux-graph target-id))
                   (target-x (or (dag-draw-node-x-coord target-node) 0)))
              (push (cons target-x weight) weighted-positions)))
           ;; Node is target of edge - minimize distance to source
           ((eq (dag-draw-edge-to-node edge) node-id)
            (let* ((source-id (dag-draw-edge-from-node edge))
                   (source-node (dag-draw-get-node aux-graph source-id))
                   (source-x (or (dag-draw-node-x-coord source-node) 0)))
              (push (cons source-x weight) weighted-positions)))))))

    ;; Calculate weighted median for L1 norm minimization
    (if weighted-positions
        (dag-draw--calculate-cost-weighted-median weighted-positions)
      0)))

(defun dag-draw--calculate-cost-weighted-median (weighted-positions)
  "Calculate weighted median from list of (position . weight) pairs.
This minimizes the L1 norm cost function Σ weight×|x - position|.
Argument WEIGHTED-POSITIONS ."
  (when weighted-positions
    ;; Sort positions by X coordinate
    (let* ((sorted-positions (sort (copy-sequence weighted-positions)
                                   (lambda (a b) (< (car a) (car b)))))
           (total-weight (apply #'+ (mapcar #'cdr sorted-positions)))
           (half-weight (/ total-weight 2.0))
           (cumulative-weight 0))

      ;; Find the weighted median
      (catch 'found
        (dolist (pos-weight sorted-positions)
          (let ((position (car pos-weight))
                (weight (cdr pos-weight)))
            (setq cumulative-weight (+ cumulative-weight weight))
            (when (>= cumulative-weight half-weight)
              (throw 'found position))))
        ;; Fallback: return first position if no median found
        (car (car sorted-positions))))))

(defun dag-draw--enforce-separation-constraints (aux-graph)
  "Final pass to ensure all separation constraints are met.
Argument AUX-GRAPH ."
  (let ((rank-groups (dag-draw--group-nodes-by-rank aux-graph)))

    (ht-each (lambda (_rank nodes-in-rank)
               (when (> (length nodes-in-rank) 1)
                 ;; Sort nodes by current X position
                 (let ((sorted-nodes (sort (copy-sequence nodes-in-rank)
                                           (lambda (a b)
                                             (< (dag-draw-node-x-coord (dag-draw-get-node aux-graph a))
                                                (dag-draw-node-x-coord (dag-draw-get-node aux-graph b)))))))

                   ;; Adjust positions to meet separation constraints
                   (let ((current-x 0))
                     (dolist (node-id sorted-nodes)
                       (let ((node (dag-draw-get-node aux-graph node-id)))
                         (when node
                           (let ((required-x (max current-x (dag-draw-node-x-coord node))))
                             (setf (dag-draw-node-x-coord node) required-x)
                             (setq current-x (+ required-x (dag-draw--calculate-node-spacing aux-graph node-id)))))))))))
             rank-groups)))


(defun dag-draw--calculate-preferred-x-position (aux-graph node-id)
  "Calculate preferred X position for NODE-ID based on GKNV cost minimization.
According to GKNV paper: minimize Σ Ω(e)×ω(e)×|x_w - x_v| for all edges.
Argument AUX-GRAPH ."
  (let ((cost-edges '())
        (total-weight 0))

    ;; Find cost edges (weight > 0) connected to this node
    (dolist (edge (dag-draw-graph-edges aux-graph))
      (let ((weight (dag-draw-edge-weight edge)))
        (when (and (> weight 0)  ; Only cost edges, not separation edges
                   (or (eq (dag-draw-edge-from-node edge) node-id)
                       (eq (dag-draw-edge-to-node edge) node-id)))
          (let ((other-node-id (if (eq (dag-draw-edge-from-node edge) node-id)
                                   (dag-draw-edge-to-node edge)
                                 (dag-draw-edge-from-node edge))))
            (push (cons other-node-id weight) cost-edges)
            (setq total-weight (+ total-weight weight))))))

    ;; Calculate weighted average position based on GKNV cost function
    ;; Higher weights mean stronger attraction (nodes should be closer)
    (if (> total-weight 0)
        (let ((weighted-sum 0))
          (dolist (cost-edge cost-edges)
            (let* ((other-node-id (car cost-edge))
                   (edge-weight (cdr cost-edge))
                   (other-node (dag-draw-get-node aux-graph other-node-id))
                   (other-x (or (dag-draw-node-x-coord other-node) 0)))
              ;; Weight by edge importance - higher weight = stronger pull
              (setq weighted-sum (+ weighted-sum (* edge-weight other-x)))))
          (/ weighted-sum total-weight))
      0)))

(defun dag-draw--calculate-node-spacing (graph node-id)
  "Calculate spacing needed after NODE-ID for next node.
Argument GRAPH ."
  (let* ((node (dag-draw-get-node graph node-id))
         (node-width (if node (dag-draw-node-x-size node) 60))
         (nodesep (or (dag-draw-graph-node-separation graph) 2)))
    (+ node-width nodesep)))

;;; Helper functions for TDD tests




(defun dag-draw--get-nodes-in-rank (graph rank)
  "Get all nodes in specified RANK.
Argument GRAPH ."
  (let ((nodes-in-rank '()))
    (ht-each (lambda (node-id node)
               (when (= (or (dag-draw-node-rank node) 0) rank)
                 (push node-id nodes-in-rank)))
             (dag-draw-graph-nodes graph))
    nodes-in-rank))

(defun dag-draw--position-with-auxiliary-graph (graph)
  "Position nodes using GKNV auxiliary GRAPH method (Section 4.2).
Creates constraint auxiliary graph and applies network simplex for
optimal X-coordinates."
  (let ((aux-graph (dag-draw--build-constraint-auxiliary-graph graph)))
    ;; Apply network simplex to auxiliary graph for X-coordinate optimization
    (dag-draw--network-simplex-x-coordinates aux-graph)

    ;; Extract X-coordinates from auxiliary graph back to original graph
    (dag-draw--extract-x-coordinates-from-auxiliary aux-graph graph)))

(defun dag-draw--extract-x-coordinates-from-auxiliary (aux-graph original-graph)
  "Extract X-coordinates from auxiliary graph to original graph.
Only copies coordinates for original nodes, ignoring auxiliary
edge nodes.
Argument AUX-GRAPH .
Argument ORIGINAL-GRAPH ."
  (ht-each (lambda (node-id node)
             ;; Only copy coordinates for original nodes (not auxiliary edge nodes)
             (unless (string-match "^aux_edge_" (symbol-name node-id))
               (let ((original-node (dag-draw-get-node original-graph node-id)))
                 (when original-node
                   (setf (dag-draw-node-x-coord original-node)
                         (dag-draw-node-x-coord node))))))
           (dag-draw-graph-nodes aux-graph)))

;;; ASCII-native coordinate functions

(defun dag-draw--assign-y-coordinates-ascii (graph)
  "ASCII-native Y coordinate assignment working directly in grid coordinates.
Per GKNV Section 4: Y coordinates determined by rank,
same for all nodes in rank.
In ASCII mode, we work directly in integer
grid coordinates to prevent collapse.
Argument GRAPH ."

  ;; Get rank information from nodes
  (let ((rank-to-nodes (ht-create))
        (max-rank -1))

    ;; Group nodes by rank
    (ht-each (lambda (_node-id node)
               (let ((rank (or (dag-draw-node-rank node) 0)))
                 (setq max-rank (max max-rank rank))
                 (unless (ht-get rank-to-nodes rank)
                   (ht-set! rank-to-nodes rank '()))
                 (ht-set! rank-to-nodes rank
                         (cons node (ht-get rank-to-nodes rank)))))
             (dag-draw-graph-nodes graph))

    ;; Assign ASCII grid Y coordinates directly
    ;; Use the graph's configured rank-separation (D3.6: Y = rank × ranksep)
    (let ((rank-separation (dag-draw-graph-rank-separation graph)))
      (ht-each (lambda (rank nodes)
                 (let ((y-coord (* rank rank-separation)))
                   (dolist (node nodes)
                     (setf (dag-draw-node-y-coord node) y-coord))))
               rank-to-nodes))))

(defun dag-draw--position-with-auxiliary-graph-ascii (graph)
  "ASCII-native X coordinate positioning in grid coordinates.
Per GKNV Section 4.2: Use auxiliary GRAPH method but with ASCII
integer constraints."

  ;; Start with high-resolution positioning to get optimal layout
  (dag-draw--position-with-auxiliary-graph graph)

  ;; Convert to ASCII grid coordinates with proper spacing
  ;; Group nodes by rank to ensure consistent horizontal spacing
  (let ((rank-groups (ht-create))
        (_ascii-node-separation 25))  ; Reasonable horizontal spacing between node boundaries

    ;; Group nodes by rank
    (ht-each (lambda (_node-id node)
               (let ((rank (or (dag-draw-node-rank node) 0)))
                 (unless (ht-get rank-groups rank)
                   (ht-set! rank-groups rank '()))
                 (ht-set! rank-groups rank
                         (cons node (ht-get rank-groups rank)))))
             (dag-draw-graph-nodes graph))

    ;; For each rank, assign ASCII X coordinates with dynamic spacing
    ;; Per GKNV Section 1.2: nodesep(G) - minimum horizontal separation between node boxes
    (ht-each (lambda (_rank nodes)
               ;; Sort nodes by their ASSIGNED ORDER (respects Pass 2 ordering)
               (let ((sorted-nodes (sort nodes
                                        (lambda (a b)
                                          (< (or (dag-draw-node-order a) 0)
                                             (or (dag-draw-node-order b) 0)))))
                     (ascii-x 5))  ; Start with left padding

                 ;; Assign dynamically spaced ASCII X coordinates using ρ(a,b) separation formula
                 (dolist (node sorted-nodes)
                   (setf (dag-draw-node-x-coord node) ascii-x)
                   ;; Calculate spacing to next node using GKNV ρ(a,b) formula
                   ;; ρ(a,b) = (xsize(a) + xsize(b))/2 + nodesep(G)
                   ;; For now, use node's xsize + nodesep as spacing
                   (let* ((node-xsize (dag-draw-node-x-size node))
                          (nodesep (dag-draw-graph-node-separation graph))
                          (spacing (+ node-xsize nodesep)))
                     ;; Next node starts after this node's bounding box + separation
                     (setq ascii-x (+ ascii-x spacing))))))
             rank-groups)))

(defun dag-draw--round-coordinates-for-ascii (graph)
  "Round all coordinates to ASCII-friendly integer values.
Argument GRAPH ."
  (ht-each (lambda (_node-id node)
             (let ((x (dag-draw-node-x-coord node))
                   (y (dag-draw-node-y-coord node)))
               (when x (setf (dag-draw-node-x-coord node) (round x)))
               (when y (setf (dag-draw-node-y-coord node) (round y)))))
           (dag-draw-graph-nodes graph)))

(defun dag-draw--ensure-ascii-spacing (graph)
  "Ensure minimum ASCII spacing between nodes to prevent overlap.
Argument GRAPH ."
  (let ((node-list (ht-values (dag-draw-graph-nodes graph)))
        (min-spacing 5))  ; Minimum spacing for ASCII readability
    ;; Sort by X coordinate
    (setq node-list (sort node-list (lambda (a b)
                                     (< (or (dag-draw-node-x-coord a) 0)
                                        (or (dag-draw-node-x-coord b) 0)))))

    ;; Adjust spacing
    (let ((current-x 5))  ; Start with padding
      (dolist (node node-list)
        (when (dag-draw-node-x-coord node)
          (when (< (dag-draw-node-x-coord node) current-x)
            (setf (dag-draw-node-x-coord node) current-x))
          (setq current-x (+ (dag-draw-node-x-coord node) min-spacing)))))))

(provide 'dag-draw-pass3-positioning)

;;; dag-draw-pass3-positioning.el ends here
