search

brandonchinn178 / circle-of-suck

A website scraping collegiate sports scores and finding a circle of suck
https://brandonchinn178.github.io/circle-of-suck
2 stars 2 forks source link

Replace longest path with closest hamiltonian cycle #46

Closed brandonchinn178 closed 4 years ago

brandonchinn178 commented 4 years ago

If a hamiltonian cycle doesn't exist, we should try to find the closest hamiltonian cycle, defined as a hamiltonian cycle created by adding an edge between two nodes that are not already connected by an edge directed in either direction. e.g.

A -> B -> C

Doesn't have a hamiltonian cycle, but the closest hamiltonian cycle is

A -> B -> C (->) A

since neither (C,A) nor (A,C) are currently in the graph.

We should then render these close edges differently to indicate that these edges do not exist yet

brandonchinn178 commented 4 years ago

This should reduce to a shortest hamiltonian cycle problem. Encode current games as edges with weight 0 and every future game as edges going both ways with weight 1. I might be able to code up a prototype today