This should help you over the first hurdle. At the end of the following snippet you have two hashes to start with. One hash describes the edges and the other the vertices found. Putting these informations into hashes let you access them by node/vertex number quite easily:

#!/usr/bin/perl
use strict;
use warnings;

use 5.010;
use Data::Dumper;

my $VERY_BIG_NUM = 2_000_000_000;

my @problem = grep { $_ !~ /^\s*#/ and $_ !~ /^\s*$/ } map { chomp; $_
+ } <DATA>;
die "ERROR: Problem description incomplete."
    unless(@problem >= 3);

my ($num_of_vertices, $num_of_edges) = split / /, shift @problem;
die "ERROR: Not enough vertices given."
    unless($num_of_vertices and $num_of_vertices > 1);
die "ERROR: No edge given."
    unless($num_of_edges);

die "ERROR: Number of edges not equal to declare numberd $num_of_edges
+ of edges."
    if(@problem - 1 != $num_of_edges);

# Get the problem to solve
my ($start_vertex, $end_vertex) = split / /, pop @problem;
say "Problem with $num_of_vertices vertices and $num_of_edges edges";
say "Determine shortes path from vertex $start_vertex to $end_vertex";

# read the remaining edges
my %vertices;
my %edges;

foreach my $edge (@problem) {
    my ($start, $end) = split / /, $edge;
    $edges{$start}->{$end} = {
        'weight' => 1,
    };
    $edges{$end}->{$start} = $edges{$start}->{$end};

    foreach my $node ($start, $end) {
        $vertices{$node} = {
            'predecessor' => undef,
            'distance' => $node == $start_vertex ? 0 : $VERY_BIG_NUM,
        };
    }
}

say "Vertices: " . Dumper(\%vertices);
say "Edges: " . Dumper(\%edges);


__DATA__
5 6
1 2
2 3
2 4
4 5
1 3
3 5
1 5
[download]

We all - at least me - will be interested to see how your algorithms will be implemented.

Regards
McA

saurabh2k26:

You don't really need external modules to handle problems like this. It's pretty simple to represent graphs and trees with the basic perl data structures:

$ cat foo.pl
#!/usr/bin/env perl
use strict;
use warnings;
use Data::Dump qw(pp);

my $t = <DATA>;
my ($nV, $nE) = split /\s+/,$t;

# read graph
my %G;
my ($src, $dst);
while (<DATA>) {
    next if /^\s+$/;
    ($src, $dst) = split /\s+/;
    last if !$nE--;
    $G{$src}{$dst}=0;
    $G{$dst} = {} if ! exists $G{$dst};
}

print pp(\%G),"\nStart: $src, End: $dst\n\n";

__DATA__
5 6
1 2
2 3
2 4
4 5
1 3
3 5
1 5

$ perl foo.pl
{
  1 => { 2 => 0, 3 => 0 },
  2 => { 3 => 0, 4 => 0 },
  3 => { 5 => 0 },
  4 => { 5 => 0 },
  5 => {},
}
Start: 1, End: 5
[download]

Since your data was a graph, I used a hash to represent the data. If you had a tree, you could use nested array references. Once you read it in, it's just a matter of adding the algorithm you want to try.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

Thanks, i tried this and it works and i am getting to understand it. But again, Data::Dump is not allowed in programming contests. Can you update your code without using Data::Dump

saurabh2k26:

I just used Data::Dump to print the data structure to the screen. You don't need it at all, but I needed it or you wouldn't see what data structure was created. Once you understand the data structure and create your algorithm, you can present the results any way you like.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

You wanted to get a starting point. You got one, no two.

Do you want to win a contest or do you want to learn Perl?

Regards
McA

Hi,

there are several algorithms out there to determine the shortest path, e.g. Dijkstra's algorithm. So, what you have to do is to implement this algorithm in Perl.

Where are your concrete programming problems?

Regards
McA

I dont know where to start. I mean, after taking inputs, how to store them as vertex and edges. How to check the connecting edges.

saurabh2k26:

As you can see from McA's and my code examples, there are plenty of ways to represent the data structures. For the code McA presented, you can check if a node exists via if (exists $vertices{$node}) { ... } and edges with if (exists $edges{$src}{$dst}) { ... }. In my example, I opted to use a two-level hash, where the first key is the source node and the second key is the destination. So in mine you'd test whether a node exists the same way as McA presented, but to check for the edge, you need to use if (exists $G{$src} and exists $G{$src}{$dst}) { ... }. (You can omit the first clause if you know that the source node exists, but if you're not certain, you need the first clause so that you don't accidentally create (through autovivification) new graph nodes. For example, if you add this line just before the print statement in my code:

print "BAM!\n" if exists $G{25}{30};
[download]

You'll find that node 25 gets added to your graph:

{
  1  => { 2 => 0, 3 => 0 },
  2  => { 3 => 0, 4 => 0 },
  3  => { 5 => 0 },
  4  => { 5 => 0 },
  5  => {},
  25 => {},
}
Start: 1, End: 5
[download]

Update: If I were going to store any significant data in the nodes, then I'd make it a three-level hash, where the second level would be {EDGES} to let you represent the graph structure, and other keys would hold the node-specific data. The data elements under the {EDGES} can hold edge-specific data, like so:

my %G = (
   1=>{ EDGES=> { # Edges for node 1
           2=>{ "Data for edge 1->2" },
           3=>{ "Data for edge 1->3" },
        FOO=> { "a data element for node 1" },
        BAR=> { "another data elemment for node 1" },
   },
   2=> ...
}
[download]

If you use McA's method, you can just use the two hashes to hold the data, instead of adding a hash key layer.

...roboticus

When your only tool is a hammer, all problems look like your thumb.

The IMHO easiest way to represent your data is a hash of arrays, (though the input format looks icky.)

For instance $edge{2}=[3,4]

So you'll need a parser to read the input into this HoA (see Perldsc for details) and a search algorithm like Dijkstra's algorithm.

Please show us some of your attempts to help you, I long stopped providing code for stuff looking like homework. ;)

PS: tried to post this 5h ago but the site was unresponsive. in the meantime people tried to pamper the OP with ready to use code...O.o

LanX! Quoting wikipedia:

In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Of course it can be done in perl! For a sample problem such as given, here's a sample solution.

#! /usr/bin/perl

chomp ((undef, my @D) = <DATA>);
(my $Q = pop @D) =~ s/ /\\b.+\\b/;

sub xt { grep s/\b(\d+),\1\b/$1/, map qq/$_[0],$_/, @_ }
sub tx { print,exit for grep /^$Q$/, @_; map {xt $_, @_} @_ }

push @D, tx @D for \(@D);

__DATA__
5 6
1 2
2 3
2 4
4 5
1 3
3 5
1 5
[download]

Updates: Fix the /$Q/ test per Loops's suggestion. Add \b-s to s///.

> without simple cycles is a tree.

Look at the data to discover the circle cycle :)

1 2; 2 3; 1 3

Cheers Rolf

_{(addicted to the Perl Programming Language and ☆☆☆☆ :)}

This does not look as a cycle or a circle to me.

Such a shame that Graph is out of support.

use 5.16.2;
use warnings;

use Graph;

my $g = Graph->new;

while (<DATA>) {
    $g->add_edge (m/(\w+)/g);
    }

say join "-" => $g->SP_Dijkstra (1, 5);
__END__
5 6
1 2
2 3
2 4
4 5
1 3
3 5

->

1-3-5
[download]