30 KiB
30 KiB
Notes
ok, not so simple
'how to find 3 edges which if removed split graph into 2 components'
i guess i could find all cycles? and then what?
then if i have graph without cycles and all of the removed edges, maybe i can figure out how to remove one edge, to make two components, and all (k - 2) edges back in a way that would not connect those components.
well, the cycles maybe should have been broken elsewhere? for most cycles - it doesn't matter.
for cycles that break into 2 components, does it?
ok. if i have the no-cycle graph. then we can maybe start searching for 'third' edge to remove.
i remove it, i get two components. then as a test - exactly two edges when added should connect those components. if that happens - i have an answer
sounds good
making code to get components.
now.
make method to remove all cycles.
save the removed edges to slice
i guess could be a method that modifies the graph and returns all removed edges. and test that
why a node ends up without any edges?
=== RUN TestRemoveAllCycles
graph_test.go:55: initial graph is {Nodes:map[bvb:[bvb : Set{xhk, hfx, ntq}] cmg:[cmg : Set{qnr, nvd, lhk, bvb, rzs}] frs:[frs : Set{qnr, lhk, lsr}] hfx:[hfx : Set{rhn, bvb, pzl, ntq, xhk}] jqt:[jqt : Set{rhn, xhk, nvd, ntq}] lhk:[lhk : Set{nvd, lsr, frs, cmg}] lsr:[lsr : Set{rzs, frs, lhk}] ntq:[ntq : Set{jqt, hfx, bvb, xhk}] nvd:[nvd : Set{lhk}] pzl:[pzl : Set{lsr, hfx, nvd}] qnr:[qnr : Set{nvd, rzs, frs}] rhn:[rhn : Set{bvb, hfx, xhk}] rsh:[rsh : Set{lsr, rzs, frs, pzl}] rzs:[rzs : Set{lsr, rsh, qnr, cmg}] xhk:[xhk : Set{hfx, rhn, bvb, ntq}]]}
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from lsr and neighbors Set{lhk, rzs, frs}
2023/12/25 08:14:02 initial dfs from lsr to lhk with initial visited Set{lsr}
2023/12/25 08:14:02 > step from lsr to lhk. visited : Set{lsr}
2023/12/25 08:14:02 > step from lhk to frs. visited : Set{lsr, lhk}
2023/12/25 08:14:02 > step from frs to lsr. visited : Set{lhk, frs, lsr}
2023/12/25 08:14:02 <<<< cycle true, from frs to lsr
2023/12/25 08:14:02 entering remove edge for frs and lsr
2023/12/25 08:14:02 removed first [frs : Set{qnr, lhk}]
2023/12/25 08:14:02 removed second [lsr : Set{lhk, rzs}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from xhk and neighbors Set{hfx, rhn, bvb, ntq}
2023/12/25 08:14:02 initial dfs from xhk to ntq with initial visited Set{xhk}
2023/12/25 08:14:02 > step from xhk to ntq. visited : Set{xhk}
2023/12/25 08:14:02 > step from ntq to jqt. visited : Set{xhk, ntq}
2023/12/25 08:14:02 > step from jqt to rhn. visited : Set{xhk, ntq, jqt}
2023/12/25 08:14:02 > step from rhn to bvb. visited : Set{rhn, xhk, ntq, jqt}
2023/12/25 08:14:02 > step from bvb to xhk. visited : Set{xhk, ntq, jqt, rhn, bvb}
2023/12/25 08:14:02 <<<< cycle true, from bvb to xhk
2023/12/25 08:14:02 entering remove edge for bvb and xhk
2023/12/25 08:14:02 removed first [bvb : Set{hfx, ntq}]
2023/12/25 08:14:02 removed second [xhk : Set{ntq, hfx, rhn}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from rhn and neighbors Set{bvb, hfx, xhk}
2023/12/25 08:14:02 initial dfs from rhn to xhk with initial visited Set{rhn}
2023/12/25 08:14:02 > step from rhn to xhk. visited : Set{rhn}
2023/12/25 08:14:02 > step from xhk to hfx. visited : Set{rhn, xhk}
2023/12/25 08:14:02 > step from hfx to bvb. visited : Set{rhn, xhk, hfx}
2023/12/25 08:14:02 > step from bvb to hfx. visited : Set{hfx, rhn, xhk, bvb}
2023/12/25 08:14:02 <<<< cycle true, from bvb to hfx
2023/12/25 08:14:02 entering remove edge for bvb and hfx
2023/12/25 08:14:02 removed first [bvb : Set{ntq}]
2023/12/25 08:14:02 removed second [hfx : Set{rhn, pzl, ntq, xhk}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from rsh and neighbors Set{frs, pzl, lsr, rzs}
2023/12/25 08:14:02 initial dfs from rsh to frs with initial visited Set{rsh}
2023/12/25 08:14:02 > step from rsh to frs. visited : Set{rsh}
2023/12/25 08:14:02 > step from frs to qnr. visited : Set{rsh, frs}
2023/12/25 08:14:02 > step from qnr to nvd. visited : Set{qnr, rsh, frs}
2023/12/25 08:14:02 > step from nvd to lhk. visited : Set{rsh, frs, qnr, nvd}
2023/12/25 08:14:02 > step from lhk to cmg. visited : Set{rsh, frs, qnr, nvd, lhk}
2023/12/25 08:14:02 > step from cmg to qnr. visited : Set{rsh, frs, qnr, nvd, lhk, cmg}
2023/12/25 08:14:02 <<<< cycle true, from cmg to qnr
2023/12/25 08:14:02 entering remove edge for cmg and qnr
2023/12/25 08:14:02 removed first [cmg : Set{nvd, lhk, bvb, rzs}]
2023/12/25 08:14:02 removed second [qnr : Set{nvd, rzs, frs}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from rzs and neighbors Set{rsh, qnr, cmg, lsr}
2023/12/25 08:14:02 initial dfs from rzs to cmg with initial visited Set{rzs}
2023/12/25 08:14:02 > step from rzs to cmg. visited : Set{rzs}
2023/12/25 08:14:02 > step from cmg to nvd. visited : Set{rzs, cmg}
2023/12/25 08:14:02 > step from nvd to lhk. visited : Set{cmg, nvd, rzs}
2023/12/25 08:14:02 > step from lhk to cmg. visited : Set{cmg, lhk, nvd, rzs}
2023/12/25 08:14:02 <<<< cycle true, from lhk to cmg
2023/12/25 08:14:02 entering remove edge for lhk and cmg
2023/12/25 08:14:02 removed first [lhk : Set{frs, nvd, lsr}]
2023/12/25 08:14:02 removed second [cmg : Set{rzs, nvd, bvb}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from qnr and neighbors Set{nvd, rzs, frs}
2023/12/25 08:14:02 initial dfs from qnr to nvd with initial visited Set{qnr}
2023/12/25 08:14:02 > step from qnr to nvd. visited : Set{qnr}
2023/12/25 08:14:02 > step from nvd to lhk. visited : Set{qnr, nvd}
2023/12/25 08:14:02 > step from lhk to nvd. visited : Set{lhk, qnr, nvd}
2023/12/25 08:14:02 <<<< cycle true, from lhk to nvd
2023/12/25 08:14:02 entering remove edge for lhk and nvd
2023/12/25 08:14:02 removed first [lhk : Set{lsr, frs}]
2023/12/25 08:14:02 removed second [nvd : Set{}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from jqt and neighbors Set{rhn, xhk, nvd, ntq}
2023/12/25 08:14:02 initial dfs from jqt to xhk with initial visited Set{jqt}
2023/12/25 08:14:02 > step from jqt to xhk. visited : Set{jqt}
2023/12/25 08:14:02 > step from xhk to ntq. visited : Set{jqt, xhk}
2023/12/25 08:14:02 > step from ntq to bvb. visited : Set{jqt, xhk, ntq}
2023/12/25 08:14:02 > step from bvb to ntq. visited : Set{jqt, xhk, ntq, bvb}
2023/12/25 08:14:02 <<<< cycle true, from bvb to ntq
2023/12/25 08:14:02 entering remove edge for bvb and ntq
2023/12/25 08:14:02 removed first [bvb : Set{}]
2023/12/25 08:14:02 removed second [ntq : Set{jqt, hfx, xhk}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from xhk and neighbors Set{hfx, rhn, ntq}
2023/12/25 08:14:02 initial dfs from xhk to hfx with initial visited Set{xhk}
2023/12/25 08:14:02 > step from xhk to hfx. visited : Set{xhk}
2023/12/25 08:14:02 > step from hfx to xhk. visited : Set{xhk, hfx}
2023/12/25 08:14:02 <<<< cycle true, from hfx to xhk
2023/12/25 08:14:02 entering remove edge for hfx and xhk
2023/12/25 08:14:02 removed first [hfx : Set{ntq, rhn, pzl}]
2023/12/25 08:14:02 removed second [xhk : Set{rhn, ntq}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from lsr and neighbors Set{lhk, rzs}
2023/12/25 08:14:02 initial dfs from lsr to rzs with initial visited Set{lsr}
2023/12/25 08:14:02 > step from lsr to rzs. visited : Set{lsr}
2023/12/25 08:14:02 > step from rzs to qnr. visited : Set{lsr, rzs}
2023/12/25 08:14:02 > step from qnr to rzs. visited : Set{lsr, rzs, qnr}
2023/12/25 08:14:02 <<<< cycle true, from qnr to rzs
2023/12/25 08:14:02 entering remove edge for qnr and rzs
2023/12/25 08:14:02 removed first [qnr : Set{frs, nvd}]
2023/12/25 08:14:02 removed second [rzs : Set{cmg, lsr, rsh}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from pzl and neighbors Set{lsr, hfx, nvd}
2023/12/25 08:14:02 initial dfs from pzl to lsr with initial visited Set{pzl}
2023/12/25 08:14:02 > step from pzl to lsr. visited : Set{pzl}
2023/12/25 08:14:02 > step from lsr to lhk. visited : Set{pzl, lsr}
2023/12/25 08:14:02 > step from lhk to lsr. visited : Set{lsr, lhk, pzl}
2023/12/25 08:14:02 <<<< cycle true, from lhk to lsr
2023/12/25 08:14:02 entering remove edge for lhk and lsr
2023/12/25 08:14:02 removed first [lhk : Set{frs}]
2023/12/25 08:14:02 removed second [lsr : Set{rzs}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from rhn and neighbors Set{xhk, bvb, hfx}
2023/12/25 08:14:02 initial dfs from rhn to xhk with initial visited Set{rhn}
2023/12/25 08:14:02 > step from rhn to xhk. visited : Set{rhn}
2023/12/25 08:14:02 > step from xhk to rhn. visited : Set{xhk, rhn}
2023/12/25 08:14:02 <<<< cycle true, from xhk to rhn
2023/12/25 08:14:02 entering remove edge for xhk and rhn
2023/12/25 08:14:02 removed first [xhk : Set{ntq}]
2023/12/25 08:14:02 removed second [rhn : Set{bvb, hfx}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from rsh and neighbors Set{frs, pzl, lsr, rzs}
2023/12/25 08:14:02 initial dfs from rsh to frs with initial visited Set{rsh}
2023/12/25 08:14:02 > step from rsh to frs. visited : Set{rsh}
2023/12/25 08:14:02 > step from frs to qnr. visited : Set{rsh, frs}
2023/12/25 08:14:02 > step from qnr to frs. visited : Set{rsh, frs, qnr}
2023/12/25 08:14:02 <<<< cycle true, from qnr to frs
2023/12/25 08:14:02 entering remove edge for qnr and frs
2023/12/25 08:14:02 removed first [qnr : Set{nvd}]
2023/12/25 08:14:02 removed second [frs : Set{lhk}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from rhn and neighbors Set{bvb, hfx}
2023/12/25 08:14:02 initial dfs from rhn to hfx with initial visited Set{rhn}
2023/12/25 08:14:02 > step from rhn to hfx. visited : Set{rhn}
2023/12/25 08:14:02 > step from hfx to rhn. visited : Set{rhn, hfx}
2023/12/25 08:14:02 <<<< cycle true, from hfx to rhn
2023/12/25 08:14:02 entering remove edge for hfx and rhn
2023/12/25 08:14:02 removed first [hfx : Set{pzl, ntq}]
2023/12/25 08:14:02 removed second [rhn : Set{bvb}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from pzl and neighbors Set{hfx, nvd, lsr}
2023/12/25 08:14:02 initial dfs from pzl to lsr with initial visited Set{pzl}
2023/12/25 08:14:02 > step from pzl to lsr. visited : Set{pzl}
2023/12/25 08:14:02 > step from lsr to rzs. visited : Set{pzl, lsr}
2023/12/25 08:14:02 > step from rzs to cmg. visited : Set{pzl, lsr, rzs}
2023/12/25 08:14:02 > step from cmg to rzs. visited : Set{pzl, lsr, rzs, cmg}
2023/12/25 08:14:02 <<<< cycle true, from cmg to rzs
2023/12/25 08:14:02 entering remove edge for cmg and rzs
2023/12/25 08:14:02 removed first [cmg : Set{nvd, bvb}]
2023/12/25 08:14:02 removed second [rzs : Set{lsr, rsh}]
2023/12/25 08:14:02 >>>> starting new find cycle
2023/12/25 08:14:02 initial search from rhn and neighbors Set{bvb}
2023/12/25 08:14:02 initial dfs from rhn to bvb with initial visited Set{rhn}
2023/12/25 08:14:02 > step from rhn to bvb. visited : Set{rhn}
2023/12/25 08:14:02 <<<< cycle false, from to
graph_test.go:57: removed edges Set{{lhk nvd}, {hfx xhk}, {frs qnr}, {cmg rzs}, {bvb xhk}, {bvb hfx}, {cmg qnr}, {cmg lhk}, {qnr rzs}, {hfx rhn}, {frs lsr}, {rhn xhk}, {bvb ntq}, {lhk lsr}}
graph_test.go:58: after removal graph is {Nodes:map[bvb:[bvb : Set{}] cmg:[cmg : Set{nvd, bvb}] frs:[frs : Set{lhk}] hfx:[hfx : Set{pzl, ntq}] jqt:[jqt : Set{rhn, xhk, nvd, ntq}] lhk:[lhk : Set{frs}] lsr:[lsr : Set{rzs}] ntq:[ntq : Set{xhk, jqt, hfx}] nvd:[nvd : Set{}] pzl:[pzl : Set{nvd, lsr, hfx}] qnr:[qnr : Set{nvd}] rhn:[rhn : Set{bvb}] rsh:[rsh : Set{frs, pzl, lsr, rzs}] rzs:[rzs : Set{lsr, rsh}] xhk:[xhk : Set{ntq}]]}
--- PASS: TestRemoveAllCycles (0.00s)because i was overwriting nodes on file read
now why i get empty sets?
=== RUN TestRemoveAllCycles
graph_test.go:55: initial graph is {Nodes:map[bvb:[bvb : Set{cmg, rhn, xhk, hfx, ntq}] cmg:[cmg : Set{lhk, bvb, rzs, qnr, nvd}] frs:[frs : Set{rsh, qnr, lhk, lsr}] hfx:[hfx : Set{xhk, rhn, bvb, pzl, ntq}] jqt:[jqt : Set{rhn, xhk, nvd, ntq}] lhk:[lhk : Set{nvd, lsr, frs, cmg}] lsr:[lsr : Set{rsh, pzl, lhk, rzs, frs}] ntq:[ntq : Set{jqt, hfx, bvb, xhk}] nvd:[nvd : Set{pzl, qnr, lhk, jqt, cmg}] pzl:[pzl : Set{hfx, nvd, rsh, lsr}] qnr:[qnr : Set{cmg, nvd, rzs, frs}] rhn:[rhn : Set{jqt, xhk, bvb, hfx}] rsh:[rsh : Set{lsr, rzs, frs, pzl}] rzs:[rzs : Set{qnr, cmg, lsr, rsh}] xhk:[xhk : Set{hfx, rhn, bvb, ntq, jqt}]]}
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from xhk and neighbors Set{rhn, bvb, ntq, jqt, hfx}
2023/12/25 08:31:09 initial dfs from xhk to rhn with initial visited Set{xhk}
2023/12/25 08:31:09 > step from xhk to rhn. visited : Set{xhk}
2023/12/25 08:31:09 > step from rhn to jqt. visited : Set{xhk, rhn}
2023/12/25 08:31:09 > step from jqt to rhn. visited : Set{xhk, rhn, jqt}
2023/12/25 08:31:09 <<<< cycle true, from jqt to rhn
2023/12/25 08:31:09 entering remove edge for jqt and rhn
2023/12/25 08:31:09 before remove first [jqt : Set{xhk, nvd, ntq, rhn}]
2023/12/25 08:31:09 removed first [jqt : Set{ntq, xhk, nvd}]
2023/12/25 08:31:09 before remove second [jqt : Set{nvd, ntq, xhk}]
2023/12/25 08:31:09 removed second [rhn : Set{hfx, xhk, bvb}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from pzl and neighbors Set{hfx, nvd, rsh, lsr}
2023/12/25 08:31:09 initial dfs from pzl to nvd with initial visited Set{pzl}
2023/12/25 08:31:09 > step from pzl to nvd. visited : Set{pzl}
2023/12/25 08:31:09 > step from nvd to jqt. visited : Set{pzl, nvd}
2023/12/25 08:31:09 > step from jqt to ntq. visited : Set{pzl, nvd, jqt}
2023/12/25 08:31:09 > step from ntq to xhk. visited : Set{pzl, nvd, jqt, ntq}
2023/12/25 08:31:09 > step from xhk to jqt. visited : Set{ntq, pzl, nvd, jqt, xhk}
2023/12/25 08:31:09 <<<< cycle true, from xhk to jqt
2023/12/25 08:31:09 entering remove edge for xhk and jqt
2023/12/25 08:31:09 before remove first [xhk : Set{jqt, hfx, rhn, bvb, ntq}]
2023/12/25 08:31:09 removed first [xhk : Set{ntq, hfx, rhn, bvb}]
2023/12/25 08:31:09 before remove second [xhk : Set{hfx, rhn, bvb, ntq}]
2023/12/25 08:31:09 removed second [jqt : Set{nvd, ntq}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from frs and neighbors Set{rsh, qnr, lhk, lsr}
2023/12/25 08:31:09 initial dfs from frs to lhk with initial visited Set{frs}
2023/12/25 08:31:09 > step from frs to lhk. visited : Set{frs}
2023/12/25 08:31:09 > step from lhk to nvd. visited : Set{frs, lhk}
2023/12/25 08:31:09 > step from nvd to cmg. visited : Set{lhk, frs, nvd}
2023/12/25 08:31:09 > step from cmg to lhk. visited : Set{frs, nvd, lhk, cmg}
2023/12/25 08:31:09 <<<< cycle true, from cmg to lhk
2023/12/25 08:31:09 entering remove edge for cmg and lhk
2023/12/25 08:31:09 before remove first [cmg : Set{qnr, nvd, lhk, bvb, rzs}]
2023/12/25 08:31:09 removed first [cmg : Set{nvd, bvb, rzs, qnr}]
2023/12/25 08:31:09 before remove second [cmg : Set{bvb, rzs, qnr, nvd}]
2023/12/25 08:31:09 removed second [lhk : Set{nvd, lsr, frs}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from xhk and neighbors Set{hfx, rhn, bvb, ntq}
2023/12/25 08:31:09 initial dfs from xhk to ntq with initial visited Set{xhk}
2023/12/25 08:31:09 > step from xhk to ntq. visited : Set{xhk}
2023/12/25 08:31:09 > step from ntq to jqt. visited : Set{xhk, ntq}
2023/12/25 08:31:09 > step from jqt to ntq. visited : Set{xhk, ntq, jqt}
2023/12/25 08:31:09 <<<< cycle true, from jqt to ntq
2023/12/25 08:31:09 entering remove edge for jqt and ntq
2023/12/25 08:31:09 before remove first [jqt : Set{ntq, nvd}]
2023/12/25 08:31:09 removed first [jqt : Set{nvd}]
2023/12/25 08:31:09 before remove second [jqt : Set{nvd}]
2023/12/25 08:31:09 removed second [ntq : Set{xhk, hfx, bvb}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from nvd and neighbors Set{jqt, cmg, pzl, qnr, lhk}
2023/12/25 08:31:09 initial dfs from nvd to cmg with initial visited Set{nvd}
2023/12/25 08:31:09 > step from nvd to cmg. visited : Set{nvd}
2023/12/25 08:31:09 > step from cmg to bvb. visited : Set{nvd, cmg}
2023/12/25 08:31:09 > step from bvb to cmg. visited : Set{cmg, nvd, bvb}
2023/12/25 08:31:09 <<<< cycle true, from bvb to cmg
2023/12/25 08:31:09 entering remove edge for bvb and cmg
2023/12/25 08:31:09 before remove first [bvb : Set{cmg, rhn, xhk, hfx, ntq}]
2023/12/25 08:31:09 removed first [bvb : Set{xhk, hfx, ntq, rhn}]
2023/12/25 08:31:09 before remove second [bvb : Set{rhn, xhk, hfx, ntq}]
2023/12/25 08:31:09 removed second [cmg : Set{rzs, qnr, nvd}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from frs and neighbors Set{rsh, qnr, lhk, lsr}
2023/12/25 08:31:09 initial dfs from frs to lsr with initial visited Set{frs}
2023/12/25 08:31:09 > step from frs to lsr. visited : Set{frs}
2023/12/25 08:31:09 > step from lsr to rzs. visited : Set{frs, lsr}
2023/12/25 08:31:09 > step from rzs to cmg. visited : Set{frs, lsr, rzs}
2023/12/25 08:31:09 > step from cmg to rzs. visited : Set{lsr, rzs, cmg, frs}
2023/12/25 08:31:09 <<<< cycle true, from cmg to rzs
2023/12/25 08:31:09 entering remove edge for cmg and rzs
2023/12/25 08:31:09 before remove first [cmg : Set{rzs, qnr, nvd}]
2023/12/25 08:31:09 removed first [cmg : Set{qnr, nvd}]
2023/12/25 08:31:09 before remove second [cmg : Set{qnr, nvd}]
2023/12/25 08:31:09 removed second [rzs : Set{lsr, rsh, qnr}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from ntq and neighbors Set{xhk, hfx, bvb}
2023/12/25 08:31:09 initial dfs from ntq to bvb with initial visited Set{ntq}
2023/12/25 08:31:09 > step from ntq to bvb. visited : Set{ntq}
2023/12/25 08:31:09 > step from bvb to rhn. visited : Set{ntq, bvb}
2023/12/25 08:31:09 > step from rhn to xhk. visited : Set{bvb, ntq, rhn}
2023/12/25 08:31:09 > step from xhk to hfx. visited : Set{bvb, ntq, rhn, xhk}
2023/12/25 08:31:09 > step from hfx to bvb. visited : Set{xhk, bvb, ntq, rhn, hfx}
2023/12/25 08:31:09 <<<< cycle true, from hfx to bvb
2023/12/25 08:31:09 entering remove edge for hfx and bvb
2023/12/25 08:31:09 before remove first [hfx : Set{rhn, bvb, pzl, ntq, xhk}]
2023/12/25 08:31:09 removed first [hfx : Set{ntq, xhk, rhn, pzl}]
2023/12/25 08:31:09 before remove second [hfx : Set{pzl, ntq, xhk, rhn}]
2023/12/25 08:31:09 removed second [bvb : Set{ntq, rhn, xhk}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from rhn and neighbors Set{xhk, bvb, hfx}
2023/12/25 08:31:09 initial dfs from rhn to bvb with initial visited Set{rhn}
2023/12/25 08:31:09 > step from rhn to bvb. visited : Set{rhn}
2023/12/25 08:31:09 > step from bvb to rhn. visited : Set{bvb, rhn}
2023/12/25 08:31:09 <<<< cycle true, from bvb to rhn
2023/12/25 08:31:09 entering remove edge for bvb and rhn
2023/12/25 08:31:09 before remove first [bvb : Set{ntq, rhn, xhk}]
2023/12/25 08:31:09 removed first [bvb : Set{ntq, xhk}]
2023/12/25 08:31:09 before remove second [bvb : Set{ntq, xhk}]
2023/12/25 08:31:09 removed second [rhn : Set{xhk, hfx}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from rhn and neighbors Set{xhk, hfx}
2023/12/25 08:31:09 initial dfs from rhn to hfx with initial visited Set{rhn}
2023/12/25 08:31:09 > step from rhn to hfx. visited : Set{rhn}
2023/12/25 08:31:09 > step from hfx to pzl. visited : Set{rhn, hfx}
2023/12/25 08:31:09 > step from pzl to rsh. visited : Set{rhn, hfx, pzl}
2023/12/25 08:31:09 > step from rsh to frs. visited : Set{hfx, pzl, rsh, rhn}
2023/12/25 08:31:09 > step from frs to qnr. visited : Set{rsh, frs, rhn, hfx, pzl}
2023/12/25 08:31:09 > step from qnr to cmg. visited : Set{rsh, frs, rhn, hfx, pzl, qnr}
2023/12/25 08:31:09 > step from cmg to qnr. visited : Set{hfx, pzl, qnr, cmg, rsh, frs, rhn}
2023/12/25 08:31:09 <<<< cycle true, from cmg to qnr
2023/12/25 08:31:09 entering remove edge for cmg and qnr
2023/12/25 08:31:09 before remove first [cmg : Set{qnr, nvd}]
2023/12/25 08:31:09 removed first [cmg : Set{nvd}]
2023/12/25 08:31:09 before remove second [cmg : Set{nvd}]
2023/12/25 08:31:09 removed second [qnr : Set{nvd, rzs, frs}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from lsr and neighbors Set{rsh, pzl, lhk, rzs, frs}
2023/12/25 08:31:09 initial dfs from lsr to frs with initial visited Set{lsr}
2023/12/25 08:31:09 > step from lsr to frs. visited : Set{lsr}
2023/12/25 08:31:09 > step from frs to rsh. visited : Set{lsr, frs}
2023/12/25 08:31:09 > step from rsh to frs. visited : Set{lsr, frs, rsh}
2023/12/25 08:31:09 <<<< cycle true, from rsh to frs
2023/12/25 08:31:09 entering remove edge for rsh and frs
2023/12/25 08:31:09 before remove first [rsh : Set{frs, pzl, lsr, rzs}]
2023/12/25 08:31:09 removed first [rsh : Set{rzs, pzl, lsr}]
2023/12/25 08:31:09 before remove second [rsh : Set{rzs, pzl, lsr}]
2023/12/25 08:31:09 removed second [frs : Set{qnr, lhk, lsr}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from rhn and neighbors Set{xhk, hfx}
2023/12/25 08:31:09 initial dfs from rhn to xhk with initial visited Set{rhn}
2023/12/25 08:31:09 > step from rhn to xhk. visited : Set{rhn}
2023/12/25 08:31:09 > step from xhk to hfx. visited : Set{rhn, xhk}
2023/12/25 08:31:09 > step from hfx to pzl. visited : Set{rhn, xhk, hfx}
2023/12/25 08:31:09 > step from pzl to rsh. visited : Set{rhn, xhk, hfx, pzl}
2023/12/25 08:31:09 > step from rsh to rzs. visited : Set{rhn, xhk, hfx, pzl, rsh}
2023/12/25 08:31:09 > step from rzs to rsh. visited : Set{rzs, rsh, rhn, xhk, hfx, pzl}
2023/12/25 08:31:09 <<<< cycle true, from rzs to rsh
2023/12/25 08:31:09 entering remove edge for rzs and rsh
2023/12/25 08:31:09 before remove first [rzs : Set{lsr, rsh, qnr}]
2023/12/25 08:31:09 removed first [rzs : Set{qnr, lsr}]
2023/12/25 08:31:09 before remove second [rzs : Set{lsr, qnr}]
2023/12/25 08:31:09 removed second [rsh : Set{pzl, lsr}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from xhk and neighbors Set{hfx, rhn, bvb, ntq}
2023/12/25 08:31:09 initial dfs from xhk to hfx with initial visited Set{xhk}
2023/12/25 08:31:09 > step from xhk to hfx. visited : Set{xhk}
2023/12/25 08:31:09 > step from hfx to pzl. visited : Set{xhk, hfx}
2023/12/25 08:31:09 > step from pzl to rsh. visited : Set{xhk, hfx, pzl}
2023/12/25 08:31:09 > step from rsh to pzl. visited : Set{pzl, xhk, hfx, rsh}
2023/12/25 08:31:09 <<<< cycle true, from rsh to pzl
2023/12/25 08:31:09 entering remove edge for rsh and pzl
2023/12/25 08:31:09 before remove first [rsh : Set{pzl, lsr}]
2023/12/25 08:31:09 removed first [rsh : Set{lsr}]
2023/12/25 08:31:09 before remove second [rsh : Set{lsr}]
2023/12/25 08:31:09 removed second [pzl : Set{lsr, hfx, nvd}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from rsh and neighbors Set{lsr}
2023/12/25 08:31:09 initial dfs from rsh to lsr with initial visited Set{rsh}
2023/12/25 08:31:09 > step from rsh to lsr. visited : Set{rsh}
2023/12/25 08:31:09 > step from lsr to frs. visited : Set{rsh, lsr}
2023/12/25 08:31:09 > step from frs to qnr. visited : Set{frs, lsr, rsh}
2023/12/25 08:31:09 > step from qnr to nvd. visited : Set{lsr, rsh, frs, qnr}
2023/12/25 08:31:09 > step from nvd to jqt. visited : Set{rsh, frs, qnr, nvd, lsr}
2023/12/25 08:31:09 > step from jqt to nvd. visited : Set{lsr, rsh, frs, qnr, nvd, jqt}
2023/12/25 08:31:09 <<<< cycle true, from jqt to nvd
2023/12/25 08:31:09 entering remove edge for jqt and nvd
2023/12/25 08:31:09 before remove first [jqt : Set{nvd}]
2023/12/25 08:31:09 removed first [jqt : Set{}]
2023/12/25 08:31:09 before remove second [jqt : Set{}]
2023/12/25 08:31:09 removed second [nvd : Set{cmg, pzl, qnr, lhk}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from bvb and neighbors Set{ntq, xhk}
2023/12/25 08:31:09 initial dfs from bvb to ntq with initial visited Set{bvb}
2023/12/25 08:31:09 > step from bvb to ntq. visited : Set{bvb}
2023/12/25 08:31:09 > step from ntq to xhk. visited : Set{bvb, ntq}
2023/12/25 08:31:09 > step from xhk to hfx. visited : Set{ntq, xhk, bvb}
2023/12/25 08:31:09 > step from hfx to pzl. visited : Set{bvb, ntq, xhk, hfx}
2023/12/25 08:31:09 > step from pzl to nvd. visited : Set{pzl, bvb, ntq, xhk, hfx}
2023/12/25 08:31:09 > step from nvd to qnr. visited : Set{hfx, pzl, nvd, bvb, ntq, xhk}
2023/12/25 08:31:09 > step from qnr to nvd. visited : Set{pzl, nvd, bvb, ntq, xhk, hfx, qnr}
2023/12/25 08:31:09 <<<< cycle true, from qnr to nvd
2023/12/25 08:31:09 entering remove edge for qnr and nvd
2023/12/25 08:31:09 before remove first [qnr : Set{nvd, rzs, frs}]
2023/12/25 08:31:09 removed first [qnr : Set{rzs, frs}]
2023/12/25 08:31:09 before remove second [qnr : Set{frs, rzs}]
2023/12/25 08:31:09 removed second [nvd : Set{pzl, lhk, cmg}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from pzl and neighbors Set{lsr, hfx, nvd}
2023/12/25 08:31:09 initial dfs from pzl to lsr with initial visited Set{pzl}
2023/12/25 08:31:09 > step from pzl to lsr. visited : Set{pzl}
2023/12/25 08:31:09 > step from lsr to rsh. visited : Set{pzl, lsr}
2023/12/25 08:31:09 > step from rsh to lsr. visited : Set{pzl, lsr, rsh}
2023/12/25 08:31:09 <<<< cycle true, from rsh to lsr
2023/12/25 08:31:09 entering remove edge for rsh and lsr
2023/12/25 08:31:09 before remove first [rsh : Set{lsr}]
2023/12/25 08:31:09 removed first [rsh : Set{}]
2023/12/25 08:31:09 before remove second [rsh : Set{}]
2023/12/25 08:31:09 removed second [lsr : Set{rzs, frs, pzl, lhk}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from rhn and neighbors Set{xhk, hfx}
2023/12/25 08:31:09 initial dfs from rhn to xhk with initial visited Set{rhn}
2023/12/25 08:31:09 > step from rhn to xhk. visited : Set{rhn}
2023/12/25 08:31:09 > step from xhk to hfx. visited : Set{rhn, xhk}
2023/12/25 08:31:09 > step from hfx to pzl. visited : Set{hfx, rhn, xhk}
2023/12/25 08:31:09 > step from pzl to lsr. visited : Set{rhn, xhk, hfx, pzl}
2023/12/25 08:31:09 > step from lsr to frs. visited : Set{xhk, hfx, pzl, rhn, lsr}
2023/12/25 08:31:09 > step from frs to qnr. visited : Set{rhn, lsr, xhk, hfx, pzl, frs}
2023/12/25 08:31:09 > step from qnr to rzs. visited : Set{qnr, rhn, lsr, xhk, hfx, pzl, frs}
2023/12/25 08:31:09 > step from rzs to lsr. visited : Set{hfx, rzs, pzl, frs, qnr, rhn, lsr, xhk}
2023/12/25 08:31:09 <<<< cycle true, from rzs to lsr
2023/12/25 08:31:09 entering remove edge for rzs and lsr
2023/12/25 08:31:09 before remove first [rzs : Set{lsr, qnr}]
2023/12/25 08:31:09 removed first [rzs : Set{qnr}]
2023/12/25 08:31:09 before remove second [rzs : Set{qnr}]
2023/12/25 08:31:09 removed second [lsr : Set{lhk, frs, pzl}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from frs and neighbors Set{qnr, lhk, lsr}
2023/12/25 08:31:09 initial dfs from frs to qnr with initial visited Set{frs}
2023/12/25 08:31:09 > step from frs to qnr. visited : Set{frs}
2023/12/25 08:31:09 > step from qnr to rzs. visited : Set{frs, qnr}
2023/12/25 08:31:09 > step from rzs to qnr. visited : Set{frs, qnr, rzs}
2023/12/25 08:31:09 <<<< cycle true, from rzs to qnr
2023/12/25 08:31:09 entering remove edge for rzs and qnr
2023/12/25 08:31:09 before remove first [rzs : Set{qnr}]
2023/12/25 08:31:09 removed first [rzs : Set{}]
2023/12/25 08:31:09 before remove second [rzs : Set{}]
2023/12/25 08:31:09 removed second [qnr : Set{frs}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from frs and neighbors Set{qnr, lhk, lsr}
2023/12/25 08:31:09 initial dfs from frs to qnr with initial visited Set{frs}
2023/12/25 08:31:09 > step from frs to qnr. visited : Set{frs}
2023/12/25 08:31:09 > step from qnr to frs. visited : Set{frs, qnr}
2023/12/25 08:31:09 <<<< cycle true, from qnr to frs
2023/12/25 08:31:09 entering remove edge for qnr and frs
2023/12/25 08:31:09 before remove first [qnr : Set{frs}]
2023/12/25 08:31:09 removed first [qnr : Set{}]
2023/12/25 08:31:09 before remove second [qnr : Set{}]
2023/12/25 08:31:09 removed second [frs : Set{lsr, lhk}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from frs and neighbors Set{lsr, lhk}
2023/12/25 08:31:09 initial dfs from frs to lhk with initial visited Set{frs}
2023/12/25 08:31:09 > step from frs to lhk. visited : Set{frs}
2023/12/25 08:31:09 > step from lhk to nvd. visited : Set{frs, lhk}
2023/12/25 08:31:09 > step from nvd to cmg. visited : Set{lhk, nvd, frs}
2023/12/25 08:31:09 > step from cmg to nvd. visited : Set{nvd, cmg, frs, lhk}
2023/12/25 08:31:09 <<<< cycle true, from cmg to nvd
2023/12/25 08:31:09 entering remove edge for cmg and nvd
2023/12/25 08:31:09 before remove first [cmg : Set{nvd}]
2023/12/25 08:31:09 removed first [cmg : Set{}]
2023/12/25 08:31:09 before remove second [cmg : Set{}]
2023/12/25 08:31:09 removed second [nvd : Set{pzl, lhk}]
2023/12/25 08:31:09 >>>> starting new find cycle
2023/12/25 08:31:09 initial search from cmg and neighbors Set{}
2023/12/25 08:31:09 <<<< cycle false, from to
graph_test.go:57: removed edges Set{{frs qnr}, {cmg lhk}, {bvb cmg}, {bvb rhn}, {lsr rzs}, {jqt nvd}, {nvd qnr}, {cmg nvd}, {jqt rhn}, {cmg rzs}, {frs rsh}, {rsh rzs}, {jqt ntq}, {cmg qnr}, {lsr rsh}, {jqt xhk}, {bvb hfx}, {pzl rsh}, {qnr rzs}}
graph_test.go:58: after removal graph is {Nodes:map[bvb:[bvb : Set{ntq, xhk}] cmg:[cmg : Set{}] frs:[frs : Set{lhk, lsr}] hfx:[hfx : Set{rhn, pzl, ntq, xhk}] jqt:[jqt : Set{}] lhk:[lhk : Set{nvd, lsr, frs}] lsr:[lsr : Set{frs, pzl, lhk}] ntq:[ntq : Set{bvb, xhk, hfx}] nvd:[nvd : Set{pzl, lhk}] pzl:[pzl : Set{lsr, hfx, nvd}] qnr:[qnr : Set{}] rhn:[rhn : Set{xhk, hfx}] rsh:[rsh : Set{}] rzs:[rzs : Set{}] xhk:[xhk : Set{ntq, hfx, rhn, bvb}]]}
--- PASS: TestRemoveAllCycles (0.00s)
PASS
ok sunshine.industries/aoc2023/day25 0.003skind of bruteforce
graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 518391 graph_test.go:93: hopefully as answer: 0 graph_test.go:93: hopefully as answer: 518391 graph_test.go:93: hopefully as answer: 0