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

[Ivan B. Serezhkin]

Ivan B. Serezhkin wrote:
> Kaltashkin Eugene wrote:
> 
>> легко. http://zhecka.323f.net.ru/temp/pack.tar.gz
> 
> А можно человеческое объяснение формата ?
> Я правильно понял, что имя файла - это свич, а всё что в ковывчечках - 
> это мак устройства на порту?
> а всё что без кавычечков  мусор ?
> 
> А ещё лучше хотим датадампер хэша
> {
> 	свич =>{
> 		порт=>мак,
> 		порт=>мак
> 		},
> 	свич =>{
> ....
> }
> 
> И это, а как из этих данных понять, что свич воткнут в свич ?
> 
> 


Вообщем попробую объяснить как я решаю такие задачи:
Поиск в ширину,
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
Таким образом, узел у которого отрезали все тупики сам становится тупиком




-- 
Ivan B. Serezhkin