![Thu Jan 16 08:03:03 2014 (19.7k) by Esraa_Swillam [...] mentor.com](/Ticket/Attachment/1313092/695990/image001.png){kind=link}
| Subject: | longest path is not calculated correctly in this case |
| Date: | Thu, 16 Jan 2014 13:02:44 +0000 |
| To: | "bug-Graph [...] rt.cpan.org" <bug-Graph [...] rt.cpan.org> |
| From: | "Swillam, Esraa" <Esraa_Swillam [...] mentor.com> |
Hi there,
I have a weighted directed acyclic graph and I wan tto calculate its longest path length
If my graph looks like below, longest path or diameter is not calculated correctly it gets confused between last 2 branches and pick the one with smaller weight instead
[cid:image001.png@01CF12CC.017E5A80]
my $g = Graph::Directed->new;
my $edge_list = [
{
u=>"a",
v=>"b",
l=>2,
w=>4.25,
},
{
u=>"b",
v=>"c",
l=>2,
w=>2,
},
{
u=>"c",
v=>"d",
l=>2,
w=>2,
},
{
u=>"d",
v=>"e",
l=>2,
w=>2,
},
{
u=>"d",
v=>"f",
l=>2,
w=>2,
},
{
u=>"e",
v=>"g",
l=>6,
w=>2,
},
{
u=>"f",
v=>"g",
l=>4,
w=>2,
},
];
foreach my $edge (@$edge_list) {
message ("$edge->{u}:$edge->{v}:$edge->{l}:$edge->{w}");
$g->add_weighted_edge ($edge->{u},$edge->{v},$edge->{l});
}
print "The graph is $g\n";
my $check_DAG= $g->is_directed_acyclic_graph;
my $gd = $g->diameter;
my @lp = $g->longest_path;
my $lp = $g->longest_path;
my $edge_check = $g->has_edge("1,2", "3,4");
message ("This Graph is DAG $check_DAG");
message ("Graph diameter is $gd");
message ("Graph longest shortest path length is $lp");
message ("Graph longest shortest path length is @lp");
output:
The graph is a-b,b-c,c-d,d-e,d-f,e-g,f-g
This Graph is DAG 1
Graph diameter is 12
Graph longest shortest path length is 12
Graph longest shortest path length is a b c d f g
Thanks for providing fast feedback
Thanks
-Regards
Esraa
Message body is not shown because it is too large.