Carl Love

Carl Love

28045 Reputation

25 Badges

12 years, 334 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

@acer IMO, if one is using 1D-input, then the expression-form for-while-do-until loop offers the greatest flexibility:

  • has a bona fide assignable return value;
  • can be used inside other expressions;
  • allows any extra statements inside without changing the return value and without changing the displayed values (unless that is desired);
  • allows any of the control structures that an ordinary do loop allows: whileuntil, multilevel break and next;
  • no detectable efficiency differences compared with seq or elementwise; in particular, expression sequences are built in linear, not quadratic, time.

Example:

Bools:= (
     for x in [0,1,2] do
         es1:= "extra statement 1";
         #Handle true/false/FAIL trichotomy: 
         if (b:= is(x in RealRange(Open(0), infinity))) then
             es2:= "extra statement 2"; 
             yes 
         elif b = FAIL then  #See 10th and 13th paragraphs of "Description" on the
             undecidable     #help page ?assume
         else
             es3:= "extra 3"; 
             no 
         fi 
     until b = FAIL
);
                     Bools := no, yes, yes

Indeed, this is the finest looping construct that I've ever seen in any language. Bravo, Maple kernel developers!

@Carlos36r printlevel is an all-or-nothing thing pretty much only suitable for debugging. It'll show the results of all statements executed at the given level or lower. Assignments to a for loop index are considered statements for this purpose, and, of course, that's useful information for debugging. 

There are several things that you could do instead:

1. Wrap the for loop in parentheses (only works in 1D-input AFAIK):

(for x in [0,1,2] do if is(x in RealRange(Open(0), infinity)) then yes else no fi od)  
                         
no, yes, yes

2. Use elementwise operators instead of a loop:

`if`~(is~([0,1,2], RealRange(Open(0), infinity)), yes, no)[]
                         no, yes, yes

3. Use seq (prefix-form looping operator):

seq(`if`(is(x in RealRange(Open(0), infinity)), yes, no), x= (0,1,2))  
                         
no, yes, yes

and others.

@vs140580 

[Moderator's comment: This Reply refers to a Reply that has been deleted.]

What you have written immediately above is highly specific to circulant graphs, whereas the rest of this thread is "pure" general combinatorics. Thus, if you'd like for these specific circulant-graph issues to be addressed, you should start a new Question thread. You've used circulant graphs as examples elsewhere is this thread; that's fine. However, in your most-recent Reply, they are not examples but rather the main issue.

Also, like I said before, please put the relevant parts of the text from your PDFs directly in your MaplePrimes's posts. If, in addition to that, you also want to attach the PDFs, that's fine.

@vs140580 You asked:

  • Which copy of C_4 represents with respect to which vertex if that can be told it will be great

If you could describe a method by which that can be known, then I'll include it.

  • Now put a new G and a new H it is taking sometime attached the same code with the new G and H

As I said, the method that I showed in the worksheet immediately above was not meant to be efficient. Its only purpose was for you to verify that its results were correct before I started working on a more-efficient version.

It's utterly impossible to use that worksheet on the problem that you're currently trying. You should kill it as soon as possible. It'll surely run out of memory and crash before finding a single cover. Here's why: |S| = 200 and n=10 (so, I guess that this is the example with which you started this thread). So, the number of n-subsets of S is binomial(200,10) = 22451004309013280 = 2.2 * 10^16 = 22 quadrillion. The worksheet tries to generate all those subsets before checking any of them.

  • Is it possible to print each IC cover set as it comes , as full excecution may take time I dont know if it is possible

In the code in the Answer (where G = K[n]), that's not possible because all the covers are built at the same time (with a loop that goes from 2 to n). In other words, the construction is "breadth first". That was the main thing that I did to improve the efficiency. Any branches that show violations of the singleton-intersection rule are pruned as soon as possible. This leads to a great reduction of the number of n-subsets of S that need to be checked. 

@vs140580 In order to make sure that I understand your requirements, I need you to verify the correctness of the following solution to your example of embedding C[4] in K[2,2,2]. I am not proposing this as an efficient solution technique; I just need to know whether its final result is correct before proceeding. This worksheet runs in under 5 seconds, and the result is 8 isomorphism covers.

restart:

Automorphs:= (G::Graph)->
local A:= op(4,G), n:= numelems(A), V:= [$n], p, E:= {seq}((op@`{}`~)~(V, A));
    {seq}(subs(V=~ p, E), p= combinat:-permute(n))
:

GT:= GraphTheory:  C:= combinat:

n:= 6:

H:= GT:-Graph([$n], {{1,2}, {2,3}, {3,4}, {4,1}}); #C[4]

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6], Array(1..6, {(1) = {2, 4}, (2) = {1, 3}, (3) = {2, 4}, (4) = {1, 3}, (5) = {}, (6) = {}}), `GRAPHLN/table/1`, 0)

G:= GT:-CompleteGraph(2,2,2); #K[2,2,2]

GRAPHLN(undirected, unweighted, [1, 2, 3, 4, 5, 6], Array(1..6, {(1) = {3, 4, 5, 6}, (2) = {3, 4, 5, 6}, (3) = {1, 2, 5, 6}, (4) = {1, 2, 5, 6}, (5) = {1, 2, 3, 4}, (6) = {1, 2, 3, 4}}), `GRAPHLN/table/7`, 0)

E:= GT:-Edges(G);

{{1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 4}, {2, 5}, {2, 6}, {3, 5}, {3, 6}, {4, 5}, {4, 6}}

S:= select(s-> s subset E, Automorphs(H)):

E:= `{}`~(E) union {{}}:

IC:= select(s-> (p-> `intersect`(p[]))~(C:-choose(s,2)) = E, C:-choose(S,n));

{{{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}, {{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 5}, {4, 5}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 6}, {4, 6}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 5}, {2, 3}, {2, 5}}, {{1, 4}, {1, 6}, {2, 4}, {2, 6}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {3, 5}, {3, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {4, 5}, {4, 6}}}, {{{1, 3}, {1, 4}, {3, 6}, {4, 6}}, {{1, 3}, {1, 6}, {2, 3}, {2, 6}}, {{1, 4}, {1, 5}, {2, 4}, {2, 5}}, {{1, 5}, {1, 6}, {4, 5}, {4, 6}}, {{2, 3}, {2, 4}, {3, 5}, {4, 5}}, {{2, 5}, {2, 6}, {3, 5}, {3, 6}}}}

 

Download IsoCovers.mw

Also, please post the text from your PDFs directly in MaplePrimes. If you want to also attach the PDF, that's okay, but I'll like the text (regardless of its formatting) to be in MaplePrimes.

@Carl Love By implementing a large number of small efficiencies, I've made IsoCovers twice as fast as the version that I posted yesterday. The new code is in the Answer immediately above.

@acer Thanks. I agree, and I edited my Answer accordingly. And I know that the job can be done with a single pair of quotes. Stylistically, I prefer separate pairs for the suffixed and x.

@Carl Love Here is an example of the set sizes involved in my IsoCovers procedure. The large sets are processed with Iterators, so memory is not an issue, only time.

Suppose that H is a simple 3-cycle and 4 isolated vertices. So n |V| = 7 and m = 3K[7] has binomial(7,2) = 21 edges. This set of edges is called E. So, there are binomial(21,3) = 1330 candidate subsets of E to check for isomorphism with H. Clearly, the number of 3-cycles in K[7] is binomial(7,3) = 35, so this is the size of S, the set of isomorphs of H. So the number of candidates for the final set is binomial(35, 7) = 6,724,520. For each of those, we need to check the 21 pairwise intersections.

@vs140580 Here is that program, for what it's worth. The sizes of the sets involved are enormous, so this is only practical for very small n.

IsoCovers:= proc(H::Graph) 
uses GT= GraphTheory, It= Iterator, C= combinat;
local
    n:= GT:-NumberOfVertices(H), V:= [$n], m:= GT:-NumberOfEdges(H),
    E:= GT:-Edges(GT:-CompleteGraph(n)), s, S, J, P
;
    S:= {
        for J in It:-Combination(binomial(n,2), m) do
            s:= E[[seq](J+~1)];
            if GT:-IsIsomorphic(H, GT:-Graph(V, s)) then s else fi
        od
    };
    {
        for J in It:-Combination(nops(S), n) do
            s:= S[[seq](J+~1)];
            P:= (p-> `intersect`(p[]))~(C:-choose(s,2));
            if nops~(P) = {1} and `union`(P[]) = E then s else fi
        od
    }
end proc
:           
GT:= GraphTheory:
H:= GT:-Graph([$4], {{1,2}, {1,3}, {2,3}});
H := Graph 7: an undirected graph with 4 vertices and 3 edge(s)

IsoCovers(H);
     {{{{1, 2}, {1, 3}, {2, 3}}, {{1, 2}, {1, 4}, {2, 4}}, 
       {{1, 3}, {1, 4}, {3, 4}}, {{2, 3}, {2, 4}, {3, 4}}}}

 

@vs140580 A correction for your line

ListTools:-Categorize((x, y) ->(( x[1] = y[1]) and numelems(select(member,x,y))=1), L)

is

ListTools:-Categorize((x,y)-> x[1] = y[1] and nops(x intersect y) = 1, L)

You may consider the returned singleton sublists as irrelevant; if so, they can be removed by

remove(x-> nops(x)=1, [%])

@vs140580 Yes, it can be done with an easy modification of the above code if and m are not too large. But I don't understand your usage of n-1 instead of nK[n] by definition has n vertices, not n-1.

Your list is a list of SETS of sets. I emphasized the first "SETS" because I think that your Question doesn't quite make sense if sets are used at that level (although sets are fine to represent edges). And it doesn't quite make sense because you've emphasized the sequential aspect of those sets, but the order of those sets is completely determined by Maple's automatic simpification of sets and it has nothing to do with any graph-related property. Indeed, if one of your sets contains {0, 1} as an element, then that's guaranteed to be the first element (unless perchance you allow self-loops). There's no way that you can use sets in Maple and impose upon them some order that is useful for your purpose.

Why do you ask "Is this a bug?" so often? Why do you constantly make comparisons with Mathematica? I'm extremely suspicious about your motivation for posting to MaplePrimes. You seem to have a sufficiently high level of programming skill that you could determine whether something is a bug, and you can read the code of MatrixPower to figure out why it is slow.

If you're so dissatisfied with Maple, then don't use it.

@Christopher2222 I agree absolutely that the default quality should be 100%; any other default is ridiculous. 

@mmcdara Here is what I think that the OP means by "suppressing function dependencies": If f is a Maple symbol or name---notprocedure[*1]---then f()f(0)f(x)f(x,y), etc., are all what Maple calls functions. I think that the OP would like all such instances to prettyprint display as simply f. By "prettyprint display", I mean that the way that they are displayed in a Standard worksheet (at default interface settings) is to be changed without altering Maple's internal (kernel) representation of the objects or its mathematical or computational understanding of them.

[*1] It's also possible (and indeed very common) for a procedure named f to return a function whose 0th operand is f via the syntax return 'procname'(args) or other closely related syntax.

First 52 53 54 55 56 57 58 Last Page 54 of 709