Re: Challenge: Find median string in a list

[blokhead]

This problem in graph theory is known as the graph center problem. So here's a cop-out solution using Graph.pm:

use strict;
use warnings;
use Text::LevenshteinXS;
use Graph;

my $data = lc qq[Lorem ipsum dolor sit amet, consectetuer adipiscing e
+lit.
  Mauris vulputate nunc. Pellentesque pretium. Nam tortor. Vivamus sed
+ eros
  ut arcu consectetuer auctor. Nunc ultrices nisi. Phasellus congue se
+m quis
  nulla. Sed consequat. Etiam consectetuer. Sed ultricies libero at ma
+gna
  commodo nonummy. Sed quis arcu. Integer massa lectus, ultrices non, 
+faucibus
  eget, sagittis eget, lacus. ];

my @words = $data =~ m/\w+/g;

my $g = Graph::Undirected->new;

for my $i (0 .. $#words) {
  for my $j ($i+1 .. $#words) {
    $g->add_weighted_edge( @words[$i,$j], distance(@words[$i,$j]) );
  }
}

my $apsp = $g->all_pairs_shortest_paths;
my ($center, $radius) = (undef, 1_000_000);
for (@words) {
    my $x = $apsp->vertex_eccentricity($_);
    ($center, $radius) = ($_, $x) if $x < $radius;
}

print "$center ($radius)\n";

I'm sure there should be a more efficient algorithm for graph center than computing all pairs shortest paths (although it makes a difference if the bottleneck is computing Levenshtein distance or dealing with the big graph), but this is a starting point. Especially interesting would be an algorithm that explored the graph in an "on-line" fashion to avoid precomputing all the pairwise distances.

BTW, Graph.pm does offer a center_vertices method for the APSP object, but it appears to be broken (at least in my version of the module).

[Limbic~Region]

blokhead,
This solution took nearly 5 hours (compared to 0.28 seconds). I am not sure how well it would have done if center_vertices would have worked.