如何实现一个无向图使用邻接表在Perl或Java PPI？ [英] How do I implement a undirected graph for PPI using adjacency list in Perl or Java?

问题描述

我在类似下面的格式的文本文件的蛋白质的列表：

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  

我想从文本文件阅读和使用邻接表无论是在Java或Perl中的无向图执行。我要计算的最小和最大数目的边，节点之间的最短和最长的路径，以及其它类似的功能。

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.

推荐答案

在Perl中，你可以重新present使用哈希像这样的图：

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.

有关这一点，你可以使用Dijkstra算法。简单地说，这是怎样的算法如下：

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

让我们调用start节点A和终端B节点。

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

假设我们已经知道，从A到B，如果我们在B，然后回溯使用最廉价的路径应该把我们带回一点上，我们的步骤的最短路径A. Dijkstra算法开始于A和记录的成本路径将所有A的相邻节点，并且重复该过程针对每个相邻节点。一旦这样做，那么我们就可以通过选自B回溯到打印从A到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.

要获取节点的数目：打印键％图; 要获取边的数量，你会要算（唯一）的条目数量在每个哈希表元素，例如计算边数的一个节点：打印键％{$图{ATF-1'}};

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

这篇关于如何实现一个无向图使用邻接表在Perl或Java PPI？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！