2

I've a list of proteins in a text file like the format below:

ATF-1 MET4  
ATF-1 NFE2L1  
ATF-2 ATF-7  
ATF-2 B-ATF    
ARR1 ARR1  
ARR1 CHOP

I want to read from the text file and implement them in undirected graph using adjacency lists either in Java or in Perl. I want to calculate the minimum and maximum number of edges, the shortest and longest path between nodes, and other similar functions.

the Tin Man
  • 158,662
  • 42
  • 215
  • 303
Michael.Z
  • 37
  • 5

2 Answers2

3

In perl, you can represent the graph using hash like this:

use warnings;
use strict;

my %graph;
sub add_edge {
    my ($n1, $n2) = @_;
    $graph{$n1}{$n2} = 1;
    $graph{$n2}{$n1} = 1;
}

sub show_edges {
    foreach my $n1 (keys %graph) {
        foreach my $n2 (keys %{$graph{$n1}}) {
            print "$n1 <-> $n2\n";
        }
    }
}

while (<>) {
    my ($n1, $n2) = split /\s+/;
    add_edge($n1, $n2);
}

show_edges();

Run it like this:

perl script.pl input.txt

For the shortest path you'll have to decide the start and end node that you want to search the shortest path for.

For this you can use Dijkstra's algorithm. In a nutshell this is how the algorithm works:

Let's call the start node A and the end node B.

Assume that we already know the shortest path for going from A to B. If we are at B, then backtracking our steps using the cheapest path should bring us back to point A. Dijkstra's algorithm starts at A and records the cost of path for going to all of A's adjacent nodes, and repeats the process for each of the adjacent nodes. Once done, then we can print the shortest path from A to B by backtracking from B to A.

To get the number of nodes: print keys %graph; To get the number of edges you'll have to count (uniquely) the number of entries in each of the hash elements, for example to count the number of edges for one node: print keys %{$graph{'ATF-1'}};

holygeek
  • 15,653
  • 1
  • 40
  • 50
  • oh thanks holygeek it reads all the files. but still I don't have idea how to calculate the shortest path, the maximum and minimum of edges, and counting the number of nodes and edges. can you please help me on that? – Michael.Z Dec 24 '11 at 09:11
  • Then you need to read up on some basic Graph Theory. Google searches for `"shortest path" graph theory` and so forth will give you some good ideas on how to implement these algorithms. – Zéychin Dec 25 '11 at 09:27
  • thank you all. especially holygeek, thanks for taking time to read my problem and get a solution. – Michael.Z Dec 25 '11 at 09:42
  • hey Holygeek: please help me to finalize my project here is what i've tried for the Dijkstra algorithm, but still doesn't work. – Michael.Z Dec 27 '11 at 12:29
0

Take a look at Open source libraries to design directed graphs. Their suggestion was to use JGraphT. The javadoc shows that they have implemented a wide range of graph operations, including shortest path.

Community
  • 1
  • 1
Richard Povinelli
  • 1,419
  • 1
  • 14
  • 28