How to know you might need a homomorphic transform

typical algorithm requires a global scan of the data, e.g., O(n), O(n^2), etc.
multiple queries for the same kind of scan result.
one scan of the data allows storing all query results in a more searchable form.
"index"ing: compute results, index by more appropriate key, can look up faster.

acid test:

 Time(Scan)+k*Time(newLookup)<k*Time(oldLookup=Scan)

Why is Tuples.pm a homomorphism rather than an isomorphism?

hashes don't preserve order.

[ $a,$b,$c ] => tuples->{$a}->{$b}->{$c}={}

 [ 1,2,3 ] => $tuples->{1}->{2}->{3}= {}; 
 [ 1,4,6 ] => $tuples->{1}->{4}->{6}= {};

When I transform this back, I could get either

 [ 1,2,3 ]
 [ 1,4,6 ]

 [ 1,4,6 ]
 [ 1,2,3 ]

So this is isomorphism (modulo equivalence of all tuple orders),
but only homomorphism (if order matters).

in grader:

 [ 'add',1,2,3 ]
 [ 'add',1,4,6 ]
 [ 'del',1,2,3 ]

is not equivalent to

 [ 'add',1,4,6 ]
 [ 'del',1,2,3 ]
 [ 'add',1,2,3 ]

Representing a graph

Entities are nodes and edges

First cut: represent nodes and edges with other things.

 $nodes->{$city}=1 if $city represents a node
 $edges->{$c1}->{$c2}=$dist if distance between $c1 and $c2 = $dist

both are necessary:
- I may give you a non-existent city! Return undef, need $nodes list
- YOU need to be able to convert from pairs of cities ($c1,$c2) to their distance really fast (Avg(1)). ($edges->{$c1}->{$c2} is O(log n), Avg(1)

Encapsulating a graph:

you must encapsulate all data for the graph into the reference that represents a graph.

 $g = {}; 
 bless $g, "Shortest"; 
 $g->{'nodes'} describes nodes. 
 $g->{'edges'} describes edges.

Two tries:

Graph1.pm: everything except reasonable data abstraction.
Graph.pm, Edges.pm, Nodes.pm: a try at a more reasonable structure.

A relatively naive Graph implementation

Edges and nodes are hashes of info in tuples.

Consider the code:

contents of perl_extra/Graph1.pm...
#! /var/local/couch/bin/perl

package Graph1; 

require Exporter; 
use Data::Dumper; 
use strict; 

BEGIN { 
    @Graph1::ISA = qw(Exporter); 
    @Graph1::EXPORT = qw(); 
    @Graph1::EXPORT_OK = qw(); 
} 

# build a Graph1 from a list of tuples 
sub new { 
    my $pack   = shift; # package name
    my $tuples = shift; # argument in new Graph1(arg)
    my $self   = {}; 	# my resulting graph representation. 
    $self->{'nodes'}={}; # I have no nodes. 
    $self->{'edges'}={}; # I have no edges. 
    foreach my $t ( @$tuples ) { 
	$self->{'nodes'}->{$t->[0]}=1;	# $t->[0] is a city 
	$self->{'nodes'}->{$t->[1]}=1;  # $t->[1] is a city
        #                  city1      city2    distance
	$self->{'edges'}->{$t->[0]}->{$t->[1]}=$t->[2]; 
    } 
    return bless $self; 
} 

# $g->nodes === $g->{'nodes'}
sub nodes { $_[0]->{'nodes'} } 

# $g->edges === $g->{'edges'} 
sub edges { $_[0]->{'edges'} } 

#  $g->is_node($c) === (defined $g->{'nodes'}->{$c})
sub is_node { defined $_[0]->nodes->{$_[1]} } 

#  $g->is_edge($c,$d) === (defined $g->{'edges'}->{$c}->{$d})
sub is_edge { defined $_[0]->{'edges'}->{$_[1]}->{$_[2]} } 

#  $g->distance($c,$d) === ($g->{'edges'}->{$c}->{$d})
sub distance { $_[0]->{'edges'}->{$_[1]}->{$_[2]} } 

# game: preserve coherence between adding tuples
# at beginning or later
# $g = new Graph1($tuples) ; <=> $g=new Graph1(); $g->addtuples($tuples)

# add tuples to tuple space, updating other data as we go
sub addtuples { 
    my $self = shift; 
    my $tuples = shift; 
    foreach my $t (@$tuples) { 
	$self->{'nodes'}->{$t->[0]}=1;
	$self->{'nodes'}->{$t->[1]}=1;
	$self->{'edges'}->{$t->[0]}->{$t->[1]}=$t->[2]; 
    } 
} 

# to delete a tuple, delete it from the homomorphic 
# representations of 'nodes' and 'edges'. 
sub deltuples { 
    my $self = shift; 
    my $tuples = shift; 
    my $edges = $self->{'edges'}; 
    foreach my $t (@$tuples) { 
        delete $edges->{$t->[0]}->{$t->[1]}; 
        delete $edges->{$t->[0]} 
	    if %{$edges->{$t->[0]}} == 0
    } 
    # a city might not be in any tuple anymore: override
    $self->{'nodes'} = {}; 
    my $nodes = $self->{'nodes'}; 
    foreach my $k (keys %{$edges}) { 
	my $v = $edges->{$k}; 
	$nodes->{$k}=1; 
        foreach my $l (keys %$v) { 
	    $nodes->{$l}=1; 
	} 
    } 
} 

1; 
...end of perl_extra/Graph1.pm

Call this with:

contents of perl_extra/Graph1.test...
#! /var/local/couch/bin/perl 

use Data::Dumper; 
use Graph1; 

require "/g/150PPP/class/a2/cities.pl"; 
my $g = new Graph1($roads); 
print "before delete, g=".Dumper($g); 
$g->deltuples([['boston','concord',0]]); 
print "after delete, g=".Dumper($g); 
...end of perl_extra/Graph1.test

This produces:

contents of perl_extra/Graph1.test.out...
before delete, g=$VAR1 = bless( {
                 'edges' => {
                              'boston' => {
                                            'albany' => 169,
                                            'newyork' => 208,
                                            'portland' => 109,
                                            'concord' => 78
                                          },
                              'harrisburg' => {
                                                'pittsburgh' => 208,
                                                'buffalo' => 266
                                              },
                              'scranton' => {
                                              'harrisburg' => 120,
                                              'buffalo' => 266,
                                              'syracuse' => 136
                                            },
                              'albany' => {
                                            'montreal' => 247,
                                            'scranton' => 173,
                                            'syracuse' => 146
                                          },
                              'newyork' => {
                                             'philly' => 106,
                                             'harrisburg' => 195,
                                             'scranton' => 136,
                                             'albany' => 156
                                           },
                              'baltimore' => {
                                               'harrisburg' => 72,
                                               'washington' => 37
                                             },
                              'charleston' => {
                                                'cincinnati' => 206,
                                                'lexington' => 177,
                                                'bluefield' => 107,
                                                'columbus' => 167,
                                                'knoxville' => 315
                                              },
                              'concord' => {
                                             'albany' => 151,
                                             'montreal' => 247
                                           },
                              'washington' => {
                                                'harrisburg' => 109,
                                                'richmond' => 106,
                                                'columbus' => 431,
                                                'roanoke' => 233,
                                                'charleston' => 342,
                                                'pittsburgh' => 247
                                              },
                              'philly' => {
                                            'harrisburg' => 105,
                                            'scranton' => 122,
                                            'baltimore' => 96
                                          },
                              'richmond' => {
                                              'norfolk' => 93,
                                              'roanoke' => 166,
                                              'raleigh' => 155,
                                              'greensboro' => 215,
                                              'charleston' => 309,
                                              'wilmington' => 254
                                            },
                              'portland' => {
                                              'calais' => 245,
                                              'montreal' => 255,
                                              'quebec' => 282,
                                              'bangor' => 132,
                                              'concord' => 95
                                            },
                              'roanoke' => {
                                             'asheville' => 214,
                                             'knoxville' => 256,
                                             'greensboro' => 99,
                                             'raleigh' => 163
                                           },
                              'pittsburgh' => {
                                                'columbus' => 186,
                                                'charleston' => 227,
                                                'cleveland' => 129,
                                                'buffalo' => 219
                                              }
                            },
                 'nodes' => {
                              'boston' => 1,
                              'harrisburg' => 1,
                              'scranton' => 1,
                              'quebec' => 1,
                              'baltimore' => 1,
                              'columbus' => 1,
                              'buffalo' => 1,
                              'cincinnati' => 1,
                              'richmond' => 1,
                              'portland' => 1,
                              'knoxville' => 1,
                              'greensboro' => 1,
                              'wilmington' => 1,
                              'calais' => 1,
                              'montreal' => 1,
                              'albany' => 1,
                              'newyork' => 1,
                              'asheville' => 1,
                              'norfolk' => 1,
                              'cleveland' => 1,
                              'concord' => 1,
                              'charleston' => 1,
                              'washington' => 1,
                              'philly' => 1,
                              'lexington' => 1,
                              'bangor' => 1,
                              'bluefield' => 1,
                              'roanoke' => 1,
                              'pittsburgh' => 1,
                              'raleigh' => 1,
                              'syracuse' => 1
                            }
               }, 'Graph1' );
after delete, g=$VAR1 = bless( {
                 'edges' => {
                              'boston' => {
                                            'albany' => 169,
                                            'newyork' => 208,
                                            'portland' => 109
                                          },
                              'harrisburg' => {
                                                'pittsburgh' => 208,
                                                'buffalo' => 266
                                              },
                              'scranton' => {
                                              'harrisburg' => 120,
                                              'buffalo' => 266,
                                              'syracuse' => 136
                                            },
                              'albany' => {
                                            'montreal' => 247,
                                            'scranton' => 173,
                                            'syracuse' => 146
                                          },
                              'newyork' => {
                                             'philly' => 106,
                                             'harrisburg' => 195,
                                             'scranton' => 136,
                                             'albany' => 156
                                           },
                              'baltimore' => {
                                               'harrisburg' => 72,
                                               'washington' => 37
                                             },
                              'charleston' => {
                                                'cincinnati' => 206,
                                                'lexington' => 177,
                                                'bluefield' => 107,
                                                'columbus' => 167,
                                                'knoxville' => 315
                                              },
                              'concord' => {
                                             'albany' => 151,
                                             'montreal' => 247
                                           },
                              'washington' => {
                                                'harrisburg' => 109,
                                                'richmond' => 106,
                                                'columbus' => 431,
                                                'roanoke' => 233,
                                                'charleston' => 342,
                                                'pittsburgh' => 247
                                              },
                              'philly' => {
                                            'harrisburg' => 105,
                                            'scranton' => 122,
                                            'baltimore' => 96
                                          },
                              'richmond' => {
                                              'norfolk' => 93,
                                              'roanoke' => 166,
                                              'raleigh' => 155,
                                              'greensboro' => 215,
                                              'charleston' => 309,
                                              'wilmington' => 254
                                            },
                              'portland' => {
                                              'calais' => 245,
                                              'montreal' => 255,
                                              'quebec' => 282,
                                              'bangor' => 132,
                                              'concord' => 95
                                            },
                              'roanoke' => {
                                             'asheville' => 214,
                                             'knoxville' => 256,
                                             'greensboro' => 99,
                                             'raleigh' => 163
                                           },
                              'pittsburgh' => {
                                                'columbus' => 186,
                                                'charleston' => 227,
                                                'cleveland' => 129,
                                                'buffalo' => 219
                                              }
                            },
                 'nodes' => {
                              'boston' => 1,
                              'scranton' => 1,
                              'harrisburg' => 1,
                              'quebec' => 1,
                              'baltimore' => 1,
                              'columbus' => 1,
                              'buffalo' => 1,
                              'cincinnati' => 1,
                              'richmond' => 1,
                              'portland' => 1,
                              'knoxville' => 1,
                              'greensboro' => 1,
                              'wilmington' => 1,
                              'calais' => 1,
                              'albany' => 1,
                              'montreal' => 1,
                              'newyork' => 1,
                              'asheville' => 1,
                              'norfolk' => 1,
                              'cleveland' => 1,
                              'concord' => 1,
                              'charleston' => 1,
                              'washington' => 1,
                              'philly' => 1,
                              'bangor' => 1,
                              'lexington' => 1,
                              'bluefield' => 1,
                              'roanoke' => 1,
                              'raleigh' => 1,
                              'pittsburgh' => 1,
                              'syracuse' => 1
                            }
               }, 'Graph1' );
...end of perl_extra/Graph1.test.out

Code notes:
- If you delete a tuple, you need to regenerate the node list. This is expensive and requires a scan of the whole hash. You can avoid this by re-implementing the node list with access counts.
- Nodes and edges are not concepts separate from this code, which makes the code particularly difficult to read.

Access counts

One annoying thing is that I delete lots of tuples.
This causes a recomputation of the whole node list.
One can avoid this with access counts
When adding a tuple containing a node $city:
```
 
$nodes->{$city}++; 
```

When deleting the same city:

 
$nodes->{$city}--; 
delete $nodes->{$city} if $nodes->{$city} == 0;

This saves the whole phase of recomputing the city data after a deletion.

Encapsulating node lists

Consider the code:

contents of perl_extra/Nodes.pm...
#! /var/local/couch/bin/perl 

package Nodes; 
require Exporter;
use Set; 
use strict; 

BEGIN { 
    @Nodes::ISA = qw(Exporter Set); 
    @Nodes::EXPORT = qw(); 
    @Nodes::EXPORT_OK = qw(); 
} 

# construct a new Edge set from an array of tuples 
sub new { 
    my $package = shift; 
    my $tuples = shift; 
    my $self = bless { }; 
    $self->addtuples($tuples); 
    return $self; 
} 

# add an array of tuples to the Node set
sub addtuples { 
    my $self = shift; 
    my $tuples = shift; 
    foreach my $t (@$tuples) { 
	$self->Set::add($t->[0],$t->[1]); 
    } 
} 

# compute the node list for an edge list
sub contents { 
    my $self = shift; 
    return keys %$self; 
} 
# sub contents { keys %{$_[0]} } 

1; # must return this so 'use' works. 
...end of perl_extra/Nodes.pm

This produces exactly the same effect as the previous nodes element, but is nicely encapsulated into its own package.

Encapsulating edge lists

Consider the code:

contents of perl_extra/Edges.pm...
#! /var/local/couch/bin/perl 

package Edges; 
require Exporter;
use Nodes; 
use strict; 

BEGIN { 
    @Edges::ISA = qw(Exporter); 
    @Edges::EXPORT = qw(); 
    @Edges::EXPORT_OK = qw(); 
} 

# construct a new Edge set from an array of tuples 
sub new { 
    my $package = shift; 
    my $tuples = shift; 
    my $self = bless { }; 
    $self->addtuples($tuples); 
    return $self; 
} 

sub distance { 
    my $self = shift; 
    my $source = shift; 
    my $sink = shift; 
    return $self->{$source}->{$sink}; 
} 

# add tuples to the Edge set
sub addtuples { 
    my $self = shift; 
    my $tuples = shift; 
    foreach my $t (@$tuples) { $self->add(@$t); } 
} 

# delete tuples from the Edge set 
sub deltuples { 
    my $self = shift; 
    my $tuples = shift; 
    foreach my $t (@$tuples) { $self->del(@$t); } 
} 

# add one edge
sub add { 
    my $self = shift; 
    my $source = shift; 
    my $sink = shift; 
    my $distance = shift; 
    $self->{$source}->{$sink}= $distance; 
} 
# sub add { $_[0]->{$_[1]}->{$_[2]}=$_[3] } 

# delete an edge 
sub del { 
    my $self = shift; 
    my $source = shift; 
    my $sink = shift; 
    delete $self->{$source}->{$sink}; 
    delete $self->{$source} if %{$self->{$source}} == 0; 
} 
# sub del { 
#   delete $_[0]->{$_[1]}->{$_[2]}; 
#   delete $_[0]->{$_[1]} if %{$_[0]->{$_[1]}}==0; 
# } 

# compute the node list for an edge list
sub nodes { 
    my $self = shift; 
    my $nodes = new Nodes; 
    foreach my $k (keys %$self) { 
	$nodes->add($k); 
	foreach my $l (keys %{$self->{$k}}) { 
	    $nodes->add($l); 
	} 
    } 
    return $nodes; 
} 

# compute neighbors reachable from a given node
sub neighbors {
    my $self = shift; 
    my $node = shift; 
    return keys %{$self->{$node}}; 
} 

# return an array of all edges, just like the one used to create this
sub tuples { 
    my $self = shift; 
    my $out = []; 
    foreach my $k (keys %$self) { 
	foreach my $l (keys %{$self->{$k}}) { 
	    push(@$out,[$k,$l,$self->{$k}->{$l}]); 
	} 
    } 
    return $out; 
} 

1; # must return this so 'use' works. 
...end of perl_extra/Edges.pm

This produces exactly the same effect as the previous edges element, but is nicely encapsulated into its own package.

Using encapsulated Nodes and Edges

Consider the code:

contents of perl_extra/Graph.pm...
#! /var/local/couch/bin/perl

package Graph; 

require Exporter; 
use Data::Dumper; 
use Nodes; 	# store node list 
use Edges; 	# store edge list 
use Queue; 	# needed for BFS diameter computation
use strict; 

BEGIN { 
    @Graph::ISA = qw(Exporter); 
    @Graph::EXPORT = qw(); 
    @Graph::EXPORT_OK = qw(); 
} 

# build a Graph from a list of tuples 
sub new { 
    my $pack = shift; 
    my $tuples = shift; 
    my $self = {}; 
    $self->{'nodes'}=new Nodes($tuples); 
    $self->{'edges'}=new Edges($tuples);
    return bless $self; 
} 

sub nodes { $_[0]->{'nodes'} } 
sub edges { $_[0]->{'edges'} } 
sub is_node { $_[0]->nodes->member($_[1]) } 
sub distance { $_[0]->edges->distance($_[1],$_[2]) } 

# add tuples to tuple space, updating other data as we go
sub addtuples { 
    my $self = shift; 
    my $tuples = shift; 
    $self->nodes->addtuples($tuples); 
    $self->edges->addtuples($tuples); 
} 

# to delete a tuple, delete it from the homomorphic representations
# 'nodes' and 'edges'. 
sub deltuples { 
    my $self = shift; 
    my $tuples = shift; 
    $self->edges->deltuples($tuples); 
    # a city might not be in any tuple anymore: override
    $self->{'nodes'} =$self->edges->nodes; 
} 

# depth contour calculation needed to construct search problems. 
# this is NOT AS EFFICIENT as Dijkstra on a complete graph, 
# but MIGHT be more efficient on a sparse one...
sub contours { 
    my $self = shift; 
    my $start = shift; # a starting city 

    # create a depth contour from the starting point using BFS
    my $contour = {}; 
    $contour->{$start}=0; 
    my $q = new Queue($start); 
    while (! $q->empty) { 
	my $next = $q->dequeue; 
	foreach my $r ($self->edges->neighbors($next)) { 
	    if (! defined $contour->{$r}
		  or $contour->{$r}>$contour->{$next}+1) { 
		$contour->{$r}= $contour->{$next}+1 ; 
		$q->enqueue($r);  # must try again 
	    } 
	} 
    } 

    # invert contour into sets of cities 
    my $choices = []; 
    foreach my $k ( keys %$contour) { 
	push(@{$choices->[$contour->{$k}]},$k); 
    } 
    return $choices; 
} 

1; 
...end of perl_extra/Graph.pm

This uses two independent sub-objects to embody nodes and edges.
Finer points:
- Chained blessed references: $self->edges->distance($c1,$c2) is evaluated as follows:
  - $self is a Graph
  - $self->edges calls a member function, returns $self->{'edges'}, which is an instance of Edges.
  - $self->edges->distance refers to Edges::distance, which gives the correct result.
  Each step of this has a different blessing that changes the scope of names.
- Homomorphic map from a depths to "cities at depth": The code:
```
 
# invert contour into sets of cities 
my $choices = []; 
foreach my $k ( keys %$contour) { 
    push(@{$choices->[$contour->{$k}]},$k); 
} 
```
  converts
```
 
$contour = { 
   'boston'=>0, 
   'hoboken'=>1, 
   'joiseycity'=>1, 
   'hoople'=>2
} ; 
```
  into an array of cities at each depth:
```
 
$choices = [ 
   [ 'boston' ], 
   [ 'hoboken', 'joiseycity' ], 
   [ 'hoople' ], 
] ; 
```
  so that $choices->[$i] is the list of cities that appear at depth $i.

My common errors with structures

Mostly, I tend to make errors concerning side-effects of a computation.
If you change the content of a reference, it changes the content of everything that contains the reference.
When a reference is copied, it is a pointer that is copied.
Changing the copy changes all copies.

Consider the code:

 
my $g = new Graph(['a','n',1]); 
my $adjacent = $g->{'edges'}->{'a'}; 
$adjacent->{'n'}=0; ## corrupted $g!

or, even worse:

 
my $tuples = [['a','n','2'],['g','h',5]]; 
my $e = &juggle($tuples); 
sub juggle { 
  my $t = shift;
  my $out = {}; 
  foreach my $s (@$t) { 
    my $first = shift(@$s); 
    my $second = shift(@$s); 
    my $dist = shift(@$s); 
    $out->{$first}->{$second}->{$dist}++; 
  } 
  return $out; 
}

After this, $tuples is [[],[]]!

Ways to optimize assignment 2

Eliminate copying in subroutine calls.
Detect and quickly answer degenerate queries (city doesn't exist, e.g.)
Cache results for use in subsequent calls.
Transform data structures to minimize runtime.
Intelligently choose between data structures and algorithms based upon graph structure.

lecture in color

downloaded on Nov-23-2009 03:26:05 PM,
was last modified on Dec-31-1969 07:00:00 PM.
All lecture note content is copyright 2003 by
Alva L. Couch, Computer Science, Tufts University
(couch at cs dot tufts dot edu)