;;; dag-draw-pass2-ordering.el --- Vertex ordering 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 2 (Ordering) of the GKNV graph drawing algorithm
;; as specified in "A Technique for Drawing Directed Graphs" (Gansner, Koutsofios,
;; North, Vo).
;;
;; GKNV Reference: Section 3 (lines 891-1192), Figures 3-1, 3-2, 3-3
;; Decisions: D2.1 (Initial order), D2.2 (Weighted median), D2.3 (Max iterations),
;;            D2.4 (Transpose), D2.5 (No-adjacent handling), D2.6 (Flat edges),
;;            D2.7 (Tie-breaking), D2.8 (Virtual nodes), D2.9 (Self-loops)
;; Algorithm: Weighted median heuristic with transposition
;;
;; Key Requirements:
;; - Create virtual nodes for long edges before ordering
;; - Use biased weighted median (GKNV innovation)
;; - Apply transpose heuristic for 20-50% improvement
;; - 24 iterations fixed (adaptive termination possible)
;; - Alternating up/down sweeps through ranks
;; - Nodes with no adjacency keep current position
;;
;; Baseline Status: ✅ Compliant
;;
;; GKNV Section 3 states: "Generally, the weighted median is biased toward the side
;; where vertices are more closely packed." (Innovation: weighted interpolation)
;;
;; See doc/implementation-decisions.md (D2.1-D2.9) for full decision rationale.

;;; Code:

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

;;; Virtual Nodes for Long Edges

(defun dag-draw--create-virtual-nodes (graph)
  "Create virtual nodes for edges spanning multiple ranks.
Returns a new GRAPH with virtual nodes inserted."
  (let ((new-graph (dag-draw-copy-graph graph))
        (virtual-counter 0))

    ;; Clear edges - we'll rebuild them with virtual nodes
    (setf (dag-draw-graph-edges new-graph) '())

    ;; Process each edge from original graph
    (dolist (edge (dag-draw-graph-edges graph))
      (let* ((nodes (dag-draw--edge-nodes graph edge))
             (from-rank (dag-draw-node-rank (car nodes)))
             (to-rank (dag-draw-node-rank (cdr nodes)))
             (rank-span (- to-rank from-rank)))

        (if (<= rank-span 1)
            ;; Edge spans only one rank - add directly
            (push edge (dag-draw-graph-edges new-graph))

          ;; Edge spans multiple ranks - add virtual nodes
          (let ((prev-node-id (dag-draw-edge-from-node edge)))
            (dotimes (i (1- rank-span))
              (let* ((virtual-id (intern (format "virtual_%d" (cl-incf virtual-counter))))
                     (virtual-rank (+ from-rank i 1))
                     (virtual-node (dag-draw-node-create
                                   :id virtual-id
                                   :label ""
                                   :x-size 1  ; Minimal size
                                   :y-size 1
                                   :rank virtual-rank)))

                ;; Add virtual node to graph
                (ht-set! (dag-draw-graph-nodes new-graph) virtual-id virtual-node)

                ;; Add edge from previous to virtual
                (let ((virtual-edge (dag-draw-edge-create
                                    :from-node prev-node-id
                                    :to-node virtual-id
                                    :weight (dag-draw-edge-weight edge))))
                  (push virtual-edge (dag-draw-graph-edges new-graph)))

                (setq prev-node-id virtual-id)))

            ;; Add final edge from last virtual to target
            (let ((final-edge (dag-draw-edge-create
                              :from-node prev-node-id
                              :to-node (dag-draw-edge-to-node edge)
                              :weight (dag-draw-edge-weight edge))))
              (push final-edge (dag-draw-graph-edges new-graph)))))))

    new-graph))

;;; Rank Organization

(defun dag-draw--organize-by-ranks (graph)
  "Organize nodes by rank into a list of lists.
Returns a vector where index i contains list of nodes at rank i.
Calculates actual max rank from nodes if GRAPH max-rank is not set correctly."
  ;; Calculate actual max rank from all nodes (GKNV algorithm compliance)
  (let ((actual-max-rank 0))
    (ht-each (lambda (_node-id node)
               (let ((rank (dag-draw-node-rank node)))
                 (when (and rank (> rank actual-max-rank))
                   (setq actual-max-rank rank))))
             (dag-draw-graph-nodes graph))

    ;; Use calculated max rank or graph's max rank, whichever is larger
    (let* ((graph-max-rank (or (dag-draw-graph-max-rank graph) 0))
           (max-rank (max actual-max-rank graph-max-rank))
           (ranks (make-vector (1+ max-rank) '())))

      ;; Group nodes by rank
      (ht-each (lambda (node-id node)
                 (let ((rank (or (dag-draw-node-rank node) 0)))
                   (when (<= rank max-rank)
                     (push node-id (aref ranks rank)))))
               (dag-draw-graph-nodes graph))

      ;; Reverse each rank list to maintain insertion order
      (dotimes (i (length ranks))
        (setf (aref ranks i) (nreverse (aref ranks i))))

      ranks)))

;;; Edge Crossing Calculation

(defun dag-draw--count-crossings-between-ranks (graph rank1-nodes rank2-nodes)
  "Count edge crossings between two adjacent ranks.
Argument GRAPH .
Argument RANK1-NODES .
Argument RANK2-NODES ."
  (let ((crossings 0)
        (edges-between '()))

    ;; Collect edges between the two ranks
    (dolist (from-node rank1-nodes)
      (dolist (edge (dag-draw-get-edges-from graph from-node))
        (when (member (dag-draw-edge-to-node edge) rank2-nodes)
          (push edge edges-between))))

    ;; Count crossings between edge pairs
    (let ((edge-list edges-between))
      (while edge-list
        (let ((edge1 (car edge-list)))
          (dolist (edge2 (cdr edge-list))
            (when (dag-draw--edges-cross-p graph edge1 edge2
                                          rank1-nodes rank2-nodes)
              (setq crossings (1+ crossings))))
          (setq edge-list (cdr edge-list)))))

    crossings))

(defun dag-draw--edges-cross-p (_graph edge1 edge2 rank1-nodes rank2-nodes)
  "Check if two edges cross given the current node ordering.
Argument GRAPH .
Argument EDGE1 .
Argument EDGE2 .
Argument RANK1-NODES .
Argument RANK2-NODES ."
  (let ((from1 (dag-draw-edge-from-node edge1))
        (to1 (dag-draw-edge-to-node edge1))
        (from2 (dag-draw-edge-from-node edge2))
        (to2 (dag-draw-edge-to-node edge2)))

    (let ((pos1-from (cl-position from1 rank1-nodes))
          (pos1-to (cl-position to1 rank2-nodes))
          (pos2-from (cl-position from2 rank1-nodes))
          (pos2-to (cl-position to2 rank2-nodes)))

      ;; Edges cross if relative order is different in the two ranks
      (and pos1-from pos1-to pos2-from pos2-to
           (not (eq (< pos1-from pos2-from)
                    (< pos1-to pos2-to)))))))

;;; Weighted Median Heuristic

(defun dag-draw--calculate-median-position (graph node-id adjacent-rank-nodes &optional size-aware)
  "Calculate median position for a node based on adjacent rank.
If SIZE-AWARE is non-nil, consider node sizes to prevent overlaps.
Argument GRAPH .
Argument NODE-ID .
Argument ADJACENT-RANK-NODES ."
  (let ((adjacent-positions '())
        (adjacent-sizes '()))

    ;; Collect positions of adjacent nodes
    (dolist (edge (dag-draw-get-edges-from graph node-id))
      (let* ((target (dag-draw-edge-to-node edge))
            (pos (cl-position target adjacent-rank-nodes)))
        (when pos
          (push pos adjacent-positions)
          (when size-aware
            (let ((target-node (dag-draw-get-node graph target)))
              (push (list :width (dag-draw-node-x-size target-node)
                         :height (dag-draw-node-y-size target-node))
                    adjacent-sizes))))))

    (dolist (edge (dag-draw-get-edges-to graph node-id))
      (let* ((source (dag-draw-edge-from-node edge))
            (pos (cl-position source adjacent-rank-nodes)))
        (when pos
          (push pos adjacent-positions)
          (when size-aware
            (let ((source-node (dag-draw-get-node graph source)))
              (push (list :width (dag-draw-node-x-size source-node)
                         :height (dag-draw-node-y-size source-node))
                    adjacent-sizes))))))

    (if (null adjacent-positions)
        -1.0  ; Special value for nodes with no adjacent connections
      (if size-aware
          (dag-draw--weighted-median adjacent-positions (reverse adjacent-sizes))
        (dag-draw--weighted-median adjacent-positions)))))

(defun dag-draw--weighted-median (positions &optional node-sizes)
  "Calculate weighted median of POSITIONS with optional size-aware spacing.
This implements the biased median described in the GKNV paper, enhanced with
size-aware adjustments to prevent overlaps when NODE-SIZES is provided."
  (if (null positions)
      0.0
    (if (null node-sizes)
        ;; Traditional median calculation
        (let ((sorted-pos (sort positions #'<))
              (len (length positions)))
          (cond
           ;; Single position
           ((= len 1)
            (float (car sorted-pos)))

           ;; Two positions - average
           ((= len 2)
            (/ (+ (car sorted-pos) (cadr sorted-pos)) 2.0))

           ;; Odd number - true median
           ((cl-oddp len)
            (float (nth (/ len 2) sorted-pos)))

           ;; Even number - weighted average of two middle elements
           (t
            (let* ((mid (/ len 2))
                   (left-pos (nth (1- mid) sorted-pos))
                   (right-pos (nth mid sorted-pos))
                   (left-extent (- left-pos (car sorted-pos)))
                   (right-extent (- (car (last sorted-pos)) right-pos)))

              ;; Bias toward side with more spread
              (if (= (+ left-extent right-extent) 0)
                  (/ (+ left-pos right-pos) 2.0)
                (/ (+ (* right-pos left-extent) (* left-pos right-extent))
                   (+ left-extent right-extent)))))))
      ;; Size-aware median calculation
      (dag-draw--size-aware-weighted-median positions node-sizes))))

(defun dag-draw--basic-weighted-median (positions)
  "Calculate basic weighted median without size considerations.
This implements the biased median described in the GKNV paper.
Argument POSITIONS ."
  (if (null positions)
      0.0
    (let ((sorted-pos (sort positions #'<))
          (len (length positions)))
      (cond
       ;; Single position
       ((= len 1)
        (float (car sorted-pos)))

       ;; Two positions - average
       ((= len 2)
        (/ (+ (car sorted-pos) (cadr sorted-pos)) 2.0))

       ;; Odd number - true median
       ((cl-oddp len)
        (float (nth (/ len 2) sorted-pos)))

       ;; Even number - weighted average of two middle elements
       (t
        (let* ((mid (/ len 2))
               (left-pos (nth (1- mid) sorted-pos))
               (right-pos (nth mid sorted-pos))
               (left-extent (- left-pos (car sorted-pos)))
               (right-extent (- (car (last sorted-pos)) right-pos)))

          ;; Bias toward side with more spread
          (if (= (+ left-extent right-extent) 0)
              (/ (+ left-pos right-pos) 2.0)
            (/ (+ (* right-pos left-extent) (* left-pos right-extent))
               (+ left-extent right-extent)))))))))

(defun dag-draw--size-aware-weighted-median (positions node-sizes)
  "Calculate size-aware weighted median that prevents overlaps.
POSITIONS is list of position values, NODE-SIZES is list of size plists."
  (if (or (= (length positions) 1) (null node-sizes))
      ;; Fall back to basic median if no size info or single position
      (dag-draw--basic-weighted-median positions)
    ;; Create position-size pairs and sort by position
  (let* ((pos-size-pairs (cl-mapcar (lambda (pos size)
                                     (list pos (plist-get size :width) (plist-get size :height)))
                                   positions node-sizes))
         (sorted-pairs (sort pos-size-pairs (lambda (a b) (< (car a) (car b)))))
         (adjusted-positions '()))

    ;; Calculate spacing between nodes to prevent overlaps
    (let ((current-pos (caar sorted-pairs))
          (current-pair (car sorted-pairs)))
      (push current-pos adjusted-positions)

      (dolist (pair (cdr sorted-pairs))
        (let* ((desired-pos (car pair))
               (node-width (cadr pair))
               (prev-width (cadr current-pair))
               ;; Minimum separation needed to prevent overlap
               (min-separation (+ (/ prev-width 2.0) (/ node-width 2.0) 2.0))) ; +2 for buffer

          ;; Adjust position if it would cause overlap
          (let ((min-allowed-pos (+ current-pos min-separation)))
            (setq current-pos (max desired-pos min-allowed-pos))
            (setq current-pair pair)
            (push current-pos adjusted-positions))))

      ;; Calculate median of adjusted positions
      (let ((final-positions (reverse adjusted-positions)))
        ;; Call basic median to avoid infinite recursion
        (dag-draw--basic-weighted-median final-positions))))))

;;; Node Ordering Within Ranks

(defun dag-draw--order-rank-by-median (graph rank-nodes adjacent-rank-nodes _direction &optional size-aware)
  "Order nodes in a rank using weighted median heuristic.
DIRECTION is `down' or `up' indicating sweep direction.
If SIZE-AWARE is non-nil, consider node sizes to prevent overlaps.
Argument GRAPH .
Argument RANK-NODES .
Argument ADJACENT-RANK-NODES ."
  (let ((nodes-with-medians '()))

    ;; Calculate median for each node
    (dolist (node-id rank-nodes)
      (let ((median (dag-draw--calculate-median-position
                     graph node-id adjacent-rank-nodes size-aware)))
        (push (cons node-id median) nodes-with-medians)))

    ;; Sort by median position
    (let ((sorted-pairs (sort nodes-with-medians
                             (lambda (a b) (< (cdr a) (cdr b))))))

      ;; Handle nodes with no connections (median = -1)
      (let ((connected-nodes '())
            (isolated-nodes '()))
        (dolist (pair sorted-pairs)
          (if (< (cdr pair) 0)
              (push (car pair) isolated-nodes)
            (push (car pair) connected-nodes)))

        ;; Return connected nodes first, then isolated
        (append (nreverse connected-nodes) (nreverse isolated-nodes))))))

;;; Local Transposition Optimization

(defun dag-draw--transpose-adjacent (graph ranks rank-idx)
  "Try transposing adjacent nodes within a rank to reduce crossings.
Argument GRAPH .
Argument RANKS .
Argument RANK-IDX ."
  (let ((rank-nodes (aref ranks rank-idx))
        (improved t)
        (total-improvement 0))

    ;; Only try transpose if we have multiple nodes
    (when (> (length rank-nodes) 1)
      (while improved
        (setq improved nil)

        ;; Try swapping each adjacent pair
        (dotimes (i (1- (length rank-nodes)))
          (let ((node1 (nth i rank-nodes))
                (node2 (nth (1+ i) rank-nodes)))

            ;; Calculate crossings before swap
            (let ((before-crossings (dag-draw--calculate-local-crossings
                                    graph ranks rank-idx i)))

              ;; Perform swap
              (setf (nth i rank-nodes) node2)
              (setf (nth (1+ i) rank-nodes) node1)

              ;; Calculate crossings after swap
              (let ((after-crossings (dag-draw--calculate-local-crossings
                                     graph ranks rank-idx i)))

                (let ((improvement (- before-crossings after-crossings)))
                  (if (> improvement 0)  ; Any positive improvement
                      ;; Keep the swap
                      (progn
                        (setq improved t)
                        (setq total-improvement (+ total-improvement improvement)))
                    ;; Revert the swap
                    (progn
                      (setf (nth i rank-nodes) node1)
                      (setf (nth (1+ i) rank-nodes) node2)))))))))

      ;; Update the ranks array
      (setf (aref ranks rank-idx) rank-nodes))

    total-improvement))

(defun dag-draw--calculate-local-crossings (graph ranks rank-idx pos)
  "Calculate crossings involving edges from position POS and POS+1 in rank.
Argument GRAPH .
Argument RANKS .
Argument RANK-IDX ."
  (let ((crossings 0))

    ;; Check crossings with previous rank
    (when (> rank-idx 0)
      (setq crossings (+ crossings
                        (dag-draw--count-crossings-between-ranks
                         graph
                         (list (nth pos (aref ranks rank-idx))
                               (nth (1+ pos) (aref ranks rank-idx)))
                         (aref ranks (1- rank-idx))))))

    ;; Check crossings with next rank
    (when (< rank-idx (1- (length ranks)))
      (setq crossings (+ crossings
                        (dag-draw--count-crossings-between-ranks
                         graph
                         (list (nth pos (aref ranks rank-idx))
                               (nth (1+ pos) (aref ranks rank-idx)))
                         (aref ranks (1+ rank-idx))))))

    crossings))

;;; Main Ordering Algorithm

(defun dag-draw-order-vertices (graph)
  "Order vertices within ranks to minimize edge crossings.

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

Implements GKNV Pass 2 (Section 3) using weighted median heuristic
and transposition with enhanced convergence detection.  Enhanced
with aesthetic principles A1-A4 evaluation per Section 1.1.

Returns the modified GRAPH with order assignments within each rank."
  (let* ((graph-with-virtuals (dag-draw--create-virtual-nodes graph))
         (ranks (dag-draw--organize-by-ranks graph-with-virtuals))
         (convergence-result (dag-draw--crossing-reduction-with-convergence
                             graph-with-virtuals ranks)))

    ;; Apply best ordering back to original graph
    (dag-draw--apply-ordering-to-graph graph (ht-get convergence-result 'best-ranks))

    ;; Log convergence information
    (when dag-draw-debug-output
      (message "Crossing reduction completed: iterations=%s crossings=%s converged=%s"
               (ht-get convergence-result 'iterations)
               (ht-get convergence-result 'final-crossings)
               (ht-get convergence-result 'converged)))

    ;; GKNV Section 1.1: Evaluate aesthetic principles for ordering decisions
    (let ((ordering-aesthetics (dag-draw--evaluate-ordering-aesthetics graph)))
      (when (> (plist-get ordering-aesthetics :crossing-count) 0)
        (when dag-draw-debug-output
          (message "GKNV A2: Edge crossings detected (%d) - visual anomalies present"
                   (plist-get ordering-aesthetics :crossing-count)))))

    graph))

(defun dag-draw--crossing-reduction-with-convergence (graph ranks)
  "Enhanced crossing reduction with sophisticated convergence detection.
Returns hash table with convergence information.
Argument GRAPH .
Argument RANKS ."
  (cl-block dag-draw--crossing-reduction-with-convergence
    (let* ((max-iterations 20)
           (convergence-threshold 5)
           (oscillation-window 8)
           (best-ranks (copy-sequence ranks))
           (best-crossings most-positive-fixnum)
           (iterations-without-improvement 0)
           (crossings-history '())
           (ranks-history '())
           (result (ht-create)))

    ;; Initial ordering
    (dag-draw--initialize-ordering graph ranks)
    (let ((initial-crossings (dag-draw--count-total-crossings graph ranks)))
      (setq best-crossings initial-crossings)
      (push initial-crossings crossings-history))

    ;; Iterative improvement with convergence detection
    (let ((iteration 0)
          (converged nil))

      (while (and (< iteration max-iterations)
                  (not converged))

        (let ((forward (= (mod iteration 2) 0))
              (_prev-crossings best-crossings))

          ;; Sweep through ranks
          (if forward
              ;; Forward pass (top to bottom)
              (dotimes (r (1- (length ranks)))
                (when (> (length (aref ranks (1+ r))) 1)
                  (setf (aref ranks (1+ r))
                        (dag-draw--order-rank-by-median
                         graph
                         (aref ranks (1+ r))
                         (aref ranks r)
                         'down
                         nil))))

            ;; Backward pass (bottom to top)
            (cl-loop for r from (- (length ranks) 2) downto 0 do
              (when (> (length (aref ranks r)) 1)
                (setf (aref ranks r)
                      (dag-draw--order-rank-by-median
                       graph
                       (aref ranks r)
                       (aref ranks (1+ r))
                       'up
                       nil)))))

          ;; Apply local transposition
          (dotimes (r (length ranks))
            (dag-draw--transpose-adjacent graph ranks r))

          ;; Check current solution quality
          (let ((current-crossings (dag-draw--count-total-crossings graph ranks)))
            (push current-crossings crossings-history)
            (push (copy-sequence ranks) ranks-history)

            ;; Update best solution
            (if (< current-crossings best-crossings)
                (progn
                  (setq best-crossings current-crossings)
                  (setq best-ranks (copy-sequence ranks))
                  (setq iterations-without-improvement 0))
              (setq iterations-without-improvement (1+ iterations-without-improvement)))

            ;; Check convergence conditions
            (setq converged (dag-draw--check-convergence
                           crossings-history
                           ranks-history
                           iterations-without-improvement
                           convergence-threshold
                           oscillation-window))

            (setq iteration (1+ iteration))))

      ;; Check for iteration limit reached
      (when (>= iteration max-iterations)
        (message "Reached iteration limit (%d), stopping" max-iterations))

      ;; Store results
      (ht-set! result 'best-ranks best-ranks)
      (ht-set! result 'final-crossings best-crossings)
      (ht-set! result 'iterations iteration)
      (ht-set! result 'converged converged)
      (ht-set! result 'crossings-history (reverse crossings-history)))

    result))))

(defun dag-draw--check-convergence (crossings-history _ranks-history
                                   iterations-without-improvement
                                   convergence-threshold oscillation-window)
  "Advanced convergence detection for crossing reduction algorithm.
Returns t if algorithm has converged.
Argument CROSSINGS-HISTORY .
Argument RANKS-HISTORY .
Argument ITERATIONS-WITHOUT-IMPROVEMENT .
Argument CONVERGENCE-THRESHOLD .
Argument OSCILLATION-WINDOW ."
  (cond
   ;; 1. No improvement for several iterations
   ((>= iterations-without-improvement convergence-threshold)
    t)

   ;; 2. Optimal solution found (zero crossings)
   ((and crossings-history (= (car crossings-history) 0))
    t)

   ;; 3. Oscillation detection - check if we're cycling between solutions
   ((and (>= (length crossings-history) oscillation-window)
         (dag-draw--detect-oscillation crossings-history oscillation-window))
    t)

   ;; 4. Diminishing returns - improvement rate is too slow
   ((and (>= (length crossings-history) 6)
         (dag-draw--detect-diminishing-returns crossings-history))
    t)

   ;; Continue optimization
   (t nil)))

(defun dag-draw--detect-oscillation (crossings-history window-size)
  "Detect if crossing counts are oscillating between the same values.
Argument CROSSINGS-HISTORY .
Argument WINDOW-SIZE ."
  (when (>= (length crossings-history) window-size)
    (let* ((recent-values (seq-take crossings-history window-size))
           (unique-values (seq-uniq recent-values)))
      ;; If we only have 2-3 unique values in recent history, likely oscillating
      (and (<= (length unique-values) 3)
           (> (length recent-values) (length unique-values))))))

(defun dag-draw--detect-diminishing-returns (crossings-history)
  "Detect if the rate of improvement has slowed significantly.
Argument CROSSINGS-HISTORY ."
  (when (>= (length crossings-history) 6)
    (let* ((recent-6 (seq-take crossings-history 6))
           (recent-3 (seq-take recent-6 3))
           (previous-3 (seq-drop recent-6 3))
           (recent-improvement (- (apply #'max recent-3) (apply #'min recent-3)))
           (previous-improvement (- (apply #'max previous-3) (apply #'min previous-3))))
      ;; If recent improvement is less than 10% of previous improvement
      (and (> previous-improvement 0)
           (< recent-improvement (* 0.1 previous-improvement))))))

(defun dag-draw--initialize-ordering (_graph ranks)
  "Initialize node ordering within RANKS.
Argument GRAPH ."
  ;; Simple initialization - keep existing order or randomize
  (dotimes (r (length ranks))
    (let ((rank-nodes (aref ranks r)))
      ;; For now, just keep the existing order
      ;; Could implement DFS-based initialization here
      (setf (aref ranks r) rank-nodes))))

(defun dag-draw--count-total-crossings (graph ranks)
  "Count total edge crossings in current ordering.
Argument GRAPH .
Argument RANKS ."
  (let ((total 0))
    (dotimes (r (1- (length ranks)))
      (setq total (+ total
                    (dag-draw--count-crossings-between-ranks
                     graph
                     (aref ranks r)
                     (aref ranks (1+ r))))))
    total))

(defun dag-draw--apply-ordering-to-graph (graph ranks)
  "Apply the computed ordering back to the original GRAPH nodes.
Argument RANKS ."
  (dotimes (r (length ranks))
    (let ((rank-nodes (aref ranks r))
          (order 0))
      (dolist (node-id rank-nodes)
        (let ((node (dag-draw-get-node graph node-id)))
          ;; Only set order for non-virtual nodes
          (when (and node (not (string-match "^virtual_" (symbol-name node-id))))
            (setf (dag-draw-node-order node) order)
            (setq order (1+ order))))))))

;;; Missing GKNV Functions for Advanced Crossing Reduction

(provide 'dag-draw-pass2-ordering)

;;; dag-draw-pass2-ordering.el ends here
