Beefy Boxes and Bandwidth Generously Provided by pair Networks
Keep It Simple, Stupid
 
PerlMonks  

Tree in perl

by saurabh2k26 (Initiate)
on Nov 17, 2014 at 14:01 UTC ( #1107410=perlquestion: print w/replies, xml ) Need Help??

saurabh2k26 has asked for the wisdom of the Perl Monks concerning the following question:

I use PERL to participate in many online quiz websites like codechef, hackerrank etc. In such contest, installing a module like Graphs is not allowed. I observed that no one attempts such problem using PERL, most of them use C++, but in other problems, people do you PERL a lot.

I am looking for a approach in PERL without using any module for TREE problems

Sample problem: find shortest path from a to b

Input
line 1= no of vertex(v) and no of edges(e)(separated by space)
Next e lines containing v1 and v2 ie there exists a edge between v1 and v2
Next line contains a and b
Sample:
5 6
1 2
2 3
2 4
4 5
1 3
3 5
1 5
So we want shortest path from 1 to 5
OUTPUT
1-3-5

Replies are listed 'Best First'.
Re: Tree in perl
by McA (Priest) on Nov 17, 2014 at 15:04 UTC

    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

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

    Regards
    McA

Re: Tree in perl
by roboticus (Chancellor) on Nov 17, 2014 at 15:05 UTC

    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

    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

        A reply falls below the community's threshold of quality. You may see it by logging in.
Re: Tree in perl
by McA (Priest) on Nov 17, 2014 at 14:12 UTC

    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};

        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

        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=> ... }

        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.

Re: Tree in perl
by LanX (Sage) on Nov 17, 2014 at 19:41 UTC
    It's a graph not a tree problem.

    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. ;)

    Cheers Rolf

    (addicted to the Perl Programming Language and ☆☆☆☆ :)

    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

Re: Tree in perl
by oiskuu (Hermit) on Nov 17, 2014 at 20:27 UTC

    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

    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.
Re: Tree in perl
by Tux (Canon) on Nov 18, 2014 at 20:44 UTC

    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

    Enjoy, Have FUN! H.Merijn

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1107410]
Approved by Corion
Front-paged by tye
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (2)
As of 2022-08-14 17:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?