Как реализовать ненаправленный граф для PPI, используя список смежности в Perl или Java?

Question

У меня есть список белков в текстовом файле, как в формате ниже:

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

Я хочу прочитать из текстового файла и реализовать их в неориентированном графе, используя списки смежности в Java или в Perl. Я хочу вычислить минимальное и максимальное количество ребер, самый короткий и самый длинный путь между узлами и другие подобные функции.

Answer 1

В 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

Для кратчайшего пути вам нужно будет выбратьначальный и конечный узлы, по которым вы хотите искать кратчайший путь.

Для этого вы можете использовать алгоритм Дейкстры.В двух словах, как работает алгоритм:

Давайте назовем начальный узел A и конечный узел B.

Предположим, что мы уже знаем кратчайший путь для перехода от A к B. Еслимы находимся в точке B, тогда возврат к нашим шагам с использованием самого дешевого пути должен вернуть нас к точке A. Алгоритм Дейкстры начинается с A и записывает стоимость пути для перехода ко всем смежным узлам A, а также повторяет процесс для каждого из соседних узлов.узлы.После этого мы можем напечатать кратчайший путь от A до B, вернувшись назад от B к A.

Чтобы получить количество узлов: print keys %graph; Чтобы получить количество ребер, которые вы должны посчитать (однозначно) количество записей в каждом из элементов хеша, например для подсчета количества ребер для одного узла: print keys %{$graph{'ATF-1'}};

Answer 2

Взгляните на библиотеки с открытым исходным кодом для разработки ориентированных графов .Их предложением было использовать JGraphT . javadoc показывает, что они реализовали широкий спектр операций с графами, включая кратчайший путь .