[Moscow.pm] Взрыв мозга или занимательная топология

[Kaltashkin Eugene]

Ivan B. Serezhkin пишет:
> Вообщем попробую объяснить как я решаю такие задачи:
> Поиск в ширину,
> my @queue=qw(list of neighbors);
> while (@queue) {
>      my $element=shift @queue;
>      last if $element->distance > $deepnes;
>      push @queue, map {$_->distance($element->distance()+1);$_} grep {! 
> $_->marked()} $element->neighbors();
>      $element->mark();
> }
> Эта штука позволяет потрогать все близкие точки на глубину $deepnes
> и расставит им расстояние от начального.
> Но не позволяет найти путь.
>   

А у нас нет расстояния от начального элемента. Мы еще не знаем в каком 
узле живёт тот или иной адрес.

> Путь ищется  перебором в глубину,
> my @queue=($begin_of_path);
> my @path=();
> my $element;
> while (@queue) {
>      my $element=pop @queue;
>      push @path, $element;
>      last if $element==$end_of_path;
>      if ($element->neighbors() -1) {
> 	shift  @queue, $element->neighbors();
>      } else {
> 	$element->mark_deleted;
>      }
> }
> print "Path: " . join(' - ', grep {!$_->deleted} @path);
> Соответственно neighbors ищется без учёта deleted
> Таким образом, узел у которого отрезали все тупики сам становится тупиком
>   
это понятно, проблем с определением тупика нет. Ибо если в узле всего 
один порт где присутствует больше
чем 1 устройство, значит этот узел конечный, и этот порт является 
downlinkом для узла расположенного выше по иерархии.
Проблема с определением портов в обоих узлах которые являются точками 
входа-выхода, ибо скажем центральный узел и все узлы до искомого будут 
содержать в своей таблице адреса всех устройств сети, но узел с искомым 
устройством может быть не подключен напрямую к центральному узлу.