Have bubble finder algorithms been discussed anywhere? Is SWATH's bubble finder still considered to be the best out there?

I personally prefer this one:

viewtopic.php?f=15&t=21335&p=183152&hilit=probubble#p183152

...but I might be a bit biased.

               / Promethius / Enigma / Wolfen /

"A man who has no skills can be taught, a man who has no honor has nothing."

I'm not sure I'm reading that correctly. Does it only find bubbles with one gate? Don't Gold bubbles usually have 3-4 gates?

A bubble should only have one way in. It might have more than one way out though.

               / Promethius / Enigma / Wolfen /

"A man who has no skills can be taught, a man who has no honor has nothing."

I'm interested in things like cutting the whole universe into large pieces... or finding a minimal cut that encloses all the MSLs.

The best person to contact on that would be EP. I know he has worked with bubble algorithms a lot. Might be able to modify the bubble script to allow more than 1 warp in to come up with larger "cuts". Defending it would be harder than the single warp-in, but a corp could do it possibly.

               / Promethius / Enigma / Wolfen /

"A man who has no skills can be taught, a man who has no honor has nothing."

I've done a lot of work with bubble searches over the years. I didn't study others' algorithms, but rather I came up with my own methods. I do believe I came up with a unique algorithm (after years of trying) that is able to find all single-door bubbles in the entire universe by running a single breadth-first search. Do you know where I might publish my work, and finally be recognized for my brilliance?

The obvious problem with bubble searches is that they can take forever to run. A simple single-door bubble search could be done by avoiding a sector, performing a BFS from Terra, and seeing how many sectors were queued. It would be Sectors-1 unless the voided sector is the door for a single-door bubble. An un-optimized TWX script can run this on a 5K universe in about 6 seconds, but the time that it takes increases exponentially with size. So a 30K universe (6x bigger) would take about 36 times as long, or 3.6 minutes. Natively, it would be much faster though. I think of this as an outside-looking-in approach, where you are looking for the "shadow" left when a sector is avoided. Assuming complete warp data, this method is comprehensive, but slows (without optimization) beyond a single-door, or in larger universes. For the TWXers, that script is as follows:Conversely you can attempt the opposite, or what I think of as an inside-looking-out approach, which is where optimizations like you mention come in. Here you might approach it by avoiding a sector, then performing a BFS on each of the avoid's adjacents that are farther from Terra. You have to use incoming warps, and you optimize by setting stopping points like maximum queue size and MSL sectors. I believe this is the technique used by SWATH, using maximum queue size as the stopping point. This can be much faster than the earlier approach, but often you don't know the maximum size of a Gold bubble. It could be up to Sectors-100, so the practical bubble limit is 1/2 of the size of the universe. But if you used that as your queue limit, you're back to the exponential slowness of the first approach.

Still, there are a number of ways to optimize either approach, which we could brainstorm here or via chat sometime. IM me if you want to schedule something.