Algorithm-Networksort
view release on metacpan or search on metacpan
lib/Algorithm/Networksort.pm view on Meta::CPAN
Algorithm::Networksort - Create Sorting Networks.
=begin html
<svg xmlns="http://www.w3.org/2000/svg"
xmlns:xlink="http://www.w3.org/1999/xlink" width="90" height="84" viewbox="0 0 90 84">
<title>Bose-Nelson Sort for N = 4</title>
<defs>
<g id="I_1c13" style="stroke-width:2; fill:#000; stroke:#000" >
<line x1="12" y1="0" x2="78" y2="0" />
</g>
<g id="C1_1c13" style="stroke-width:2;fill:#000; stroke:#000" >
<line x1="0" y1="0" x2="0" y2="14" />
<circle cx="0" cy="0" r="2" /> <circle cx="0" cy="14" r="2" />
</g>
<g id="C2_1c13" style="stroke-width:2;fill:#000; stroke:#000" >
<line x1="0" y1="0" x2="0" y2="28" />
<circle cx="0" cy="0" r="2" /> <circle cx="0" cy="28" r="2" />
</g>
</defs>
<g id="bosenelson04_1c13">
<use xlink:href="#I_1c13" y="21" /> <use xlink:href="#I_1c13" y="35" />
<use xlink:href="#I_1c13" y="49" /> <use xlink:href="#I_1c13" y="63" />
<use xlink:href="#C1_1c13" x="24" y="21" /> <use xlink:href="#C1_1c13" x="24" y="49" />
<use xlink:href="#C2_1c13" x="38" y="21" /> <use xlink:href="#C2_1c13" x="52" y="35" />
<use xlink:href="#C1_1c13" x="66" y="35" />
</g>
</svg>
<p>Bose-Nelson sorting network, inputs = 4, drawn as a Knuth diagram.</p>
<!--
This diagram was generated with the code in the SYNOPSIS; if you change
the code then please generate a new diagram from it.
-->
lib/Algorithm/Networksort.pm view on Meta::CPAN
=begin html
<p>Embedded in a web page, this will produce</p>
<svg xmlns="http://www.w3.org/2000/svg"
xmlns:xlink="http://www.w3.org/1999/xlink" width="278" height="154" viewbox="0 0 278 154">
<title>9-input Network by Robert W. Floyd</title>
<defs>
<g id="I_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="18" y1="0" x2="260" y2="0" />
<circle style="fill:#000; stroke:#000" cx="18" cy="0" r="2" /> <circle style="fill:#000; stroke:#000" cx="260" cy="0" r="2" />
</g>
<g id="C1_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="14" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="14" r="2" />
</g>
<g id="C3_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="42" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="42" r="2" />
</g>
<g id="C2_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="28" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="28" r="2" />
</g>
<g id="C4_454d" style="stroke-width:2" >
<line style="fill:#000; stroke:#000" x1="0" y1="0" x2="0" y2="56" />
<circle style="fill:#04c; stroke:#04c" cx="0" cy="0" r="2" /> <circle style="fill:#00c; stroke:#00c" cx="0" cy="56" r="2" />
</g>
</defs>
<g id="floyd09_454d">
<use xlink:href="#I_454d" y="21" /> <use xlink:href="#I_454d" y="35" />
<use xlink:href="#I_454d" y="49" /> <use xlink:href="#I_454d" y="63" />
<use xlink:href="#I_454d" y="77" /> <use xlink:href="#I_454d" y="91" />
<use xlink:href="#I_454d" y="105" /> <use xlink:href="#I_454d" y="119" />
<use xlink:href="#I_454d" y="133" />
<use xlink:href="#C1_454d" x="27" y="21" /> <use xlink:href="#C1_454d" x="27" y="63" />
<use xlink:href="#C1_454d" x="27" y="105" /> <use xlink:href="#C1_454d" x="41" y="35" />
<use xlink:href="#C1_454d" x="41" y="77" /> <use xlink:href="#C1_454d" x="41" y="119" />
<use xlink:href="#C1_454d" x="55" y="21" /> <use xlink:href="#C1_454d" x="55" y="63" />
<use xlink:href="#C1_454d" x="55" y="105" /> <use xlink:href="#C3_454d" x="69" y="21" />
<use xlink:href="#C3_454d" x="83" y="63" /> <use xlink:href="#C3_454d" x="97" y="21" />
<use xlink:href="#C3_454d" x="111" y="35" /> <use xlink:href="#C3_454d" x="125" y="77" />
<use xlink:href="#C3_454d" x="139" y="35" /> <use xlink:href="#C3_454d" x="153" y="49" />
<use xlink:href="#C3_454d" x="167" y="91" /> <use xlink:href="#C3_454d" x="181" y="49" />
<use xlink:href="#C2_454d" x="195" y="35" /> <use xlink:href="#C2_454d" x="195" y="91" />
<use xlink:href="#C4_454d" x="209" y="49" /> <use xlink:href="#C2_454d" x="223" y="77" />
<use xlink:href="#C2_454d" x="237" y="49" /> <use xlink:href="#C1_454d" x="237" y="91" />
<use xlink:href="#C1_454d" x="251" y="49" />
</g>
</svg>
=end html
=cut
sub graph_svg
{
my $self = shift;
lib/Algorithm/Networksort.pm view on Meta::CPAN
$b_style = qq(style="fill:$clrset{inputbegin}; stroke:$clrset{inputbegin}");
$l_style = qq(style="fill:$clrset{inputline}; stroke:$clrset{inputline}");
$e_style = qq(style="fill:$clrset{inputend}; stroke:$clrset{inputend}");
}
$string .=
qq( <defs>\n) .
qq( <!-- Define the input line template. -->\n) .
qq( <g id="I$salt" $g_style >\n) .
qq( <desc>Input line</desc>\n) .
qq( <line $l_style x1="$grset{hz_margin}" y1="0" x2="$right_margin" y2="0" />\n);
if ($i_radius > 0)
{
$string .= qq( <circle $b_style cx="$grset{hz_margin}" cy="0" r="$i_radius" />) .
qq( <circle $e_style cx="$right_margin" cy="0" r="$i_radius" />\n);
}
$string .= qq( </g>\n\n);
#
# Set up the comparator templates, and like the input template,
# either set a single default color, or color the components
# individually.
#
$string .= qq( <!-- Define the different comparator lines. -->\n);
lib/Algorithm/Networksort.pm view on Meta::CPAN
my $clen = $to - $from;
if ($cmptr[$clen] == 0)
{
$cmptr[$clen] = 1;
my $endpoint = $vcoord[$to] - $vcoord[$from];
$string .=
qq( <g id="C$clen$salt" $g_style >\n) .
qq( <desc>Comparator size $clen</desc>\n) .
qq( <line $l_style x1="0" y1="0" x2="0" y2="$endpoint" />\n);
if ($c_radius > 0)
{
$string .= qq( <circle $b_style cx="0" cy="0" r="$c_radius" />) .
qq( <circle $e_style cx="0" cy="$endpoint" r="$c_radius" />\n);
}
$string .= qq( </g>\n);
}
}
$string .= qq( </defs>\n\n);
#
# End of definitions. Draw the input lines as a group.
#
$string .= qq( <g id=") . $self->nwid() . qq($salt">\n);
#
# If there's a background color, insert as the first element a <rect>
# with the full size of the view and a fill of the desired color.
#
if (defined $clrset{background})
{
$string .= qq( <rect width="100%" height="100%" style="fill:$clrset{background}" />\n);
}
$string .= qq( <!-- Draw the input lines. -->\n);
$string .= qq( <use xlink:href="#I$salt" y="$vcoord[$_]" />\n) for (0..$inputs-1);
#
# Draw our comparators.
# Each member of a group of comparators is drawn in the same column.
#
$string .= qq(\n <!-- Draw the comparator lines. -->\n);
my $hidx = 0;
for my $group (@node_stack)
{
my $h = $hcoord[$hidx++];
for my $comparator (@$group)
{
my($from, $to) = @$comparator;
my $clen = $to - $from;
my $v = $vcoord[$from];
$string .= qq( <!-- [$from,$to] -->) .
qq(<use xlink:href="#C$clen$salt" x="$h" y="$v" />\n);
}
}
$string .= qq( </g>\n</svg>\n);
return $string;
}
=head3 graph_text()
Returns a string that graphs out the network's comparators in plain text.
lib/Algorithm/Networksort.pm view on Meta::CPAN
Sorting and Searching> (2nd ed.), Addison Wesley Longman Publishing Co., Inc.,
Redwood City, CA, 1998.
=item
Sherenaz W. Al-Haj Baddar and Kenneth E. Batcher,
B<Designing Sorting Networks: A New Paradigm>, Springer-Verlag, 2011
=item
Kenneth Batcher's web site (L<http://www.cs.kent.edu/~batcher/>) lists
his publications, including his paper listed above.
=back
=head1 AUTHOR
John M. Gamble may be found at B<jgamble@cpan.org>
=cut
( run in 0.865 second using v1.01-cache-2.11-cpan-df04353d9ac )