2020 twenty-four merry days of Perl Feed

Gift Exchanges as a Practical Example of Cyclic Directional Graphs

Graph::Easy - 2020-12-21

2020 has been time consuming - a global pandemic, giant fires, horrific floods and political unrest - which has left us little time for side projects. This year we're looking back to happier times into the 20+ year archive with the Best of the Perl Advent Calendar.

Sometimes, graphs are huge, complex drawings showing the far-stretching relationships between myriads of elements.

Other times? We just feel the need to draw a few boxes and arrows to get a visual idea of what the heck is going on.

For those latter cases, Graph::Easy is your friend.

Graph::Easy is a helping elf with no delusion of grandeur. It is primary meant for tackling modest graphs (think less than 100 nodes), but it does it with a simplicity and an ease of use that is very nice indeed.

For example, let's say you're managing a gift exchange. A simple one where you just have to decide who's giving to who, and what. Well, that's easy enough:

use 5.16.0;

use Graph::Easy;
use List::AllUtils qw/ shuffle /;

my @peeps = shuffle qw/
    alice bernard charlotte dee ezekiel
    felicia gregory heidi isaac julia karl
    leo marie nathan
/
;

my @gifts = shuffle qw/
    book CD slippers teddy bear bathrobe
    mittens scarf chocolate candles wine
    clock calendar mirror playing cards
    beanie
/
;

my $exchange = Graph::Easy->new;

while( my( $i, $p ) = each @peeps ) {
# from, to, gift
$exchange->add_edge( $p, $peeps[$i-1], $gifts[$i] );
}

Our graph now contains all the information we want, and we can get it back in a variety of formats. We can get a human-friendly list of edges:

print $exchange->as_txt;

which will output

    [ ezekiel ] -- wine --> [ heidi ]
    [ heidi ] -- CD --> [ bernard ]
    [ bernard ] -- slippers --> [ charlotte ]
    [ charlotte ] -- playing --> [ leo ]
    [ leo ] -- book --> [ karl ]
    [ karl ] -- cards --> [ nathan ]
    [ nathan ] -- chocolate --> [ felicia ]
    [ felicia ] -- scarf --> [ marie ]
    [ marie ] -- teddy --> [ gregory ]
    [ gregory ] -- bear --> [ dee ]
    [ dee ] -- beanie --> [ alice ]
    [ alice ] -- mirror --> [ julia ]
    [ julia ] -- bathrobe --> [ isaac ]
    [ isaac ] -- clock --> [ ezekiel ]

or we can get an ascii representation of the graph:

    print $exchange->as_ascii;

which output

            chocolate
    +-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
    v                                                                                                                                                                                                                                                                       |
    +-------+  beanie   +---------+  candles   +------+  book   +---------+  teddy   +---------+  cards   +-------+  clock   +-----------+  slippers   +--------+  calendar   +---------+  bear   +-----+  mittens   +-------+  playing   +-----+  mirror   +-------+  CD   +-------+
    | marie | --------> | gregory | ---------> | karl | ------> | ezekiel | -------> | felicia | -------> | isaac | -------> | charlotte | ----------> | nathan | ----------> | bernard | ------> | dee | ---------> | julia | ---------> | leo | --------> | alice | ----> | heidi |
    +-------+           +---------+            +------+         +---------+          +---------+          +-------+          +-----------+             +--------+             +---------+         +-----+            +-------+            +-----+           +-------+       +-------+

Granted, that format is useful for small graphes, but it get hard to grok for bigger ones. For those, there are better suited graphical output formats. Like svg, provided by Graph::Easy::As_svg (which is not part of the core Graph::Easy distribution):

print $exchange->as_svg;

which gives us the prettier

Untitled graph playing clock bathrobe candles wine calendar CD bear teddy mittens book slippers mirror chocolate ezekiel nathan karl leo alice dee julia heidi charlotte felicia gregory bernard marie isaac

And, of course, in true Perlish fashion, we can also take things into our own hands and just work on the graph ourselves:

printf "From: %s, To: %s, item: %s\n", 
    $_->label,
# because we know there's only one edge per peep
map { $_->to->label, $_->label }$_->edges for $exchange->nodes;

which gives us

    From: alice, To: karl, item: beanie
    From: bernard, To: leo, item: playing
    From: charlotte, To: felicia, item: CD
    From: dee, To: dee, item: chocolate
    From: ezekiel, To: marie, item: mittens
    From: felicia, To: dee, item: chocolate
    From: gregory, To: nathan, item: bathrobe
    From: heidi, To: ezekiel, item: book
    From: isaac, To: bernard, item: cards
    From: julia, To: charlotte, item: mirror
    From: karl, To: julia, item: scarf
    From: leo, To: gregory, item: clock
    From: marie, To: alice, item: calendar
    From: nathan, To: nathan, item: bathrobe

See Also

Gravatar Image This article contributed by: Yanick Champoux <yanick@cpan.org>