Name | Modified | Size | Downloads / Week | Status |
---|---|---|---|---|

Totals: 5 Items | 4.6 kB | 1 | ||

v0.1.3 | 2014-05-31 | 5 | ||

v0.1.2 | 2014-03-20 | 3 | ||

v0.1.1 | 2012-12-03 | 1 | ||

v0.1.0 | 2012-11-25 | 2 | ||

README | 2014-05-31 | 4.6 kB | 1 |

=============================================================================
An FKT Algorithm implementation
=============================================================================
Author: David Kühling <dvdkhlng TA gmx TOD de>
License: GPLv3; NO WARRANTY!
Homepage: http://sourceforge.net/projects/fkt
Mailing List: fkt-discuss@lists.sourceforge.net
(subscribe/archives: https://lists.sourceforge.net/lists/listinfo/fkt-discuss)
Introduction
------------
The FKT algorithm computes the number of weighted perfect matchings of a
planar graph.
Installation
------------
On most Unix installations this should do:
./configure && make && make install
Notes on Implementation
-----------------------
* This needs Gforth to run, version 0.7.0 should do. Gforth is available on
almost any Linux installation, just locate and install the corresponding
package. There are also Windows and Mac-OS versions, although setting this
up may involve a little bit more work. More information here:
http://bernd-paysan.de/gforth.html
If you've problems making Gforth run on your platform, try asking on
Gforth's mailinglist:
http://lists.gnu.org/mailman/listinfo/gforth
* We compute (weighted) number of matchings over finite fields. Everything
done in integer arithmetic so no problems with numeric accuracy and
stability. Result is modulo 2^31-1 on 32-bit Linux installations and
modulo 9223372036854775783 on 64-bit installations.
* You can compute the number of matchings with practically unlimited
accuracy: just compute using different modulus, then apply the chinese
remainder theorem.
* For some graphs negative number of matchings is returned, and the author
doesn't yet understand why. Note that negative "N" actually means
"modulus-N".
* Complex weights are supported, actually weights of Gaussian numbers.
Computation is again done via finite fields GF(p^2), so you're fine as long
as you don't wrap around the modulus and as long as the polynomial is
irreducable, see complex.fs for more information
Usage
-----
The FKT package is a little unpolished. See the man-page of the fkt command
(./fkt.1) to see whether it suits you. For an example graph file to use with
the 'fkt' command see './graphparse-test.graph'.
In case you need more functionality, create a simple forth script to define
your graph and run the computation. You can also export your graphs as
postscript to visually check your input. Here is an exampe, to compute
matchings for the graph from the FKT wikipedia page, just create a file with
this contents:
--8<--
#! /usr/bin/gforth
warnings off
require ./fkt.fs
\ define the graph from the FKT_algorithm wikipedia page
\ Coordinates of graph nodes (planar embedding)
10 CONSTANT #nodes \ make sure this reflects number of nodes
DOUBLE , HERE
0 5 2, 1 5 2, 2 5 2, \ tuples of x-y coordinates followed by '2,'
0 4 2, 1 4 2, 2 4 2,
0 3 2, 1 3 2, 2 3 2,
1 2 2,
CONSTANT xy{
\ Edges
14 CONSTANT #edges \ make sure this reflects number of edges
DOUBLE , HERE
0 1 2, 1 2 2, \ tuples of point-indices followed by '2,'
0 3 2, 1 4 2, 2 5 2,
3 4 2, 4 5 2,
3 6 2, 4 7 2, 5 8 2,
7 8 2,
6 9 2, 7 9 2, 8 9 2,
CONSTANT edges{
\ Weights
INTEGER , HERE \ weights corresponding to edges above
1 , 1 , \ each edge weight followed by a ','
1 , 1 , 1 ,
1 , 1 ,
1 , 1 , 1 ,
1 ,
1 , 1 , 1 ,
CONSTANT weights{
\ Export graph to postscript file named "graph.ps"
require ./drawing.fs
#nodes #edges xy{ edges{ weights{ s" graph.ps" print-drawing
\ Compute number of matchings and output to stdout
CR .( #matchings: )
#nodes #edges xy{ edges{ weights{ }#weighted-matchings .
\ Or try with complex weights
DOUBLE , HERE \ weights corresponding to edges above
1 0 2, 1 0 2, \ each 'real imag' tuple followed by '2,'
1 0 2, 1 0 2, 1 0 2,
1 0 2, 1 0 2,
1 0 2, 1 0 2, 1 0 2,
1 0 2,
1 0 2, 1 0 2, 1 0 2,
CONSTANT zweights{
\ Export graph with complex weigtks to postscript file named "zgraph.ps"
#nodes #edges xy{ edges{ zweights{ s" zgraph.ps" print-drawing
\ Compute number of matchings using complex weights, output to stdout
CR .( "complex" #matchings: )
#nodes #edges xy{ edges{ zweights{ }#zweighted-matchings SWAP . .
\ Quit
CR BYE
--8<--
Then save as fkt-run.fs, and run using
gforth ./fkt-run.fs
Contact
-------
Send questions and comments to the mailing list
https://lists.sourceforge.net/lists/listinfo/fkt-discuss