如何在 Perl 或 Java 中使用邻接表实现 PPI 无向图？

发布于 2024-12-23 05:10:07 字数 222 浏览 2 评论 0原文

我在文本文件中有一个蛋白质列表，格式如下：

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

我想从文本文件中读取并使用 Java 或 Perl 中的邻接表在无向图中实现它们。我想计算边的最小和最大数量、节点之间的最短和最长路径以及其他类似的函数。

原文

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.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

吃→可爱长大的 2024-12-30 05:10:07

在 Perl 中，您可以使用散列来表示图形，如下所示：像

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

这样运行：

perl script.pl input.txt

对于最短路径，您必须决定要搜索最短路径的起始节点和结束节点。

为此，您可以使用 Dijkstra 算法。简而言之，该算法的工作原理是：

让我们将起始节点称为 A，将结束节点称为 B。

假设我们已经知道从 A 到 B 的最短路径。如果我们在 B，则使用最便宜的回溯步骤路径应该带我们回到点 A。Dijkstra 算法从 A 开始，记录到达 A 的所有相邻节点的路径成本，并对每个相邻节点重复该过程。完成后，我们可以通过从 B 回溯到 A 来打印从 A 到 B 的最短路径。

要获取节点数： print keys %graph;
要获取边数，您必须（唯一地）计算每个散列元素中的条目数，例如计算一个节点的边数： print keys %{$graph{'ATF -1'}};

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

回复收藏 0 原文