use Graph;
use strict;
use warnings;

my $g = Graph->new;

$g->add_edges(
	[0,1],
	[0,1],
	[0,1],
	[1,344],
	[1,202],
	[1,300],
	[2,3],
	[3,4],
	[4,202],
	[4,345],
	[4,5],
	[4,6],
	[5,440],
	[5,500],
	[5,508],
	[5,6],
	[5,505],
	[6,7],
	[6,201],
	[6,507],
	[6,503],
	[7,503],
	[7,2],
	[7,507],
	[7,200],
	[200,202],
	[202,201],
	[202,2],
	[300,2],
	[300,344],
	[300,502],
	[300,506],
	[300,202],
	[344,300],
	[345,4],
	[440,5],
	[500,5],
	[502,300],
	[503,6],
	[503,7],
	[505,5],
	[506,300],
	[507,6],
	[507,7],
	[508,6],
);

my $apsp = $g->all_pairs_shortest_paths;

my @V = sort { $a <=> $b } $g->vertices;
my %V; @V{@V}=@V;

print <<EOF;
The graph has the following states:

@V

Valid state transitions are:

$g

EOF

while (1)
{
	print "Enter a sequence of states on a single line. (blank line to exit)\n";
	local @ARGV;
	$_ = <>; chomp;
	my @P = split /\D+/;
	@P or last;
	grep { not exists $V{$_} } @P and warn("Sorry, at least one of those is not a valid state.\n"), next;

	for my $i ( 0 .. $#P-1 )
	{
		my @p2 = ( $P[$i], $P[$i+1] );
		my @PV = $apsp->path_vertices(@p2);
		@PV < 2 and print("The given state transition (@p2) is not valid in the given graph.\n"), next;
		$PV[0] eq $p2[0] && $PV[-1] eq $p2[-1] or warn("Bogus! (@p2) -> (@PV)!\n"), next;
		shift @PV; pop @PV;
		@PV and print "The given state transition (@p2) skips some states: (@PV)\n";
	}
}