Asymptotically Typeable

Home Blog RSS

Upon Reading a Friend's Message about the Awesomeness of the Kosaraju Algorithm

Sun, 08 Mar 2020
  1. Let us say you reader work as a match-maker
  2. And a client complain'd about a deal-breaker.
  3. "She dated a dear friend before" was what he said,
  4. "I'd find it most abhor if we had shared a bed.
  5. Not known to my social circle make sure she be,
  6. Or by god, this bad-buck business I'll rate shabby."
  7. A problem like this one dear ol' Kosaraju
  8. Tried to solve. But was it more than what he could chew?
  9. Fear not, for foresight sleekly set him out to find
  10. An algorithm so neat; a one-of-a-kind.
  11. One that runs linearly in time and in space,
  12. Designed neatly to be speedy and full of grace.
  13. You must interpret first people as a network
  14. Where Bob connects to Alice if he was a jerk,
  15. or a lover, or simply in acknowledgement.
  16. Then comsume one strongly connected component
  17. That clearly does not include your careful client
  18. And pick potentials from that pool to be compliant.
  19. But how do you go about finding a strongly
  20. Connected component from a graph so quickly?
  21. Precisely that process Kosaraju and kin
  22. Published the year after nineteen seventy sev'n.
  23. Let list L from holding elements be acquit,
  24. First step is to set all vertices to-visit.
  25. Then one by one through the vertices you should loop
  26. And view each as visited, and its neighbors group
  27. To recurse on them after in L they'd instill
  28. If the vertex was marked to-visit, else nil.
  29. When pushing the neighbors be certain to prepend
  30. Cause the next step will crucially on it depend:
  31. To go in twine in the L-defined-order 'long
  32. The vertices and assign each itself belong.
  33. Where assignment is defined being twixt two nodes
  34. For former in the latter's assignment it abodes
  35. And its neighbors' assignment's nest in the latter
  36. If the former is assigned, else nil's the matter.
  37. For your match-making mess mister reader rummage
  38. Through those client-unassigned to avoid damage.