Topolojik Sıralama

package main

import (
	"fmt"
	"maps"
	"slices"
)

type DAG struct {
	adj   map[string][]string
	nodes map[string]bool
}

func NewDAG() *DAG {
	return &DAG{adj: map[string][]string{}, nodes: map[string]bool{}}
}

func (g *DAG) AddNode(n string) { g.nodes[n] = true }

// AddEdge: from → to (from, to'nun ön koşuludur)
func (g *DAG) AddEdge(from, to string) {
	g.AddNode(from)
	g.AddNode(to)
	g.adj[from] = append(g.adj[from], to)
	slices.Sort(g.adj[from])
}

func (g *DAG) Nodes() []string { return slices.Sorted(maps.Keys(g.nodes)) }

// inDegrees: her düğümün kaç gelen kenarı var
func (g *DAG) inDegrees() map[string]int {
	deg := map[string]int{}
	for _, n := range g.Nodes() {
		deg[n] = 0
	}
	for _, targets := range g.adj {
		for _, t := range targets {
			deg[t]++
		}
	}
	return deg
}

// kahn: giriş derecesi tabanlı topolojik sıralama — O(V + E)
func (g *DAG) kahn() ([]string, bool) {
	deg := g.inDegrees()

	// Derecesi sıfır olanlarla başla (alfabetik: deterministik çıktı)
	var ready []string
	for _, n := range g.Nodes() {
		if deg[n] == 0 {
			ready = append(ready, n)
		}
	}
	slices.Sort(ready)

	var order []string
	for len(ready) > 0 {
		cur := ready[0]
		ready = ready[1:]
		order = append(order, cur)

		for _, next := range g.adj[cur] {
			deg[next]--
			if deg[next] == 0 {
				ready = append(ready, next)
				slices.Sort(ready) // deterministik sıra
			}
		}
	}

	// Tüm düğümler sıralandıysa döngü yok
	return order, len(order) == len(g.nodes)
}

// levels: aynı anda yapılabilecek işleri gruplar
func (g *DAG) levels() ([][]string, bool) {
	deg := g.inDegrees()
	var current []string
	for _, n := range g.Nodes() {
		if deg[n] == 0 {
			current = append(current, n)
		}
	}

	var result [][]string
	processed := 0
	for len(current) > 0 {
		slices.Sort(current)
		result = append(result, current)
		processed += len(current)

		var next []string
		for _, node := range current {
			for _, t := range g.adj[node] {
				deg[t]--
				if deg[t] == 0 {
					next = append(next, t)
				}
			}
		}
		current = next
	}
	return result, processed == len(g.nodes)
}

func main() {
	g := NewDAG()
	deps := [][2]string{
		{"Matematik", "Algoritmalar"},
		{"Matematik", "İstatistik"},
		{"Algoritmalar", "Yapay Zekâ"},
		{"Algoritmalar", "Makine Öğrenmesi"},
		{"İstatistik", "Makine Öğrenmesi"},
	}
	for _, d := range deps {
		g.AddEdge(d[0], d[1])
	}

	fmt.Println("bağımlılıklar (ön koşul → ders):")
	for _, d := range deps {
		fmt.Printf("  %s → %s\n", d[0], d[1])
	}

	fmt.Println()
	fmt.Println("giriş dereceleri:")
	deg := g.inDegrees()
	for _, n := range g.Nodes() {
		fmt.Printf("  %-20s %d\n", n, deg[n])
	}

	order, ok := g.kahn()
	fmt.Println()
	fmt.Println("topolojik sıra (döngü yok:", ok, "):")
	for i, n := range order {
		fmt.Printf("  %d. %s\n", i+1, n)
	}

	fmt.Println()
	fmt.Println("paralel yapılabilecek gruplar (dönem planı):")
	lvls, _ := g.levels()
	for i, level := range lvls {
		fmt.Printf("  dönem %d: %v\n", i+1, level)
	}
	fmt.Println("en az dönem sayısı:", len(lvls))
}

package main

import (
	"fmt"
	"maps"
	"slices"
)

type DAG struct {
	adj   map[string][]string
	nodes map[string]bool
}

func NewDAG() *DAG {
	return &DAG{adj: map[string][]string{}, nodes: map[string]bool{}}
}

func (g *DAG) AddNode(n string) { g.nodes[n] = true }

func (g *DAG) AddEdge(from, to string) {
	g.AddNode(from)
	g.AddNode(to)
	g.adj[from] = append(g.adj[from], to)
	slices.Sort(g.adj[from])
}

func (g *DAG) Nodes() []string { return slices.Sorted(maps.Keys(g.nodes)) }

// topoDFS: DFS çıkış sırasının tersi — O(V + E)
func (g *DAG) topoDFS() ([]string, bool) {
	const (
		white = 0 // hiç ziyaret edilmedi
		gray  = 1 // ziyaret ediliyor (yığında)
		black = 2 // tamamlandı
	)
	color := map[string]int{}
	var order []string
	hasCycle := false

	var dfs func(string)
	dfs = func(node string) {
		if hasCycle {
			return
		}
		color[node] = gray

		for _, next := range g.adj[node] {
			switch color[next] {
			case gray:
				hasCycle = true // GRİ bir düğüme dönmek: döngü!
				return
			case white:
				dfs(next)
			}
		}
		color[node] = black
		order = append(order, node) // çıkışta ekle
	}

	for _, n := range g.Nodes() {
		if color[n] == white {
			dfs(n)
		}
	}
	if hasCycle {
		return nil, false
	}
	slices.Reverse(order) // çıkış sırasının tersi
	return order, true
}

// findCycle: döngü varsa yolunu döndürür
func (g *DAG) findCycle() []string {
	const (
		white = 0
		gray  = 1
		black = 2
	)
	color := map[string]int{}
	parent := map[string]string{}
	var cycle []string

	var dfs func(string) bool
	dfs = func(node string) bool {
		color[node] = gray
		for _, next := range g.adj[node] {
			switch color[next] {
			case gray:
				// Döngüyü geri kur
				cycle = []string{next}
				for n := node; n != next && n != ""; n = parent[n] {
					cycle = append(cycle, n)
				}
				slices.Reverse(cycle)
				cycle = append(cycle, next)
				return true
			case white:
				parent[next] = node
				if dfs(next) {
					return true
				}
			}
		}
		color[node] = black
		return false
	}

	for _, n := range g.Nodes() {
		if color[n] == white && dfs(n) {
			return cycle
		}
	}
	return nil
}

func main() {
	// Geçerli DAG
	g := NewDAG()
	for _, d := range [][2]string{
		{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"}, {"D", "E"},
	} {
		g.AddEdge(d[0], d[1])
	}

	order, ok := g.topoDFS()
	fmt.Println("DAG için DFS tabanlı topolojik sıra:")
	fmt.Println("  ", order, "| geçerli:", ok)
	fmt.Println("  döngü:", g.findCycle())

	// Döngülü graf
	cyclic := NewDAG()
	for _, d := range [][2]string{
		{"A", "B"}, {"B", "C"}, {"C", "A"}, {"C", "D"},
	} {
		cyclic.AddEdge(d[0], d[1])
	}
	order2, ok2 := cyclic.topoDFS()
	fmt.Println()
	fmt.Println("döngülü graf:")
	fmt.Println("  topolojik sıra:", order2, "| geçerli:", ok2)
	fmt.Println("  bulunan döngü:", cyclic.findCycle())

	// Kendine döngü
	self := NewDAG()
	self.AddEdge("X", "X")
	fmt.Println()
	fmt.Println("kendine döngü:")
	_, ok3 := self.topoDFS()
	fmt.Println("  geçerli:", ok3, "| döngü:", self.findCycle())

	// Bağlantısız DAG
	forest := NewDAG()
	forest.AddEdge("A", "B")
	forest.AddEdge("C", "D")
	forest.AddNode("E")
	order4, ok4 := forest.topoDFS()
	fmt.Println()
	fmt.Println("bağlantısız DAG:")
	fmt.Println("  topolojik sıra:", order4, "| geçerli:", ok4)
}

package main

import (
	"fmt"
	"maps"
	"slices"
)

type Digraph struct {
	adj   map[string][]string
	nodes map[string]bool
}

func NewDigraph() *Digraph {
	return &Digraph{adj: map[string][]string{}, nodes: map[string]bool{}}
}

func (g *Digraph) AddEdge(from, to string) {
	g.nodes[from], g.nodes[to] = true, true
	g.adj[from] = append(g.adj[from], to)
	slices.Sort(g.adj[from])
}

func (g *Digraph) Nodes() []string { return slices.Sorted(maps.Keys(g.nodes)) }

type color int

const (
	white color = iota
	gray
	black
)

// analyze: üç renkli DFS ile döngü ve renk geçmişini raporlar
func (g *Digraph) analyze() (bool, []string) {
	colors := map[string]color{}
	var log []string

	var dfs func(string) bool
	dfs = func(node string) bool {
		colors[node] = gray
		log = append(log, fmt.Sprintf("%s → GRİ", node))

		for _, next := range g.adj[node] {
			switch colors[next] {
			case gray:
				log = append(log, fmt.Sprintf("%s → %s: GRİ düğüme dönüş → DÖNGÜ", node, next))
				return true
			case black:
				log = append(log, fmt.Sprintf("%s → %s: SİYAH, zaten işlenmiş (sorun yok)", node, next))
			case white:
				if dfs(next) {
					return true
				}
			}
		}
		colors[node] = black
		log = append(log, fmt.Sprintf("%s → SİYAH", node))
		return false
	}

	for _, n := range g.Nodes() {
		if colors[n] == white {
			if dfs(n) {
				return true, log
			}
		}
	}
	return false, log
}

func main() {
	// Elmas şekli: ziyaret edilmiş düğüme rastlanır ama döngü YOK
	diamond := NewDigraph()
	for _, e := range [][2]string{{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"}} {
		diamond.AddEdge(e[0], e[1])
	}

	fmt.Println("ELMAS GRAF (A→B→D, A→C→D):")
	cyc, log := diamond.analyze()
	for _, l := range log {
		fmt.Println("  ", l)
	}
	fmt.Println("  döngü var mı:", cyc)

	// Gerçek döngü
	fmt.Println()
	cyclic := NewDigraph()
	for _, e := range [][2]string{{"A", "B"}, {"B", "C"}, {"C", "A"}} {
		cyclic.AddEdge(e[0], e[1])
	}
	fmt.Println("DÖNGÜLÜ GRAF (A→B→C→A):")
	cyc2, log2 := cyclic.analyze()
	for _, l := range log2 {
		fmt.Println("  ", l)
	}
	fmt.Println("  döngü var mı:", cyc2)

	fmt.Println()
	fmt.Println("ÖNEMLİ: Yönsüz grafta 'ziyaret edilmiş komşu' döngü demekti.")
	fmt.Println("Yönlü grafta yetmez; komşunun HÂLÂ YIĞINDA olması gerekir.")
}

package main

import (
	"fmt"
	"maps"
	"slices"
	"strings"
)

type BuildSystem struct {
	deps    map[string][]string // hedef → ön koşulları
	targets map[string]bool
}

func NewBuildSystem() *BuildSystem {
	return &BuildSystem{deps: map[string][]string{}, targets: map[string]bool{}}
}

// Require: target, prerequisites'e bağımlıdır
func (b *BuildSystem) Require(target string, prerequisites ...string) {
	b.targets[target] = true
	for _, p := range prerequisites {
		b.targets[p] = true
	}
	b.deps[target] = append(b.deps[target], prerequisites...)
	slices.Sort(b.deps[target])
}

func (b *BuildSystem) Targets() []string { return slices.Sorted(maps.Keys(b.targets)) }

// BuildOrder: Kahn ile derleme sırası
func (b *BuildSystem) BuildOrder() ([]string, []string, error) {
	// Ters graf: ön koşul → ona bağımlı olan
	forward := map[string][]string{}
	inDeg := map[string]int{}
	for _, t := range b.Targets() {
		inDeg[t] = 0
	}
	for target, prereqs := range b.deps {
		for _, p := range prereqs {
			forward[p] = append(forward[p], target)
			inDeg[target]++
		}
	}
	for k := range forward {
		slices.Sort(forward[k])
	}

	var ready []string
	for _, t := range b.Targets() {
		if inDeg[t] == 0 {
			ready = append(ready, t)
		}
	}
	slices.Sort(ready)

	var order []string
	for len(ready) > 0 {
		cur := ready[0]
		ready = ready[1:]
		order = append(order, cur)
		for _, next := range forward[cur] {
			inDeg[next]--
			if inDeg[next] == 0 {
				ready = append(ready, next)
				slices.Sort(ready)
			}
		}
	}

	if len(order) != len(b.targets) {
		// Döngüde kalan hedefleri bul
		var stuck []string
		inOrder := map[string]bool{}
		for _, o := range order {
			inOrder[o] = true
		}
		for _, t := range b.Targets() {
			if !inOrder[t] {
				stuck = append(stuck, t)
			}
		}
		return nil, stuck, fmt.Errorf("dairesel bağımlılık: %s", strings.Join(stuck, ", "))
	}

	// Paralel gruplar
	return order, b.parallelGroups(forward), nil
}

func (b *BuildSystem) parallelGroups(forward map[string][]string) []string {
	inDeg := map[string]int{}
	for _, t := range b.Targets() {
		inDeg[t] = 0
	}
	for _, prereqs := range b.deps {
		_ = prereqs
	}
	for target, prereqs := range b.deps {
		inDeg[target] = len(prereqs)
	}

	var current []string
	for _, t := range b.Targets() {
		if inDeg[t] == 0 {
			current = append(current, t)
		}
	}

	var groups []string
	round := 1
	for len(current) > 0 {
		slices.Sort(current)
		groups = append(groups, fmt.Sprintf("aşama %d: %s", round, strings.Join(current, ", ")))
		var next []string
		for _, node := range current {
			for _, t := range forward[node] {
				inDeg[t]--
				if inDeg[t] == 0 {
					next = append(next, t)
				}
			}
		}
		current = next
		round++
	}
	return groups
}

func main() {
	// Gerçekçi bir Go projesi bağımlılık grafı
	b := NewBuildSystem()
	b.Require("app", "handlers", "config")
	b.Require("handlers", "models", "validators")
	b.Require("models", "database")
	b.Require("validators", "models")
	b.Require("database", "config")
	b.Require("config")

	fmt.Println("bağımlılıklar:")
	for _, t := range b.Targets() {
		if len(b.deps[t]) == 0 {
			fmt.Printf("  %-12s (bağımlılık yok)\n", t)
			continue
		}
		fmt.Printf("  %-12s ← %s\n", t, strings.Join(b.deps[t], ", "))
	}

	order, groups, err := b.BuildOrder()
	if err != nil {
		fmt.Println("hata:", err)
		return
	}

	fmt.Println()
	fmt.Println("derleme sırası:")
	for i, t := range order {
		fmt.Printf("  %d. %s\n", i+1, t)
	}

	fmt.Println()
	fmt.Println("paralel derleme aşamaları:")
	for _, g := range groups {
		fmt.Println("  " + g)
	}

	// Dairesel bağımlılık
	fmt.Println()
	broken := NewBuildSystem()
	broken.Require("a", "b")
	broken.Require("b", "c")
	broken.Require("c", "a")
	broken.Require("d")

	_, stuck, err2 := broken.BuildOrder()
	fmt.Println("bozuk proje:")
	if err2 != nil {
		fmt.Println("  hata:", err2)
		fmt.Println("  döngüde kalan hedefler:", stuck)
	}
}