srfi 25 support (arrays in Dr.scheme), so I don't have to explicitly deal with vectors within vectors
CTS
environment (under windows XP). The one library which I have been able
to find is SLIB, but the file that is mentioned in the readme for
loading the library in Mz. Scheme doesn't appear to come in the
downloaded package and the library also seems to be intend to
primarily for Linux.
thanks in advance for anyone who replies
chain...@hotmail.com
> I am trying to find a library to add srfi-25 support to my Dr. Scheme
> environment (under windows XP). The one library which I have been able
> to find is SLIB, but the file that is mentioned in the readme for
> loading the library in Mz. Scheme doesn't appear to come in the
> downloaded package and the library also seems to be intend to
> primarily for Linux.
Hi:
Not beeing sure whether it will also hold for Dr. Scheme. However, I
once used srfi-25 in my Bigloo environment but quickly jettisoned it
due to its dog slow performance as compared to Bigloo its own vector
types. I haven't figured out how to tune srfi-25 because I haven't
undestood the recipie which comes somewhere hidden in the
distribution.
That surely is one of the big disatvantages of srfi stuff. You never
know their behaviour in advance as long as the distribution itslef
does not support it.
By the way: what is wrong with vectors of vectors?
Fensterbrett
PS: Yes though I have to agree that srfi-1 is really outstanding;
especially its documentation is fairly good. But still: I do not know
how to use it if Bigloo wouldn't support it (one can easily make a
srfi-1 Bigloo library; the Bigloo distribution delivers the
scaffolding for doing it).
CTS
>
> Not beeing sure whether it will also hold for Dr. Scheme. However, I
> once used srfi-25 in my Bigloo environment but quickly jettisoned it
> due to its dog slow performance as compared to Bigloo its own vector
> types. I haven't figured out how to tune srfi-25 because I haven't
> undestood the recipie which comes somewhere hidden in the
> distribution.
>
> That surely is one of the big disatvantages of srfi stuff. You never
> know their behaviour in advance as long as the distribution itslef
> does not support it.
>
> By the way: what is wrong with vectors of vectors?
because then I'll have to write my own little package to create the
illusion of two dimensional arrays, when in fact behind the scenes
what is actually happening is the constant reading and writing of an
entire vector to some index of another vector, which would be fairly
slow as well.
I wouldn't mind doing that, if my problem made extensive use of
vectors.
However, what I am doing is designing a graph isomorphism algorithm,
and two dimensional vectors (with N by N elements) happen to make
sense for certain internal representations of graphs.
are there any user friendly schemes which support two dimensional
arrays out of the box, or would I be better of trying out Common Lisp?
(this last comment is not an attempt to start any language war, but
the looping constructs and larger array of builtin data types look
fairly seductive)
> Fensterbrett
> PS: Yes though I have to agree that srfi-1 is really outstanding;
> especially its documentation is fairly good. But still: I do not know
> how to use it if Bigloo wouldn't support it (one can easily make a
> srfi-1 Bigloo library; the Bigloo distribution delivers the
> scaffolding for doing it).
How did srfi-1 come up?
Bradd W. Szonye
CTS <parvus...@netscape.net> wrote:
> because then I'll have to write my own little package to create the
> illusion of two dimensional arrays, when in fact behind the scenes
> what is actually happening is the constant reading and writing of an
> entire vector to some index of another vector, which would be fairly
> slow as well.
It's extremely unlikely to work like that. In particular, you do *not*
need to read or write an entire vector just because it's stored in
another vector. That's because Scheme vectors are described by
*location*, not by contents. It's about as efficient as implementing a
two-dimensional vector in C as an array of pointers.
--
Bradd W. Szonye
http://www.szonye.com/bradd
chain...@hotmail.com
> because then I'll have to write my own little package to create the
> illusion of two dimensional arrays, when in fact behind the scenes
> what is actually happening is the constant reading and writing of an
> entire vector to some index of another vector, which would be fairly
> slow as well.
>
> I wouldn't mind doing that, if my problem made extensive use of
> vectors.
>
> However, what I am doing is designing a graph isomorphism algorithm,
> and two dimensional vectors (with N by N elements) happen to make
> sense for certain internal representations of graphs.
>
> are there any user friendly schemes which support two dimensional
> arrays out of the box, or would I be better of trying out Common Lisp?
> (this last comment is not an attempt to start any language war, but
> the looping constructs and larger array of builtin data types look
> fairly seductive)
Hi:
I doubt that vectors of vectors are really that slow; at least under
Bigloo. I can only tell you the following: Bigloo its vectors (or in
case of a matrix) are in the realm of "only 2 times slower than using
C pointers".
Concerning Common Lisp. You shouldn't fall for and believe that Common
Lisp is fast. The only option there I would assume is using ECBL Lisp.
It is some kind of a "Bigloo"-Lisp. I mean you can create stand alones
and their matrix access times are as fast as Bigloo its ones. I made
once some tests. I am not a Common Lisp expert but I used the type
declarations what I gathered from some experts on the newsgroup. At
the same time I used my Bigloo code (vectors of vectors) and to my
surprise both displayed the same execution time. CMUCL showed a factor
of 2 slower execution time (same type declarations as the ones under
ECBL).
That said: I do not buy it that Common Lisp is necessarily faster than
at least Bigloo for numerical computations. I think Common Lispers
should get real. with their statements: "ah, but when using type
declarations we can show you that ah ehm we are as fast as Fortran".
Btw: why not trying Bigloo?
Or better: use some small typical benchmarks in your field of work or
profession and post the results with an annotation what you had
expected. I mean there are often people they expect the following:
plus/minus 0.1% of C speed. Such a thing is surely unrealistic. I
think your chance of getting some clues then is especially great in
comp.lang.scheme as opposed to comp.lang lisp where you would get the
advice in case of a speed penalty: hey guy, your are wrong, your
project is wrong as long as it does not fit to Common Lisp.
Fensterbrett
Anton van Straaten
> I am trying to find a library to add srfi-25 support to my Dr. Scheme
> environment (under windows XP). The one library which I have been able
> to find is SLIB, but the file that is mentioned in the readme for
> loading the library in Mz. Scheme doesn't appear to come in the
> downloaded package and the library also seems to be intend to
> primarily for Linux.
In DrScheme v206 (and probably many earlier versions), SRFI-25 is included.
All you should need to do is:
(require (lib "25.ss" "srfi"))
If that doesn't work, post the error message you get.
Anton
--
; breaking the Perl lock on cryptic .sigs:
(list->string(call-with-current-continuation(lambda(x)(let*((z(map(lambda
(c)(reverse(cons c(call-with-current-continuation(lambda(k)(list k 0))))))
(string->list"patsonm")))(i(apply max(map car z)))(cs(cddr(assoc i z)))(xs
(append(string->list(case i((4)"ul")((5)"@")((6)"i")((12)"c.")((15)(x cs))
(else"")))cs))(k(cadr(list-ref(map(lambda(i)(list-ref z i))(list 3 0 4 1 2
5 4 4 5 2 3 5 4 1 6))i))))(k `(,@xs ,k ,(+ i 1)))))))
Eric Marsden
cl> Concerning Common Lisp. You shouldn't fall for and believe that
cl> Common Lisp is fast.
the Common Lisp specification is not fast (especially reading all of
it!). However, several implementations of the Common Lisp langage
can generate fast code.
cl> That said: I do not buy it that Common Lisp is necessarily faster than
cl> at least Bigloo for numerical computations. I think Common Lispers
cl> should get real.
people who use Bigloo get real (and fixnum), but they don't get bignum
or complex or rational. That's a bit of a pity if you're doing
numerical computations.
A pleasant feature of Common Lisp implementations such as CMUCL is
that they default to providing a complete numerical tower, and return
correct results even when you overflow a fixnum. By using type
declarations and optimizing for speed over safety, you can attain
speeds similar to Bigloo (which I agree is a very nice implementation
of almost-Scheme).
--
Eric Marsden <URL:http://www.laas.fr/~emarsden/>
Noel Welsh
> I am trying to find a library to add srfi-25 support to my Dr. Scheme
Ummm.... (require (lib "25.ss" "srfi")) in DrScheme 206 does the job...
Noel
CTS
>
> In DrScheme v206 (and probably many earlier versions), SRFI-25 is included.
> All you should need to do is:
>
> (require (lib "25.ss" "srfi"))
>
> If that doesn't work, post the error message you get.
>
> Anton
thanks, it works
I where can I find documentation on srfi support in doctor scheme? so
I do not have to go through this again, because when I searched for
such information, I couldn't find it.
Thank You to all who responded
Anton van Straaten
> I where can I find documentation on srfi support in doctor scheme? so
> I do not have to go through this again, because when I searched for
> such information, I couldn't find it.
If you search for "srfis" in the DrScheme Help Desk, it returns a link to a
page entitled "PLT Scheme support for SRFIs". (You can search for "srfi"
too, it just returns more hits.) That page has the info about how to load a
SRFI, and a list of the supported SRFIs.
Anton
David Rush
> However, what I am doing is designing a graph isomorphism algorithm,
You've had some kind of insight which gets you past the basic NP-completeness
of the problem? Do tell. Or have you just determined that you don't
need to handle the full problem? I've been wrestling with this one for
years. Inquiring minds want to know.
david rush
--
It's always tempting to impute
Unlikely virtues to the cute
-- P. J. O'Rourke
Ray Dillinger
>
> parvus...@netscape.net (CTS) writes:
> > However, what I am doing is designing a graph isomorphism algorithm,
>
> You've had some kind of insight which gets you past the basic NP-completeness
> of the problem? Do tell. Or have you just determined that you don't
> need to handle the full problem? I've been wrestling with this one for
> years. Inquiring minds want to know.
>
late 80s/early 90s by Zamir Bavel.
Turns out that graph isomorphism is only hard in the worst case; usually
graphs have only a small number of 'generator' states (states forming
the smallest set from which the rest of the graph may be reached), and
you get lots of opportunities to trim possible solutions. Basically,
every possible isomorphism represents a mapping of generators to
generators, and this is usually *MUCH* less work than the old algorithm
of trying every possible mapping of state to state.
Of course, it's still NP in the worst case, in the same way that binary
trees have order(N) insert in the worst case.
Bear
CTS
> parvus...@netscape.net (CTS) writes:
> > However, what I am doing is designing a graph isomorphism algorithm,
>
> You've had some kind of insight which gets you past the basic NP-completeness
> of the problem? Do tell. Or have you just determined that you don't
> need to handle the full problem? I've been wrestling with this one for
> years. Inquiring minds want to know.
>
> david rush
well, I'm not sure if I've made a breakthrough, as I'm still just in
the design/thinking about how to do it stage, but it seems to me both
that if certain parts of the algorithm (which will in the initial
version have a factorial level of growth) can be rewritten so that
they have a polynomial growth, then the entire algorithm will be
polynomial.
I'm not going to have much time to work on it till this summer, and I
may very well not get any where beyond simply implementing the initial
version of the algorithm, as I am still only in high school and won't
have any serious exposure to computer science (beyond the basics that
I have taught myself) until college. The algorithm, I might add, seems
as if it would also work for directed graphs as well.
basically, the graph will go through several stages where it is
represented in different ways. First it will be fed in as a list that
encodes both the number of nodes as some integer N with the nodes
themselves being
labeled 0 through N-1 and with the rest of the list containing all the
edges of the graph represented as pairs of numbers this will look
something like (3 (0 1) (0 2) (1 2) ), though if I had it so that it
also accepted directed graphs this would look like (3 (0 1) (1 0) (0
2) (2 0) (1 2) (2 1))
this is read in, and converted to an N by N array (the reason why I
had asked in my previous posting) that contains #t or #f in a given
location X Y which indicates if node X is connected by an edge to node
Y.
This is then used to determine if the two graphs have the same number
of nodes and same number of nodes of the same degree, among other
things. Then, if the graph can't be identified as a special case for
which a more efficient alternative method exists, the algorithm will
generate the set of all paths (by this I mean acyclic walks that
terminate at a node with a degree of 1 or when it will reach a node
that it has already visited if it continues) that originate from each
node and is not a subset of another path, this seems as if it will
have a growth of about N! , (this is only done if the graph is)
then using information derived from these three representations of the
graph, which would allow the set of mappings between the , I
will have a function that generates functions which will try to
relabel one graph so that it is identical to the other (I'm not going
into much detail with this part as I am still trying to figure out how
it will do certain partso of this) . Identifying whether a particular
relabelling of a graph leads to it matching the other graph will be
done by sorting the resulting paths using something akin to radix or
bucket sort and seeingif the resulting ordered sets of paths are
identical
please note that all estimations about the worst case time of each
part of the algorithm assumes a complete graph (a graph of N nodes
each of degree N-1 )
Does this make sense, and is it a novel approach?
----------------------
all emails should be addressed to cartazio at yahoo dot com
Jeffrey M. Vinocur
CTS <parvus...@netscape.net> wrote:
>David Rush <dr...@aol.net> wrote in message news:<okfbrnv2w...@aol.net>...
>
>well, I'm not sure if I've made a breakthrough, as I'm still just in
>the design/thinking about how to do it stage, but it seems to me both
>that if certain parts of the algorithm (which will in the initial
>version have a factorial level of growth) can be rewritten so that
>they have a polynomial growth, then the entire algorithm will be
>polynomial.
(I don't want to stomp on your enthusiasm, but so you know, the
odds are not in your favor.)
>[...] this seems as if it will have a growth of about N!
Ah ha, I think we found your problem. Factorial time is *worse*
than exponential. Consider:
2^n: 2 x 2 x 2 x 2 x 2 x 2 x 2 x ... x 2 (n factors)
3^n: 3 x 3 x 3 x 3 x 3 x 3 x 3 x ... x 3 (n factors)
4^n: 4 x 4 x 4 x 4 x 4 x 4 x 4 x ... x 4 (n factors)
n!: 1 x 2 x 3 x 3 x 4 x 5 x 6 x ... x n (n factors)
n^n: n x n x n x n x n x n x n x ... x n (n factors)
Do you sort of see how each product is much larger than the one
before it?
--
Jeffrey M. Vinocur * jm...@cornell.edu
http://www.people.cornell.edu/pages/jmv16/
CTS
> >the design/thinking about how to do it stage, but it seems to me both
> >that if certain parts of the algorithm (which will in the initial
> >version have a factorial level of growth) can be rewritten so that
> >they have a polynomial growth, then the entire algorithm will be
> >polynomial.
>
> (I don't want to stomp on your enthusiasm, but so you know, the
> odds are not in your favor.)
>
>
> >[...] this seems as if it will have a growth of about N!
>
> Ah ha, I think we found your problem. Factorial time is *worse*
> than exponential. Consider:
>
> 2^n: 2 x 2 x 2 x 2 x 2 x 2 x 2 x ... x 2 (n factors)
> 3^n: 3 x 3 x 3 x 3 x 3 x 3 x 3 x ... x 3 (n factors)
> 4^n: 4 x 4 x 4 x 4 x 4 x 4 x 4 x ... x 4 (n factors)
>
> n!: 1 x 2 x 3 x 3 x 4 x 5 x 6 x ... x n (n factors)
>
> n^n: n x n x n x n x n x n x n x ... x n (n factors)
>
> Do you sort of see how each product is much larger than the one
> before it?
yes I was aware of this. Note that I said worst case is N!, not the
normal case.
you see, the two parts with the worst cases of N! are only like that
if the properties of each node is indistinquishable from that of every
other node,
if the nodes have properties that make them unique in comparision to
the others, the best case could be N, such as if the two graphs are
both null, complete, or if each has only one node of any given degree.
It should also be noted that in many cases it will have a polynomial
growth when proving two graphs are not isomorphic
for certain cases, the algorithm will have a less than exponetial
growth, though I can't say more than that until I fully implement it
---------------
does anyone have any advice concerning algorithm design in general
that I may
find useful?
tal...@noshpam.lbl.government
parvus...@netscape.net (CTS) writes:
> you see, the two parts with the worst cases of N! are only like that
> if the properties of each node is indistinquishable from that of every
> other node,
> if the nodes have properties that make them unique in comparision to
> the others, the best case could be N, such as if the two graphs are
> both null, complete, or if each has only one node of any given degree.
> It should also be noted that in many cases it will have a polynomial
> growth when proving two graphs are not isomorphic
Well, for non-degenerate cases, sure. You could even cook up examples
that solve it in O(1) time. But that isn't really the same thing as
solving the complete problem it all its generality...
BTW, you may want to fully grok how NAUTY approaches the
problem. Using heuristics and efficient code, NAUTY is able to answer
the graph isomorphism question for most graphs in a reasonable amount
of time ( still NP-hard, though... ).
NAUTY:
http://tinyurl.com/2p3q4
> does anyone have any advice concerning algorithm design in general
> that I may
> find useful?
I'm personally a big fan of forward-star representations of graphs (
especially sparse ones ):
Goldberg et al. "Shortest Path Algorithms: Theory and Experimental
Evaluation". ACM-SIAM Symposium on Discrete Algorithms. 1994.
~Tomer
--
()
tal...@noshpam.lbl.government
> parvus...@netscape.net (CTS) writes:
>> However, what I am doing is designing a graph isomorphism algorithm,
>
> You've had some kind of insight which gets you past the basic NP-completeness
> of the problem? Do tell. Or have you just determined that you don't
> need to handle the full problem? I've been wrestling with this one for
> years. Inquiring minds want to know.
Last time I checked, the literature maintains that the graph
isomorphism problem is classified as being NP-hard ( having not been
proven to be in P or NP ), not NP-complete.
~Tomer
>
> david rush
> --
> It's always tempting to impute
> Unlikely virtues to the cute
> -- P. J. O'Rourke
--
()
Programmer in Chief
> David Rush <dr...@aol.net> writes:
>
> > parvus...@netscape.net (CTS) writes:
> >> However, what I am doing is designing a graph isomorphism algorithm,
Why is this in comp.lang.scheme, with srfi-25 in the subject line?
Are you thinking of programming your algorithm in Scheme?
Go for it! Scheme should be a good language for tinkering with
such things.
> Last time I checked, the literature maintains that the graph
> isomorphism problem is classified as being NP-hard ( having not been
> proven to be in P or NP ), not NP-complete.
It must have been a while since you checked, you have forgotten
basic definitions. The problem of checking isormorphism of arbitrary
graphs is obviously in NP, which means just that if you give me
the mapping from nodes of one graph to nodes of the other, I can
quickly (e.g. n^2 time) check that the edges match.
Last time I checked. it was not known to be NP-hard, which means at
least as hard as any problem in NP, and smart people were guessing
it is probably not NP-hard, but rather easier than an NP-complete
problem. It is also not known to be in P, which makes it a candidate
for an intermediate problem...harder than P, but not NP-hard.
NP-complete means both in NP (NP-easy) and NP-hard, so we don't know
if it's that.
-- Keith
Fabien Todescato
http://www.cs.sunysb.edu/~algorith/files/graph-isomorphism.shtml
.
A practical algorithm that I have used reduces the problem of finding
the isomorphism between two graphs to that of finding the cliques of the
so-called 'association graph' derived from these two graphs.
See
http://www.cs.sunysb.edu/~algorith/files/clique.shtml
for the clique problem.
Instead of resorting to backtracking to compute the cliques of a graph,
you may use Binary Decision Diagrams - BDD - or ZBDDs, that are a
variant thereof.
See
http://www.chl.chalmers.se/~vahidi/bdd/main.html
for informations about the use of BDDs and ZBDDs in order to solve graph
problems.
Cheers.
Fabien Todescato