// Copyright (c) 2016 Kiel University and others.
// Copyright (c) 2026 The elk-go Authors.
//
// This program and the accompanying materials are made available under the
// terms of the Eclipse Public License 2.0 which is available at
// https://www.eclipse.org/legal/epl-2.0.
//
// SPDX-License-Identifier: EPL-2.0

package networksimplex

import 

const (
	removeSubtreesThreshold = 40
	fuzzySmallerThanZero    = -1e-10
)

// NetworkSimplex determines an optimal weighted layering of an acyclic graph.
type NetworkSimplex struct {
	graph                      *Graph
	previousLayeringNodeCounts []int
	balance                    bool
	iterationLimit             int

	edges             []EdgeID
	treeEdges         []EdgeID
	sources           []NodeID
	edgeVisited       []bool
	postOrder         int
	postOrderID       []int
	lowestPostOrderID []int
	cutvalue          []float64
	subtreeStack      []subtreeEntry
}

type subtreeEntry struct {
	node NodeID
	edge EdgeID
}

func ( *Graph) *NetworkSimplex {
	return &NetworkSimplex{graph: , iterationLimit: math.MaxInt}
}

func ( *NetworkSimplex) ( bool) *NetworkSimplex {
	.balance = 
	return 
}

func ( *NetworkSimplex) ( []int) *NetworkSimplex {
	.previousLayeringNodeCounts = append([]int(nil), ...)
	return 
}

func ( *NetworkSimplex) ( int) *NetworkSimplex {
	.iterationLimit = 
	return 
}

// Execute computes the layering and stores each result in Node.Layer.
func ( *NetworkSimplex) () {
	if len(.graph.Nodes) == 0 {
		return
	}
	for ,  := range append([]NodeID(nil), .graph.Nodes...) {
		.graph.Node().Layer = 0
	}
	 := len(.graph.Nodes) >= removeSubtreesThreshold
	if  {
		.removeSubtrees()
	}
	.initialize()
	.feasibleTree()
	,  := .leaveEdge()
	for  := 0;  &&  < .iterationLimit; ++ {
		,  := .enterEdge()
		if ! {
			panic("no entering edge found")
		}
		.exchange(, )
		,  = .leaveEdge()
	}
	if  {
		.reattachSubtrees()
	}
	 := .normalize()
	if .balance {
		.balanceLayers()
	}
}

func ( *NetworkSimplex) () {
	 := len(.graph.Nodes)
	for ,  := range append([]NodeID(nil), .graph.Nodes...) {
		.graph.Node().treeNode = false
	}
	.postOrderID = make([]int, )
	.lowestPostOrderID = make([]int, )
	.sources = .sources[:0]

	 := make([]EdgeID, 0)
	for ,  := range append([]NodeID(nil), .graph.Nodes...) {
		.graph.Node().internalID = 
		if len(.graph.Node().IncomingEdges) == 0 {
			.sources = append(.sources, )
		}
		 = append(, .graph.Node().OutgoingEdges...)
	}
	for ,  := range  {
		.graph.Edge().internalID = 
		.graph.Edge().treeEdge = false
	}
	.cutvalue = make([]float64, len())
	.edgeVisited = make([]bool, len())
	.edges = 
	.treeEdges = make([]EdgeID, 0, len())
	.postOrder = 1
}

func ( *NetworkSimplex) () {
	.subtreeStack = .subtreeStack[:0]
	 := make([]NodeID, 0)
	for ,  := range .graph.Nodes {
		if len(.graph.Node().ConnectedEdges()) == 1 {
			 = append(, )
		}
	}
	for len() > 0 {
		 := [0]
		 = [1:]
		 := .graph.Node().ConnectedEdges()
		if len() == 0 {
			continue
		}
		 := [0]
		 := len(.graph.Node().OutgoingEdges) != 0
		 := .graph.Edge().Other()
		if  {
			.graph.Node().IncomingEdges = removeFirst(.graph.Node().IncomingEdges, )
		} else {
			.graph.Node().OutgoingEdges = removeFirst(.graph.Node().OutgoingEdges, )
		}
		if len(.graph.Node().ConnectedEdges()) == 1 {
			 = append(, )
		}
		.subtreeStack = append(.subtreeStack, subtreeEntry{node: , edge: })
		.graph.Nodes = removeFirst(.graph.Nodes, )
	}
}

func ( *NetworkSimplex) () {
	for len(.subtreeStack) > 0 {
		 := len(.subtreeStack) - 1
		 := .subtreeStack[]
		.subtreeStack = .subtreeStack[:]
		 := .graph.Edge(.edge).Other(.node)
		if .graph.Edge(.edge).Target == .node {
			.graph.Node().OutgoingEdges = append(.graph.Node().OutgoingEdges, .edge)
			.graph.Node(.node).Layer = .graph.Node().Layer + .graph.Edge(.edge).Delta
		} else {
			.graph.Node().IncomingEdges = append(.graph.Node().IncomingEdges, .edge)
			.graph.Node(.node).Layer = .graph.Node().Layer - .graph.Edge(.edge).Delta
		}
		.graph.Nodes = append(.graph.Nodes, .node)
	}
}

func ( *NetworkSimplex) () {
	.topologicalLayering()
	if len(.edges) == 0 {
		return
	}
	clear(.edgeVisited)
	for .tightTreeDFS(.graph.Nodes[0]) < len(.graph.Nodes) {
		,  := .minimalSlack()
		if ! {
			panic("no minimal-slack edge found")
		}
		 := .graph.Edge()
		 := .graph.Node(.Target).Layer - .graph.Node(.Source).Layer - .Delta
		if .graph.Node(.Target).treeNode {
			 = -
		}
		for ,  := range append([]NodeID(nil), .graph.Nodes...) {
			if .graph.Node().treeNode {
				.graph.Node().Layer += 
			}
		}
		clear(.edgeVisited)
	}
	clear(.edgeVisited)
	.postorderTraversal(.graph.Nodes[0])
	.calculateCutvalues()
}

func ( *NetworkSimplex) () {
	 := make([]int, len(.graph.Nodes))
	for ,  := range .graph.Nodes {
		[.graph.Node().internalID] += len(.graph.Node().IncomingEdges)
	}
	 := append([]NodeID(nil), .sources...)
	for len() > 0 {
		 := [0]
		 = [1:]
		for ,  := range append([]EdgeID(nil), .graph.Node().OutgoingEdges...) {
			 := .graph.Edge()
			 := .Target
			 := .graph.Node().Layer + .Delta
			.graph.Node().Layer = max(.graph.Node().Layer, )
			 := .graph.Node().internalID
			[]--
			if [] == 0 {
				 = append(, )
			}
		}
	}
}

func ( *NetworkSimplex) ( NodeID) (int, int) {
	,  := math.MaxInt, math.MaxInt
	for ,  := range .graph.Node().ConnectedEdges() {
		 := .graph.Edge()
		 := .graph.Node(.Target).Layer - .graph.Node(.Source).Layer
		if .Target ==  &&  <  {
			 = 
		} else if  <  {
			 = 
		}
	}
	if  == math.MaxInt {
		 = -1
	}
	if  == math.MaxInt {
		 = -1
	}
	return , 
}

func ( *NetworkSimplex) ( NodeID) int {
	 := 1
	.graph.Node().treeNode = true
	for ,  := range .graph.Node().ConnectedEdges() {
		 := .graph.Edge().internalID
		if .edgeVisited[] {
			continue
		}
		.edgeVisited[] = true
		 := .graph.Edge().Other()
		if .graph.Edge().treeEdge {
			 += .()
			continue
		}
		 := .graph.Edge()
		 := .Delta == .graph.Node(.Target).Layer-.graph.Node(.Source).Layer
		if !.graph.Node().treeNode &&  {
			.graph.Edge().treeEdge = true
			.treeEdges = append(.treeEdges, )
			 += .()
		}
	}
	return 
}

func ( *NetworkSimplex) () (EdgeID, bool) {
	 := math.MaxInt
	var  EdgeID
	 := false
	for ,  := range .edges {
		 := .graph.Edge()
		if .graph.Node(.Source).treeNode == .graph.Node(.Target).treeNode {
			continue
		}
		 := .graph.Node(.Target).Layer - .graph.Node(.Source).Layer - .Delta
		if  <  {
			, ,  = , , true
		}
	}
	return , 
}

func ( *NetworkSimplex) ( NodeID) int {
	 := math.MaxInt
	for ,  := range .graph.Node().ConnectedEdges() {
		 := .graph.Edge().internalID
		if .graph.Edge().treeEdge && !.edgeVisited[] {
			.edgeVisited[] = true
			 = min(, .(.graph.Edge().Other()))
		}
	}
	 := .graph.Node().internalID
	.postOrderID[] = .postOrder
	.lowestPostOrderID[] = min(, .postOrder)
	.postOrder++
	return .lowestPostOrderID[]
}

func ( *NetworkSimplex) ( NodeID,  EdgeID) bool {
	 := .graph.Edge()
	 := .graph.Node(.Source).internalID
	 := .graph.Node(.Target).internalID
	 := .graph.Node().internalID
	if .lowestPostOrderID[] <= .postOrderID[] &&
		.postOrderID[] <= .postOrderID[] &&
		.lowestPostOrderID[] <= .postOrderID[] &&
		.postOrderID[] <= .postOrderID[] {
		return .postOrderID[] >= .postOrderID[]
	}
	return .postOrderID[] < .postOrderID[]
}

func ( *NetworkSimplex) () {
	 := make([]NodeID, 0)
	for ,  := range append([]NodeID(nil), .graph.Nodes...) {
		.graph.Node().unknownCutvalues = .graph.Node().unknownCutvalues[:0]
		for ,  := range .graph.Node().ConnectedEdges() {
			if .graph.Edge().treeEdge {
				.graph.Node().unknownCutvalues = append(.graph.Node().unknownCutvalues, )
			}
		}
		if len(.graph.Node().unknownCutvalues) == 1 {
			 = append(, )
		}
	}
	for ,  := range  {
		 := 
		for len(.graph.Node().unknownCutvalues) == 1 {
			 := .graph.Node().unknownCutvalues[0]
			 := .graph.Edge()
			 := .internalID
			.cutvalue[] = .Weight
			,  := .Source, .Target
			for ,  := range .graph.Node().ConnectedEdges() {
				if  ==  {
					continue
				}
				 := .graph.Edge()
				if .treeEdge {
					if  == .Source ||  == .Target {
						.cutvalue[] -= .cutvalue[.internalID] - .Weight
					} else {
						.cutvalue[] += .cutvalue[.internalID] - .Weight
					}
				} else if  ==  {
					if .Source ==  {
						.cutvalue[] += .Weight
					} else {
						.cutvalue[] -= .Weight
					}
				} else if .Source ==  {
					.cutvalue[] -= .Weight
				} else {
					.cutvalue[] += .Weight
				}
			}
			.graph.Node().unknownCutvalues = removeFirst(.graph.Node().unknownCutvalues, )
			.graph.Node().unknownCutvalues = removeFirst(.graph.Node().unknownCutvalues, )
			if  ==  {
				 = 
			} else {
				 = 
			}
		}
	}
}

func ( *NetworkSimplex) () (EdgeID, bool) {
	for ,  := range .treeEdges {
		 := .graph.Edge()
		if .treeEdge && .cutvalue[.internalID] < fuzzySmallerThanZero {
			return , true
		}
	}
	return 0, false
}

func ( *NetworkSimplex) ( EdgeID) (EdgeID, bool) {
	if !.graph.Edge().treeEdge {
		panic("input edge is not a tree edge")
	}
	 := math.MaxInt
	var  EdgeID
	 := false
	for ,  := range .edges {
		 := .graph.Edge()
		if .isInHead(.Source, ) && !.isInHead(.Target, ) {
			 := .graph.Node(.Target).Layer - .graph.Node(.Source).Layer - .Delta
			if  <  {
				, ,  = , , true
			}
		}
	}
	return , 
}

func ( *NetworkSimplex) (,  EdgeID) {
	if !.graph.Edge().treeEdge {
		panic("leave edge is not a tree edge")
	}
	if .graph.Edge().treeEdge {
		panic("enter edge is already a tree edge")
	}
	.graph.Edge().treeEdge = false
	.treeEdges = removeFirst(.treeEdges, )
	.graph.Edge().treeEdge = true
	.treeEdges = append(.treeEdges, )
	 := .graph.Edge()
	 := .graph.Node(.Target).Layer - .graph.Node(.Source).Layer - .Delta
	if !.isInHead(.Target, ) {
		 = -
	}
	for ,  := range append([]NodeID(nil), .graph.Nodes...) {
		if !.isInHead(, ) {
			.graph.Node().Layer += 
		}
	}
	.postOrder = 1
	clear(.edgeVisited)
	.postorderTraversal(.graph.Nodes[0])
	.calculateCutvalues()
}

func ( *NetworkSimplex) () []int {
	,  := math.MinInt, math.MaxInt
	for ,  := range .graph.Nodes {
		 = min(, .graph.Node().Layer)
		 = max(, .graph.Node().Layer)
	}
	 := make([]int, -+1)
	for ,  := range append([]NodeID(nil), .graph.Nodes...) {
		.graph.Node().Layer -= 
		[.graph.Node().Layer]++
	}
	for ,  := range .previousLayeringNodeCounts {
		if  == len() {
			break
		}
		[] += 
	}
	return 
}

func ( *NetworkSimplex) ( []int) {
	for ,  := range append([]NodeID(nil), .graph.Nodes...) {
		 := .graph.Node()
		if len(.IncomingEdges) != len(.OutgoingEdges) {
			continue
		}
		 := .Layer
		,  := .minimalSpan()
		for  := .Layer -  + 1;  < .Layer+; ++ {
			if [] < [] {
				 = 
			}
		}
		if [] < [.Layer] {
			[.Layer]--
			[]++
			.graph.Node().Layer = 
		}
	}
}