Advent-of-Code-2023/day25/graph.go

package day25

import (
	"fmt"
	"log"
	"os"
	"strings"

	mapset "github.com/deckarep/golang-set/v2"
)

type Graph struct {
	Nodes map[string]*Node
}

type Node struct {
	Name      string
	Neighbors mapset.Set[string]
}

func (n Node) String() string {
	return fmt.Sprintf("[%s : %+v]", n.Name, n.Neighbors)
}

func ReadGraphFile(filename string) (g Graph) {
	g.Nodes = map[string]*Node{}

	bytes, err := os.ReadFile(filename)
	if err != nil {
		panic(err)
	}
	text := strings.TrimSpace(string(bytes))
	for _, line := range strings.Split(text, "\n") {
		g.readGraphLine(line)
	}

	return
}

func (g *Graph) readGraphLine(l string)  {
	firstSplit := strings.Split(l, ":")

	node, exists := g.Nodes[firstSplit[0]]
	if !exists {
		node = &Node{
			Name:      firstSplit[0],
			Neighbors: mapset.NewSet[string](),
		}
	}

	secondSplit := strings.Fields(firstSplit[1])

	for _, neighborName := range secondSplit {
		neighbor, exists := g.Nodes[neighborName]
		if !exists {
			neighbor = &Node{
				Name:      neighborName,
				Neighbors: mapset.NewSet[string](),
			}
			g.Nodes[neighborName] = neighbor
		}
		neighbor.Neighbors.Add(node.Name)
		node.Neighbors.Add(neighbor.Name)
	}

	g.Nodes[node.Name] = node

	return
}

// NOTE this is so sad. nodeA.Neighbors.Remove(nodeB.Name) hangs for a reason i don't understand
func (g *Graph) RemoveEdge(a, b string) {
	// log.Printf("entering remove edge for %s and %s", a, b)
	nodeA, existsA := g.Nodes[a]
	// log.Println("got first node", nodeA, existsA)
	nodeB, existsB := g.Nodes[b]
	// log.Println("got second node", nodeB, existsB)
	if !existsA || !existsB {
		panic("requesting not found node")
	}

	// log.Println("before removals")
	// log.Println("before remove first", nodeA)
	// nodeA.Neighbors = newANeighbors
	nodeA.Neighbors = nodeA.Neighbors.Difference(mapset.NewSet[string](nodeB.Name))
	// nodeA.Neighbors.Remove(nodeB.Name)
	// log.Println("removed first", nodeA)

	// log.Println("before remove second", nodeB)
	// nodeB.Neighbors = newBNeighbors
	nodeB.Neighbors = nodeB.Neighbors.Difference(mapset.NewSet[string](nodeA.Name))
	// nodeB.Neighbors.Remove(nodeA.Name)
	// log.Println("removed second", nodeB)
}

func (g *Graph) AddEdge(a, b string) {
	nodeA, existsA := g.Nodes[a]
	nodeB, existsB := g.Nodes[b]
	if !existsA || !existsB {
		panic("requesting not found node")
	}
	nodeA.Neighbors.Add(nodeB.Name)
	nodeB.Neighbors.Add(nodeA.Name)
}

func (g *Graph) findCycle() (from, to string, exists bool) {
	// log.Printf(">>>> starting new find cycle")
	var firstNode *Node
	for _, n := range g.Nodes {
		firstNode = n
		break
	}
	// log.Printf("initial search from %s and neighbors %+v", firstNode.Name, firstNode.Neighbors)
	for neighborName := range firstNode.Neighbors.Iter() {
		initialVisited := mapset.NewSet[string](firstNode.Name)
		// log.Printf("initial dfs from %s to %s with initial visited %+v", firstNode.Name, neighborName, initialVisited)
		from, to, exists = g.dfcCycle(firstNode.Name, neighborName, initialVisited)
		if exists {
			break
		}
	}

	// log.Printf("<<<< cycle %t, from %s to %s", exists, from, to)
	return
}

func (g *Graph) dfcCycle(fromName, atName string, visited mapset.Set[string]) (cycleFrom, cycleTo string, cycleExists bool) {
	// log.Printf("> step from %+v to %+v. visited : %+v", fromName, atName, visited)
	if visited.Cardinality() == len(g.Nodes) {
		log.Println("exit by visited all")
		return
	}

	atNode := g.Nodes[atName]

	if visited.Contains(atName) {
		return fromName, atName, true
	}

	for neighborName := range atNode.Neighbors.Iter() {
		if neighborName == fromName {
			continue
		}
		newVisited := visited.Clone()
		newVisited.Add(atName)
		cycleFrom, cycleTo, cycleExists = g.dfcCycle(atName, neighborName, newVisited)
		if cycleExists {
			break
		}
	}

	return
}

func (g *Graph) ComponentFrom(fromName string) (component mapset.Set[string]) {
	startNode := g.Nodes[fromName]
	component = mapset.NewSet[string](startNode.Name)
	toVisit := startNode.Neighbors.Clone()

	for toVisit.Cardinality() > 0 {
		runnerNodeName, _ := toVisit.Pop()
		if component.Contains(runnerNodeName) {
			continue
		}
		component.Add(runnerNodeName)
		runnerNode := g.Nodes[runnerNodeName]
		unvisitedNeighbors := runnerNode.Neighbors.Difference(component)
		// log.Printf("adding %s to component. neighbors %+v, adding %+v to visit",
		// 	runnerNodeName, runnerNode.Neighbors, unvisitedNeighbors)
		toVisit = toVisit.Union(unvisitedNeighbors)
	}

	return
}

func (g *Graph) ToMermaid() (result string) {
	result += "flowchart TD\n"
	edges := mapset.NewSet[string]()

	for _, node := range g.Nodes {
		for neighborName := range node.Neighbors.Iter() {
			var first, second string
			if node.Name < neighborName {
				first = node.Name
				second = neighborName
			} else {
				first = neighborName
				second = node.Name
			}
			edges.Add(fmt.Sprintf("\t%s --- %s\n", first, second))
		}
	}

	for line := range edges.Iter() {
		result += line
	}
	return
}

func (g *Graph)SaveAsMermaid(filename string) {
	mmd := g.ToMermaid()

	file, err := os.Create(filename)
	if err != nil {
		panic(err)
	}
	defer func() {
		if err := file.Close(); err != nil {
			panic(err)
		}
	}()

	file.WriteString(mmd)
}

type Edge struct {
	smaller, bigger string
}
func (e Edge)String() string {
	return fmt.Sprintf("%s/%s", e.smaller, e.bigger)
}

func CreateEdge(a, b string) Edge {
	var smaller, bigger string
	if a < b {
		smaller = a
		bigger = b
	} else {
		smaller = b
		bigger = a
	}
	return Edge{smaller, bigger}
}

func (g *Graph) RemoveAllCycles() (removedEdges mapset.Set[Edge]) {
	removedEdges = mapset.NewSet[Edge]()
	hasCycle := true
	var from, to string
	for hasCycle {
		from, to, hasCycle = g.findCycle()
		if hasCycle {
			// log.Printf("\n!!!! found cycle %s to %s\n", from, to)
			edgeToRemove := CreateEdge(from, to)
			removedEdges.Add(edgeToRemove)
			g.RemoveEdge(from, to)
		}
	}
	return
}

func (g *Graph) TryToSplit() (componentSizeMult int) {
	// first remove all cycles
	removedEdges := g.RemoveAllCycles()
	g.SaveAsMermaid("after-removing-cycles.mmd")
	// log.Printf("all removed edges %+v, two of them are necessary to split initial graph into 2 ", removedEdges)

	triedEdges := mapset.NewSet[Edge]()

	for _, node := range g.Nodes {
		for neighborName := range node.Neighbors.Iter() {
			edge := CreateEdge(neighborName, node.Name)
			if triedEdges.Contains(edge) {
				continue
			}
			triedEdges.Add(edge)
			// first remove the edge
			g.RemoveEdge(edge.bigger, edge.smaller)

			// then ask for components of the nodes of removed edge
			compA := g.ComponentFrom(edge.bigger)
			compB := g.ComponentFrom(edge.smaller)

			// iterate over the initially removed edges. only two of them should be 'connecting'
			// i.e were necessary to remove
			necessaryEdgesCount := 0
			for initiallyRemovedEdge := range removedEdges.Iter() {
				endA, endB := initiallyRemovedEdge.bigger, initiallyRemovedEdge.smaller
				isNonNecessary := (compA.Contains(endA) && compA.Contains(endB)) || (compB.Contains(endA) && compB.Contains(endB))
				if !isNonNecessary {
					// log.Printf("with edge %+v test removed, the %+v also seems necessary", edge, initiallyRemovedEdge)
					necessaryEdgesCount += 1
				}
			}
			// log.Printf("with edge %+v test removed neessary count is %d", edge, necessaryEdgesCount)

			// if we found 2 necessary, then our currently tried edge is the third necesary to remove
			// and out two components are the searched
			if necessaryEdgesCount == 2 {
				return compA.Cardinality() * compB.Cardinality()
			}

			// in the end add edge back if not fitting
			g.AddEdge(edge.bigger, edge.smaller)
		}
	}

	// now huh. if we didn't find `necessaryEdgesCount == 2`
	// that means 0, 1 or 3

	return
}