CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner:
Representing a connection matrix of graph

 



rushadrena
Novice

Aug 8, 2012, 4:58 AM

Post #1 of 18 (3376 views)
Representing a connection matrix of graph Can't Post

Hi all ,
I have this form of representation in array (N X 2) for my graph(undirected):-
a b
c d
a d
c a
f g
f h
What i want is its representation in this form
my %connections=(a=>[b,d],c=>[d,a],f=>[g,h]);


Laurent_R
Veteran / Moderator

Aug 8, 2012, 10:51 AM

Post #2 of 18 (3369 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

Hi,

If I understand what you want, you may try something like this (assuming the data is read from a file):


Code
my %HoA; 
while (<FILE>) {
($key, $value) = split;
push @{$HoA{$key}}, $value;
}



wickedxter
User

Aug 8, 2012, 4:27 PM

Post #3 of 18 (3356 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

this works

Code
use strict; 
use warnings;

my %connections;


while (<DATA>){
my ($value1, $value2) = split(' ');

$connections{$value1} = [] if ! defined $connections{$value1};

push (@{$connections{$value1}},$value2);

}


for my $keys (keys %connections){
print "$keys : ";
for my $array (@{$connections{$keys}}){
print "$array";
}
print "\n";
}


__DATA__
a b
c d
a d
c a
f g
f h


OUTPUTS:


Code
c : da 
a : bd
f : gh



(This post was edited by wickedxter on Aug 8, 2012, 4:27 PM)


rushadrena
Novice

Aug 9, 2012, 2:38 AM

Post #4 of 18 (3343 views)
Re: [wickedxter] Representing a connection matrix of graph [In reply to] Can't Post

This is what I have written : -


Code
# Takes input in the form 'a,b|c' 
# How to run : perl code.pl 'a,b|c' 'c,d|e' 'a,d|e'
# Outputs a NX3 for the above input data.
# Outputs connections in Nx2 form
use Data::Dumper;


$arg=join(' ',@ARGV);
@det=split //, $arg;

for ($i=0; $i <=8; $i++)
{$trip[$i]=$det[2*$i];}

my @array;
while (@trip) {
push(@array, [ splice(@trip, 0, 3) ]);
}
print "@$_\n" for @array;

for ($i=0; $i <=2; $i++)
{
for ($j=0; $j <=1; $j++)
{ $con[$i][$j]=$array[$i][$j];}
}
print "\n==========connections======\n";
print "from->to\n";
print " @$_\n" for @con;


Now do you know how to modify the above code so that it would read the input data(in the same format as presented in comments section) from a text file (each in a new line).
Actually I want to represent the Nx2 output which is :::
==========connections======
from->to
a b
c d
a d


For the above output I want this representation ::::

Code
%connections=(a=>[b,d],c=>[d]);



(This post was edited by rushadrena on Aug 9, 2012, 5:08 AM)


Laurent_R
Veteran / Moderator

Aug 9, 2012, 10:52 AM

Post #5 of 18 (3337 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

I'm not entirely sure I understand what you want, but the code I posted should do what you want.

It takes the input in the form:

a b
c d
a d

and stores the result in a hash of arrays in the form :

(a=>[b,d],c=>[d])


rushadrena
Novice

Aug 9, 2012, 9:15 PM

Post #6 of 18 (3331 views)
Re: [Laurent_R] Representing a connection matrix of graph [In reply to] Can't Post

Hi Laurent . I clubbed my code along with your code. But while trying to run it ,my pc goes out of memory/cpu (the while loop isnt getting terminated).



Code
# Takes input in the form 'a,b|c'  
# How to run : perl code.pl 'a,b|c' 'c,d|e' 'a,d|e'
# Outputs a NX3 for the above input data.
# Outputs connections in Nx2 form
use Data::Dumper;


$arg=join(' ',@ARGV);
@det=split //, $arg;

for ($i=0; $i <=8; $i++)
{$trip[$i]=$det[2*$i];}

my @array;
while (@trip) {
push(@array, [ splice(@trip, 0, 3) ]);
}
print "@$_\n" for @array;

for ($i=0; $i <=2; $i++)
{
for ($j=0; $j <=1; $j++)
{ $con[$i][$j]=$array[$i][$j];}
}
print "\n==========connections======\n";
print "from->to\n";
print " @$_\n" for @con;

my %HoA;
while (@con) {
($key, $value) = split;
push @{$HoA{$key}}, $value;
}


OUTPUT
[xguest@localhost Downloads]$ perl code.pl 'a,b|c' 'c,d|e' 'a,d|e'
a b c
c d e
a d e

==========connections======
from->to
a b
c d
a d
Out of memory!


(This post was edited by rushadrena on Aug 9, 2012, 9:17 PM)


Laurent_R
Veteran / Moderator

Aug 9, 2012, 11:19 PM

Post #7 of 18 (3324 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

The while syntax was assuming the data was in a file.



If in an array you should do this:




Code
foreach (@con) {  

# ...



rushadrena
Novice

Aug 10, 2012, 1:53 AM

Post #8 of 18 (3319 views)
Re: [Laurent_R] Representing a connection matrix of graph [In reply to] Can't Post

Ok so as you suggested I made the changes but while printing the hash its not printing the values rather adresses (see the code and output below) :

Code
  
my %HoA;
foreach (@con) {
($key, $value) = split;
push @{$HoA{$key}}, $value;
}
# PRINTING
foreach (keys %HoA) {
print "$_ => $HoA{$_}\n";
}


======OUTPUT======
ARRAY(0x82c70c4) => ARRAY(0x82c6ef4)
ARRAY(0x82c6f64) => ARRAY(0x82c6e94)
ARRAY(0x82c6fa4) => ARRAY(0x82c6ee4)


Laurent_R
Veteran / Moderator

Aug 10, 2012, 5:25 AM

Post #9 of 18 (3307 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

Yes, you have to dereference these values.

For example:


Code
my %HoA;  
while (<DATA>) {
($key, $value) = split;
push @{$HoA{$key}}, $value if defined $value;
}

foreach my $key (keys %HoA) {
print "\n $key => ";
print "$_ " foreach (@{$HoA{$key}});
}
print "\n";


__DATA__
a b
c d
a f
c a
f g
f h


which gives the following output:

c => d a
a => b f
f => g h


rushadrena
Novice

Aug 10, 2012, 5:56 AM

Post #10 of 18 (3304 views)
Re: [Laurent_R] Representing a connection matrix of graph [In reply to] Can't Post

As per all your suggestions I did this but its not printing anything at all.
Laurent are you reading the "DATA" from a text file in the same directory if yes then let me know a little about how you are doing it. Because Im actually reading the @con in the while loop.


Code
my %HoA;   
foreach (@con) {
($key, $value) = split;
push @{$HoA{$key}}, $value if defined $value;
}

foreach my $key (keys %HoA) {
print "\n $key => ";
print "$_ " foreach (@{$HoA{$key}});
}
print "\n";



Laurent_R
Veteran / Moderator

Aug 10, 2012, 8:44 AM

Post #11 of 18 (3298 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

The data I am reading from is located at the end of the program, after the __DATA__ markup:


Code
__DATA__   
a b
c d
a f
c a
f g
f h


I think your @con array is probably not populated as you expect, and therefore the hash of arrays does not get populated.


Laurent_R
Veteran / Moderator

Aug 11, 2012, 1:06 AM

Post #12 of 18 (3282 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

I gave you the complete way of printing the data the way you wish in order to show how to access the data elements in the structure, but if you just want to pretty print the hash data structure, you should probably use the Data::Dumper module.


rushadrena
Novice

Aug 11, 2012, 7:48 AM

Post #13 of 18 (3276 views)
Re: [Laurent_R] Representing a connection matrix of graph [In reply to] Can't Post

Thanks a lot Laurent.
But my problem is that I want to read the "DATA" generated from the program itself and thus my "DATA" isn't static/hard coded. So could you please help figure how to format the @con properly ,because @con has to be used for further data analysis and passing on to other functions etc. in an extension of the same program. So if there's a fault with @con then that's my main concern.


Laurent_R
Veteran / Moderator

Aug 11, 2012, 9:09 AM

Post #14 of 18 (3271 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

I for sure understand that you don't want to process static data appended at the end of your program. That wouldn't be very useful, this was just an example for you. If you were reading from a file lines looking like the sample data at the end of my program, you could use exactly the same syntax.

Your slightly different syntax is correct to visit all the @con array elements.

But for your program as you showed it to work correctly, each of the @con array elements needs to contain a pair of words separated by a white space. For example, you could possibly have:

Code
$con[0] may contain "a b" 
$con[1] may contain "foo bar"
$con[2] may contain "Jan 01"
$con[3] may contain "Feb 02"
etc.


The main point is that for the syntax:

Code
foreach (@con) { 
($one, $two) = split ;
# ...
}

to work correctly, the @con array element being visited must contain two words separated by a white space (or, at least two words, but if there are more than two words, only the first two words would be taken into account).

In other words, each array element must contain something looking more or less like anyone of the lines I used in my input example (except that the words may contain more than one letter).

The alternative is that you tell me what you currently have in the @con array, so that I can change my sample syntax to fit it to your data format, if possible.

Currently, it looks like @con might just be empty. Possibily you chould try to print it contents. Or maybe I could help you if you told me how you are currently trying to populate this array.


(This post was edited by Laurent_R on Aug 11, 2012, 9:17 AM)


rushadrena
Novice

Aug 11, 2012, 1:24 PM

Post #15 of 18 (3256 views)
Re: [Laurent_R] Representing a connection matrix of graph [In reply to] Can't Post

Thanks Laurent,
1.> Actually the content of @con(which has two columns only) is there in the post #6 of this thread.
==========connections======
from->to
a b
c d
a d

2.> @con is getting its content from @array which has 3 columns.
So if the user enters these as arguments to the code :-
'a,b|c' 'c,d|e' 'a,d|e'
Then the code should save this input in 3x3 array(a row corresponding to each of the three input).
Then the code should extract first two columns of this array and save them in @con (connection).
Now this @con will be used to generate the hash the result of which should be :- (a=>[b,d],c=>[d])


Laurent_R
Veteran / Moderator

Aug 11, 2012, 5:12 PM

Post #16 of 18 (3248 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

It is really a data format issue.

As I said, the code you presented (derived from what I proposed) is based on the idea that the data elements contain pairs of words separated by a space character.

If your @con array has data in a different format, it will not work.

Your data description (a,b|c' 'c,d|e' 'a,d|e') is different, therefore the program cannot read the data.

At the same time, I do not see how you are storing something like (a,b|c' 'c,d|e' 'a,d|e') in a simple array.

Please explain what you really want and how you expect it to work.

The code I presented does work fine; if it does not work for you, then there must be something else that does not work in your code.


BillKSmith
Veteran

Aug 11, 2012, 8:34 PM

Post #17 of 18 (3242 views)
Re: [rushadrena] Representing a connection matrix of graph [In reply to] Can't Post

Laurent is certainly right. Your requirements are hopelessly inconsistent from one post to the next. I have answered a nearly identical post in the perl monks forum. This suggests that either this is a school assignment or you have no interest in learning perl, but want someone to do your work for you. If this is not true, I suggest that you post a complete working package, including your perl code, all referenced data files, instructions for running it, and the exact output expected. We will be able to run it, examine the output, and help you correct the code.

Your post #15 is a step in the right direction, but I am not sure what code you are using or exactly what is wrong. I do not see any need for either @array or @con. I would parse the arguments with a regular expression, and store the data directly in the hash. Note: Your sample data is used if no arguments are provided.



Code
  

# Takes input in the form 'a,b|c'
# How to run : perl code.pl 'a,b|c' 'c,d|e' 'a,d|e'
# Outputs a NX3 for the above input data.
# Outputs connections in Nx2 form
use strict;
use warnings;

@ARGV = ('a,b|c', 'c,d|e', 'a,d|e') unless @ARGV;

my %HoA;
foreach ( @ARGV ) {
m/^([a-z])[,]([a-z])[|]([a-z])$/ ;
push @{$HoA{$1}}, $2;
}
print "\n===========\@HoA=====\n";
print "from->to\n";
while (my ($key, $values) = each %HoA) {
print $key, "=> [", join(',', @$values), "]\n";
}

SAMPLE_OUTPUT (default data)


=========HOA=======

from->to
c=> [d]
a=> [b,d]

Good Luck,
Bill

(This post was edited by BillKSmith on Aug 11, 2012, 8:58 PM)


rushadrena
Novice

Aug 11, 2012, 11:31 PM

Post #18 of 18 (3238 views)
Re: [BillKSmith] Representing a connection matrix of graph [In reply to] Can't Post

That was spot on !!!!
Thanks Bill, Laurent and wikedxter.
And its not a homework but related to some research.
I definitely will try to frame my questions properly the next time onwards.
Now I have to parse through this Hash in order to find all the connected components in this graph (along with their vertices and connections). Could you suggest me a module or algorithm which would help me achieve the same.

Thanks a lot for your precious time, all you guys.

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives