#!/usr/local/bin/perl -w
# graph-traverse.pl -- Traversiert einen zusammenhaengenden Graphen.

sub depth_first_search {
    my $node = shift;
    return if exists $node->{'DFSVISITED'};

    $node->{'DFSVISITED'} = 1;

    if (exists $node->{'NEXT'}) {
    foreach my $neigh ( map { $_->{'NEIGH'} }
                    @{$node->{'NEXT'}} ) {
        depth_first_search($neigh);
    }
    }

    proceed($node->{'VALUE'});
}

sub breadth_first_search {
    my $node  = shift;
    my @queue = ();

    $node->{'BFSVISITED'} = 1;
    proceed($node->{'VALUE'});

    push(@queue, map { $_->{'NEIGH'} } @{$node->{'NEXT'}});
    while (defined ($node = shift @queue)) {
    next if exists $node->{'BFSVISITED'};
        $node->{'BFSVISITED'} = 1;

        proceed($node->{'VALUE'});
    push(@queue, map { $_->{'NEIGH'} } @{$node->{'NEXT'}});
    }
}

sub create_undirected_weighted_graph {
    my $net;

    while (<DATA>) {
        chomp;
    next if /^\s*#/;

    ($from, $to, $cost) = split(/:\s*/);

    $net->{$from} = {} unless exists $net->{$from};
    $net->{$to}   = {} unless exists $net->{$to};

    $net->{$from}->{'VALUE'} = "$from"
        unless exists $net->{$from}->{'VALUE'};
    $net->{$to}->{'VALUE'}   = "$to"
        unless exists $net->{$to}->{'VALUE'};

    $net->{$from}->{'NEXT'} = []
        unless exists $net->{$from}->{'NEXT'};
    $net->{$to}->{'NEXT'}   = []
        unless exists $net->{$to}->{'NEXT'};

    push(@{$net->{$from}->{'NEXT'}},
         { NEIGH => $net->{$to}, COST => $cost });
        push(@{$net->{$to}->{'NEXT'}},
         { NEIGH => $net->{$from}, COST => $cost });
    }

    return $net;
}

sub proceed {
    my $value = shift;
    print "($value)";
}

my $net = create_undirected_weighted_graph();

print "Starting from where? "; chomp($start = <STDIN>);
print "DFS-Traversal: ";
      depth_first_search($net->{$start});
      print "\n";
print "BFS-Traversal: ";
      breadth_first_search($net->{$start});
      print "\n";

__DATA__
# A                           F
# \3    1          2     5/
# C ------- D -------- E
# /3                     5\
# B                           G
D: C: 1
D: E: 2
C: A: 3
C: B: 3
E: F: 5
E: G: 5