Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

creating adjacency matrix

by ramdat (Initiate)
on Jan 06, 2011 at 02:48 UTC ( [id://880739]=perlquestion: print w/replies, xml ) Need Help??

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

Hi..I am new to perl.I want to know creating adjacency matrix for the following data: A B, B C, C D. i want matrix as following:
A B C D A 0 1 0 0 B 1 0 1 0 C 0 1 0 1 D 0 0 1 0
can any one please please help me out with the code...thanks in advance..

Replies are listed 'Best First'.
Re: creating adjacency matrix
by BrowserUk (Patriarch) on Jan 06, 2011 at 03:18 UTC

    Like this?

    #! perl -slw use strict; use Data::Dump qw[ pp ]; sub uniq{ my %h; undef @h{ @_ }; keys %h }; my @pairs = map[ split ], split ', ', 'A B, B C, C D';; my @uniq = uniq( map @$_, @pairs ); my %mat; @{ $mat{ $_ } }{ @uniq } = (0) x @uniq for @uniq; $mat{ $_->[0] }{ $_->[1] } = $mat{ $_->[1] }{ $_->[0] } = 1 for @pairs; pp \%mat; __END__ c:\test>880739 { A => { A => 0, B => 1, C => 0, D => 0 }, B => { A => 1, B => 0, C => 1, D => 0 }, C => { A => 0, B => 1, C => 0, D => 1 }, D => { A => 0, B => 0, C => 1, D => 0 }, }

    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
Re: creating adjacency matrix
by dHarry (Abbot) on Jan 06, 2011 at 10:37 UTC

    CPAN has several relevant modules. It depends on what you want to do with your graph, I assume the adjacency matrix is just the starting point. The most obvious choice: Graph::AdjacencyMatrix. It gives you additional functionality that you will probably need anyway. Take a look at the Graph modules!

    Cheers

    Harold

Re: creating adjacency matrix
by Marshall (Canon) on Jan 06, 2011 at 11:55 UTC
    You are asking for basically an "and" table. There are a bunch of ways that this could be made faster. But this is a fairly straight-forward general solution that does what you asked for.
    I did test this expanding to A-E and testing "C E" as a pair.

    that printed: A B C D E A 0 1 0 0 0 B 1 0 1 0 0 C 0 1 0 1 1 D 0 0 1 0 0 E 0 0 1 0 0
    #!/usr/bin/perl -w use strict; use Data::Dumper; =this prints A B C D A 0 1 0 0 B 1 0 1 0 C 0 1 0 1 D 0 0 1 0 =cut my @vars = qw(A B C D); my @square_matrix = map{ my @x; push (@x,0) foreach @vars; [@x] }@vars; my $num =0; my %ltr2num = map{ $_ => $num++ }@vars; my @pairs = ("A B", "B C", "C D"); ### the user input #### foreach my $pair (@pairs) { my ($x, $y) = split ' ',$pair; enter_pair_in_matrix ( $ltr2num{$x}, $ltr2num{$y}, \@square_matrix ); } dump_square_matrix(\@vars,\@square_matrix); sub enter_pair_in_matrix { my ($x,$y,$ref_matrix) = @_; $ref_matrix->[$x][$y]= 1; $ref_matrix->[$y][$x]= 1; } sub dump_square_matrix { my ($ref_vars, $ref_matrix) = @_; my @vars = @$ref_vars; print " ","@vars\n"; foreach (@$ref_matrix) { print shift @vars, " @$_\n"; } }
      Thank you very much..It worked for me.Likewise i understood @square_matrix returns address values and But I am not able understand the squarebraces of @x use in the map function..Would be thankful to your answer..
        The matrix is represented as an array of arrays.
        Add a use Data::Dumper; statement, then various print Dumper \@square_matrix; statements to see how the data is being represented.
        example of a 3x3: my @m = ([0,0,0], [0,0,0], [0,0,0]);
        Each "row" is what the [@x] represents and is the return value of the map. Another set of code in this thread uses a hash table to represent the data.

        The main idea is to make a square matrix and then each set of letters results in two entries into that matrix. Many implementations of that idea are possible, some much shorter than what I did in this case.

        Update:

        This might help you to understand what is going on without a map...a map is kind of like a "tricky" foreach() loop.

        #!/usr/bin/perl -w use strict; use Data::Dumper; my @sq_matrix_3x3; my @list = (1,2,3); foreach (@list) { push (@sq_matrix_3x3, [0,0,0]); #creates a row with 3 elements } print "3x3 Matrix: "; print Dumper \@sq_matrix_3x3;
        This is the same thing and perhaps a more familiar form of [x][y] coordinates
        my @another_2D; for (my $x=0; $x<3; $x++) { for (my $y=0; $y<3; $y++) { $another_2D[$x][$y]=0; } } print Dumper \@another_2D; __END__ prints: 3x3: $VAR1 = [ [ 0, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 0 ] ]; # print Dumper \@sq_matrix_3x3; #these both produce the same output # print Dumper \@another_2D;
Re: creating adjacency matrix
by pajout (Curate) on Jan 06, 2011 at 10:03 UTC
    It depends on planned purpose, for instance...

    my %adj = (A => ['B'], B => ['A','C'], C => ['B','D'], D =>['C']);
Re: creating adjacency matrix
by Anonymous Monk on Jul 27, 2011 at 15:39 UTC
    I have an add on question, how can I increase the value 1 , if the adjacent pair appears more then just one time? Like if A B appears 3 times, then in the matrix A B A 0 3 B 3 0

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others meditating upon the Monastery: (4)
As of 2024-04-23 23:03 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found