Carl Love

Carl Love

28075 Reputation

25 Badges

13 years, 57 days
Himself
Wayland, Massachusetts, United States
My name was formerly Carl Devore.

MaplePrimes Activity


These are replies submitted by Carl Love

This is the other set operation that I mentioned: 

FixedSizeBlocks2:= (S::set, L::nonnegint)-> local p, r, q:= iquo(nops(S), L, r), k;
    {seq}(
        {seq}(S[[seq](p[(k-1)*L+1..k*L])], k= 1..q),
        p= Iterator:-SetPartitionFixedSize([L$q, r])
    )
:
GT:= GraphTheory:
K4:= GT:-CompleteGraph(4):
FixedSizeBlocks2(GT:-Edges(K4), 3);
    {{{{1, 2}, {1, 3}, {1, 4}}, {{2, 3}, {2, 4}, {3, 4}}}, 
      {{{1, 2}, {1, 3}, {2, 3}}, {{1, 4}, {2, 4}, {3, 4}}}, 
      {{{1, 2}, {1, 3}, {2, 4}}, {{1, 4}, {2, 3}, {3, 4}}}, 
      {{{1, 2}, {1, 3}, {3, 4}}, {{1, 4}, {2, 3}, {2, 4}}}, 
      {{{1, 2}, {1, 4}, {2, 3}}, {{1, 3}, {2, 4}, {3, 4}}}, 
      {{{1, 2}, {1, 4}, {2, 4}}, {{1, 3}, {2, 3}, {3, 4}}}, 
      {{{1, 2}, {1, 4}, {3, 4}}, {{1, 3}, {2, 3}, {2, 4}}}, 
      {{{1, 2}, {2, 3}, {2, 4}}, {{1, 3}, {1, 4}, {3, 4}}}, 
      {{{1, 2}, {2, 3}, {3, 4}}, {{1, 3}, {1, 4}, {2, 4}}}, 
      {{{1, 2}, {2, 4}, {3, 4}}, {{1, 3}, {1, 4}, {2, 3}}}}

The number of partitions produced by the procedure is n!/(L!^q * q! * (n-L*q)!), where n = nops(S) and q = floor(n/L).

The n1 is the summation index variable. Note the n1 = 1 under the summation sign. You could change it to any otherwise-unused variable, provided that you change all 4 occurrences.

@Carl Love Even after setting all parameters to 1 and examining some subsets of size 6 that contain the 6 decision variables, I can make no progress with either solve or even fsolve. They're too large or complicated. I give up.

If someone else wants to look at this: At least all the equations are algebraic functions (rational functions & fractional exponents) with the highest exponent being 4 and the only fractional exponent being 1/2.

@vs140580 Okay, how about this?

IsLabeledIsomorphicSubgraph:= proc(
    G1::Graph, G2::Graph, Labels::{set, list}({string, symbol, integer})
)
uses GT= GraphTheory;
local R:= GT:-IsSubgraphIsomorphic(G1, GT:-InducedSubgraph(G2, Labels), 'isomorphism');
    if [R][1] then subs(R[2], GT:-Edges(G1)) else false fi    
end proc
:

 

@MaPal93 Sorry, I made a mistake in the command  EqP:= eval(Eq, indets(EqN, name)=~ 1): That sets all variables to 1, including the decision variables V. Change it to

EqP:= eval(Eq, (indets(EqN, name) minus V)=~ 1):

@MaPal93 Why do you think that there's a solution? 

@mehdibgh There are two different variables t here: a global t in the matrices, and a local t in the procedure. Easiest way to fix it (but not the most-robust way): Change for t from to for :-t from. The :- prefix always refers to a global variable.

There are some possibilities of ambiguity for the 2nd case. What do you want returned for

SublistSubs([a,a]= x, [a,a,a], type2) ?

Both [x, a, a] and [x, x, a] seem reasonable. 

@Stretto An inert operator expression is type function in Maple, with the function name being the operator in backquotes, such as `%/`. (That doesn't generalize to non-inert operator expressions.) If f is a function, then op(k, f) is its kth argument, and op(0, f) is the function name. So, 3 %/ 6 is stored internally as `%/`(3, 6).

I think that this procedure will handle all cases (even when there's no inert operators in the expression):

NumerDenom:= (e::algebraic)-> local f;
    eval([numer,denom](evalindets[2](e, specfunc(`%/`), f, value@map)), f= (x-> x))
:
NumerDenom(x*3 %/ 6/y);

             [3 x, 6 y]

Since I think that that handles all cases, using an overload isn't necessary; but since you asked, the command is overload, it has a help page, and, yes, it filters through a list of procedures until finding the first one whose parameters are a type match for the arguments.

@jalal The code for a "does not exist" symbol is

dne:= `#mo("∄");`;

Then you could do subs(undefined= dne, whatever ).

@Stretto I don't think that there's anything simpler; if there was, it'd be in ListTools, and one can check that it isn't. Three consecutive list elements has no more "structural identity" in Maple than do three elements in random, disconnected locations. In other, it's not a single object in memory that can be "pointed to".

@vs140580 I've read your proposal carefully, several times. My experience and knowledge tells me that this problem is very likely to be extremely intractable (and almost certainly NP-hard); so I'm not interested in devoting any time to it at this time.

Please don't mention it again unless you or someone else has made significant progress on it.

By the way, you never acknowledged my solution to the "all possible graph products" problem. 

@mehdibgh Yes, I've noticed that for many years. The amount reported by Task Manager is always twice the amount reported on the worksheet's status bar. For example, for a brand new worksheet, or following a restart and gc(), the status bar says 4.18M and Task Manager says 8.4 MB (8.4 = 2*4.18 to two significant digits). Since the computer obviously struggles profusely for memory when Task Manager says its usage is near 100%, the Task Manager number must be the accurate one.

I have no idea why this is. I hope that someone from Maplesoft can answer this.

@vs140580 The only reasonable starting point that I can see would use the command GraphTheory:-IsSubgraphIsomorphic, which was introduced in Maple 2021. And, it should be used with its isomorphism option (which returns the isomorphism rather than simply true or false), which was introduced in Maple 2022.

@Carl Love The disjunctions of the subsets of the 8 conditions usually produce boolean expressions that can be much simplified. Doing that simplification (with Logic:-BooleanSimplify) substituting the simplified form into the procedure passed to RelationGraph is more efficient.

RelationGraph:= proc(f, V::list({integer, symbol, string}))
local n:= {$1..nops(V)}, i, F:= i-> j-> f(V[i],V[j]);
    GraphTheory:-Graph(V, [seq](select(F(i), n, _rest), i= n))
end proc
:

GraphProducts:= proc(
    GG::Graph, HH::Graph, 
    Rel::{
        set(integer[1..8]), 
        identical(
            ("Cartesian", "box"), ("strong", "normal", "AND"), ("lexicographic"),
            ("modular"), ("homomorphic"), ("co-normal", "disjunctive", "OR"),
            ("tensor", "Kronecker", "categorical", "direct")
        )
    }:= "Cartesian",
    {
        vertex_format::{string, symbol}:= "%A:%A",
        labeltype::identical(string, symbol):= string
    }
)
uses GT= GraphTheory, L= Logic;
local
    i, j, G:= 1, H:= 2,
    V:= GT:-Vertices~([GG,HH]), 
    E:= convert~(op~(4, [GG,HH]), table), #the edges, effectively
    P:= [seq](seq([i,j], j= 1..nops(V[H])), i= 1..nops(V[G])), 
    Vgh:= (
        curry(`if`(labeltype=string, sprintf, nprintf), vertex_format)
        @ ((i,j)-> (V[G][i],V[H][j])) 
        @ op
    )~(P),
    J:= op~(table(Vgh=~ P)),
    Edge:= proc(u,v) local k:= op(procname); J[v][k] in E[k][J[u][k]] end proc,
    Eq:= proc(u,v) local k:= op(procname); J[v][k] = J[u][k] end proc,
    eG, eH, qG, qH, #symbolic boolean variables (Edge of G, eQual in H, etc.)
    PrimRels:= (And~@table)([  #the 8 primitive relations (or conditions):
        1= (eG, qH),      2= (Not(eG), qH),      3= (eG, eH), 4= (Not(eG), eH),
        5= (eG, Not(eH)), 6= (Not(eG), Not(eH)), 7= (qG, eH), 8= (qG, Not(eH))
    ]),
    NamedRels:= table([  #some subsets of the above, named for user convenience:
        ("Cartesian", "box")=~                             ``({1,7}), 
        ("strong", "normal", "AND")=~                      ``({1,3,7}),
        "lexicographic"=                                   ``({1,3,5,7}), 
        "modular"=                                         ``({3,6}), 
        "homomorphic"=                                     ``({5,7,8}), 
        ("co-normal", "disjunctive", "OR")=~               ``({1,3,4,5,7}),
        ("tensor", "Kronecker", "categorical", "direct")=~ ``({3})
    ])
;
    RelationGraph( 
        subs(
            _B= subs(
                {L:-`&not`= `not`, L:-`&and`= `and`, L:-`&or`= `or`},
                {(eG,qG, eH,qH)=~ (Edge[G],Eq[G], Edge[H],Eq[H])(_u,_v)},
                L:-BooleanSimplify(Or(map2(index, PrimRels, op(NamedRels[Rel]))[]))
            ),
            [_u= u, _v= v],
            proc(u,v) option remember;
                if u=v then false  #Disallow self-loops.
                elif J[u][G] > J[v][G] or Eq[G](u,v) and J[u][H] > J[v][H] then
                    thisproc(v,u)  #Assume symmetry (no directed edges) for efficiency.
                else evalb(_B)
                fi
            end proc
        ),
        Vgh
    )
end proc
:
GT:= GraphTheory: RG:= GT:-RandomGraphs: CT:= CodeTools:
G:= GT:-CycleGraph(5): H:= GT:-CycleGraph(4):
GH:= CT:-Usage(GraphProducts(G, H, "co-normal", labeltype= symbol));
memory used=0.64MiB, alloc change=0 bytes, cpu time=16.00ms, 
real time=16.00ms, gc time=0ns

GH := Graph 18: an undirected unweighted graph with 20 vertices and 140 edge(s)

 

First 78 79 80 81 82 83 84 Last Page 80 of 709