NAME
Algorithm::SixDegrees - Find a path through linked elements in a set
VERSION
Version 1.00
SYNOPSIS
use Algorithm::SixDegrees;
my $sd1 = Algorithm::SixDegrees->new();
$sd1->data_source( actors => \&starred_in );
$sd1->data_source( movies => \&stars_of );
@elems = $sd1->make_link('actors', 'Tom Cruise', 'Kevin Bacon');
my $sd2 = Algorithm::SixDegrees->new();
$sd2->forward_data_source( friends => \&friends, @args );
$sd2->reverse_data_source( friends => \&friend_of, @args );
@elems = $sd2->make_link('friends', 'Bob', 'Mark');DESCRIPTION
Algorithm::SixDegrees is a Perl implementation of a breadth-first search through a set of linked elements in order to find the shortest possible chain linking two specific elements together.
In simpler terms, this module will take a bunch of related items and attempt to find a relationship between two of them. It looks for the shortest (and generally, simplest) relationship it can find.
CONSTRUCTOR
new()
Algorithm::SixDegrees requires use as an object; it can't (yet) be used as a stand-alone module. new takes no arguments, however.
FUNCTIONS
forward_data_source( name => \&sub, @args );
Tells Algorithm::SixDegrees that all items in the data set relating to name can be retrieved by calling sub. See "SUBROUTINE RULES".
In our friends example above, if Bob considers Mark a friend, but Mark doesn't consider Bob a friend, calling the sub with "Bob" as an argument should return "Mark", but calling the sub with "Mark" as an argument should not return "Bob".
reverse_data_source( name => \&sub, @args );
Tells Algorithm::SixDegrees that all items in the data set related to by name can be retrieved by calling sub. See "SUBROUTINE RULES".
In the same friends example, calling the sub with "Bob" as an argument should not return "Mark", but calling the sub with "Mark" as an argument should return "Bob".
data_source( name => \&sub, @args );
Sets up a data source as both forward and reverse. This is useful if the data source is mutually relational; that is, in our actors/movies example, Kevin Bacon is always in Mystic River, and Mystic River always has Kevin Bacon in it.
make_link
Does the work of making the link. Returns a list or arrayref, based on calling context.
error
Returns the current value of $Algorithm::SixDegrees::ERROR. See "SUBROUTINE RULES".
SUBROUTINE RULES
Passed-in subroutines should take at least one argument, which should be some form of unique identifier, and return a list of unique identifiers that have a relation to the argument.
The unique identifiers must be able to be compared with eq.
The identifiers should be unique in datatype; that is, in an actor/movie relationship, "Kevin Bacon" can be both the name of an actor and a movie.
A linked data type must return identifiers that relate across the link; that is, for an actor/movie relationship, an actor subroutine should return movies, and a movie subroutine should return actors.
Additional arguments can be provided; these will be stored in the object and passed through as the second and further arguments to the subroutine. This may be useful, for example, if you're using some form of results caching and need to pass a tied handle around.
If you return explicit undef, please set $Algorithm::SixDegrees::ERROR with an error code. Explicit undef means that an error occurred that should terminate the search; it should be returned as a one-element list.
AUTHOR
Pete Krawczyk, <petek@cpan.org>
BUGS
Please report any bugs or feature requests to bug-algorithm-sixdegrees@rt.cpan.org, or through the web interface at http://rt.cpan.org. I will be notified, and then you'll automatically be notified of progress on your bug as I make changes.
ACKNOWLEDGEMENTS
Andy Lester and Ricardo Signes wrote Module::Starter, which helped get the framework up and running fairly quickly.
Brad Fitzpatrick of http://livejournal.com for giving me access to a LiveJournal interface to determine linking information on that site, which enabled me to write the algorithm that has been reduced into this module.
COPYRIGHT & LICENSE
Copyright 2005 Pete Krawczyk, All Rights Reserved.
This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.