The task is to write (or find) a script (preferabbly in Perl, but
another language is okay) to recognize network patterns composed from
three different types of edges. There are three input files, one for
each type of edge. Each input file (red, green and black) contains two
columns of vertices, delimited by a tab. The types of patterns to be
detected are illustrated in the figure located at
http://img.villagephotos.com/p/2005-4/994983/scenario.GIF The simplest
is a triangle (A in figure), with one edge from red, one red from
green, and one edge from black. Additional desired patterns to be
recognized are demonstrated in the figure B, C and D. Additionally,
the script should pick out chains of these patterns, connected by red,
as demonstrated in E.
Ideally, the script should output the most complete/complex pattern
possible (encompassing the most edges possible). Keep in mind that
these patterns will be picked out from a network of many many edges of
all three colors connected in seemingly random ways (the full network
has several thousand edges). One rule should be followed: Red and
green will never share the same edge in the input network, but black
may share the same edge as red or green, but it shouldn't be detected
as satisfying the pattern unless it forms a third edge (etc.),
although overlapping with the red or green edge does not preclude the
formation of the shape. It would be desirable for a script to pick out
instances like F and G as well; however this should either be in a
separate version than the other script or be optional when running the
script. The script should output the resulting sub networks along with
the colors of each edge (vertex1 vertex2 color). This script should be
relatively straightforward when built with a series of hashes. For
example, a script to recognize triangles can be found at
http://lists.canonical.org/pipermail/kragen-hacks/1998-November/000127.html
.