/
README
131 lines (96 loc) · 5.42 KB
/
README
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
Tutte Polynomial Generator (v0.9.X)
===================================
This is an early release of a program for computing tutte polynomials
for undirected graphs. As such, this version has had relatively
little testing done on it and should be considered EXTREMELY
EXPERIMENTAL. There are almost certainly outstanding bugs in the code
remaining to be fixed. As such, this software is provided as is, and
the authors and their respective insititutions accept no
responsibility for any problem arising from the use of this software.
We would appreciate any bug reports you have and/or suggestions on
improving the code. We'd also be very interested in hearing about
anyone interested in using the code for research (or other) purposes.
In particular, whether or not the current version is fast enough to
process the input graphs you want.
If you wish to be notified of updates to this software, please let us
know.
Thanks!
David J. Pearce
Gary Haggard
License
=======
The majority of files are currently under the following simple and quite
unrestrictive license:
"(C) Copyright David James Pearce and Gary Haggard, 2007.
Permission to copy, use, modify, sell and distribute this software
is granted provided this copyright notice appears in all copies.
This software is provided "as is" without express or implied
warranty, and with no claim as to its suitability for any purpose.
Email: david.pearce@mcs.vuw.ac.nz"
This license may not be removed from any of the files in question.
This software makes use of Brendan McKay's excellent "Nauty" program
for determining (amongst other things) whether two graphs are
isomorphic or not. You can find more information about this program
here: http://cs.anu.edu.au/~bdm/nauty
All files from the Nauty program are located in the nauty/
subdirectory. The following license applies to all files in the
nauty/ directory (see nauty.h for more details):
"Copyright (1984-2004) Brendan McKay. All rights reserved. Permission
is hereby given for use and/or distribution with the exception of
sale for profit or application with nontrivial military significance.
You must not remove this copyright notice, and you must document any
changes that you make to this program.
This software is subject to this copyright only, irrespective of
any copyright attached to any package of which this is a part.
This program is only provided "as is". No responsibility will be taken
by the author, his employer or his pet rabbit for any misfortune which
befalls you because of its use. I don't think it will delete all your
files, burn down your computer room or turn your children against you,
but if it does: stiff cheddar. On the other hand, I very much welcome
bug reports, or at least I would if there were any bugs.
RIP, 1989
If you wish to acknowledge use of this program in published articles,
please do so by citing the User's Guide:
B. D. McKay, nauty User's Guide (Version 1.5), Technical Report
TR-CS-90-02, Australian National University, Department of
Computer Science, 1990."
Installation Instructions
=========================
To compile the system, run the following:
> ./configure
> make
This will build the executable "tutte" in the directory tutte/. If
you do not have the GMP library installed, you will need to disable
GMP support by passing "--disable-gmp" to configure.
The configure script accepts many options, and to get a full list of
them simply run "./configure --help".
The system has been sucessfully compiled on the following platforms:
1) NetBSD + Linux with GCC 4.1.2
2) Windows (under Cygwin) with GCC 4.1.?
Command-line Options
====================
Currently, the tutte program accepts a number of command-line options.
You can run "tutte --help" to see a list. We will not examine all of
them here, but there are a few which you should know about:
"-c<x> --cache-size=<x>"
The system uses an internal cache to store previously seen subgraphs,
in order to prevent their (unnecessary) recomputation. The size of
this cache will certainly affect performance for largish (>15
vertices) input graphs.
We do not recommend giving all available physical RAM to the cache,
since this will result in thrashing. Instead, 80--90% of physical RAM
is ideal. For example, suppose your machine has 1GB of physical RAM.
Then, we'd use the switch "-c800M" to allocate 800 Megabytes of it to
the internal cache.
"-i --info"
This gives some information on the size of the computation tree which
can be useful. In particular, it tells you the size of the
computation tree and gives values for T(1,1) and T(2,2) which can be
used to help verify correctness.
"--sparse" "--dense"
This selects an edge selection heuristic suited to either "sparse" or
"dense" graphs. The default is select the best based on a density
threshold of 0.5. You may find forcing the heuristic will improve
performance dramatically for your problem.
An example command-line we might us is:
tutte -ic800M --sparse ../examples/edge20