Bibliothèque de graphes prenant en charge les étiquettes de bord

Question

Je suis tombé sur Perl's Graph library ce matin. J'avais l'habitude d'écrire un programme rapide pour trouver tous les composants (faiblement) connectés dans un graphe orienté. Voici le programme.

use strict; 
use Graph; 
use Data::Dumper; 

my $g = Graph->new(); 
foreach my $file(@ARGV) 
{ 
    open(my $IN, "<", $file) or die("cannot open '$file'"); 
    while(my $line = <$IN>) 
    { 
    chomp($line); 
    my($source, $target, $edge_label) = split(/\t/, $line); 
    $g->add_edge($source, $target); 
    } 
    close($IN); 
} 

my @clusters = $g->weakly_connected_components(); 
print Dumper(\@clusters); 

... et les fichiers de données d'entrée ressemblent à ceci.

n1 n2 some_data_encoded_in_a_label 
n1 n3 some_data_encoded_in_a_label 
n4 n5 some_data_encoded_in_a_label 
... 

... où la première colonne est le label de noeud de source, la deuxième colonne est l'étiquette du noeud cible, et la troisième colonne est une étiquette de bord. J'ai quelques fichiers de données, chacun avec des dizaines de milliers d'arêtes.

Ce script rapide-n-sale a fait le travail, mais il y avait quelques choses qui auraient été bien d'avoir.

• Les composants connectés sont retournés par la méthode weakly_connected_components étaient simplement des tableaux de labels de noeud, de sorte que les liaisons entre ces noeuds sont perdues.
• Même si la méthode renvoyait un ensemble de noeuds et un ensemble d'arêtes, la bibliothèque n'autorise pas le stockage d'étiquettes ou de données associées à chaque arête, ce qui est peu pratique.

Y a-t-il d'autres bibliothèques de graphes qui incluent l'une de ces fonctionnalités ou les deux? La langue de mise en œuvre n'est pas très important - je suis ouvert à C/C++, Python, Perl, R, etc.

Answer 1

changement

$g->add_edge($source, $target); 

à (zéro ou une étiquette par bord)

$g->add_edge($source, $target); 
$labels{$source}{$target} = $edge_label; 

ou (un nombre quelconque d'étiquettes par bord)

$g->add_edge($source, $target); 
push @{ $labels{$source}{$target} }, $edge_label; 

et recherche juste l'étiquette quand vous en avez besoin.

(Pour les graphes non orientés, ajoutez chaque étiquette deux fois, une fois pour source-> cible et une fois pour Target-> Source.)