NAME

Algorithm::SixDegrees - Find a path through linked elements in a set

VERSION

Version 1.01

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

Peter 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

Thank you to Slaven Rezić and Peter John Acklam for bug reports. Apologies it took so long to see and fix them. (So much for notifications...)

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-2020 Peter Krawczyk, All Rights Reserved.

This program is free software; you can redistribute it and/or modify it under the same terms as Perl itself.

cpanm Algorithm::SixDegrees

perl -MCPAN -e shell
install Algorithm::SixDegrees