#12630 closed enhancement (fixed)
Add representations of quivers and quiver algebras to sage
Reported by:  JStarx  Owned by:  AlexGhitza 

Priority:  major  Milestone:  sage6.3 
Component:  algebra  Keywords:  algebra, quiver, module, days49 
Cc:  jhpalmieri, was, stumpc5, saliola, SimonKing, gmoose05, d.rupel@…, mguaypaq, nthiery, virmaux, ncohen  Merged in:  
Authors:  Jim Stark, Simon King, Mathieu GuayPaquet, Aladin Virmaux  Reviewers:  Simon King, Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  f3402ef (Commits, GitHub, GitLab)  Commit:  
Dependencies:  #12412, #12413, #14806, #15491, #15623, #15810  Stopgaps: 
Description (last modified by )
This will add classes dealing with quivers, quiver algebras, representations of quivers, elements of these representations, homomorphisms between these representations, and spaces of homomorphisms between these representations.
There's a lot here that is really easily computable. We can compute socles, quotients, radicals, duals, and more for any finite dimensional representation. We can compute projective covers of modules so AuslanderRieten translations have been implemented and there's certainly potential for future enhancements dealing with homology and cohomology. There's only so much I can say here but everything is fully documented and should be self explanatory.
Two shortcomings are that quivers need to be acyclic (to keep things finite dimensional) and this code does not handle quivers with relations. As far as quivers with relations go there are comments in the code detailing what should be done to implement that. It's well within the reach of Sage, I just don't have the time to do it at the moment.
About the commits
The second commit is supposed to split the code into chewable bits (so that maintenance and cythonization will become easier), introduces a parent structure for the paths of a quiver (namely: a free small category), makes paths inherit from Element (but not from UniqueRepresentation
!) and fixes some tests. The third commit uses Sage's infrastructure for morphisms and homsets of representations, and it reduces the pollution of the global namespace.
Attachments (10)
Change History (284)
comment:1 Changed 10 years ago by
 Status changed from new to needs_review
comment:2 Changed 10 years ago by
 Cc stumpc5 saliola added
 Dependencies changed from 12412, 12413 to #12412, #12413
 Description modified (diff)
comment:3 Changed 10 years ago by
 Cc SimonKing added
comment:4 Changed 10 years ago by
JStarx, are you coming to Sage Days 38? One of the themes is this sort of thing.
 Wiki page for Sage Days 38
 Official webpage (for registration and funding requests)
comment:5 followups: ↓ 6 ↓ 9 Changed 10 years ago by
 Description modified (diff)
Correct me if I'm wrong, but my understanding is that a simplylaced quiver is a quiver whose underlying undirected graph is Dynkin type A, D, or E. If this is what you meant then no, this patch doesn't focus on simplylaced quivers. Any finite acyclic quiver is allowed, it could have multiple edges, be disconnected, it doesn't need to be Dynkin or even affine Dynkin.
Also it's important that the quivers in my patch have unique representation in Sage because they are part of the defining data of a parent, whereas the point of the combinat quivers is that they can be mutated. So I'm not sure combining the two classes makes sense. I would be very interested in what Simon has to say about this (and in general about my patch) from an algebra/representation theory perspective, as I'm pretty new to Sage development.
Franco: I hadn't really considered the possibility till now. But with funding I would definitely be able to come. I'll go ahead and apply.
comment:6 in reply to: ↑ 5 Changed 10 years ago by
Replying to JStarx:
Correct me if I'm wrong, but my understanding is that a simplylaced quiver is a quiver whose underlying undirected graph is Dynkin type A, D, or E. If this is what you meant then no, this patch doesn't focus on simplylaced quivers. Any finite acyclic quiver is allowed, it could have multiple edges, be disconnected, it doesn't need to be Dynkin or even affine Dynkin.
Starting with any quiver, you can construct a skewsymmetric matrix (m_{i,j}) with m_{i,j} is the number of edges from i to j minus the number of edges from j to i (one is always supposed to be 0). That's what I meant with simplylaced. One can also think of quivers (like in type B) coming from a skewsymmetrizable matrix (i.e., M such that DM is skewsymmetric for a positive diagonal matrix D), where the edges are labeled (m_{i,j},m_{j,i}). Our "combinatorial quiver" can be construced for any skewsymmetrizable matrix (not in any way restriced to finite or affine types).
Also it's important that the quivers in my patch have unique representation in Sage because they are part of the defining data of a parent, whereas the point of the combinat quivers is that they can be mutated. So I'm not sure combining the two classes makes sense.
This might be right. We could also think of two classes "Quiver" and "CombinatorialQuiver?" (as your construction is really the one Gabriel named quiver), and then having maps between them. Can you think of any interaction between the two concepts (like mutating in sinks and sources corresponds in finite types to picking a particular Coxeter element, which corresponds to picking a particular AuslanderReiten quiver  we are also currently preparing a paper where we give an alternative combinatorial view on AuslanderReiten translates in finite types  any further ideas, maybe beyond finite types)?
Best, Christian
comment:7 followup: ↓ 8 Changed 10 years ago by
Unfortunately I'm no expert on AuslanderReiten theory, but I think the idea of two separate classes with an easy way of converting makes sense. I also think the conversions should be very easy to do, as both classes can already take a DiGraph? as input.
I think the easiest way to work this would be to go ahead and get both patches into Sage independently. After that happens it would only take a minor tweak to make the constructors accept Quivers of the other type as input.
comment:8 in reply to: ↑ 7 Changed 10 years ago by
Replying to JStarx:
Unfortunately I'm no expert on AuslanderReiten theory, but I think the idea of two separate classes with an easy way of converting makes sense. I also think the conversions should be very easy to do, as both classes can already take a DiGraph? as input.
I think the easiest way to work this would be to go ahead and get both patches into Sage independently. After that happens it would only take a minor tweak to make the constructors accept Quivers of the other type as input.
That approach makes sense to me. By the way: For my own work (computing ext algebras of basic algebras), I'd need finite dimensional quotients of quiver algebras with cycles. So, for now, I think I have to rely on my own implementation.
comment:9 in reply to: ↑ 5 Changed 10 years ago by
Replying to JStarx:
Franco: I hadn't really considered the possibility till now. But with funding I would definitely be able to come. I'll go ahead and apply.
I'm glad that you are considering it. I think you'd make a great fit. Christian is coming as well.
Maybe we can convince Simon to come also?
comment:10 Changed 10 years ago by
 Reviewers set to PatchBot
 Status changed from needs_review to needs_work
 Work issues set to doctest failure
A doctest fails on 5.0.beta7:
sage t force_lib devel/sage12630/sage/modules/quiver_module.py ********************************************************************** File "/storage/masiao/sage5.0.beta7patchbot/devel/sage12630/sage/modules/quiver_module.py", line 2235: sage: y Expected: b + a Got: a + b **********************************************************************
It looks pretty harmless, but please check it out anyway.
comment:11 Changed 10 years ago by
 Reviewers PatchBot deleted
 Status changed from needs_work to needs_review
 Work issues doctest failure deleted
I added comparisons to the QuiverPath? class and CombinatorialFreeModuleElement? should use should now use those comparisons to determine the order that monomials are printed in. I think previously the order was based on the id of the elements which explains why the patchbot could be getting different output then I was.
comment:12 Changed 10 years ago by
 Status changed from needs_review to needs_work
There is one error in the tests, that has to be corrected, see the bot report.
Please also remove all trailing whitespaces (there seems to be many..)
comment:14 Changed 10 years ago by
Some trivial comments again :
 the bot is not quite happy about the first line of the description : maybe it is better to write "trac #12630" than "trac12630"
 there is still one failing doctest, that needs to be corrected (easy)
Changed 10 years ago by
comment:15 Changed 10 years ago by
The commit message is changed and I think I fixed the bug. I say I think because all tests pass on my machine, but I did find a spot where I converted a set to a list without sorting so I think that's what's causing the difference between my machine and the patchbot.
comment:16 Changed 10 years ago by
Is the patch really so big that trac can not show it in html but only offers to download it?
Anyway, just to make sure that we are talking about the same: When you say "I did find a spot where I converted a set to a list without sorting", do you mean "a spot in a doctest", or "a spot somewhere in the innards of my code"? Because only the first would matter here.
comment:17 followup: ↓ 18 Changed 10 years ago by
Innards of my code (line 1047). Why would only the first matter?
comment:18 in reply to: ↑ 17 Changed 10 years ago by
Replying to JStarx:
Innards of my code (line 1047). Why would only the first matter?
Because I thought that the failing doctest was of the kind "display a set or dict that is returned by some method". In that case, the only problem would be a nonunique string representation.
But now I was looking at the actual error the patchbot complained about, and I see that the error went beyond that. If I understand correctly, you have a set, and transform it into a tuple in order to use it in a cache key, and then you display the cache key in one test, right?
Then you are right that the innards ought to be changed, because if you used nonordered tuples for a cache key then the cache was broken.
Note that there is an immutable version of sets, called "frozenset". It can be used in cache keys! It is faster to compare two frozensets than to have two tuples, one of them sorted, sort the second tuple, and compare then:
sage: S = frozenset(randint(1,10000) for _ in range(1000)) sage: T = deepcopy(S) sage: %timeit S==T 625 loops, best of 3: 33.8 µs per loop sage: S2 = tuple(S) sage: T2 = sorted(tuple(S)) sage: T2==S2 False sage: sorted(S2)==T2 True sage: %timeit sorted(S2)==T2 625 loops, best of 3: 312 µs per loop
Hence, if the cache access is time critical, then you could consider to use frozenset (which would mean to be careful in the doctest, because again the doctest would test against the nonunique string representation of the cache key). But if time is no problem, then using sorted tuples in the cache keys is fine.
comment:19 Changed 10 years ago by
I don't think that code is going to end up being time critical, but that's definitely useful information for the future, I didn't know about frozensets.
Well, looks like patchbot balked due to server issues.
comment:20 Changed 10 years ago by
Ok, now there is at least one try on which all tests passed for the patchbot. The subsequent fail is again a server issue and not a patch issue, so I conclude that the bug is fixed.
comment:21 Changed 10 years ago by
Hello everyone,
I just want to point out that development of this patch is continuing on the sagecombinat queue. I put this patch up on the queue as well as the recent code that Jim wrote to interface with QPA. The patches are named (subject to change, of course):
 12630_quivers.patch
 qpa_interfacefs.patch
 12630_quivers_reviewfs.patch
Some work is needed to merge these two patches; the idea being that one should delegate anything that Sage can't do to QPA. So some reorganization and categorification of the code is necessary. I started this with my review patch.
JStarx has done an incredible amount of great work with these two patches and we really should get these into Sage. Thank you, JStarx!
Franco
comment:22 Changed 10 years ago by
 Cc gmoose05 added
Hi all,
I just learned about this code this past week at Sage Days 40, and also wanted to let JStarx know it is much appreciated! I will be working with Christian Stump to discuss how to deal with the two related notions of quivers. (Trac Tickets 10527 and 10538) This was also discussed with Franco and others this past week.
Gregg
comment:23 Changed 9 years ago by
Here is a new patch, where all tests pass on 5.6.
apply trac_12630_quivers_v2.patch
comment:24 Changed 9 years ago by
apply trac_12630_quivers_v2.patch
comment:25 Changed 9 years ago by
 Cc d.rupel@… added
comment:26 Changed 9 years ago by
Dear Frederic,
Thank you for updating this patch. I had a quick question. Was the main change a rebase so that this applies on Sage 5.6 or were there other changes that we should be aware of?
Also, I should mention that as of Sage 5.6, ticket #10538 has been merged in that handles the ClusterQuiver? class. This class is "Quivers" for those users interested in cluster algebra methods. We decided to change this from the previous "Quiver" because of the name conflict with this patch. So now the two classes should play nicely just fine and on the combinat queue and in Sage (once this is merged) both classes should be able to be imported.
In the future, it probably would make sense to have methods allowing the user to go from a ClusterQuiver? to a Quiver or viceversa.
Gregg
P.S. By the way, I will be at Sage Days at ICERM next week, and in case any developers would like to discuss this further there, I'd be more than happy.
comment:27 Changed 9 years ago by
I have only made a very minor change, such that all tests pass again.
It consists of replacing a test "if not(xx)" by a test "if xx=None or xx=False"
This test was checking the existence of a coercion.
This was failing because of #9016: "make morphisms hashable", which was introduced in 5.6.beta1
comment:28 Changed 9 years ago by
Hello,
There is a problem here, found by pyflakes:
sage/modules/quiver_module.py:6655: local variable 'H' is assigned to but never used
Changed 9 years ago by
comment:29 Changed 9 years ago by
new patch
 with correction of a small problem in the doc formatting
 with unused local variable assignement being commented
comment:30 Changed 9 years ago by
for the bot:
apply trac_12630_quivers_v2.patch
comment:31 Changed 9 years ago by
In the past few weeks (or even months) I have been a bit too busy with other things. So, I'm sorry for my silence.
Let me try to summarise what your code does (correct me if I am wrong) and ask my questions on it, followed by a summary of what I soon need for my project. Then I suggest a code structure that might be useful (but is perhaps biased, as it is influenced from my project). Hopefully we can then make a plan how to avoid duplication of work.
What the code provides
 a
QuiverFactory
, that returns immutable quivers (a new subclass ofDiGraph
) and uses caching. The factory refuses to create quivers with loops.  algebras of acyclic quivers (thus, finite dimensional) and their elements; no quotient algebras.
 representation of acyclic quivers.
 a class
QuiverPath
, that is aUniqueRepresentation
and defines multiplication and stuff, but does not implement the elements of anything.  various classes that together implement representation of quivers, homsets etc.
The code is entirely in Python, so, does likely not address speed. Having quotients of acyclic quiver algebras is considered phase 2, having quotients of general quivers is considered phase 3. It is stated that most of the quiver code would work with cycles, only the algebras would need significant changes.
Questions on your code
 You state that most of the code would work with cyclic quivers. So, why do you require acyclicity everywhere? Why don't you just provide a (cached) method
is_acyclic
that is called when you really need acylicity, raising an error if there are cycles?  What is the rôle of
QuiverPath
? It is not inheriting from any algebraic base class, and is not even the element of anything. I'd rather expect that aQuiverPath
is element of aQuiver
.  Why do you use
UniqueRepresentation
onQuiverPath
? Assume that you have two quivers, and assume they are labelled in such a way that both quivers contain a path that starts at vertex 1 and ends at vertex 2 with edge sequence a, b, c, d. Would you really say that these two paths, that belong to totally different quivers, are identical?
What I need soon
I try to provide an efficient implementation of my noncommutative version of the F5 algorithm for modules over basic algebras (hence, modules over finite dimensional quotients of quiver algebras). The background is that the F5 algorithm (in contrast to other Gröbner basis algorithms) would also allow to compute a minimal generating set for the module (actually: Loewy layers of the module), provided that a negative degree monomial ordering is used. The quivers I'm working with will typically contain cycles.
Hence, I need
 Quivers. Would be good to have a unique representation and immutability. Must allow cycles.
 The algebraic structure formed by the paths in a quiver, subject to concatenation of paths. How to call it? Florent suggests "monoidoid", I suggest "multimonoid". In any case, it is an associative magma. It might be possible to identify the quiver with this algebraic structure; hence, a quiver would not just be a digraph, but would also inherit from some algebraic base class and would belong to the category of associative magmas. Of course I want elements of this algebraic structure.
 I need to be able to choose a monomial ordering on the paths (i.e., compatible with concatenation of paths). It must be possible to choose an ordering that first compares paths by negative length.
 Quiver algebras, i.e., the algebra generated by the aforementioned associative magma that is given by the paths in a quiver, with a monomial ordering inherited from the ordering of paths. I guess that some generic (and already existing!) code would just work.
 Finite dimensional quotients of quiver algebras, and their elements.
 Modules over finite dimensional quotients of quiver algebras. Note that modules over noncommutative rings are currently not implemented.
My speed requirements
The following operations should be super fast:
In the quiver (considered as an associative magma)
 concatenation of paths
 comparison of paths
 hashing of paths
 test whether a given path w starts with a given path v
Speed in the quiver algebra is not essential (hence, I could really live with slow generic code here). However, multiplication in the finite dimensional path algebra quotients should be very fast.
Suggested code structure
 Quivers are not just finite digraphs, but they should IMHO be identified with the associative magma given by path concatenation. Hence, the base class
Quiver_generic
should use a unique factory and inherit fromDiGraph
(this is what you do) and should inherit from Parent, being initialised in the categoryAssociativeMagmas()
(create this category, if it does not exist already). QuiverPath
should use some algebraic base class and should be used to construct the element class of a quiver.QuiverPath
should be cythoned. I have some experimental code, that unfortunately is spread over different machines. Approaches that I tested: Encode a path as an integer (if the quiver has n arrows then you read the integer as an nadic number, and the sequence of digits yields the sequence of arrows in the path
 Encode a path as
*unsigned char
. Hence, you have a list of at most 255 arrows of your quiver, and a sequence of bytes corresponds to a sequence of arrows.  Same as the previous, but use a dense representation: If you have less arrows, then squeeze several arrows into one byte. By consequence, you need less memory.
 Number the arrows locally. Hence, if you are at a certain vertex, then your numbering takes into account only the outgoing arrows that start at this vertex. Hence, if you use
*unsigned char
, then you can work with quivers that may have much more than 255 arrows, as long as each vertex has not more than 255 outgoing arrows.  Same as the previous, but use a dense representation.
It seems to be that the last approach was best for my applications, but I really need to test again, as the code rotted for a couple of months.
 We could use (existing?) general code for obtaining the quiver algebra of a general quiver, and use your code if the quiver happens to be acyclic.
 I have experimental code (rotting since months) for finite dimensional quotients of quiver algebras. Multiplication in the quotient is implemented by matrix multiplication, and a vector space basis of the algebra quotient is given by those paths that are not leading monomial of a quotient relation.
Plans to combine work
It seems that our projects intersect only in one point: We use quivers. You would proceed with representations of acyclic quivers (which is not in my focus), while I would proceed with finite dimensional quotients of quiver algebras (which is not in your focus).
But we could combine forces in the implementation of quivers. Do you think it would work for you that your QuiverFactory
is modified such that it also allows to create quivers with cycles? Would it work for you that Quiver_generic
inherits from both DiGraph
and Parent
and is initialised as an associative magma, using QuiverPath
as element class? Would it work for you that QuiverPath
is cythoned, using whatever dense representation as described above, with comparison by negative length? I think your code concerning representations for the special case of acyclic quivers would still work.
In any case, I should try to reconstruct my experimental code...
comment:32 Changed 9 years ago by
From the documentation of the patch:
9 A Quiver is a directed graph used for representation theory. In Sage a Quiver 10 is different from a directed graph in the following ways: 11 12  The vertices of a DiGraph are arbitrary sage objects, but the vertices of a 13 Quiver must be labeled by integers. 14 15  DiGraphs can have cycles (paths that start and end at the same vertex) and 16 even loops (edges whose initial and terminal vertices are equal). In this 17 implementation a Quiver must be acyclic (and can not have loops). 18 19  The edges of a DiGraph are labeled with arbitrary sage objects or None if no 20 label is specified. Each edge of a Quiver must be labeled with a nonempty 21 string. The label cannot begin with 'e_' or contain '*' and distinct edges 22 must have distinct labels. 23 24  DiGraphs do not have a unique representation in Sage; Quivers do.
All these properties could easily be enforced by using a UniqueFactory
that returns plain immutable digraphs. Given the above specification, I really don't see the need to create Quiver_generic
as a subclass of DiGraph
.
comment:33 followup: ↓ 34 Changed 9 years ago by
I am both puzzled and impressed: Aren't modules in Sage currently only defined over commutative algebras? But then, why does it work to let QuiverRep_generic
inherit from sage.modules.module.Module?
Concerning the location of the class definitions, I think that one should not squeeze all code into sage.modules.quiver_module: This file should only contain QuiverRep_generic
and related definitions, but not Quiver_generic
, QuiverPath
or QuiverAlgebra
:
 If one thinks that a quiver is a graph, then it should be defined somewhere in sage.graphs. If one thinks that a quiver is an associative magma that also happens to be a graph (I'd prefer this point of view!), then one might create a new section sage.magmas for it, or simply put it into sage.monoids.
 A quiver algebra is an algebra. Hence, it should be put into sage.algebras.
 If one thinks of
QuiverPath
as an element of a quivertheassociativemagma, then it should be put into the same section (sage.magmas or sage.monoids) and used as element_class of quivertheassociativemagma; but even in this case,QuiverPath
and quivertheassociativemagma should be defined in different files, so that it will later be easier to changeQuiverPath
into optimized Cython code.
IMHO, the code will be much easier to maintain when it was divided into smaller parts distributed into appropriate sections of Sage.
comment:34 in reply to: ↑ 33 Changed 9 years ago by
Replying to SimonKing:
Concerning the location of the class definitions, I think that one should not squeeze all code into sage.modules.quiver_module: This file should only contain
QuiverRep_generic
and related definitions, but notQuiver_generic
,QuiverPath
orQuiverAlgebra
:
I still think that breaking the code up into smaller portions would help. But meanwhile I think that my first suggestion (distribute the code over sage.algebras, sage.magmas, sage.modules and so on) is bad.
Why not distribute the code onto several files, but in one new section sage.quivers? I could imagine sage.quivers.factory (returning a unique digraph), sage.quivers.paths (paths with concatenation, eventually written in Cython), sage.quivers.magma (the parent for the aforementioned paths), sage.quivers.representation (modules for acyclic quivers), sage.quivers.algebra (path algebras, not necessarily acyclic), and later modules for finitedimensional quotient algebras, their elements and modules.
Would you mind if I provide a patch that changes the code accordingly?
comment:35 Changed 9 years ago by
I am now in the process of splitting the code up and turn Quiver_generic
into a parent structure whose elements are instances of QuiverPath
. After all, you do want that "path in quiver" may return True.
I noticed one oddity in the UniqueFactory
of Quiver: There is a digraph temporarily created, just to read off the list of vertices and edges for a unique key. And in the end, another digraph is created, namely the quiver itself (which inherits from DiGraph
) Couldn't the unique key be obtained directly, at the same time checking sanity of the input (you require specific labels)?
comment:36 Changed 9 years ago by
Quiver_generic.__init__
provides a lot of different arguments, but it seems that they can't be used with the QuiverFactory
. I'll try to make the factory more transparent with respect to keyword arguments.
comment:37 Changed 9 years ago by
Quiver_generic.__init__
provides a lot of different arguments, but it seems that they can't be used with the QuiverFactory
. I'll try to make the factory more transparent with respect to keyword arguments.
It is nice that calling certain methods of DiGraph
results in an attribute error. But it would be even nicer if one would obtain the attribute error before calling the method. This is how it could be achieved:
sage: from sage.graphs.digraph import DiGraph sage: class C(DiGraph): ....: @property ....: def _forbidden_attribute(self): ....: raise AttributeError ....: add_cycle = _forbidden_attribute ....: add_edge = _forbidden_attribute ....: sage: c = C() sage: c.add_<TAB> # tab completion of forbidden attributes works c.add_cycle c.add_edge c.add_edges c.add_path c.add_vertex c.add_vertices # Note that the following is c.add_cycle, not c.add_cycle() sage: c.add_cycle  AttributeError Traceback (most recent call last) <ipythoninput782cae30af75f> in <module>() > 1 c.add_cycle <ipythoninput52839f68577a9> in _forbidden_attribute(self) 2 @property 3 def _forbidden_attribute(self): > 4 raise AttributeError 5 add_cycle = _forbidden_attribute 6 add_edge = _forbidden_attribute AttributeError: sage: hasattr(c, 'add_cycle') False sage: hasattr(c, 'add_edge') False
comment:38 Changed 9 years ago by
I am now experimenting with the following setting:
 I suggest to let Quiver inherit from
UniqueRepresentation
,DiGraph
andParent
.  In your
UniqueFactory
, you create a key for caching by creating aDiGraph
and asking it for the (sorted) lists of vertices and edges. I suggest to do the same in__classcall__
, but with one additional twist: After all, what we want to return is aDiGraph
(namely a quiver). So, we create a new Quiver instance Q, initialise Q as aDiGraph
and obtain from it the key. If it turns out that this key has already been used in the cache, then we return the cached instance and drop Q.
 Otherwise, we complete the initialisation of Q (which essentially means calling Parent.init), put it into the cache, and return it.
In that way, one can use all arguments that are available for digraphs. For example, one could create two quivers with essentially the same edges, but using different graph backends.
Using @property as I suggested in my previous post would not work, because we need the mutation methods while we initialise Q as a DiGraph
.
comment:39 Changed 9 years ago by
 Dependencies changed from #12412, #12413 to #12412, #12413, #14535
 Status changed from needs_review to needs_work
 Work issues set to Split into different modules. Use parents and elements.
I suggest to add #14535 as a dependency. It allows to create immutable graphs.
If I understood correctly, sagecombinatdevel agrees with the following plan:
 There is no mathematical difference between a quiver and a digraph. Immutable graphs are provided by #14535. Hence, for now, there seems to be no need for a separate subclass "Quiver" of "DiGraph?". But of course, we could have a factory, that returns immutable digraphs after checking that all labels are as we want them.
 How shall we call the algebraic structure formed by the paths in a quiver?
PathMonoid
?PathMagma
?QuiverMonoid
?QuiverMagma
? All the algebraic stuff (representations, path algebra, and also list of quiver paths in contrast to list of paths as a digraph) should be accessible from there. Methods like "is_sink" should be implemented onDiGraph
.  In contrast to Jim's code,
QuiverPath
should be an element, namely an element of the aforementioned algebraic structure.  We should allow directed cycles and loops where possible. We can currently only have quiver representations for acyclic quivers. But there is no reason to restrict
QuiverMonoid
andQuiverAlgebra
to the acyclic case.  "
QuiverMonoid
" should be a unique parent. I suggest usingUniqueRepresentation
, the key ultimately being an immutable digraph. A custom__classcall__
method could accept a broader range of arguments, that could then be turned into an immutable digraph used as key.  A
QuiverMonoid
M is not aDiGraph
. Of course, it can return the underlying quiver byM.quiver()
(which could actually be identical with the graph used as a key when creating M), and M is uniquely determined byM.quiver()
.
comment:40 followup: ↓ 41 Changed 9 years ago by
I think the correct name for the "algebraic structure" containing the paths is "the free category generated by a quiver".
So maybe a good name can be FreeCategory? or FreeSmallCategory? ?
comment:41 in reply to: ↑ 40 Changed 9 years ago by
Replying to chapoton:
I think the correct name for the "algebraic structure" containing the paths is "the free category generated by a quiver".
So maybe a good name can be FreeCategory? or FreeSmallCategory? ?
True, mathematically. Do you think that the tobecreated class for this algebraic structure should be implemented as a Category
, i.e., inherit from Category
, with objects corresponding to the vertices of the quiver, and homsets corresponding to the arrows? Or should it just be called FreeSmallCategory
?
comment:42 Changed 9 years ago by
 Dependencies changed from #12412, #12413, #14535 to #12412, #12413
It seems that inheriting from both Parent and Category would mean to ask for trouble (e.g., if F is the free small category of a quiver, then F.element_class of Ftheparent would be used for the paths in F, while F.element_class of Fthecategory would be used for the elements of F's objects, i.e., of its vertices). Moreover, providing a general framework for immutable graphs means "opening a can of worms".
By the latter, I start to understand the motivation for introducing a separate class for "quiverthegraph": It is mainly a digraph, but it is made immutable by overriding certain mutating methods. At the end of the day, it would be better to keep the class Quiver
, but perhaps using UniqueRepresentation
(because this yields a fast hash) rather than a UniqueFactory
.
Still, I think the code should be split up into smaller pieces, and there should be a proper parent for "quivertheassociativemagma", called FreeSmallCategory
(which for now should just be a Parent, but not inherit from Category) and turning QuiverPath
into a proper element (and I still don't see why it should be a UniqueRepresentation
).
I removed the dependency on "immutable graphs" that I had introduced.
comment:43 Changed 9 years ago by
It seems that QuiverAlgebra
may be superseded by Nicolas Thiéry's functorial construction patch. However, I think it would be better to not make the functorial construction patch a dependency, and Nicolas seems to agree.
comment:44 Changed 9 years ago by
+1 for splitting up this patch bomb.
Using a separate directory for quiver stuff would be great, too. I would prefer singular sage.quiver.representation
over plural sage.quivers.representations
comment:45 Changed 9 years ago by
I am currently working on a patch according to the comments above. It has
algebra.py free_small_category.py homspace.py __init__.py morphism.py paths.py quiver.py representation.py
in sage/quivers.
quiver would be for the "immobilised" version of digraph, paths for the element class of the parent structure that is defined in free_small_category, and I suppose you correctly guess the content of homspace, algebra, morphism and representation.
Is this OK?
comment:46 followup: ↓ 47 Changed 9 years ago by
I'm hoping that everything so far is allowing loops, since that is the case of interest for me ;)
I would still prefer sage.quiver
over sage.quivers
since sage.quivers.algebra
makes me cry a little bit inside. But I do realize that the Sage library is totally inconsistent in the use of plural vs. singular, so its your call.
comment:47 in reply to: ↑ 46 Changed 9 years ago by
Replying to vbraun:
I'm hoping that everything so far is allowing loops, since that is the case of interest for me ;)
Same here.
I would still prefer
sage.quiver
oversage.quivers
sincesage.quivers.algebra
makes me cry a little bit inside. But I do realize that the Sage library is totally inconsistent in the use of plural vs. singular, so its your call.
I thought plural is good, because we have sage.algebras, sage.modules, sage.graphs, sage.categories, sage.rings, etc.
comment:48 Changed 9 years ago by
There is also sage.matrix
, sage.geometry
, sage.plot,
sage.structure`, etc. As I said, totally inconsistent.
comment:49 Changed 9 years ago by
 Description modified (diff)
 Keywords days49 added
Even though my patch isn't finished, I'll post it, so that we can discuss about it at SD49. Many doctests currently fail.
Apply trac_12630_quivers_v2.patch quiver_distributed_code.patch
comment:50 Changed 9 years ago by
Here are the current failures:
sage t sage/quivers/paths.py # 91 doctests failed sage t sage/quivers/representation.py # 450 doctests failed sage t sage/quivers/homspace.py # 127 doctests failed sage t sage/quivers/free_small_category.py # ValueError in doctesting framework sage t sage/quivers/quiver.py # 118 doctests failed sage t sage/quivers/algebra.py # 78 doctests failed sage t sage/quivers/morphism.py # 290 doctests failed
Scary. But I guess most of them are due to change of syntax. In the original code, one was able to create a paths without reference to a quiver, and then multiply them. In the new code, one needs to have a quiver, get the associated free small category, and construct elements of it. I think this is cleaner. And after all, in real applications, we have a quiver.
comment:51 Changed 9 years ago by
 Cc mguaypaq added
comment:52 followup: ↓ 57 Changed 9 years ago by
 Cc nthiery added
Some comments from a discussion with Nicolas:
 Currently, we say
FreeSmallCategory
. Isn't it simply a semigroup?  If it is a semigroup (in particular, if it is declared in the category of semigroups, and not in the category of magmas, it might be possible that we can inherit most of the functionality that is now in
QuiverAlgebra
. Namely, there already isSemigroups.Algebras
.  Slight problem: Currently, the invalid path is not mentioned in the list of elements of the free small category / semigroup of a quiver, but it is recognised as an element. This is odd, but on the other hand, when we add it to the list of elements, then the dimension of the algebra will be one more.
comment:53 Changed 9 years ago by
 Cc virmaux added
comment:54 Changed 9 years ago by
I have updated the second patch. It is still not finished, but it has improved:
sage t sage/quivers/paths.py # 91 doctests failed sage t sage/quivers/representation.py # 450 doctests failed sage t sage/quivers/homspace.py # 127 doctests failed sage t sage/quivers/quiver.py # 117 doctests failed sage t sage/quivers/morphism.py # 290 doctests failed
comment:55 Changed 9 years ago by
I updated the second patch again. sage/quivers/paths.py is now fine. Thus we have:
sage t sage/quivers/representation.py # 450 doctests failed sage t sage/quivers/homspace.py # 127 doctests failed sage t sage/quivers/quiver.py # 117 doctests failed sage t sage/quivers/morphism.py # 290 doctests failed
comment:56 Changed 9 years ago by
Currently, if a quiver Q1 is a subdigraph (not necessarily induced) of a quiver Q2, then any element of Q1.free_small_category()
can be converted into Q2.free_small_category()
. I think it makes sense to say that this conversion actually is a coercion.
comment:57 in reply to: ↑ 52 ; followup: ↓ 58 Changed 9 years ago by
Replying to SimonKing:
Some comments from a discussion with Nicolas:
 Currently, we say
FreeSmallCategory
. Isn't it simply a semigroup?
If you add the zero element to your set of paths.
 If it is a semigroup (in particular, if it is declared in the category of semigroups, and not in the category of magmas, it might be possible that we can inherit most of the functionality that is now in
QuiverAlgebra
. Namely, there already isSemigroups.Algebras
. Slight problem: Currently, the invalid path is not mentioned in the list of elements of the free small category / semigroup of a quiver, but it is recognised as an element. This is odd, but on the other hand, when we add it to the list of elements, then the dimension of the algebra will be one more.
In this case, one wants the "contracted" semigroup algebra (where the 0 of the algebra is identified with the zero of the semigroup).
PS. I don't have the time right now to follow everything that you are doing, but I am really interested in this and hope to have a closer look sometime soon.
comment:58 in reply to: ↑ 57 ; followup: ↓ 60 Changed 9 years ago by
Replying to saliola:
Replying to SimonKing:
Some comments from a discussion with Nicolas:
 Currently, we say
FreeSmallCategory
. Isn't it simply a semigroup?If you add the zero element to your set of paths.
In this case, one wants the "contracted" semigroup algebra (where the 0 of the algebra is identified with the zero of the semigroup).
How to organise work?
I'd suggest that I continue working on the second patch, until stuff works with the current implementation of path algebras. And in a third patch, one could then (try to) do everything with contracted semigroup algebras.
Other suggestion?
comment:59 Changed 9 years ago by
For the next snapshot of the second patch, we have
sage t sage/quivers/representation.py # 450 doctests failed sage t sage/quivers/homspace.py # 127 doctests failed sage t sage/quivers/quiver.py # 41 doctests failed sage t sage/quivers/morphism.py # 290 doctests failed
It implements coercion (in the case of subdigraphs) and modifies some code in sage.quivers.representation.py to make things work. I guess the 450 doctest failures now mainly come from the wrong import location.
comment:60 in reply to: ↑ 58 Changed 9 years ago by
Replying to SimonKing:
Replying to saliola:
Replying to SimonKing:
Some comments from a discussion with Nicolas:
 Currently, we say
FreeSmallCategory
. Isn't it simply a semigroup?If you add the zero element to your set of paths.
In this case, one wants the "contracted" semigroup algebra (where the 0 of the algebra is identified with the zero of the semigroup).
How to organise work?
I'd suggest that I continue working on the second patch, until stuff works with the current implementation of path algebras. And in a third patch, one could then (try to) do everything with contracted semigroup algebras.
Agreed. I don't know whether there is any support for contracted semigroup algebras at this point.
comment:61 Changed 9 years ago by
I now come to morphisms. Potential problem: The signature of QuiverRepHom
is (domain, codomain, data). To be consistent with the signature of other morphisms, should we change this into (Homspace, data)? By Homspace, I mean the space of morphisms from domain to codomain, which currently is constructed internally in the init method.
Or should we not bother about the signature?
comment:62 followup: ↓ 63 Changed 9 years ago by
+1 about (Homspace, data) as signature for consistency with other hom spaces.
As far as I know, there is no support for contracted semigroup algebras at this point.
Cheers,
Nicolas
comment:63 in reply to: ↑ 62 Changed 9 years ago by
Replying to nthiery:
+1 about (Homspace, data) as signature for consistency with other hom spaces.
OK. And then, I have to recall (or: to be reminded) how one is supposed to implement a homspace. Perhaps it will not be needed to have a specialised homset class here? But how does one make sure that the generic homset creates a morphism that belongs to a particular morphism class?
comment:64 Changed 9 years ago by
 Work issues changed from Split into different modules. Use parents and elements. to Fix doctests. Use existing infrastructure for homspace/morphism.
Changed 9 years ago by
comment:65 Changed 9 years ago by
 Description modified (diff)
We've (virmaux and mguaypaq) been working on import statement problems and we fixed most of them.
Now:
sage t homspace.py # 22 doctests failed sage t morphism.py # 28 doctests failed sage t quiver.py # 14 doctests failed sage t representation.py # 91 doctests failed
We created all.py and added it in the global sage/all.py.
comment:66 Changed 9 years ago by
Great! So, you fixed most of the 600 failing tests. Thank you!
For the patchbot:
Apply trac_12630_quivers_v2.patch quiver_distributed_code.patch trac_12630_fix_import_statement.patch
comment:67 Changed 9 years ago by
... which probably means you should add your names to the Author(s) field. We can then perhaps crossreview.
Changed 9 years ago by
comment:68 Changed 9 years ago by
 Description modified (diff)
We've fixed some "typo" errors, most of the tests now pass. There remains a few errors involving:
 _factory_version
 linear_dual
 weird _repr_ in QuiverHomSpaceFactory.create_key
sage t sage/quivers/homspace.py # 3 doctests failed sage t sage/quivers/quiver.py # 1 doctest failed sage t sage/quivers/representation.py # 3 doctests failed
For the patchbot:
Apply trac_12630_quivers_v2.patch quiver_distributed_code.patch trac_12630_fix_import_statement.patch trac_12630_fix_some_errors.patch
comment:69 followup: ↓ 70 Changed 9 years ago by
Nicolas and I believe that it is not a good idea to put everything (in particular: stuff like QuiverRep
) into the global namespace.
It may be a good idea to put Quiver into the global name space, because Quiver is the entrance point for everything else. But if you want to create a QuiverRep
, then you should either create a quiver and then call some method to create QuiverRep
(this is the preferred way), or import QuiverRep
explicitly.
comment:70 in reply to: ↑ 69 Changed 9 years ago by
Replying to SimonKing:
Nicolas and I believe that it is not a good idea to put everything (in particular: stuff like
QuiverRep
) into the global namespace.It may be a good idea to put Quiver into the global name space, because Quiver is the entrance point for everything else. But if you want to create a
QuiverRep
, then you should either create a quiver and then call some method to createQuiverRep
(this is the preferred way), or importQuiverRep
explicitly.
I agree with this. The documentation for Quiver
should then include pointers and examples on the other functions.
comment:71 Changed 9 years ago by
I saw today that Quiver is still using a UniqueFactory
, which, I think, it should not do. It should use UniqueRepresentation
, and actually I thought that I had done the change already in my first patch.
Pro: With UniqueRepresentation
, it has much faster comparison and hash.
Con: If you want to compare a quiver Q and a digraph D, you may have D==Q
but Q!=D
. I, for one, would accept this drawback.
I suggest that I will do the transition to UniqueFactory
on top of trac_12630_quivers_v2.patch quiver_distributed_code.patch trac_12630_fix_import_statement.patch trac_12630_fix_some_errors.patch, and we can take care of the last few remaining errors after this change.
comment:72 Changed 9 years ago by
Are you really sure that the patch trac_12630_fix_import_statement.patch applies?
I get
Wende trac_12630_fix_import_statement.patch an Wende Patch auf Datei sage/quivers/representation.py an FEHLSCHLAG von Teilstück #54 in Zeile 1959 1 von 67 Teilstücken sind FEHLGESCHLAGEN  speichere Ausschuss in Datei sage/quivers/representation.py.rej Patch schlug fehl und Fortsetzung unmöglich (versuche v) Patch schlug fehl, Fehlerabschnitte noch im Arbeitsverzeichnis Fehler beim Anwenden. Bitte beheben und trac_12630_fix_import_statement.patch aktualisieren
which is German and means that one part of this patch failed to apply.
For the record, I have now these patches applied (Note: quivers_v2, not quivers)
trac_12630_quivers_v2.patch quiver_distributed_code.patch trac_12630_fix_import_statement.patch
comment:73 Changed 9 years ago by
 Description modified (diff)
 Work issues changed from Fix doctests. Use existing infrastructure for homspace/morphism. to Rebase patches. Use existing infrastructure for Homspase and Morphism.
I have rebased this patch. So, I now work with this:
 trac_12630_quivers_v2.patch
 quiver_distributed_code.patch
 trac12630_fix_import_statement_sk.patch
But then, trac_12630_fix_some_errors.patch fails as well.
comment:74 Changed 9 years ago by
I hope I did not screw it up. Namely, you changed some things that I had changed in my version of quiver_distributed_code. So, perhaps I forgot to post my patch version here? Apologies.
Anyway. I will now try to get all patches clean.
comment:75 Changed 9 years ago by
 Description modified (diff)
 Work issues changed from Rebase patches. Use existing infrastructure for Homspase and Morphism. to Use existing infrastructure for Homspase and Morphism.
To facilitate work, I created a combined patch that collects all our present reworking of Jim's original code. I suggest that we work on top of it. Note that it is helpful for reviewing to have all the small patches around.
So, for now:
Apply trac_12630_quivers_v2.patch 12630_refactor_code.patch
Changed 9 years ago by
comment:76 Changed 9 years ago by
Here are some last corrections from the previous patch. The import statements are a bit cleaner (?) and I fixed some doctest errors. Because it is a little patch, I've merged it with the previous one.
sage t quiver.py # 1 doctest failed
This last one seems to be only a _repr_ problem. The object which is returned looks correct.
comment:77 Changed 9 years ago by
 Description modified (diff)
Please post the little patchfor reviewing.
Moreover, on Trac, one can only replace patches (with the same name) that one has posted oneself. Hence, the name of the patchtobeapplied has changed. So, we now have
Apply trac_12630_quivers_v2.patch 12630_refactor_code.2.patch
Changed 9 years ago by
comment:78 Changed 9 years ago by
Ok, sorry for that. So here is the little patch based on trac_12630_refactor_code.patch
comment:79 Changed 9 years ago by
OK. So, this seems indeed like a harmless change.
My plan is now to replace UniqueFactory
by UniqueRepresentation
, in order to get faster comparison and hash for quivers.
comment:80 Changed 9 years ago by
It may be that the last remaining doctest is just a problem with _repr_. However, the returned representation really looks fishy, it looks like the quiver involved is broken. So, let's investigate what is happening.
Note that I think the following test should be rewritten anyway. The morphism f should be constructed via f = P2.hom({1:[1, 1], 2:[[1], [1]]}, M2)
or so, since this is generally the preferred way of creating a morphism. Importing and directly calling a class that has a "mutilated" name (QuiverRepHom
) is not what the user is supposed to do. The simple reason is that the user would first need to learn where to import it from. But hom
is a method that the user has very likely seen before in Sage.
sage: Q2 = Quiver({1:{2:['a', 'b']}}) sage: M2 = QuiverRep(QQ, Q2, {1: QQ^2, 2: QQ^1}, {(1, 2, 'a'): [1, 0], (1, 2, 'b'): [0, 1]}) sage: P2 = Q2.P(QQ, 1) sage: from sage.quivers.morphism import QuiverRepHom sage: f = QuiverRepHom(P2, M2, {1:[1, 1], 2:[[1], [1]]}) sage: f.linear_dual() Expect: Homomorphism of representations of Quiver on 2 vertices Got: Homomorphism of representations of Quiver on Reverse of ()
The underlying problem seems to be this:
sage: Q2.reverse() Quiver on Reverse of ()
So, let's have a look at the reverse()
method.
comment:81 Changed 9 years ago by
Another thing we might want to fix:
sage: show(Q2) Traceback (most recent call last): ... /home/simon/SAGE/prerelease/sage5.10.rc1/local/lib/python2.7/sitepackages/sage/graphs/generic_graph.pyc in delete_vertices(self, vertices) 7614 attr_dict.pop(vertex, None) 7615 > 7616 self._boundary = [v for v in self._boundary if v not in vertices] 7617 7618 self._backend.del_vertices(vertices) TypeError: 'NoneType' object is not iterable
comment:82 Changed 9 years ago by
The problem lies in sage.graphs.digraph. It does:
def reverse(self): """ Returns a copy of digraph with edges reversed in direction. EXAMPLES:: sage: D = DiGraph({ 0: [1,2,3], 1: [0,2], 2: [3], 3: [4], 4: [0,5], 5: [1] }) sage: D.reverse() Reverse of (): Digraph on 6 vertices """ H = DiGraph(multiedges=self.allows_multiple_edges(), loops=self.allows_loops()) H.add_vertices(self) H.add_edges( [ (v,u,d) for (u,v,d) in self.edge_iterator() ] ) name = self.name() if name is None: name = '' H.name("Reverse of (%s)"%name) return H
Our digraph has no given name, and thus its reverse gets the name Reverse of ()
.
So, it is not convenient, but I think we should not worry about it.
comment:83 Changed 9 years ago by
The constructor of a quiver construct a Digraph with all the arguments set to None by default. Unfortunately, it seems that boundary cannot be None. If we change the init with boundary=(), the plot function works.
We don't know exactly if this is really portable or not.
Also, note from Mathieu: DiGraph? documentation disagrees with Graph documentation about _boundary=None accepted or not. Also, certainly DiGraphs? constructor should not use a mutable list as a default argument.
comment:84 followup: ↓ 85 Changed 9 years ago by
Here is the modified piece of code:
def __init__(self, data=None, pos=None, loops=True, format=None, boundary=(), weighted=True, implementation='c_graph', sparse=True, vertex_labels=True, name=None, multiedges=True, convert_empty_dict_labels_to_None=False, **kwds):
comment:85 in reply to: ↑ 84 Changed 9 years ago by
Replying to virmaux:
Here is the modified piece of code:
def __init__(self, data=None, pos=None, loops=True, format=None, boundary=(), weighted=True, implementation='c_graph', sparse=True, vertex_labels=True, name=None, multiedges=True, convert_empty_dict_labels_to_None=False, **kwds):
OK. This makes sense.
In order to not duplicate work, I propose that I "refactor the factory" now and directly incorporate the change (boundary=()
) and the fix for the only failing test.
comment:86 Changed 9 years ago by
Cool, apparently I DID already change quiver to use UniqueRepresentation
! So, the code that you showed me this morning has apparently been without my patch. That makes life a lot easier!
comment:87 Changed 9 years ago by
sage.quivers.quiver seems to be (essentially) fine now.
So, the work issue is as stated: "Use existing infrastructure for Homspase and Morphism." And I guess caching of homsets should also be done as with other homsets. Hence, no UniqueFactory
or UniqueRepresentation
here.
comment:88 Changed 9 years ago by
 Work issues changed from Use existing infrastructure for Homspase and Morphism. to Use existing infrastructure for Representation, Homspace and Morphism.
I changed my plan and will now first look at the representations.
comment:89 Changed 9 years ago by
Some random remarks on QuiverRep_generic
:
 My personal preference is to use
UniqueRepresentation
, notUniqueFactory
, but personal preferences may be negotiable. I worry about pickling, since in fact there is noloads(dumps(...))==...
test in the sources, and noTestSuite(...).run()
.
 I don't see why there is a need to provide a
__contains__
method. The default should work, provided that coercion has properly been implemented. There is a_coerce_map_from_
method, that seems to do the right thing.
_Hom_
should not raise an error, when the codomain is not a quiver representation. Instead, it should return somesage.categories.homset.Homset
(orHomsetWithBase
, because we have a base?)
sage.modules.module.Module
has abase_ring
method, and I see no need to overload it.
 For implementing
an_element
, the method_an_element_
should be implemented.
 For a quiver representation
R
,R.an_element()
,R.zero()
andR.gens()
do not return instances ofR.element_class
. So,TestSuite(R)
will complain.
 It seems that
hom()
andHom()
are not needed, since the default implementation would work (since there is_Hom_
implemented).
comment:90 Changed 9 years ago by
Ah! I just saw that the default .Hom()
method would fall back to the default homset, if _Hom_
raises a type error. So, this detail is fine.
But actually, caching of the homspace is done in sage.categories.homset
. So, I see no need to use UniqueFactory
or UniqueRepresentation
for QuiverHomspace
. And of course, QuiverHomspace
should inherit from sage.categories.homset.Homset(WithBasis)
, and not directly from Parent
.
comment:91 Changed 9 years ago by
 Description modified (diff)
I fixed the remaining doctest error, which is just due to a bad way of creating the name of digraphs. I added a "todo" for this issue, which clearly does not belong to this ticket.
It is not "needs review" yet, because I want to make homset stuff use existing infrastructure. However, all tests pass now. Hence, if my attempts concerning homsets won't work, we have at least something that works.
I started with Aladin's patch, but of course I can not replace it on Trac, and hence I went back to the name of my patch, which was the starting point of Aladin's patch. In other words:
Apply trac_12630_quivers_v2.patch trac12630_refactor_code.patch
comment:92 Changed 9 years ago by
Note (to myself): This example is currently quite slow.
sage: Q = Quiver({1:{2:['a', 'b'], 3: ['c', 'd']}, 2:{3:['e']}}) sage: Q.free_module(GF(7)).algebraic_dual()
According to %prun, the get_matrix method is the culprit:
ncalls tottime percall cumtime percall filename:lineno(function) 2480 0.403 0.000 2.216 0.001 morphism.py:629(get_matrix) 4960 0.302 0.000 0.308 0.000 dynamic_class.py:324(dynamic_class_internal) 126644 0.222 0.000 0.222 0.000 {isinstance}
comment:93 Changed 9 years ago by
Solution of the problem: In get_matrix, there is
list(self._vector[startdim:startdim + rows*cols])
If __getitem__
of self._vector
is asked to slice (which is the case here), then it first creates the list and then creates a vector out of a slice of that list (also creating a parent, I guess). And from the resulting vector, we take the list.
It should instead be
self._vector.list()[startdim:startdim + rows*cols]
Then, list()
is called only once, and no temporary slice vector is created.
comment:94 Changed 9 years ago by
 Work issues changed from Use existing infrastructure for Representation, Homspace and Morphism. to Use existing infrastructure for Representation, Homspace and Morphism. Only import "Quiver" in the global namespace, nothing else
Something else: Still, we import QuiverRepElement
and other things into the global namespace. I think this must not be. The elements of a quiver representation in fact belong to a subclass of QuiverRepElement
, namely to the element class of the quiver representation. Hence, the user is supposed to not instantiate QuiverRepElement
directly, simply because it is the wrong class.
comment:95 Changed 9 years ago by
 Description modified (diff)
 Reviewers set to Simon King
 Status changed from needs_work to needs_review
 Work issues Use existing infrastructure for Representation, Homspace and Morphism. Only import "Quiver" in the global namespace, nothing else deleted
I have provided a new patch. To make reviewing easier, I kept it separate. Once the review is done, we can think of folding it, to make it easier for the release manager.
What the new patch does
 To avoid pollution of the global namespace, only Quiver is imported at startup. There is really no need to import
QuiverRep
orQuiverRepHom
. Instead, the user is supposed to first create a quiver Q, and then useR = Q.representation(...)
orR.hom(...)
to create representations and their morphisms. By consequence, there were many trivial fixes for the doctests needed.
 In order to make
R.hom(S)
work with Sage's default infrastructure, it is needed to implement a methodnatural_map()
for the homsetR.Hom(S)
. And this homset should be returned by a methodR._Hom_(S)
. Caching is actually not needed, because this is done insage.categories.homset.Hom
. Hence, TODO: Remove theUniqueFactory
!!
 There is a default
sage.structure.parent.Parent.hom
, and there is no need to overload it. In particular, the hom() method provided by the old patch expected its arguments in the wrong order. The default is: First the data defining the morphism, second the codomain.
 an_element() should be implemented by providing _an_element_().
 There is a default
__contains__
method for parents, and there is usually no need to overload it (instead, one should implement coercions). Hence, I removed some of them. There is still__contains__
forFreeSmallCategory
, because it needs to extend whatDiGraph.__contains__
is doing. TODO: Check whether homspaces could do without the custom__contains__
!
 Speaking of default infrastructure: Elements should be created by either doing arithmetic on the generators of a parent, or by calling the parent with appropriate data, but not by passing these data to the underlying class of the elements (which does not coincide with the element class in many cases). TODO: Try to make
TestSuite()
work.
 Speedup: I have already mentioned above that
list(self._vector[startdim:startdim + rows*cols])
is a lot slower thanself._vector.list()[startdim:startdim + rows*cols]
.
 There is a default
zero
method, that caches the zero of a parent. So, there should be no need to overload it. However, some methods start withself.zero()
and then change it inplace. That's of course not allowed with a cached element, and hence I had to replaceself.zero()
with a noncachedself()
.
I think, in spite of the above TODOs, I put it as "needs review" for now, and wait for your comments. For the record, I give positive review to those parts of the code that I did not change (hence, to most of the code inside of methods, as I was mainly changing the structure of the code base and the semantics of few methods that are important for Sage's infrastructure).
Apply:
trac_12630_quivers_v2.patch trac12630_refactor_code.patch trac12630quiver_representation.patch
comment:96 Changed 9 years ago by
 Status changed from needs_review to needs_work
 Work issues set to Coverage, doctest continuation
The patchbot was quite fast! Some plugins failed:
startupmodules
+New: + sage.quivers + sage.quivers.all + sage.quivers.quiver + sage.quivers.sage
What is sage.quivers.sage??? It is not possible to import sage from sage.quivers. So, I guess this is a problem of the plugin. The other import should be fine. Note that no other modules from sage.quivers are imported during startup, which is one of the aims of my last patch.
coverage
+Full doctests quivers/algebra.py 12 / 12 = 100% +Missing doctests quivers/free_small_category.py 6 / 14 = 42% +Full doctests quivers/homspace.py 18 / 18 = 100% +Full doctests quivers/morphism.py 34 / 34 = 100% +Full doctests quivers/paths.py 13 / 13 = 100% +Missing doctests quivers/quiver.py 24 / 25 = 96% +Full doctests quivers/representation.py 58 / 58 = 100%
I will try to add the missing tests in the third patch
doctest_continuation
+ trac12630_refactor_code.patch:657 + ... counter += 1$ + trac12630_refactor_code.patch:658 + ... print p$ + trac12630_refactor_code.patch:659 + ... if counter==20:$ + trac12630_refactor_code.patch:660 + ... break$
This is in the second patch. I'll try to fix this as well.
comment:97 Changed 9 years ago by
 Status changed from needs_work to needs_review
Now the second and third patch are updated. So, it can be reviewed now, even though I'd still like to take care of the above TODOs.
Apply:
trac_12630_quivers_v2.patch trac12630_refactor_code.patch trac12630quiver_representation.patch
comment:98 Changed 9 years ago by
I am sure that the doctest error found by the patchbot is unrelated with this ticket.
comment:99 Changed 9 years ago by
 Work issues changed from Coverage, doctest continuation to Remove UniqueFactory of Homspace, Homspace.__contains__, make TestSuite work
comment:100 followup: ↓ 101 Changed 9 years ago by
 Status changed from needs_review to needs_work
 Work issues changed from Remove UniqueFactory of Homspace, Homspace.__contains__, make TestSuite work to Make HomSpace inherit from Homset; remove UniqueFactory of Homspace, Homspace.__contains__, make TestSuite work
There is now a different error reported by the patchbot (with identical patches), but both errors seem totally unrelated.
However, there is a more serious problem: There are cases when a morphism is not calling sage.categories.morphism.Morphism.__init__
. And part of the problem: QuiverHomspace
does not inherit from Homset
!!
comment:101 in reply to: ↑ 100 Changed 9 years ago by
Replying to SimonKing:
And part of the problem:
QuiverHomspace
does not inherit fromHomset
!!
But making it inherit means that one needs to overload __call__
. Alas.
comment:102 followup: ↓ 103 Changed 9 years ago by
It might be reasonable for now to overload __call__
, by first trying what is now done in the _element_constructor_
, but using an element_class. And only if this fails, Homset.__call__
should be called.
On the long run, I believe Homset.__call__
should instead obey the rules of Parent.__call__
. Hence, it should be possible to implement creation of morphisms simply by providing an attribute Element
to the homset. But this would be for a different ticket.
comment:103 in reply to: ↑ 102 Changed 9 years ago by
Replying to SimonKing:
It might be reasonable for now to overload
__call__
, by first trying what is now done in the_element_constructor_
, but using an element_class. And only if this fails,Homset.__call__
should be called.
The update of the third patch implements this short term solution.
Still TODO:
 I found that still some tests start with importing Quiver. This is not needed. Quiver, in contrast to everything else of the new stuff, is in the global namespace.
 Get rid of the unique factory
 Now, as element_class is available for the Homspaces, use it! Hence, do not create
QuiverRepHom
, but always create homomorphisms by means of the element_class.
comment:104 Changed 9 years ago by
 Status changed from needs_work to needs_review
 Work issues changed from Make HomSpace inherit from Homset; remove UniqueFactory of Homspace, Homspace.__contains__, make TestSuite work to Add a TestSuite test
Mainly done. The only missing bit is a TestSuite
test.
Apply:
trac_12630_quivers_v2.patch trac12630_refactor_code.patch trac12630quiver_representation.patch
comment:105 Changed 9 years ago by
 Status changed from needs_review to needs_work
Aha, it would really good idea to make the test suites work. For example, quiver representations can't be pickled...
sage: Q = Quiver({1:{2:['a', 'b']}}) sage: S = Q.S(QQ, 2) sage: loads(dumps(S))  AttributeError Traceback (most recent call last) <ipythoninput104ebac6f179dc> in <module>() > 1 loads(dumps(S)) /home/simon/SAGE/prerelease/sage5.11.beta3/local/lib/python2.7/sitepackages/sage/structure/sage_object.so in sage.structure.sage_object.loads (sage/structure/sage_object.c:11044)() /home/simon/SAGE/prerelease/sage5.11.beta3/local/lib/python2.7/sitepackages/sage/structure/factory.so in sage.structure.factory.lookup_global (sage/structure/factory.c:3123)() AttributeError: ("'module' object has no attribute 'QuiverRep'", <builtin function lookup_global>, ('QuiverRep',))
comment:106 Changed 9 years ago by
OK, this problem is easy to fix. Before, QuiverRep
was in the global name space. Now it isn't, hence, one needs QuiverRep = QuiverRepFactory("sage.quivers.representation.QuiverRep")
.
The next bit that makes TestSuite
of a quiver representation homset H fail is the fact that H.zero()
returns the wrong thing.
comment:107 Changed 9 years ago by
The next problem uncovered by test suites is this:
sage: Q = Quiver({1:{2:['a']}, 2:{3:['b']}}) sage: A = Q.algebra(GF(7)) age: A.one() e_1 + e_2 + e_3 sage: A.an_element() invalid path + e_1 + 2*e_2 + 3*e_3 sage: A.an_element()*A.one() e_1 + 2*e_2 + 3*e_3 sage: A.an_element()*A.one() == A.an_element() False
So, that's very bad. Apparently, an invalid path summand vanishes when multiplying, but the equality test does take them into account.
comment:108 Changed 9 years ago by
And here is the problem:
def product_on_basis(self, p1, p2): FSC = self._free_small_category p = FSC(p1)*FSC(p2) if p: return self.basis()[p] else: return self.zero()
If p is the invalid path, then it evaluates to False, but still self.basis()[p]!=self.zero()
. I think this is a bug. If one decides to distinguish the invalid path from zero, then one must accept the consequences also in multiplying elements.
comment:109 Changed 9 years ago by
Alternatively, one could decide that the invalid path is mapped to zero, which could be done by modifying sage.quivers.algebra.QuiverAlgebra.Element.__init__
.
comment:110 Changed 9 years ago by
 Status changed from needs_work to needs_review
 Work issues Add a TestSuite test deleted
I updated the last patch, and now, from my perspective, it is good to go! Hence, now it really needs review...
Changes with respect to last time:
 The invalid path now evaluates as zero in the path algebra. This was the last obstruction for
TestSuite
, and now there is aTestSuite
test for all parents (free small category, algebra, representation, homspace) involved in this patch. This was done by overloading the_monomial()
method of an algebra.  I added a
cardinality()
method for free small categories, such that the dimension of a path algebra A becomes available. Unfortunately,list(A.basis())
would not work, becauseA.basis()
(which is a free small category) is not initialised as an object ofFiniteEnumeratedsets()
perhaps it should be. I'll check how difficult this would be.
comment:111 Changed 9 years ago by
 Status changed from needs_review to needs_work
The finite/infinite enumerated set bit is easy. And I would like to add a coercion from the free small category to the quiver algebra.
comment:112 Changed 9 years ago by
 Work issues set to coercion free small category > algebra. Methods gen, gens, ngens
It would also be nice to have a gen() and gens() and ngens() method for both the free small category and the path algebras.
comment:113 Changed 9 years ago by
 Work issues changed from coercion free small category > algebra. Methods gen, gens, ngens to Quivers with loops, coercion free small category > algebra. Methods gen, gens, ngens
There is a worse problem revealed by the test suites (yes, the category framework is GREAT!!!).
Namely, the original code did assume acyclic quivers. But now, we want to support cycles (including loops) as much as possible. However, when a path is created, then it was still the case that each edge starting and ending at the same vertex was deleted when multiplying paths.
Changed 9 years ago by
Sage infrastructure for Quiver representations, their homspaces and morphisms
comment:114 Changed 9 years ago by
 Status changed from needs_work to needs_review
 Work issues Quivers with loops, coercion free small category > algebra. Methods gen, gens, ngens deleted
The updated patch does this:
 The free small category is now initialised in the category of enumerated sets, either finite (if acyclic) or infinite.
 It provides test suites for all involved parents. Being in the category of enumerated sets,
self.some_elements()
is now a lot longer, and hence some tests in the test suite from the category of monoids resp. of magmas used to fail. The underlying bugs are fixed with the new patch version.
 Now
_assign_variables
is explicitly of implicitly called for free small category and algebras. Henceself.variable_names()
is available. Other typically needed methods (gen, gens, ngens) were added, and I think it is useful to have methods returning only the arrows resp. only the idempotents of the quiver free small category or algebra.
 Now, the free small category coerces into the quiver algebra. Of course, this is demonstrated in tests.
I am happy with the implemented features, and thus I'd appreciate a final review!
Apply:
trac_12630_quivers_v2.patch trac12630_refactor_code.patch trac12630quiver_representation.patch
comment:115 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:116 Changed 8 years ago by
Why is the patchbot trying to apply patches from the dependencies, even though they are closed since ages?
20130821 23:04:31 +0100 Sage Patchbot 1.3.1 /mnt/storage2TB/patchbot/Sage/sage5.12.beta3/sage b main ... Patches for #12412: vector.patch#1667222d03769cbc34aa78a1d2fe5b65 Looking at #12413 Patches for #12413: trac_12413_linbox_crash.patch#2e514716d104d7edef0f68881794ea47 Patches for #12630: trac_12630_quivers_v2.patch#a52cb3d0b60368efe3b925679e64a286 trac12630_refactor_code.patch#ed725dca1464c303ac24cee8be2296d1 trac12630quiver_representation.patch#6609dfb0c03f73fd66d83a15015064e5 hg qpop a no patches applied hg qimport http://trac.sagemath.org/sage_trac/rawattachment/ticket/12412/vector.patch adding vector.patch to series file hg qpush applying vector.patch patching file sage/modules/vector_space_homspace.py Hunk #1 FAILED at 349 Hunk #2 FAILED at 364 Hunk #3 FAILED at 374
This was merged in sage5.0!!!
comment:117 Changed 8 years ago by
I opened a followup ticket, namely #15086 for a partial cythonification.
comment:118 followup: ↓ 119 Changed 8 years ago by
I'm wondering, from the theoretical viewpoint of a reviewer (I don't know if I'm up to the task), could it be that it's easier to review a certain set of .py files rather than the three .patches? Two of the patches are too large for the trac viewer, and it seems that hg patch files obscure the nature of many changes. If so, could you list the .py files that are significantly changed?
comment:119 in reply to: ↑ 118 Changed 8 years ago by
Replying to darij:
I'm wondering, from the theoretical viewpoint of a reviewer (I don't know if I'm up to the task), could it be that it's easier to review a certain set of .py files rather than the three .patches? Two of the patches are too large for the trac viewer, and it seems that hg patch files obscure the nature of many changes. If so, could you list the .py files that are significantly changed?
Well, I guess by keeping the patches separate, I intended to make reviewing easier. In fact, the code introduced by the first patch is totally reworked and put into different files by the second patch.
Anyway, the resulting code is mainly the contents of sage/quivers/, which is
ls sage/quivers/ algebra.py all.py free_small_category.py homspace.py __init__.py morphism.py paths.pxd paths.pyx quiver.py representation.py
If I am not mistaken, changes in other locations are relatively small, namely:
 insert
Quiver
(and onlyQuiver
, but not all the other stuff such asFreeSmallCategory
orQuiverRep
) into the global namespace  make the modules in sage.quivers part of the documentation.
Best regards, Simon
comment:120 followup: ↓ 121 Changed 8 years ago by
The patches seem to be completely broken right now. Tested on 5.12.beta5, and nothing works !
comment:121 in reply to: ↑ 120 Changed 8 years ago by
Replying to chapoton:
The patches seem to be completely broken right now. Tested on 5.12.beta5, and nothing works !
I had a look at the log of the patchbot, and it rather seems to me that the patchbot is completely broken right now. Apparently it can apply the patches, but during the tests it suddenly can't find the files that it wants to test. I don't think this is due to the patches.
comment:122 followup: ↓ 123 Changed 8 years ago by
Hello,
 first, the patchbot was my own patchbot, and indeed it is broken (or rather I made a mistake during its run on your ticket).
 second, I have myself applied the patches on a clean 5.12.beta5, and found that
Q = Quiver(something) (one of your examples)
is broken. This complains about a keyword of DiGraph
. I have managed to fix that, but then not everything works, there are still many failures.
So please try to apply your patches to a 5.12.beta5 and run the tests, and we will see if these problems are only on my side.
comment:123 in reply to: ↑ 122 Changed 8 years ago by
Replying to chapoton:
 second, I have myself applied the patches on a clean 5.12.beta5, and found that
Q = Quiver(something) (one of your examples)
is broken. This complains about a keyword of
DiGraph
. I have managed to fix that, but then not everything works, there are still many failures.
Too bad. I can confirm these problems.
comment:124 Changed 8 years ago by
 Status changed from needs_review to needs_work
comment:125 Changed 8 years ago by
 Dependencies changed from #12412, #12413 to #12412, #12413, #14806
I found that #14806 has introduced a new argument data_structure to DiGraph
, and the arguments that I pass to DiGraph.__init__
are mistakenly interpreted as "data_structure".
And now I wonder how to cope with it. We haveagain by #14806immutable digraphs, and the main purpose of "sage.quivers.quiver.Quiver" was to create immutable digraphs. So, perhaps it would be a good idea to refactor the code again, namely: Remove sage.quivers.quiver, and move its functionality to plain digraphs. Since constructions such as FreeSmallCategory
use the digraph as cache key, it would only work with immutable digraphs (which is what we want!).
comment:126 followup: ↓ 127 Changed 8 years ago by
 Cc ncohen added
Hi Nathann!
I think you are the person to answer the questions I raised in my previous post and on sagecombinatdevel:
 Are digraphs constructed with
data_structure="static_sparse"
considered being immutable? If they are, shouldn't one set the attribute._immutable
to the graph, so that the hash won't complain about mutability?  Would it be OK from your perspective to add the methods for creation of "free small category" (i.e., directed paths with concatenation), quiver representations and quiver algebras to
DiGraph
? Or would you prefer that we keep creating a subclassQuiver
ofDiGraph
providing these methods?
comment:127 in reply to: ↑ 126 ; followup: ↓ 128 Changed 8 years ago by
Helloooooooo !!
I think you are the person to answer the questions I raised in my previous post and on sagecombinatdevel:
Oh ? Hmmm, I don't always read them.
 Are digraphs constructed with
data_structure="static_sparse"
considered being immutable? If they are, shouldn't one set the attribute._immutable
to the graph, so that the hash won't complain about mutability?
No, they are not. Only the backend is immutable, the graph itself isn't. I mean, you can't add/remove vertices nor edges (you would get an exception) using the Graph object, but there is a wealth of awful things that graphs store, and that are still mutable. Like embeddings, like a LOT of stuff. Can't an edge label be mutable too, btw ? Embedding, layout, name, allowing or not multiple edges/loops.
My problem with the patch at #14535, is that decorators on methods that are heavily used could impact ALL graphs (not only the immutable ones), and also that knowing a graph is immutable is information that can make you save space and speed, which is now done. But there is nothing wrong at all with using those decorators for less critical methods, like setting the embedding or the layout ! So you can update #14535 to use #14806 and only decorate these additional methods, and get real immutable Graph objects, it seems the best way to do it !
 Would it be OK from your perspective to add the methods for creation of "free small category" (i.e., directed paths with concatenation), quiver representations and quiver algebras to
DiGraph
? Or would you prefer that we keep creating a subclassQuiver
ofDiGraph
providing these methods?
I don't really know what these methods do, to be honest.. Do they apply to all digraphs, for a start ? And do you think that you would ever want the digraphs you use to have anything to do with the parent/element stuff and facades ?
Most importantly, do you really think that you want to inherit from DiGraph? ? You can use the backends without inheriting from DiGraph? objects, and in particular you wouldn't have 10000 unrelated methods in your objects. And you could have a method from quivers to graph if you ever want to do things like computing a hamiltonian circuit in your quivers ? :P
Nathann
comment:128 in reply to: ↑ 127 ; followup: ↓ 129 Changed 8 years ago by
Replying to ncohen:
No, they are not [immutable]. Only the backend is immutable, the graph itself isn't. I mean, you can't add/remove vertices nor edges (you would get an exception) using the Graph object, but there is a wealth of awful things that graphs store, and that are still mutable. Like embeddings, like a LOT of stuff. Can't an edge label be mutable too, btw ?
Let me rephrase my question: Probably, if one really wants to play dirty, one could change edge labels. But is it possible to change edge labels by using "official" (nonunderscore) methods of the graph? If it is impossible, then I'd say the graph is immutable.
And concerning edge labels: Yes, I need them for the constructions of quiver algebras and so on.
So, if it is possible to change the edge labels of a "static_sparse" digraph by using nonunderscore method, then I'd say we can't work with digraph (and need a subclass or something else).
Embedding, layout, name, allowing or not multiple edges/loops.
This won't matter for me. Actually, if you compare digraphs ("=="), would the embedding, layout, name and so on be taken into account?
Let me rephrase my needs: For me, it is important that one can't (by nonunderscore methods) change the ==equivalence class of the graph. If this is the case, then it is immutable.
My problem with the patch at #14535, is that decorators on methods that are heavily used could impact ALL graphs
The stuff here is not related with #14535 (which is probably just a bad idea).
I don't really know what these methods do, to be honest.. Do they apply to all digraphs, for a start ?
AFAIK, there is no mathematical difference between a quiver and a digraph. And of course, for any digraph, you can construct the algebra whose monoids correspond to directed paths, which are multiplied by concatenation (yielding zero if the end/startpoints don't match): The quiver algebra.
So, yes, the mathematical notions here make sense for all digraphs.
But, as you know, I like UniqueRepresentation
. And since the digraph together with a
base ring is enough to determine the quiver algebra, I would like to use the
digraph as a cache key.
Hence, from the implementation point of view, "quiver algebra" and friends will only make sense for all immutable digraphs.
And do you think that you would ever want the digraphs you use to have anything to do with the parent/element stuff and facades ?
No. For me, the digraphs are just labels for some algebra.
Note that with the patches from here, Quiver
is not a parent. The only
parents occuring here are FreeSmallCategory
, QuiverRepresentation
and
QuiverAlgebra
none of them are digraphs.
Most importantly, do you really think that you want to inherit from DiGraph?? You can use the backends without inheriting from DiGraph? objects, and in particular you wouldn't have 10000 unrelated methods in your objects.
Well, a quiver is the same as a digraph. So, I believe it totally makes sense to have 10000 unrelated methods.
And yes, I also believe that digraph should have even more methods, namely in addition: A method returning the quiver algebra over a given ring and some methods being able to construct representations of the quiver.
The only reason for introducing a subclass Quiver
of DiGraph
was the
concern about mutability.
And you could have a method from quivers to graph if you ever want to do things like computing a hamiltonian circuit in your quivers ?
:P
Sure. But there is no mathematical reason to create a new python class for quivers. The only reason to do so was in the code.
Conclusive question
Do we have digraphs with the property that it is impossible to change the ==equivalence class by using nonunderscore methods? If we have, then I'd suggest to add a few more methods to them. And don't worry, I won't turn digraphs into parents or facades... :)
comment:129 in reply to: ↑ 128 ; followup: ↓ 130 Changed 8 years ago by
Hellooooooooo !!
Let me rephrase my question: Probably, if one really wants to play dirty, one could change edge labels. But is it possible to change edge labels by using "official" (nonunderscore) methods of the graph? If it is impossible, then I'd say the graph is immutable.
Well... You can get the edge label from a pair of vertices u,v (and that label could be a list), then modify it. But you'd be looking for trouble of course.
And concerning edge labels: Yes, I need them for the constructions of quiver algebras and so on.
Okayokay :P
So, if it is possible to change the edge labels of a "static_sparse" digraph by using nonunderscore method, then I'd say we can't work with digraph (and need a subclass or something else).
Ahem. Well, for a start, the static backend only support multiple edge, loops and labels because you need them. And most of this patch headaches, as usual, come from multiple edges, loops and labels. I personally hate them with all my heart :P
Then, as the graph is static these things have no reason to be mutable. Though the backend only stores the labels as "python objects", and Python objects can be anything. A "clean" implementation would be to refuse to convert to an immutable graph any graph which has nonimmutable edge labels, but I think that's going too far. And this implementation gives you the freedom to filter whatever you want anyway.
Embedding, layout, name, allowing or not multiple edges/loops.
This won't matter for me. Actually, if you compare digraphs ("=="), would the embedding, layout, name and so on be taken into account?
Good question. I hope not. I don't have Sage right now (it's compiling), but if g = graphs.PetersenGraph?(); g == Graph(g.edges()) says True, then we are sage and these are not taken into account.
Though it would make sense to prevent anybody from changing the embedding/layout in an immutable graph anyway. Let's pretend, at the very least :P
Let me rephrase my needs: For me, it is important that one can't (by nonunderscore methods) change the ==equivalence class of the graph. If this is the case, then it is immutable.
Well. You would have to check what == actually checks, and make sure that your equality uses exactly the same set of parameters. And to make sure that one doesn't get updated while the other one does not in the future :P
I hope that there is nothing surprising/worrying there, though.
Though of course, if two graphs with the same edges have different labels they will be different. And you can (currently) modify an edge label if the edge label object is mutable, using only nonunderscore methods.
The stuff here is not related with #14535 (which is probably just a bad idea).
Well, if you want immutable graphs you will probably have to use these decorators ! I think that two graphs cannot be equal if one allows multiple edge while the other one does not. Perhaps it is a mistake, though :P
AFAIK, there is no mathematical difference between a quiver and a digraph.
Then why would you call them quivers ? :P
And of course, for any digraph, you can construct the algebra whose monoids correspond to directed paths, which are multiplied by concatenation (yielding zero if the end/startpoints don't match): The quiver algebra.
So, yes, the mathematical notions here make sense for all digraphs.
Hmmm... Well, a .quiver_algebra()
method would make sense indeed then. Would you have many to add ?
But, as you know, I like
UniqueRepresentation
.
:D
And since the digraph together with a base ring is enough to determine the quiver algebra, I would like to use the digraph as a cache key.
It does make sense. I also need this from time to time actually O_o
Hence, from the implementation point of view, "quiver algebra" and friends will only make sense for all immutable digraphs.
Why so ? I chatted a bit with Florent about this, and it seems that you do need some specific data structure to store all these paths, and concatenate them easily and quickly and everything. I thought that calling a .quiver_algebra()
in a (possibly mutable) graph would somehow give you a new object containing that data structure, and that this would probably encode the graph in a better way too ?... By the way, this static data structure is now ... extremely cheap, compared to the current graphs. Really, really cheap. And copying it is really just a memcpy
of size g.size()
.
No. For me, the digraphs are just labels for some algebra.
Cool, cool.
Well, a quiver is the same as a digraph. So, I believe it totally makes sense to have 10000 unrelated methods.
Really, why don't you call them digraphs then ? O_o
And yes, I also believe that digraph should have even more methods, namely in addition: A method returning the quiver algebra over a given ring and some methods being able to construct representations of the quiver.
Hmmm... And what about having a quiver_albegra()
method that returns this quiver algebra, and having those method for representations be methods of this quiver algebra object ? Or would it make more sense to have these methods be methods of digraphs (or Quivers), directly ?
Conclusive question
Do we have digraphs with the property that it is impossible to change the ==equivalence class by using nonunderscore methods?
You can definitely do that if the graph has mutable edge labels. In this case the nonunderscore method .get_edge_label() would return the object, you can then modify it, and the graph should not be equal to what it was before anymore. Then you probably have to check what equality ensures right now, and I'm sorry I cannot do this but I have no Sage install available right now ^^;
If we have, then I'd suggest to add a few more methods to them. And don't worry, I won't turn digraphs into parents or facades... :)
Thaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaanks !! :P
Nathann
comment:130 in reply to: ↑ 129 ; followup: ↓ 131 Changed 8 years ago by
Replying to ncohen:
Well... You can get the edge label from a pair of vertices u,v (and that label could be a list),
Yeaaah, but then you aren't using methods "officially" supported by the graph. If you like, you can even mutate an integer: I recall a worksheet in which William demonstrated mutating an Integer.
Ahem. Well, for a start, the static backend only support multiple edge, loops and labels because you need them.
Did you just say that you made the static backend support multiple edges just for me? (blush) Thank you!
And most of this patch headaches, as usual, come from multiple edges, loops and labels. I personally hate them with all my heart
:P
OK, but they naturally occur in algebra. Algebra causes headaches, too ;)
For example, if you have a finite group whose order is a power of a prime p, then the group algebra over GF(p) can be described as a quotient of a quiver algebra with a single vertex. So, all edges are loops.
Then, as the graph is static these things have no reason to be mutable. Though the backend only stores the labels as "python objects", and Python objects can be anything. A "clean" implementation would be to refuse to convert to an immutable graph any graph which has nonimmutable edge labels, but I think that's going too far.
I totally agree.
Good question. I hope not. I don't have Sage right now (it's compiling), but if g = graphs.PetersenGraph?(); g == Graph(g.edges()) says True, then we are sage and these are not taken into account.
Good news for me:
sage: g = graphs.PetersenGraph(); g == Graph(g.edges()) True
Though it would make sense to prevent anybody from changing the embedding/layout in an immutable graph anyway. Let's pretend, at the very least
:P
That's other people's problem for me ...
Though of course, if two graphs with the same edges have different labels they will be different.
That's what I want. Namely, the generator names of the quiver algebra are obtained from the edge and vertex labels. And if they change, then the algebra should change as well. Hence, the labels should be checked in "==".
And you can (currently) modify an edge label if the edge label object is mutable, using only nonunderscore methods.
That's not what I meant. You can of course obtain the edge label by nonunderscore methods, but in order to mutate the returned label, you need to do more.
Well, if you want immutable graphs you will probably have to use these decorators ! I think that two graphs cannot be equal if one allows multiple edge while the other one does not. Perhaps it is a mistake, though
:P
Hmmmm. I'd think one shouldn't say that an immutable graph "allows" loops/multiple edges. Either it has loops or it has notif it has not, it will certainly not allow to create a loop, since it is immutable.
AFAIK, there is no mathematical difference between a quiver and a digraph.
Then why would you call them quivers ?
:P
Then why would you call them digraphs? :P
Seriously, I guess there are just two mathematical communities. Graph theorists would call them digraph, I guess, but algebraist would call them quivers.
Hmmm... Well, a
.quiver_algebra()
method would make sense indeed then. Would you have many to add ?
I'd need to look at the code. At least there would be
.free_small_category()
: This is the set of directed paths with multiplication by concatenation. I was told on sagecombinatdevel that I shouldn't call it "path magma" but "free small category"..quiver_algebra(R)
(or just.algebra(R)
?): Return the monomial algebra over R whose monomials are given by the free small category.quiver_representation(...)
: Create a module over the quiver algebra. Currently there are some shortcuts for creating a quiver representation. For example, the vertices of the quiver/digraph are in onetoone correspondence to the simple modules of the quiver algebra. And the projective covers of the simple modules are important as well.
If I recall correctly, we have 3 shortcuts, so, this would result in 6 additional methods.
Disadvantage of moving stuff to Digraph: It would again give rise to
refactoring the code. I guess this is not other people's problem ... :/
Hence, from the implementation point of view, "quiver algebra" and friends will only make sense for all immutable digraphs.
Why so ? I chatted a bit with Florent about this, and it seems that you do need some specific data structure to store all these paths, and concatenate them easily and quickly and everything. I thought that calling a
.quiver_algebra()
in a (possibly mutable) graph would somehow give you a new object containing that data structure, and that this would probably encode the graph in a better way too ?... By the way, this static data structure is now ... extremely cheap, compared to the current graphs. Really, really cheap. And copying it is really just amemcpy
of sizeg.size()
.
Right, you could always say that you have a class FreeSmallCategory
inheriting from UniqueRepresentation
, and then G.free_small_category()
should return FreeSmallCategory(G)
if G is immutable,
but FreeSmallCategory(immutable_copy(G))
otherwise.
Well, a quiver is the same as a digraph. So, I believe it totally makes sense to have 10000 unrelated methods.
Really, why don't you call them digraphs then ?
O_o
Because currently I am algebraist. I used to be a lowdimensional topologist, and I think these guys did not come to a conclusion whether it is digraph or quiver (I heard naming them both ways when I was young).
Hmmm... And what about having a
quiver_albegra()
method that returns this quiver algebra, and having those method for representations be methods of this quiver algebra object ?
Makes sense. I would agree that having a method on the quiver/digraph is actually a shortcut.
comment:131 in reply to: ↑ 130 ; followup: ↓ 132 Changed 8 years ago by
Hellooooooooo !!
I recall a worksheet in which William demonstrated mutating an Integer.
That's forbidden magic.
OK, but they naturally occur in algebra. Algebra causes headaches, too ;)
I admit that.
For example, if you have a finite group whose order is a power of a prime p, then the group algebra over GF(p) can be described as a quotient of a quiver algebra with a single vertex. So, all edges are loops.
Multiple labelled loops on a vertices. Ahahah. I owe other headaches to that while coding #14953 :P
Good news for me:
sage: g = graphs.PetersenGraph(); g == Graph(g.edges()) True
Wuuuhuuu !!
Though it would make sense to prevent anybody from changing the embedding/layout in an immutable graph anyway. Let's pretend, at the very least
:P
That's other people's problem for me ...
HMmmmmm.. Well, if you want some Graph objects to be officially immutable, it has to make sense with what the objects already store...
That's what I want. Namely, the generator names of the quiver algebra are obtained from the edge and vertex labels. And if they change, then the algebra should change as well. Hence, the labels should be checked in "==".
This equality test can also be implemented at backendlevel. Which would be MUCH faster :P
Hmmmm. I'd think one shouldn't say that an immutable graph "allows" loops/multiple edges. Either it has loops or it has notif it has not, it will certainly not allow to create a loop, since it is immutable.
I agree with you. However, the current implementation checks that these flags are equal in __eq__
. So you will probably have to modify it a bit in case the graphs are static.
Dans it would produce weird things like :
sage: g == h False sage: Graph(g,immutable=True) == Graph(g,immutable=True) True
Or perhaps we should just give up saying that two graphs are different just because of these flags... Would probably make more sense, actually.
Then why would you call them digraphs?
:P
http://en.wikipedia.org/wiki/Quiver_(mathematics) http://en.wikipedia.org/wiki/Directed_graph
HMmmm... Looks like they insist on having multiple edges and loops, which is not forbidden by digraphs. Well :P
Seriously, I guess there are just two mathematical communities. Graph theorists would call them digraph, I guess, but algebraist would call them quivers.
I'll go talk to them one by one and convince them that what they do is wrong O_O
I'd need to look at the code. At least there would be
.free_small_category()
: This is the set of directed paths with multiplication by concatenation. I was told on sagecombinatdevel that I shouldn't call it "path magma" but "free small category".
O_o
Well. As a DiGraph? user I would personally prefer "path magma", because even if I have no idea what a path magma is there is "path" in there at least. "free small category" really rings no bell at all.
But well.. It's not mine to decide ^^;
What about path_monoid
(if it is a monoid) ? :P
.quiver_algebra(R)
(or just.algebra(R)
?): Return the monomial algebra over R whose monomials are given by the free small category
What about path_alebra
?
http://en.wikipedia.org/wiki/Quiver_(mathematics)#Path_algebra
.quiver_representation(...)
: Create a module over the quiver algebra.
To me this should be .quiver_algebra().representation()
.
 Currently there are some shortcuts for creating a quiver representation. For example, the vertices of the quiver/digraph are in onetoone correspondence to the simple modules of the quiver algebra. And the projective covers of the simple modules are important as well.
If I recall correctly, we have 3 shortcuts, so, this would result in 6 additional methods.
HMmmmmm O_O;;;
Right, you could always say that you have a class
FreeSmallCategory
inheriting fromUniqueRepresentation
, and thenG.free_small_category()
should returnFreeSmallCategory(G)
if G is immutable, butFreeSmallCategory(immutable_copy(G))
otherwise.
Yep ! And I swear, it's cheap. And much more efficient than current graphs.
See youuuuuuuuuuu !
Nathann
comment:132 in reply to: ↑ 131 ; followup: ↓ 133 Changed 8 years ago by
Hi Nathann,
I had recently focused on different things, but now want to resume work hereand need some pointers/advice from you.
Replying to ncohen:
Well. As a DiGraph? user I would personally prefer "path magma", because even if I have no idea what a path magma is there is "path" in there at least. "free small category" really rings no bell at all.
I somehow agree. An argument against "path magma" was the fact that this particular magma is associative. And "associative path magma" sounds not good to me.
But well.. It's not mine to decide
^^;
What about
path_monoid
(if it is a monoid) ?:P
This would have been my choice, too. But sadly it is a monoid if and only if the quiver has precisely one vertex (which is certainly not always the case).
.quiver_algebra(R)
(or just.algebra(R)
?): Return the monomial algebra over R whose monomials are given by the free small categoryWhat about
path_alebra
? http://en.wikipedia.org/wiki/Quiver_(mathematics)#Path_algebra
I'd totally agree. However, note that the original code is due to Jim Stark, and he chose to call it quiver algebra/representation. I refactored the code and added "free small category", but I think it would be undue to change the terminology of the preexisting stuff.
.quiver_representation(...)
: Create a module over the quiver algebra.To me this should be
.quiver_algebra().representation()
.
To me as well. But it seems that some people really think of it in terms of the graph.
Right, you could always say that you have a class
FreeSmallCategory
inheriting fromUniqueRepresentation
, and thenG.free_small_category()
should returnFreeSmallCategory(G)
if G is immutable, butFreeSmallCategory(immutable_copy(G))
otherwise.Yep ! And I swear, it's cheap. And much more efficient than current graphs.
It could be that you have answered the following question already; in this case please give me a remainder: Is #14806 really enough to have immutable graphs, in the sense of "official methods such as add_vertex
will not be able to change the == and cmpclasses of the graph"?
Note that I don't care about the possibility to have mutable labels and change these inplace. This is a misuse that is in the user's own responsibility.
If you answer this question affirmatively, then the question is what we shall do with the hash:
sage: g = graphs.CompleteGraph(400) sage: gi = Graph(g,data_structure="static_sparse") sage: hash(gi) Traceback (most recent call last): ... TypeError: graphs are mutable, and thus not hashable
So, if you answer my question affirmatively, then apparently the flag gi._immutable
should be set to True
when using the immutable graph backend. Shall I open a new ticket for this?
And what is the preferred way of creating an immutable copy? Is it (as above) Graph(g, data_structure="static_sparse")
? Or is there a faster way to create an immutable copy?
Best regards, Simon
comment:133 in reply to: ↑ 132 ; followup: ↓ 142 Changed 8 years ago by
Hi Simon,
We just discussed with Nathann; for whatever it's worth, here is my feeling for the user interface aspects:
Replying to SimonKing:
I somehow agree. An argument against "path magma" was the fact that this particular magma is associative. And "associative path magma" sounds not good to me.
But well.. It's not mine to decide
^^;
What about
path_monoid
(if it is a monoid) ?:P
This would have been my choice, too. But sadly it is a monoid if and only if the quiver has precisely one vertex (which is certainly not always the case).
At this point I would go for either path_partial_monoid (if it includes the empty path as identity) or path_partial_semigroup. It will be easily found by someone interested by paths, and the "monoid" or "semigroup" piece will highlight the associative multiplicative structure and the presence, or not, of an identity.
I am even tempted by the shorter path_monoid or path_semigroup. Granted, this is an abuse. But this abuse is pretty obvious to anyone familiar with paths endowed with the concatenation product; also I have often heard this abuse made by mathematicians. As for those that don't know that are not familiar with path concatenation we can hope that they will read the documentation where this will be written in bold.
Just decide among those four the one that pleases you most!
.quiver_algebra(R)
(or just.algebra(R)
?): Return the monomial algebra over R whose monomials are given by the free small categoryWhat about
path_alebra
? http://en.wikipedia.org/wiki/Quiver_(mathematics)#Path_algebraI'd totally agree. However, note that the original code is due to Jim Stark, and he chose to call it quiver algebra/representation. I refactored the code and added "free small category", but I think it would be undue to change the terminology of the preexisting stuff.
I like path_algebra too, and it's consistent with the above. I'd say it's fair at this point to change this name.
.quiver_representation(...)
: Create a module over the quiver algebra.To me this should be
.quiver_algebra().representation()
.To me as well. But it seems that some people really think of it in terms of the graph.
My feeling:
 Provide the feature as ....algebra.representation() now.
 Add .quiver_representation() later, as an alias, if there really is a popular request for it.
Cheers,
Nicolas
comment:134 Changed 8 years ago by
Hellooooooo Simon !
I had recently focused on different things, but now want to resume work hereand need some pointers/advice from you.
Ahem. As I needed pointers and advice myself I asked Nicolas, who should shortly give his advice on the namind problems. Like this .free_small_category()
function, the Magma which is not a Magma (he told me that the operation was not defined for all pairs of paths), and hence about the monoid which is not a monoid :)
To me as well. But it seems that some people really think of it in terms of the graph.
He will answer that too.
It could be that you have answered the following question already; in this case please give me a remainder: Is #14806 really enough to have immutable graphs, in the sense of "official methods such as
add_vertex
will not be able to change the == and cmpclasses of the graph"?
No, it's not sufficient because of Graph.__eq__??
. Before anything, it checks that both graphs answer the same to Graph.allows_loops()
and Graph.allows_multiple edges()
. In particular it does not mean that the graphs have loops or multiple edges, only that they allow them. So if you want == to make sense on immutable graphs I think you would have to install your immutability decorator in those methods.
Oh, and it also checks the value of the boolean variable ._weighted
. I personally never used it, and I don't like it :P
If those three parameters are correctly managed I think that there is no problem left with __eq__
. Except that it can be made MUCH faster than the current implementation with a Clevel function of equality test in the static sparse graph backend. To be honest, reading this Python code to test equality scares me :P
Note that I don't care about the possibility to have mutable labels and change these inplace. This is a misuse that is in the user's own responsibility.
Yep. I agree with that too.
If you answer this question affirmatively, then the question is what we shall do with the hash:
sage: g = graphs.CompleteGraph(400) sage: gi = Graph(g,data_structure="static_sparse") sage: hash(gi) Traceback (most recent call last): ... TypeError: graphs are mutable, and thus not hashableSo, if you answer my question affirmatively, then apparently the flag
gi._immutable
should be set toTrue
when using the immutable graph backend. Shall I open a new ticket for this?
Yep. Along with the decorators for weights, loops and multiple edges. You will not have to wait very long for review.
And what is the preferred way of creating an immutable copy? Is it (as above)
Graph(g, data_structure="static_sparse")
? Or is there a faster way to create an immutable copy?
Ahem. There is a "faster" way for the user, but all are equally shameful from the point of view of computer speed. Any input that the Graph
constructor accepts can be used with data_structure="static_sparse"
: a normal graph will first be built, THEN its backend will be replaced by a static one. So yeah, not very efficient. That's because the Clevel method to create a static sparse graph only takes Graphs as an input.
If you think it should be made faster one trick would be to work directly on the internal dictionary into which Sage temporarily stores the input data before creating the nonstatic sparse graph backend. This may not be too much work, I don't know if it will produce a very great change in the speed (though I would stop wondering if it does), and I don't mind doing it myself if calling Graph
is too slow for your uses.
And it seems Nicolas wrote his answer while I was writing mine :)
Nathann
comment:135 followup: ↓ 139 Changed 8 years ago by
Hi Nicolas, hi Nathann,
from your answers, it seems to me the best way to proceed is like this:
 Have a new ticket to deal with hash of (practically) immutable graphs, along with
__eq__
for graphs (if I understood correctly, Nathann does not like that.allows_multiple_edges()
,.allows_loops()
and._weighted
should not be part of equality testing any longer (but: To be discussed on the new ticket).
 Rebase this ticket on top of the new one (and I guess migrate it to git...).
 Rename everything according to Nicolas' previous post (although I think it was he who suggested "free small category"
;)
)
comment:136 followup: ↓ 137 Changed 8 years ago by
+1 !
(And I wouldn't mind at all saying that two graphs are equal even when one "allows" multiple edges and the other does not)
Nathann
comment:137 in reply to: ↑ 136 Changed 8 years ago by
Replying to ncohen:
(And I wouldn't mind at all saying that two graphs are equal even when one "allows" multiple edges and the other does not)
Oops, sorry: I used too many negations. What I wanted to say was: "Nathann does not like that .allows_multiple_edges()
etc. are part of equality testing, hence, they should not be part of equality testing any longer"... Anyway, let's see what will come out on the new ticket...
comment:138 Changed 8 years ago by
For the record: #15278 deals with hash and equality check of graphs.
comment:139 in reply to: ↑ 135 Changed 8 years ago by
Replying to SimonKing:
(although I think it was he who suggested "free small category"
;)
)
Granted, it definitely came up during a discussion between the two of us :) Luckily we know more now, which made me change my mind in this specific context.
On the other hand, I guess I will keep the name FreeSmallCategories? when we will get to create this category.
Cheers,
comment:140 Changed 8 years ago by
 Branch set to u/SimonKing/ticket/12630
 Modified changed from 10/16/13 06:26:40 to 10/16/13 06:26:40
comment:141 Changed 8 years ago by
 Commit set to fda4012f91c357f3db86fb07271573886ad0da74
 Description modified (diff)
I want to finally get this ticket off my plate. So, as a starter, I was turning the three patches into three commits of a git branch (removing some trailing whitespace in the process). Next, I need to read the preceding comments again, and fix the code accordingly.
New commits:
fda4012  #12630: Use existing Sage infrastructure for quiver representations and their homspaces and morphisms 
ff82cf0  Implementation of quivers as associative magmas 
4cbb1b0  trac #12630 Add representations of quivers and quiver algebras 
comment:142 in reply to: ↑ 133 ; followup: ↓ 143 Changed 8 years ago by
Hi Nicolas,
Replying to nthiery:
What about
path_monoid
(if it is a monoid) ?:P
This would have been my choice, too. But sadly it is a monoid if and only if the quiver has precisely one vertex (which is certainly not always the case).
...
I am even tempted by the shorter path_monoid or path_semigroup. Granted, this is an abuse.
Why? AFAIK, a semigroup is the same as an associative magma (which we have here). It is not needed to have an identity in a semigroup. Hence, it is no abuse at all. And I think path semigroup is both short and descriptive, and relatively easy to guess.
I feel tempted to call it path semigroup.
I like path_algebra too, and it's consistent with the above. I'd say it's fair at this point to change this name.
Nobody has complained since you posted your comment (hence, 7 weeks ago). I'd say that in this case we are entitled to change the terminology towards something that we both find more common, namely "path algebra" rather than "quiver algebra".
.quiver_representation(...)
: Create a module over the quiver algebra.To me this should be
.quiver_algebra().representation()
.To me as well. But it seems that some people really think of it in terms of the graph.
My feeling:
 Provide the feature as ....algebra.representation() now.
 Add .quiver_representation() later, as an alias, if there really is a popular request for it.
In other words: Nathann, Nicolas and I all agree that that it is the path algebra that is represented, not the quiver.
comment:143 in reply to: ↑ 142 ; followup: ↓ 144 Changed 8 years ago by
Replying to SimonKing:
I am even tempted by the shorter path_monoid or path_semigroup. Granted, this is an abuse.
Why? AFAIK, a semigroup is the same as an associative magma (which we have here). It is not needed to have an identity in a semigroup. Hence, it is no abuse at all. And I think path semigroup is both short and descriptive, and relatively easy to guess.
It's an abuse because it's only a *partial* semigroup (with the product of two non consecutive paths giving None).
I feel tempted to call it path semigroup.
I am very fine with that. And the rest :)
comment:144 in reply to: ↑ 143 Changed 8 years ago by
Replying to nthiery:
It's an abuse because it's only a *partial* semigroup (with the product of two non consecutive paths giving None).
No, it gives an "invalid path", which is an element of the semigroup.
comment:145 followup: ↓ 146 Changed 8 years ago by
We already discussed this and I thought it was settled. Well, leave it as it is for now if it helps getting this off your plate soon. But in the long run I really believe that we don't want this invalid path, and instead only have a partial semigroup.
comment:146 in reply to: ↑ 145 Changed 8 years ago by
Replying to nthiery:
We already discussed this and I thought it was settled. Well, leave it as it is for now if it helps getting this off your plate soon. But in the long run I really believe that we don't want this invalid path, and instead only have a partial semigroup.
Yes, I recall this discussion. I could try to change the implementation accordingly. But I need one reminder: Should "None" be returned or should an arithmetic error be raised when the product in the partial semigroup is not defined?
comment:147 followup: ↓ 148 Changed 8 years ago by
PS: It has been a long time since I last looked at the code. Hence, I will need some work anyway, so, the additional work of making it a partial semigroup will hopefully not matter.
comment:148 in reply to: ↑ 147 Changed 8 years ago by
Hi Simon!
Replying to SimonKing:
PS: It has been a long time since I last looked at the code. Hence, I will need some work anyway, so, the additional work of making it a partial semigroup will hopefully not matter.
Great, thanks!
None is good. That's what we have been using for a while e.g. for crystals (where the crystal operators are partially defined), and it; handy not to have to try/catch whenever there is a risk that the operation is not defined.
Cheers,
Nicolas
comment:149 Changed 8 years ago by
 Commit changed from fda4012f91c357f3db86fb07271573886ad0da74 to 72fb2eb71459f4ac76b0d922a7ad788c660a8017
Branch pushed to git repo; I updated commit sha1. New commits:
b6ed038  trac #15623: Immutable graph backend for Posets

ee8c395  Trac 15623: Let to_graph return an immutable graph

dcb8a0b  trac #15623: rebase on 6.1.beta4

3531566  trac #15623: Rebase on updated #15622

95cecd1  trac #15623: Removing the hack from #15622, update a variable's name

dae53af  Merge branch 'develop' into ticket/15623

c5b6d59  Reinsert a bit of code that had been erroneously deleted in the previous merge commit

72fb2eb  Merge branch 'ticket/15623' into ticket/12630

comment:150 Changed 8 years ago by
 Dependencies changed from #12412, #12413, #14806 to #12412, #12413, #14806, #15491, #15623
 Modified changed from 01/30/14 10:56:21 to 01/30/14 10:56:21
comment:151 Changed 8 years ago by
By #15623 and friends, we have immutable graphs. Hence, it makes sense to add #15623 as dependency and use immutable graphs as keys for UniqueRepresentation
. This should both be faster and nicer than the current transformation into a sorted tuple of edges.
The branch isn't ready for review, as I am resuming work on it (concerning semigroups) only now.
comment:152 followup: ↓ 154 Changed 8 years ago by
This ticket currently adds a separate class Quiver, inheriting from UniqueRepresentation
and from DiGraph
, and the main reason was the fact that immutable graphs have been missing when Jim Stark provided the original implementation.
But now we have immutable graphs. So, now I would prefer to remove the new Quiver class, and instead add two methods to DiGraph?, namely
 .semigroup(),that returns the (partial) semigroup formed by the pathswithcomposition, and
 .algebra(), that would be a shortcut for .semigroup().algebra()
I would not like to turn quivers into a UniqueRepresentation
. I mean, what's the point? DiGraphs
are no parents, and hence the "unique parent" mantra won't apply to them. Only the path semigroup and the path algebra should be UniqueParent
, but not the underlying quiver.
This is a question mainly to Nathann: Could you live with two additional methods for DiGraph
? I think the discussion on this ticket suggest the answer "yes", but to be on the safe side I'm asking again...
I would like to see the following workflow for constructing a quiver representation:
 Create a digraph (aka quiver)
Q
 Create a path algebra
P = Q.algebra(k)
over a fieldk
 Create a representation of
P
viaP.representation(...)
.
This would avoid adding more stuff to the global namespace and is, I think, the natural way to construct a quiver representation.
comment:153 followup: ↓ 155 Changed 8 years ago by
Hmm. @Nathann: I just see that there might be further methods that would be added:
def is_source(self, vertex)
: Tests whether the vertex is a source in the quiver.def is_sink(self, vertex)
: Test whether the vertex is a sink in the quiver.def sources(self)
,def sinks(self)
: Return the list of all sources and sinks.
I think these methods make sense for digraphs, and should be added. But perhaps Nathann disagrees.
Then there also is a method all_paths
, but I think this should perhaps be moved to the semigroup, because it is the semigroup (not the digraph itself) that needs these paths.
comment:154 in reply to: ↑ 152 Changed 8 years ago by
 .semigroup(),that returns the (partial) semigroup formed by the pathswithcomposition, and
 .algebra(), that would be a shortcut for .semigroup().algebra()
This is a question mainly to Nathann: Could you live with two additional methods for
DiGraph
? I think the discussion on this ticket suggest the answer "yes", but to be on the safe side I'm asking again...
If you can tell me honestly that there exists only one way to associate a semigroup to a digraph, then no problem with semigroup. Is that the case ?
Same question for algebra. Is that the case ? But for this one I do not see the point of creating an alias when the normal way to access the algebra is to call it on .semigroup()
.
Nathann
comment:155 in reply to: ↑ 153 ; followup: ↓ 162 Changed 8 years ago by
Hmm. @Nathann: I just see that there might be further methods that would be added:
def is_source(self, vertex)
: Tests whether the vertex is a source in the quiver.def is_sink(self, vertex)
: Test whether the vertex is a sink in the quiver.def sources(self)
,def sinks(self)
: Return the list of all sources and sinks.I think these methods make sense for digraphs, and should be added. But perhaps Nathann disagrees.
I totally disagree. But I am admittedly in a *VERY* bad mood at the moment.
Those functions can all be written in one line. G.is_sink(v)
is equivalent to G.in_degree(v)==0
and the same holds for sink. Don't we have anything more interesting to do in Sage than add hundreds of lines of code+doc for stuff we can already do in as many characters ?
Nathann
comment:156 Changed 8 years ago by
sinks
and sources
can make sense, though.
Nathann
comment:157 followup: ↓ 158 Changed 8 years ago by
 Modified changed from 01/30/14 14:55:18 to 01/30/14 14:55:18
Hi Nathann, Simon,
Just random suggestions. Adding those methods to digraphs sounds
reasonable, with slightly more explict names like
Q.path_semigroup()
and Q.path_algebra()
. The latter could
possibly be Q.path_semigroup().algebra(QQ)
.
For Q.all_paths()
, it depends on the meaning. If it's about
listing the paths, we can just do Q.path_semigroup().list()
. If
it's about modelling the set of paths, but without the (partial)
semigroup structure given by concatenation, then Q.paths()
seems
reasonable.
Cheers,
Nicolas
comment:158 in reply to: ↑ 157 ; followup: ↓ 161 Changed 8 years ago by
Just random suggestions. Adding those methods to digraphs sounds reasonable, with slightly more explict names like
Q.path_semigroup()
andQ.path_algebra()
. The latter could possibly beQ.path_semigroup().algebra(QQ)
.
No problem with that.
For
Q.all_paths()
, it depends on the meaning.
What do you mean ? DiGraph.all_paths
already exists.
Nathann
comment:159 Changed 8 years ago by
 Modified changed from 01/30/14 15:02:54 to 01/30/14 15:02:54
What do you mean ?
DiGraph.all_paths
already exists.
oops, right, never mind my comment :)
comment:160 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:161 in reply to: ↑ 158 ; followup: ↓ 163 Changed 8 years ago by
Replying to ncohen:
Just random suggestions. Adding those methods to digraphs sounds reasonable, with slightly more explict names like
Q.path_semigroup()
andQ.path_algebra()
. The latter could possibly beQ.path_semigroup().algebra(QQ)
.No problem with that.
OK, the names make sense, and Q.path_algebra(QQ)
wouldn't be more than a shortcut for Q.path_semigroup().algebra(QQ)
anyway.
For
Q.all_paths()
, it depends on the meaning.What do you mean ?
DiGraph.all_paths
already exists.
Yes, but IIRC the all_paths
method implemented here has a different meaning. The difference is: In one case, the resulting paths are lists of visited vertices, in the other case, the resulting paths are lists of adjacent arrows. In particular, if you have multiple arrows between two vertices, the first meaning of all_paths
would count it as one path, but the second meaning would distinguish the different arrows.
comment:162 in reply to: ↑ 155 Changed 8 years ago by
Replying to ncohen:
Those functions can all be written in one line.
G.is_sink(v)
is equivalent toG.in_degree(v)==0
and the same holds for sink.
OK, that makes sense.
comment:163 in reply to: ↑ 161 ; followup: ↓ 164 Changed 8 years ago by
Yes, but IIRC the
all_paths
method implemented here has a different meaning.
Oh. You overwrite the all_paths
method inherited from DiGraph? and give it a different meaning ?...
comment:164 in reply to: ↑ 163 ; followup: ↓ 165 Changed 8 years ago by
Replying to ncohen:
Yes, but IIRC the
all_paths
method implemented here has a different meaning.Oh. You overwrite the
all_paths
method inherited from DiGraph? and give it a different meaning ?...
I believe that listing the paths (in the sense of: concatenation of arrows, with multiple different paths between the same vertices) should be the job of the pathsemigroup: After all, these are the elements of the pathsemigroup.
So, I would prefer to *not* add it as a new method of DiGraph
(perhaps calling it all_quiver_paths()
) and of course I would prefer to *not* override the all_paths()
method of DiGraph
, but I'd prefer to let it be a PathSemigroup
method.
comment:165 in reply to: ↑ 164 ; followup: ↓ 166 Changed 8 years ago by
I believe that listing the paths (in the sense of: concatenation of arrows, with multiple different paths between the same vertices) should be the job of the pathsemigroup: After all, these are the elements of the pathsemigroup.
Yet, you would be surprised to know the number of persons who have a clear understanding of what the set of all paths is, and have no idea of what a semigroup is. A set is a set, a semigroup is a set with additional structure. I don't get why enumerating the paths should make one define a structure on them. If an object representing a set of paths is to be defined somewhere, it has to be defined from a digraph, not from some specific semigroup. As I guess you can define one thousand different semigroups on a given set.
So, I would prefer to *not* add it as a new method of
DiGraph
(perhaps calling itall_quiver_paths()
) and of course I would prefer to *not* override theall_paths()
method ofDiGraph
, but I'd prefer to let it be aPathSemigroup
method.
I don't get it. You can define a set of paths from a DiGraph?, THEN you add (one) semigroup structure on top of it. Why on earth would the set of paths be obtained from a semigroup while the semigroup is the one which needs a set of paths, and not the other way around ?
Then again, just for userfriendliness reasons, you cannot reasonably ask a user to know what a semigroup is in order to enumerate the paths of a graph.
Nathann
comment:166 in reply to: ↑ 165 ; followup: ↓ 167 Changed 8 years ago by
Replying to ncohen:
Yet, you would be surprised to know the number of persons who have a clear understanding of what the set of all paths is, and have no idea of what a semigroup is. A set is a set, a semigroup is a set with additional structure. I don't get why enumerating the paths should make one define a structure on them. If an object representing a set of paths is to be defined somewhere, it has to be defined from a digraph, not from some specific semigroup. As I guess you can define one thousand different semigroups on a given set.
... but not "the" pathsemigroup.
Why on earth would the set of paths be obtained from a semigroup while the semigroup is the one which needs a set of paths, and not the other way around ?
HEY, I thought you are the guy who doesn't like to have the graph namespace polluted ;P
Then again, just for userfriendliness reasons, you cannot reasonably ask a user to know what a semigroup is in order to enumerate the paths of a graph.
That's the point. It seems that there are two different notions of "paths of a graph". One notion is "sequence of vertices that are met along the path", another notion is "sequence of directed edges that are travelled along the path".
If I see that correctly, the current implementation of all_paths()
for digraphs does the former, but the pathsemigroup relies on the latter.
So, let me reformulate my question to you.
 Do you want a new method called, say,
DiGraph.all_quiver_paths()
orDiGraph.all_arrow_sequences()
that returns what the path semigroup needs?  Do you want me to replace the current
DiGraph.all_paths()
so that it returns what the path semigroup needs?  Do you want that the path semigroup computes its underlying data on its own, without introducing a new method of
DiGraph
?
I'd be surprised if you answer "yes" to 1., and shocked if you replied "yes" to 2. Thus, I suppose you prefer 3., but perhaps I am mistaken.
comment:167 in reply to: ↑ 166 ; followup: ↓ 168 Changed 8 years ago by
Yo !
HEY, I thought you are the guy who doesn't like to have the graph namespace polluted
;P
Well, we still have to add methods from time to time, don't we ?
That's the point. It seems that there are two different notions of "paths of a graph". One notion is "sequence of vertices that are met along the path", another notion is "sequence of directed edges that are travelled along the path".
If I see that correctly, the current implementation of
all_paths()
for digraphs does the former, but the pathsemigroup relies on the latter.So, let me reformulate my question to you.
 Do you want a new method called, say,
DiGraph.all_quiver_paths()
orDiGraph.all_arrow_sequences()
that returns what the path semigroup needs?
What about DiGraph.all_paths(edges=True)
?
 Do you want me to replace the current
DiGraph.all_paths()
so that it returns what the path semigroup needs?
You are a free man and if I complain a lot I don't own the graph code. I just care about it. This all_paths
function has probably been created because somebody needed it, and if you just replace it with what you need instead we are going nowhere.
 Do you want that the path semigroup computes its underlying data on its own, without introducing a new method of
DiGraph
?
Well, you are free to do whatever you want with the code of this semigroup. Right now the all_paths
method returns a list of paths (be it with vertices or edges), and if you want to do anything fast with your semigroup you probably need to implement your own data structure to store it better.
If it is a data structure which is efficient to store path independently of what you do with it semigroup structure, well, then it should probably be called AllPaths
or something rather than semigroup. Then, your semigroup can use this data structure, by class inheritance or anything you like.
I'd be surprised if you answer "yes" to 1., and shocked if you replied "yes" to 2. Thus, I suppose you prefer 3., but perhaps I am mistaken.
I thought 2) was a joke, but I answered it seriously just in case. The answer to 3 depends on what you do with the paths : how do you plan on storing them ? A list is probably the worst you can do ^^;
Nathann
comment:168 in reply to: ↑ 167 ; followup: ↓ 169 Changed 8 years ago by
Hi Nathann,
Replying to ncohen:
What about
DiGraph.all_paths(edges=True)
?
Yes, good idea!
I thought 2) was a joke, but I answered it seriously just in case. The answer to 3 depends on what you do with the paths : how do you plan on storing them ? A list is probably the worst you can do
^^;
In the current code, it is stored in a (Python) list, and I totally agree that this is bad. But I want to see this code move forward, and the code has been refactored often enough.
So, I want a preliminary but slow version (that apparently is useful to people, or otherwise Jim Stark had not provided the code) and then replace it with something faster.
I have an implementation using two different kinds of storing it as *long
,
in compressed form. In both implementations, concatenation, comparison and
subpath test are fast enough for me...
But this will be on a new ticket, since otherwise I don't see a chance of progress here.
comment:169 in reply to: ↑ 168 ; followup: ↓ 170 Changed 8 years ago by
Yoooooooo !
In the current code, it is stored in a (Python) list, and I totally agree that this is bad.
O_o
What can you do with the *list*
of paths ? Even checking whether a path is in the list is probably faster by using the graph itself O_o
But I want to see this code move forward, and the code has been refactored often enough.
'f you say so...
So, I want a preliminary but slow version (that apparently is useful to people, or otherwise Jim Stark had not provided the code) and then replace it with something faster.
Are you open to "bets" on the meaning of "later" ? :P
I have an implementation using two different kinds of storing it as
*long
, in compressed form. In both implementations, concatenation, comparison and subpath test are fast enough for me...
Oh. It is already implemented. Then I guess the "later" may not be too far.
But this will be on a new ticket, since otherwise I don't see a chance of progress here.
ts'up to you !
Nathann
comment:170 in reply to: ↑ 169 Changed 8 years ago by
Hi Nathann!
Replying to ncohen:
What can you do with the
*list*
of paths ? Even checking whether a path is in the list is probably faster by using the graph itselfO_o
You misunderstood: I don't intend to keep a list containing paths. But currently, a path is implemented as a list of edges, and an edge is a triple "startpoint, endpoint, label". Instead, a path should be a *long
, at least in my applications.
Are you open to "bets" on the meaning of "later" ?
:P
A month, maybe two. It must not be much longer, since my grant is centred around an implementation of Faugère's F5 algorithm, generalised for path algebra quotients (punch line: in contrast to other famous Gröbner basis algorithms, F5 can compute minimal generating sets for modules).
So, I have a financial interest in having a decent implementation of path algebras soon. And in fact I have something, but it should be rebased on top of this ticket (currently, my own implementation is independent of this ticket, which means there is some code duplication). Best regards,
Simon
comment:171 followup: ↓ 172 Changed 8 years ago by
Nathann, I have some questions concerning all_paths
.
I just notice: There is the method all_paths_iterator
, and I expected it to be used in a generic implementation of all_paths
. But in fact, the generic all_paths
relies on neighbor_out_iterator
(for digraphs, at least). Why is that?
And in particular: Would neighbor_out_iterator
be the correct place to change the behaviour of the all_paths
method (depending on an optional argument, of course)?
comment:172 in reply to: ↑ 171 ; followup: ↓ 175 Changed 8 years ago by
Hello !
Nathann, I have some questions concerning
all_paths
.
Oh ?
I just notice: There is the method
all_paths_iterator
, and I expected it to be used in a generic implementation ofall_paths
. But in fact, the genericall_paths
relies onneighbor_out_iterator
(for digraphs, at least). Why is that?
Answer #1: All I know about this code is that I do not like it. Nobody should enumerate paths in Python.
Answer #2: Let me read that code...
Well, I have NO idea why this thing is implemented twice. One function should be more than enough, and I do not yet why we have both a list version and an iterator version. The iterator version should be sufficient, we can wrap the call with list
if needed, so well... O_o
Those things should probably be merged. I don't like to see heaps involved in the code of all_paths_iterator
though (which is only implemented for digraphs, for some reason). Plus I have absolutely NO idea why heaps are involved there. A list should be sufficient O_o
And in particular: Would
neighbor_out_iterator
be the correct place to change the behaviour of theall_paths
method (depending on an optional argument, of course)?
Hmmmmm... What would you want to change in neighbor_out_iterator
? My secret hope is that whatever you want neighbor_out_iterator
to give you there is already another way to obtain it, for I don't really want to add anything smart in this function which we already try to make FAST. Tell me, and we'll find a way.
Nathann
comment:173 followup: ↓ 174 Changed 8 years ago by
... or perhaps add a new method neighbor_out_arrows_iterator
, that is to be used by all_paths
depending on an optional parameter.
PS: I don't think an all_paths
method makes any sense (to people using cyclic graphs, at least). In general, you'd have an infinite list, hence, an iterator is the best you can hope for.
comment:174 in reply to: ↑ 173 ; followup: ↓ 176 Changed 8 years ago by
Hellooooo !
... or perhaps add a new method
neighbor_out_arrows_iterator
, that is to be used byall_paths
depending on an optional parameter.
list(digraphs.Circuit(5).edge_iterator(1))
?
PS: I don't think an
all_paths
method makes any sense (to people using cyclic graphs, at least). In general, you'd have an infinite list, hence, an iterator is the best you can hope for.
Paths. Not Walks. Paths do not selfintersect.
This being said, an iterator *IS* enough.
Nathann
comment:175 in reply to: ↑ 172 Changed 8 years ago by
Replying to ncohen:
Hmmmmm... What would you want to change in
neighbor_out_iterator
?
Well, in all the "quiver" applications, I want it to iterate over pathsofarrows, but it currently gives pathsofvertices.
My secret hope is that whatever you want
neighbor_out_iterator
to give you there is already another way to obtain it, for I don't really want to add anything smart in this function which we already try to make FAST. Tell me, and we'll find a way.
I have to check where in the quiver code all_paths
(or an iterator) is really used. There are (of course) iterators over the outgoing arrows of a vertex (provided by the backend), and I suppose I can build an iterator on top of it.
comment:176 in reply to: ↑ 174 ; followup: ↓ 177 Changed 8 years ago by
Replying to ncohen:
Paths. Not Walks. Paths do not selfintersect.
Paths, in the sense used by algebraists (path algebra) and topologists (fundamental group), do selfintersect.
comment:177 in reply to: ↑ 176 Changed 8 years ago by
Paths, in the sense used by algebraists (path algebra) and topologists (fundamental group), do selfintersect.
Oh. Well, they don't in graph theory.
Nathann
comment:178 Changed 8 years ago by
comment:179 followups: ↓ 180 ↓ 181 Changed 8 years ago by
Good news: all_paths
is essentially used in only one spot in the quiver code. Hence, it would certainly be possible to have an "selfintersectingarrowpathsiterator" in this spot.
comment:180 in reply to: ↑ 179 ; followup: ↓ 183 Changed 8 years ago by
Good news:
all_paths
is essentially used in only one spot in the quiver code. Hence, it would certainly be possible to have an "selfintersectingarrowpathsiterator" in this spot.
It's up to you. This can also find a place in the graph code, with a simple=False
optional flag. Anyway this all_paths
function HAS to be an iterator. And the two functions should be merged.
Nathann
comment:181 in reply to: ↑ 179 ; followup: ↓ 182 Changed 8 years ago by
Replying to SimonKing:
Good news:
all_paths
is essentially used in only one spot in the quiver code. Hence, it would certainly be possible to have an "selfintersectingarrowpathsiterator" in this spot.
... and only there. I.e., there is no need to introduce a new iterator method (or spoil an existing iterator).
comment:182 in reply to: ↑ 181 ; followup: ↓ 184 Changed 8 years ago by
... and only there. I.e., there is no need to introduce a new iterator method (or spoil an existing iterator).
The bad news is that if you wanted selfintersecting paths you will not get them by calling all_paths
, and the current code is wrong ?..
Nathann
comment:183 in reply to: ↑ 180 ; followup: ↓ 185 Changed 8 years ago by
Replying to ncohen:
It's up to you. This can also find a place in the graph code, with a
simple=False
optional flag. Anyway thisall_paths
function HAS to be an iterator. And the two functions should be merged.
Right. Spoiling the all_paths_iterator
method with an optional argument would be an option. The all_paths
method wouldn't be touched, then.
But I somehow don't like that solution. all_paths_iterator
would have two combined flavours: arrowpaths versus vertexpaths, and simple versus selfintersecting.
comment:184 in reply to: ↑ 182 Changed 8 years ago by
Replying to ncohen:
The bad news is that if you wanted selfintersecting paths you will not get them by calling
all_paths
, and the current code is wrong ?..
The current code (in the sense of: The code provided by the ticket branch) creates a subclass "Quiver" of DiGraph
, and this subclass overrides the all_paths
method. But now, the plan is to not have a subclass, since mathematically a quiver is a digraph (with multiple edges and loops).
comment:185 in reply to: ↑ 183 Changed 8 years ago by
Right. Spoiling the
all_paths_iterator
method with an optional argument would be an option. Theall_paths
method wouldn't be touched, then.
Yepyep. And I will do something about this all_paths
thing which should be an iterator.
But I somehow don't like that solution.
all_paths_iterator
would have two combined flavours: arrowpaths versus vertexpaths, and simple versus selfintersecting.
Well... That's the kind of stuff that happens at Pythonlevel... An entry point to many different algorithms. Plus what about multiple edges and simple graphs ? This will have to appear in the code too :P
Nathann
comment:186 Changed 8 years ago by
 Dependencies changed from #12412, #12413, #14806, #15491, #15623 to #12412, #12413, #14806, #15491, #15623, #15810
comment:187 Changed 8 years ago by
 Commit changed from 72fb2eb71459f4ac76b0d922a7ad788c660a8017 to dc973b43b0e24a8fc1c7446d296c743f9b9c630f
Branch pushed to git repo; I updated commit sha1. New commits:
e9796a1  trac #15810: Immutable directed graphs should know that they are directed

d6ca86c  trac #15810: The graph data structures may have a ._directed but no .directed

a16f59f  Merge branch 'ticket/15810' into ticket/12630, to make acyclicity tests work for immutable directed graphs

200b04b  Do not introduce a separate class for quivers (use immutable DiGraph)

dc973b4  Do not use "invalid path" for quivers. Fix all doctests.

comment:188 followup: ↓ 189 Changed 8 years ago by
 Status changed from needs_work to needs_review
With the new branch, all tests should pass.
The changes with respect to the previous state:
 I have removed the
Quiver
class. Rationale: Mathematically, a quiver is a multidigraph. We need it to be immutable, but meanwhile Sage provides immutable digraphs. So, we can useDiGraph
as entry point for the code:DiGraph.path_semigroup()
returns the partial semigroup formed by the paths of the quiver, subject to concatenation.  Following some discussion with people,
free small category
is now calledpath semigroup
, which seems clearer to the experts. Technically (with multiple vertices) it only is a partial semigroup, but there currently is no category of partial semigroups, and I think it would be splitting hairs to not use the category of semigroups for it.  Jim (the original author) has not commented since a long time, hence, I hope it is not too much of a problem that I renamed one central notion: I believe "path algebra" is more commonly used than "quiver algebra".
 For reasons discussed above, it is better to not have an "invalid path". Hence, if we now provide invalid data to the constructor, then an error is raised. If we try to multiply paths that can't be concatenated, then "None" is returned, according to advice of Nicolas.
I believe this ticket is now ready for review (again). From my perspective, the organisation of the code makes sense (no distinction of digraph and quiver, paths are put into a separate module that will later be cythonised, representations respectively path algebras are put into separate modules, too, and the coercion framework is implemented).
The reviewer should please have a look at the documentation. I have put some documentation into __init__.py
, which is hopefully the right thing to do to document a module that has submodules.
To be done in a followup ticket: The current code certainly is too slow. I have some preliminary faster Cython code that I plan to rebase on top of this branch. This should then also provide Gröbner bases for modules over path algebra quotientsspecifically an F5 algorithm (in my latest article, I prove that F5 can compute Loewy layers for modules over basic algebras).
comment:189 in reply to: ↑ 188 ; followup: ↓ 190 Changed 8 years ago by
Replying to SimonKing:
 Jim (the original author) has not commented since a long time, hence, I hope it is not too much of a problem that I renamed one central notion
I don't mind, in fact I'm happy that someone else has taken over :)
I've been following the discussion, but as a grad student it became time to focus on my thesis which does not involve Sage.
comment:190 in reply to: ↑ 189 Changed 8 years ago by
Replying to JStarx:
Replying to SimonKing: I don't mind, in fact I'm happy that someone else has taken over :)
Great, thank you!
See #15820 for the first followup ticket.
I've been following the discussion, but as a grad student it became time to focus on my thesis which does not involve Sage.
Good luck with your thesis!
comment:191 Changed 8 years ago by
 Branch changed from u/SimonKing/ticket/12630 to public/combinat/quivers
 Commit changed from dc973b43b0e24a8fc1c7446d296c743f9b9c630f to edb52dfad756d6dceb3e97dc97fe665c36912b87
New commits:
edb52df  mostly grammatical fixes to documentation; not a review at all

comment:192 followup: ↓ 193 Changed 8 years ago by
I've taken the liberty to fix some grammar. Also, I changed "free small category" to "path semigroup" a couple times, and I believe it would help to do the same everywhere else or explain how the path semigroup becomes a free small category explicitly (it's a bit confusing because the order of the edges in how one usually writes a path is the opposite of the order in which one composes arrows in a category).
comment:193 in reply to: ↑ 192 Changed 8 years ago by
Replying to darij:
I've taken the liberty to fix some grammar. Also, I changed "free small category" to "path semigroup" a couple times, and I believe it would help to do the same everywhere else
Absolutely! I thought I had completely removed all references to the term "free small category". If it isn't fixed yet, then it needs work.
comment:194 Changed 8 years ago by
 Commit changed from edb52dfad756d6dceb3e97dc97fe665c36912b87 to 461e1ed956a1b1623fa0e5d4a68e6c5379af4d68
comment:195 Changed 8 years ago by
 Commit changed from 461e1ed956a1b1623fa0e5d4a68e6c5379af4d68 to f7fc2eca6347a5abbebcad50bc7abe41a73a60e2
Branch pushed to git repo; I updated commit sha1. New commits:
f7fc2ec  allowed empty quiver; made homogeneous components work for quivers with cycles; fixed various places in doc

comment:196 Changed 8 years ago by
What does this mean:
In addition, the free algebra of a subquiver coerces into the algebra.
If "free algebra" means "path algebra", this is redundant as the same is claimed by the previous paragraph.
In other news, someone please check that everything works fine for the empty quiver...
comment:197 Changed 8 years ago by
If I understood correctly, the develop branch should only be explicitly merged if there is a merge conflict (which is not the case here).
Could you elaborate on
@@ 488,9 +490,16 @@ class PathAlgebra(CombinatorialFreeModule): sage: A = P.algebra(GF(7)) sage: A.homogeneous_component(2) Free module spanned by [a*c, b*d] over Finite Field of size 7  """  basis = [p for p in self._basis_keys if len(p) == n] + sage: D = DiGraph({1: {2: 'a'}, 2: {3: 'b'}, 3: {1: 'c'}}) + sage: P = D.path_semigroup() + sage: A = P.algebra(ZZ) + sage: A.homogeneous_component(3) + Free module spanned by [a*b*c, b*c*a, c*a*b] over Integer Ring + """ + basis = [] + for v in self._semigroup._quiver: + basis.extend(self._semigroup.iter_paths_by_length_and_startpoint(n, v)) M = CombinatorialFreeModule(self._base, basis, prefix='', bracket=False) M._name = "Free module spanned by {0}".format(basis) return M
, please?
The text "In addition, the free algebra of a subquiver coerces into the algebra" was a mistake. It was supposed to be "the free small category", but since it was wrongly written "free algebra", I did not searchreplace it into "In addition, the path semigroup of a subquiver coerces into the algebra.
I am now preparing a new commit changing this paragraph. In the meantime, please tell what was wrong with the homogeneous components.
comment:198 Changed 8 years ago by
Concerning the empty quiver:
sage: Q = DiGraph().path_semigroup() sage: Q Partial semigroup formed by the directed paths of Digraph on 0 vertices sage: A = Q.algebra(QQ) sage: A Path algebra of Digraph on 0 vertices over Rational Field sage: A.homogeneous_component(0) Free module spanned by [] over Rational Field sage: A.homogeneous_component(1) Free module spanned by [] over Rational Field
However, the attempt to construct a coercion of the path semigroup of an empty quiver into the path algebra of a nonempty quiver fails with an "empty set error". So, in the commit to come I'll also try to fix that corner case.
comment:199 followup: ↓ 203 Changed 8 years ago by
I think the problem with conversion of the path semigroup of the empty quiver into the path algebra of a nonempty quiver is this: The coercion framework tries to do a consistency check, for which it needs an element of the domain. But for the empty quiver, an_element()
rightfully fails with an empty set error.
Do you really think we should fix this corner case?
comment:200 Changed 8 years ago by
Concerning homogeneous components for quivers with loops or cycles: I see, the old code has run into an infinite loop, whereas the new doesn't. This change seems fine.
comment:201 Changed 8 years ago by
 Branch changed from public/combinat/quivers to u/SimonKing/ticket/12630
 Modified changed from 02/16/14 08:39:52 to 02/16/14 08:39:52
comment:202 Changed 8 years ago by
 Commit changed from f7fc2eca6347a5abbebcad50bc7abe41a73a60e2 to 823fff5635870f31cb6308b3ecb371b6899b5101
I have just pushed my changes (sorry, I keep forgetting how to push to a specific public branchunfortunately, the dev scripts keep pushing on my private branch even if the branch field of the ticket is public).
The new commit fixes the docs in a couple more places. I don't know if we really want to catch the corner case of coercing the path semigroup of an empty path (i.e., the empty set) into a path algebra. We could do so by making _coerce_map_from_
return a default conversion map rather than "True". I wouldn't care, though.
New commits:
823fff5  Some more doc fixes

comment:203 in reply to: ↑ 199 Changed 8 years ago by
Replying to SimonKing:
I think the problem with conversion of the path semigroup of the empty quiver into the path algebra of a nonempty quiver is this: The coercion framework tries to do a consistency check, for which it needs an element of the domain. But for the empty quiver,
an_element()
rightfully fails with an empty set error.Do you really think we should fix this corner case?
In a perfect world, the coercion framework would honor EmptySetError? ... Might be easy to fix. Otherwise, yes I guess ignoring the corner case is alright for now.
(In general I dislike the coercion framework using of element creation and duck typing as it does now; but that's a separate story).
comment:204 Changed 8 years ago by
Thanks for spotting the empty quiver issue. I wouldn't mind seeing that case removed for the time being, but a new ticket should be made in that case.
About merging develop: I was doing a lot of branch hopping yesterday, and I am really tired of waiting for Sage to recompile every time I'm doing that.
comment:205 Changed 8 years ago by
 Branch changed from u/SimonKing/ticket/12630 to public/combinat/quivers
 Commit changed from 823fff5635870f31cb6308b3ecb371b6899b5101 to a6b04c6c57b2362cbfa2e300a5d592ef79757fc8
New commits:
a6b04c6  a few more doc improvements

comment:206 followup: ↓ 207 Changed 8 years ago by
I changed the doc again. Simon, can you keep working on the public/combinat/quivers branch? Otherwise the branch field is getting changed over and over here  I certainly cannot push onto a branch in your namespace.
Do you think the following notions are now welldocumented enough: 1) what "path" means in the context of quivers; 2) what "partial semigroup" means and that the path semigroup is a such? By "welldocumented enough" I mean, in particular, that the documentation is in those places where one would be looking for it.
I don't understand why we have two ways to compute paths in a path semigroup:
def all_paths(self, start=None, end=None):
on the one hand, and
def iter_paths_by_length_and_startpoint(self, d, v): def iter_paths_by_length_and_endpoint(self, d, v):
on the other. Does the former have any advantages at all, such as speed in the acyclic case? All I can say is that it is broken even in the acyclic case:
sage: Q = DiGraph({i: {i+1: "a"+str(i)} for i in range(2)}) sage: Q.edges() [(0, 1, 'a0'), (1, 2, 'a1')] sage: Q.path_semigroup().all_paths() [e_0, a, 0, a*a, a*1, 0*a, 0*1, e_1, a, 1, e_2]
Apparently somewhere deep in the code it believes that every edge label is one character long. And it seems to check for acyclicity twice (and, for some reason, also checks for absence of loops?). Either way, is there a reason for this method to exist?
comment:207 in reply to: ↑ 206 ; followup: ↓ 208 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to fix or delete "all_paths()"
Replying to darij:
I changed the doc again. Simon, can you keep working on the public/combinat/quivers branch?
As I have stated above: I keep forgetting how to teach git to push to the right location, and the dev scripts will not push to a public place.
So, please tell me how I can push to a public branch.
I don't understand why we have two ways to compute paths in a path semigroup:
def all_paths(self, start=None, end=None):on the one hand, and
def iter_paths_by_length_and_startpoint(self, d, v): def iter_paths_by_length_and_endpoint(self, d, v):
I don't recall exactly, but if I recall correctly I added the iteration methods in order to have something that works in the acyclic case. I have just looked at the code: all_paths does not use the iterative methods. Perhaps it should!
All I can say is that it is broken even in the acyclic case:
sage: Q = DiGraph({i: {i+1: "a"+str(i)} for i in range(2)}) sage: Q.edges() [(0, 1, 'a0'), (1, 2, 'a1')] sage: Q.path_semigroup().all_paths() [e_0, a, 0, a*a, a*1, 0*a, 0*1, e_1, a, 1, e_2]
Wow, that's very bad and needs to be fixed. Note that list(Q.path_semigroup())
gives the correct result.
Apparently somewhere deep in the code it believes that every edge label is one character long.
It shouldn't.
And it seems to check for acyclicity twice
??
In all_paths
, I only see one location where it is tested (however, it is tested in each round of the recursion, which is bad).
(and, for some reason, also checks for absence of loops?).
If I recall correctly, when the code was written, the graph code did say that a loop does not count as a cycle. But apparently this has changed. So, perhaps we can remove the has_loops()
test.
Either way, is there a reason for this method to exist?
For all_paths
? Hm. When I think about it, I guess the iterator of the path semigroup is all what we need.
comment:208 in reply to: ↑ 207 Changed 8 years ago by
So, please tell me how I can push to a public branch.
This should do the job, I think:
git push trac HEAD:public/combinat/quivers
comment:209 Changed 8 years ago by
In my command history, I also found that git branch setupstreamto=public/public/combinat/quivers ticket/12630
should do, in the sense of "in future, git push
will push to the public branch".
I agree with your changes to the docs. Since we have the iterators, I think it makes sense to use them to replace all_paths
. I'd think we can remove that method.
comment:210 Changed 8 years ago by
Ouch, that's bad. The "all_paths" method is used to determine the number of elements of a path semigroup (see its __len__
method). Hence, we couldn't simply remove it. Or could we? We currently determine the number of elements by listing them. Instead, we could first test if the semigroup is finite, and if it is, then we could determine the cardinality by enumeration. That's not elegant, though: list(Q.path_semigroup())
would involve enumeration twice, namely when determining the length and when forming the list.
Is there a better way?
comment:211 Changed 8 years ago by
PS: Meanwhile cached methods are available for special python methods (including __len__
). Hence, we could easily cache the number of elements of a path semigroupwe don't need to enumerate it repeatedly when we ask for the length repeatedly.
comment:212 Changed 8 years ago by
Back to your example concerning a bug in all_paths: You define Q = DiGraph({i: {i+1: "a"+str(i)} for i in range(2)})
. By consequence, Q.edge_label(0,1)
does not return a list, but a single label. But all_paths
iterates over the labels of the edges between pairs of vertices. That's the wrong thing to do, of course.
Obvious fix: Do a type test, and only iterate if it is a list or tuple.
comment:213 Changed 8 years ago by
Oops! That was not a bug. I abused the DiGraph? constructor. I should have put the edge label into a list. Sorry!
The code checks acyclicity twice because first it checks if the path semigroup is finite and then it checks if the quiver is acyclic.
comment:214 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues fix or delete "all_paths()" deleted
comment:215 Changed 8 years ago by
 Commit changed from a6b04c6c57b2362cbfa2e300a5d592ef79757fc8 to 50eb7bde26c2a0c688e0500918597591097aa0cb
Branch pushed to git repo; I updated commit sha1. New commits:
50eb7bd  simplifying all_paths and improving more doc

comment:216 followup: ↓ 217 Changed 8 years ago by
So I assume this one is a real issue for a change:
sage: Q = DiGraph({1:{2:['a','b']}, 2:{3:['c']}}).path_semigroup() sage: M = Q.I(GF(3), 3) sage: N = Q.S(GF(3), 3) sage: M.quotient(N) Representation with dimension vector (2, 1, 0) sage: R = _ sage: R(M.an_element()) # wait RuntimeError: maximum recursion depth exceeded while calling a Python object
Also, please doublecheck my edits.
EDIT: smaller counterexample:
sage: Q = DiGraph({1: {}}).path_semigroup() sage: M = Q.I(GF(3), 1) sage: m = M.an_element() sage: R = M.quotient(M) sage: R(M.zero())
comment:217 in reply to: ↑ 216 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to Fix QuiverRepElement.__init__
Replying to darij:
Also, please doublecheck my edits.
The edits look fine to me. I don't know what to do here:
@@ 1822,6 +1835,8 @@ class QuiverRep_generic(Module): # TODO: This 'if' shouldn't need to be here, but sage crashes when # coercing elements into a quotient that is zero. Once Trac ticket # 12413 gets fixed only the else should need to execute. + # NOTE: This is no longer necessary. Keep around for speed or + # remove?  darij, 16 Feb 2014 if spaces[e[1]].dimension() == 0: maps[e] = spaces[e[0]].Hom(spaces[e[1]]).zero_element() else:
No idea if it improves speed when keeping it in.
EDIT: smaller counterexample:
sage: Q = DiGraph({1: {}}).path_semigroup() sage: M = Q.I(GF(3), 1) sage: m = M.an_element() sage: R = M.quotient(M) sage: R(M.zero())
It seems that either we need an _element_constructor_
method for QuiverRep_generic
, or we need to do something with QuiverRepElement.__init__
. Namely, the following works:
sage: z = R(M.zero()._elems) sage: z._elems {1: ()} sage: M.zero()._elems {1: (0)}
And similarly
sage: m = M.an_element() sage: R(m) <HANGS> sage: R(m._elems) Element of quiver representation sage: _._elems {1: ()} sage: m._elems {1: (1)}
I think according to the specification of a quotient Q of X, it should always be possible to convert any element of X into Q.
I suggest to do a typetest for the input of QuiverRepElement.__init__
.
comment:218 Changed 8 years ago by
No, it is worse. The following simply works:
sage: R.element_class(R, M.zero()) Element of quiver representation
Hence, your example fails before the element class of R comes into play.
comment:219 Changed 8 years ago by
It gets stranger and stranger.
sage: R.has_coerce_map_from(M) True sage: R.coerce_map_from(M) Homomorphism of representations of Multidigraph on 1 vertex sage: phi = _ sage: phi(M.zero()) Element of quiver representation
What else is happening in Parent.__call__
?
comment:220 Changed 8 years ago by
According to the traceback, sage.categories.morphism.CallMorphism._call_
is involved. It should not! After all, we even have a functioning coerce map.
comment:221 Changed 8 years ago by
 Work issues changed from Fix QuiverRepElement.__init__ to QuiverRepHom must not implement __call__
I found the problem!
QuiverRepHom
overrides __call__
, which is very bad. When implementing a map, one should only overload _call_
and _call_with_args
and a third method that I forgot and makes, e.g., a ring map applicable to ideals in the ring.
Why is that a problem in Parent.__call__
? Well, Parent.__call__
assumes that the convert map is wellimplemented and thus tries to save a few CPU cycles by directly calling _call_
(not __call__
) of the map.
Obvious solution: Move QuiverRepHom.__call__
to QuiverRepHom._call_
resp. QuiverRepHom._call_with_args
.
comment:222 Changed 8 years ago by
Something else needs a fix: Apparently coercion goes to the wrong direction, as there is a coercion from the path algebra of DiGraph({1:{2:['a','b']}}).path_semigroup()
to the path algebra of DiGraph({1:{2:['a']}}).path_semigroup()
. It should be opposite.
comment:223 Changed 8 years ago by
Aha! That's why: The _coerce_map_from_
method compares the underlying quivers by <=
. In the original implementation, we had a dedicated class for quivers, with a __cmp__
method. But now we are using DiGraph
, and their comparison is not what we want.
Hence, in _coerce_map_from_
we need to do what we used to do in __cmp__
we need a subgraph check.
comment:224 Changed 8 years ago by
 Commit changed from 50eb7bde26c2a0c688e0500918597591097aa0cb to b550c5013bef54098cc28c7a8ab34cf0f9fccdf9
comment:225 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues QuiverRepHom must not implement __call__ deleted
I have fixed and doctested the two remaining issues.
comment:226 followup: ↓ 227 Changed 8 years ago by
Thanks for fixing these!
What about this, do we consider it a bug?
sage: sage: P1 = DiGraph({1:{2:['a']}}).path_semigroup() sage: sage: P2 = DiGraph({1:{2:['a','b']}}).path_semigroup() sage: sage: A1 = P1.algebra(GF(3)) sage: sage: A2 = P2.algebra(GF(3)) sage: e1, e2, a, b = A2.gens() sage: A1(b) b sage: list(A1.basis()) [e_1, e_2, a]
(This is a conversion, not a coercion, map, at least.)
comment:227 in reply to: ↑ 226 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to Do not allow conversion of an arrow that is not in the quiver
Replying to darij:
What about this, do we consider it a bug?
sage: sage: P1 = DiGraph({1:{2:['a']}}).path_semigroup() sage: sage: P2 = DiGraph({1:{2:['a','b']}}).path_semigroup() sage: sage: A1 = P1.algebra(GF(3)) sage: sage: A2 = P2.algebra(GF(3)) sage: e1, e2, a, b = A2.gens() sage: A1(b) b sage: list(A1.basis()) [e_1, e_2, a]
Argh! Sure, that needs to be fixed.
comment:228 Changed 8 years ago by
Here's your problem:
sage: P1 = DiGraph({1:{2:['a']}}).path_semigroup() sage: P2 = DiGraph({1:{2:['a','b']}}).path_semigroup() sage: A1 = P1.algebra(GF(3)) sage: A2 = P2.algebra(GF(3)) sage: P2.inject_variables() Defining e_1, e_2, a, b sage: A1.monomial(b) b
comment:229 Changed 8 years ago by
... which boils down to
sage: A1._from_dict({b:A1.base_ring().one()}) b
comment:230 Changed 8 years ago by
 Commit changed from b550c5013bef54098cc28c7a8ab34cf0f9fccdf9 to 380ec0083cf4cfecd5ccd1317103ffd714ae94c9
Branch pushed to git repo; I updated commit sha1. New commits:
380ec00  Trac 12630: Monomials of path algebras must belong to the underlying quiver

comment:231 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues Do not allow conversion of an arrow that is not in the quiver deleted
If I understand correctly, _from_dict
is inherited, but _monomial
is dedicated to path algebras. And A1._monomial(b)
should of course try to convert b into an element of the underlying path semigroup, before constructing an element of itself.
Anyway: Fixed and added as test, needs review...
comment:232 Changed 8 years ago by
 Commit changed from 380ec0083cf4cfecd5ccd1317103ffd714ae94c9 to d8071d2de99458efcb8c7168b7bf6e260103156b
comment:233 Changed 8 years ago by
For the record: I agree with the two latest commits. From my perspective, the code is good to go, and I will focus on #15820 (providing a Cython version of paths).
comment:234 Changed 8 years ago by
 Commit changed from d8071d2de99458efcb8c7168b7bf6e260103156b to b2248e0da6dcd8b6c07ff91db00491ce673576e8
Branch pushed to git repo; I updated commit sha1. New commits:
b2248e0  fixes, mostly decorative

comment:235 Changed 8 years ago by
I've just pushed a number of minor doc improvements along with the occasional sourcecode edit (mainly base_ring.one()
instead of base_ring(1)
). This is a result of several hours of trying to find bugs, unsuccessfully. But there is a code smell which I'm really not happy with, despite it being mentioned in several comments in the code:
sage: Q = DiGraph({1:{2:['a'], 3:['b']}, 2:{4:['c']}, 3:{4:['d']}}).path_semigroup() sage: P = Q.P(QQ, 2) sage: v = P.zero() sage: v.set_element([1], 2) sage: v._elems {1: (), 2: (1), 3: (), 4: (0)} sage: P.zero()._elems {1: (), 2: (1), 3: (), 4: (0)}
So we can change the cached P.zero()
by using an exposed setelement method. Is there a way to prevent this from happening? I fear just mentioning it in comments is not enough; someone *will* trip over this.
This is as close as I can get to giving this a review (I fear I have neither time nor competence to do a systematic review of this). All in all, I'm seeing good and welldocumented code here; this certainly will be a very nice update to Sage.
comment:236 Changed 8 years ago by
 Status changed from needs_review to needs_work
 Work issues set to mutability of quiver representation elements
I think it is a accepted standard in Sage that zero()
and one()
are cached. And of course, cached elements should be immutable.
I see two ways to proceed. Either we replace set_element()
by _set_element()
, or we let QuiverRepElement
inherit from sage.structure.mutability.Mutability, and try to see if we can afford to let it be immutable by default. I'll try the latter first.
That said, I suppose we could completely remove the set_element
method: It is not used, except in doctests.
comment:237 Changed 8 years ago by
Speaking about mutability: I just see that quiver representation elements are hashableinheriting a hash from sage.structure.element.Element
. This relies on the string representation of the element. Anyway: If it is hashable, then it should be immutable.
comment:238 Changed 8 years ago by
Ouch. Making it inherit from sage.structure.mutability.Mutability
will be a problem: Mutability
provides a __reduce__
method, which would then be inherited by our class, thus breaking pickling.
So, I suppose we should simply "deprecate" set_element
by making it a private method.
comment:239 Changed 8 years ago by
Concerning hash: I believe it is bad that the hash depends on the name (that's a general problem, though):
sage: Q = DiGraph({1:{2:['a'], 3:['b']}, 2:{4:['c']}, 3:{4:['d']}}).path_semigroup() sage: P = Q.P(QQ, 2) sage: v = P.zero() sage: v.set_element([1], 2) sage: hash(v) 1669587902 sage: v.rename('foobar') sage: hash(v) 1969371895
So, I suggest that (in addition to making set_element
private) I implement a hash based on the data that is used for comparison.
comment:240 Changed 8 years ago by
 Commit changed from b2248e0da6dcd8b6c07ff91db00491ce673576e8 to 877777682486865f1bb401a70fc66260ff6e4094
Branch pushed to git repo; I updated commit sha1. New commits:
8777776  Trac #12630: make "set_element" a private method and implement hash

comment:241 Changed 8 years ago by
 Status changed from needs_work to needs_review
 Work issues mutability of quiver representation elements deleted
Done! Now the hash depends on the data being used for comparison, and not on the name. And set_element()
became _set_element()
. Question: Is
.. WARNING:: bla
the correct syntax for getting a warning into the doc?
New commits:
8777776  Trac #12630: make "set_element" a private method and implement hash

comment:242 Changed 8 years ago by
 Commit changed from 877777682486865f1bb401a70fc66260ff6e4094 to c5dd56af126669e380f5a9fbb1680447123d22cc
Branch pushed to git repo; I updated commit sha1. New commits:
c5dd56a  trying to be clearer about mutability in the doc

comment:243 Changed 8 years ago by
Yes, your warning syntax is correct for as far as I know.
I've fixed your doctest so that it doesn't set a bad example.
comment:244 followup: ↓ 245 Changed 8 years ago by
+1 on the recent changes (making the elements immutable; making set_element private, having a real hash function, ...)!
Just a random suggestions / questions:
 Maybe
QuiverRepElement
could inherit fromElementWrapper
? That would give it e.g. the hash for free.  Is speed critical enough to motivate inheriting from ModuleElement??
 is there a reason to use
UniqueFactory
rather thanUniqueRepresentation
?  _iadd_ and _isub_ change the element in place and therefore break immutability. Are those methods really necessary?
 In this file: vaector > vector
I am done with my teaching, and will have some time starting from March 1st. If the review is not finished by then, let me know which piece need review and I'll work on it.
Cheers,
Nicolas
comment:245 in reply to: ↑ 244 ; followup: ↓ 249 Changed 8 years ago by
Replying to nthiery:
 Maybe
QuiverRepElement
could inherit fromElementWrapper
? That would give it e.g. the hash for free.
No idea about this. I don't know how it works.
 Is speed critical enough to motivate inheriting from ModuleElement??
We are talking about QuiverRepElement
, right? Well, eventually this should become faster, too (but first, I'll focus on paths). After all, I plan to implement an F5 algorithm for modules over path algebras, and speed will be absolutely critical. But this could actually require more trickery (even freelists, to save the time that is vasted for creating and deleting elements)so much that it could be that internally I will use classes that will not be exposed to the user. So, perhaps internally I will use a class (certainly Cython cdef class) that has almost nothing to do with the current implementation.
 is there a reason to use
UniqueFactory
rather thanUniqueRepresentation
?
We have long code to create a cache key, and we have long code to create an object from a given key (which involves choosing among different implementations). I think UniqueFactory
is a better tool, since (in contrast to UniqueRepresentation
) it allows for a clean separation between the two requirements "create key" and "create object".
However, one should do one thing: Let it inherit from WithEqualityById
.
 _iadd_ and _isub_ change the element in place and therefore break immutability.
Ouch, that's bad.
Are those methods really necessary?
Well, _add_
should be enough (then, a+=b
will assign a+b
to a new instance under the old name a
, but would not change a
in place). Having in place addition mutate a
makes sense in some timecritical applications, but of course not when it is hashable (in particular when the hash is cached!).
I'll have a second look at the file, to see if there are more cases of mutation.
I am done with my teaching, and will have some time starting from March 1st. If the review is not finished by then, let me know which piece need review and I'll work on it.
Thank you in advance!
Best regards,
Simon
comment:246 Changed 8 years ago by
PS:
Yes, when I delete the _iadd_
method, then the current doctest of _iadd_
still works, but the line v+=w
will replace v
with a new instance, rather than mutate it.
comment:247 Changed 8 years ago by
 Commit changed from c5dd56af126669e380f5a9fbb1680447123d22cc to 48a8fed2d0503ea4bf4312c9a942c1fd024b0917
Branch pushed to git repo; I updated commit sha1. New commits:
48a8fed  Trac 12630: Remove mutating _iadd_ from QuiverRepElement

comment:248 Changed 8 years ago by
I have checked that _iadd_
and _isub_
have been the last places in which ._elems
is changed on an existing element.
New commits:
48a8fed  Trac 12630: Remove mutating _iadd_ from QuiverRepElement

comment:249 in reply to: ↑ 245 Changed 8 years ago by
Replying to SimonKing:
Replying to nthiery:
 Maybe
QuiverRepElement
could inherit fromElementWrapper
? That would give it e.g. the hash for free.No idea about this. I don't know how it works.
It's really just a simple base class that handle the trivial stuff when one wants to implement an element whose data structure consists of a single object (e.g. a tuple). See ElementWrapper??
We are talking about
QuiverRepElement
, right? Well, eventually this should become faster, too (but first, I'll focus on paths). After all, I plan to implement an F5 algorithm for modules over path algebras, and speed will be absolutely critical. But this could actually require more trickery (even freelists, to save the time that is vasted for creating and deleting elements)so much that it could be that internally I will use classes that will not be exposed to the user. So, perhaps internally I will use a class (certainly Cython cdef class) that has almost nothing to do with the current implementation.
Oh I see; I mistakenly thought it was modeling an element representing a quiver representation. Not an element thereof. Now I see the potential need for speed.
 is there a reason to use
UniqueFactory
rather thanUniqueRepresentation
?We have long code to create a cache key, and we have long code to create an object from a given key (which involves choosing among different implementations). I think
UniqueFactory
is a better tool, since (in contrast toUniqueRepresentation
) it allows for a clean separation between the two requirements "create key" and "create object".
Ok. At some point we should think about whether we could make a better distinction in UniqueRepresentation?. But that's of course for later.
Cheers,
Nicolas
comment:250 Changed 8 years ago by
Could someone please finish the review of this contribution? It already took more than 2 years from the original contribution to now.
comment:251 followup: ↓ 252 Changed 8 years ago by
What else needs to be reviewed?
comment:252 in reply to: ↑ 251 Changed 8 years ago by
Replying to tscrim:
What else needs to be reviewed?
Good question.
I think what happened before comment:230 is reviewed, some of the later stuff is reviewed as well. And of course one should test whether the branch is still compatible with the current develop branch, and if tests still pass.
comment:253 Changed 8 years ago by
In the good news department, all test pass on all added and modified files.
comment:254 followups: ↓ 257 ↓ 258 Changed 8 years ago by
 Commit changed from 48a8fed2d0503ea4bf4312c9a942c1fd024b0917 to b628ce36bc8f5f67a8eae6db125064a85cd85229
Branch pushed to git repo; I updated commit sha1. New commits:
81b351c  Merge branch 'public/combinat/quivers' of trac.sagemath.org:sage into public/combinat/quivers

16fa7c8  Added files to documentation.

9658528  Formatting and documentation tweaks, first pass.

a36d50b  Added title to morphisms and added tracking on conf.py for docbuild.

7330878  Minor tweaks. Moved data from __init__.py to representation.py.

14b73ae  Some more doc tweaks.

5338d69  Fixed multichar edge labels in all_paths.

2b26654  Added an __iter__() for algebra over nonzero graded components.

b628ce3  Added simple, injective, and projective for S, I, P resp.

comment:255 followup: ↓ 256 Changed 8 years ago by
 Reviewers changed from Simon King to Simon King, Travis Scrimshaw
I've made my pass through it. The first half of the commits are adding the files to the doc and doing doc formatting (and 80 width lines). I've made three changes:
 There was a bug in the
all_paths()
method would consider a single edge from1 > 2
with label'abc'
as 3 edges. Fixed.  For a path algebra
A
, theA[1]
worked. Solist(A)
would not error out (in fact, it would run for forever). I added an__iter__()
so that it would iterate over the nonzero graded components.  I made alias for
S
assimple
for a more natural name. Similarlyinjective
andprojective
forI
andP
respectively.
If you're happy with my changes, then I believe we can set this to a positive review.
comment:256 in reply to: ↑ 255 Changed 8 years ago by
Replying to tscrim:
I've made my pass through it.
Thank you very much!
The first half of the commits are adding the files to the doc and doing doc formatting (and 80 width lines).
Wait, did I really forget to include the new modules in the reference manual?? Strange.
If you're happy with my changes, then I believe we can set this to a positive review.
I'll have a look. Do all tests pass? Shall I retest it?
comment:257 in reply to: ↑ 254 Changed 8 years ago by
Replying to git:
Branch pushed to git repo; I updated commit sha1. New commits:
81b351c Merge branch 'public/combinat/quivers' of trac.sagemath.org:sage into public/combinat/quivers
What does this one do? What kind of merge was done there? Can I assume that this is nothing more but moving the existing code into another branch?
comment:258 in reply to: ↑ 254 Changed 8 years ago by
comment:259 Changed 8 years ago by
Could you elaborate on src/doc/en/reference/quivers/conf.py
? Again, this is something I don't know from when I have worked on the docs last time. I.e.: Can you please give me a pointer to a place in the developers guide or another piece of documentation, explaining how to add to the docs?
comment:260 Changed 8 years ago by
I get this error when building the doc ('make docclean' followed by 'make').
OSError: [quivers ] /home/king/Sage/git/sage/local/lib/python2.7/sitepackages/sage/quivers/representation.py:docstring of sage.quivers.representation:13: ERROR: Unknown target name: "e".
comment:261 Changed 8 years ago by
Aha!! I think it complains about this:
 each edge of the quiver is labelled with a nonempty string. The label cannot begin with 'e_' or contain '*' and distinct edges must have distinct labels.
Perhaps the 'e_'
should be enclosed in double backticks?
comment:262 Changed 8 years ago by
I agree with your changes, modulo the problem mentioned in the previous comment. Provided that the documentation builds and the tests pass, I'll post a fix for the 'e_'
problem and set it to positive review.
comment:263 Changed 8 years ago by
 Commit changed from b628ce36bc8f5f67a8eae6db125064a85cd85229 to f3402ef849622e1f5a7d88205c2911ecd6d03ffa
Branch pushed to git repo; I updated commit sha1. New commits:
f3402ef  Make documentation of quivers/representation.py build

comment:264 Changed 8 years ago by
Documentation does build, hence, I pushed the (presumably final) commit and will now wait for the test results.
New commits:
f3402ef  Make documentation of quivers/representation.py build

comment:265 Changed 8 years ago by
 Status changed from needs_review to positive_review
All tests pass! Hence, I suppose I can turn this into "positive review".
Thank you very much, to all contributors!
comment:266 Changed 8 years ago by
Yeah! Congratulations Simon!
comment:267 Changed 8 years ago by
Thanks Simon. The first commit was me merging the branch into my own (based off the current develop). As for the conf.py
, I just copied what was done in other folders (and at some point I realized it was needed, but I don't remember when). And all tests pass for me.
comment:268 Changed 8 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:269 Changed 8 years ago by
 Branch changed from public/combinat/quivers to f3402ef849622e1f5a7d88205c2911ecd6d03ffa
 Resolution set to fixed
 Status changed from positive_review to closed
comment:270 Changed 8 years ago by
 Commit f3402ef849622e1f5a7d88205c2911ecd6d03ffa deleted
Hi!
With #15801 and this ticket, I am getting the following error:
sage: Q = DiGraph({1:{3:['a']}, 2:{3:['b']}}).path_semigroup() sage: spaces = {1: QQ^2, 2: QQ^3, 3: QQ^2} sage: maps = {(1, 3, 'a'): (QQ^2).Hom(QQ^2).identity(), (2, 3, 'b'): [[1, 0], [0, 0], [0, 0]]} sage: M = Q.representation(QQ, spaces, maps) sage: TestSuite(M).run() Failure in _test_category: ... The following tests failed: _test_category
And indeed:
sage: M in M.category() False
This is due to the following (apparent?) inconsistency:
sage: M.category().base_ring() Path algebra of Multidigraph on 3 vertices over Rational Field sage: M.base_ring() Rational Field
Question: which one do we want to change?
Cheers,
Nicolas
comment:271 followup: ↓ 272 Changed 8 years ago by
We have
sage: M = QQ['t']^3 sage: M.base() Univariate Polynomial Ring in t over Rational Field sage: M.base_ring() Univariate Polynomial Ring in t over Rational Field
So, for consistency, I think we want that the base ring is the path algebra.
But, please fix this in #15801 and not here, as this ticket is closed already.
comment:272 in reply to: ↑ 271 Changed 8 years ago by
Replying to SimonKing:
So, for consistency, I think we want that the base ring is the path algebra.
Ok.
But, please fix this in #15801 and not here, as this ticket is closed already.
I agree the fix belongs to a followup ticket, and I am fine putting it
in #15801. Would you have a chance to handle it though? I had a quick
try, and am not sure of the repercussions: in particular, to avoid
ambiguities, should the current _base_ring
attribute and the
associated base_ring
method be renamed to something like
base_ring_of_representation
?
I fixed the docbuilding issues in #10963/#15801, and the latter is fair game for you if you feel like it.
Cheers,
Nicolas
comment:273 Changed 8 years ago by
Personally, I disagree (noncommutative base rings scare me, even as a noncommutative algebraist), but this is a tough question. For me, the base ring is the ring everything in sight is linear over (including noncanonical splittings and other auxiliary constructs). Whether QQ
or QQ['t']
is the base ring of QQ['t']^3
should really be up to the user to decide, not up to Sage; it depends on what one is doing. It being an attribute is a structural weakness of Sage that will bite us if we start doing serious algebra.
comment:274 Changed 8 years ago by
Thinking twice about my first feelings ... For a quiver
representation, I would also tend to have base_ring
return QQ above,
and the rep be accordingly in Modules(QQ)
. So far, in Sage,
Modules(R)
is about which ring R
we do the linear algebra with, compute
bases, etc. Later on we will have a proper hierarchy of categories for
representations (well, I have some stuff in the SageCombinat queue),
and then it will be time to put the quiver representations in the
appropriate category of this hierarchy.
The case of QQ[x]^3
is a bit different, since we really do the
linear algebra over QQ[x]
.
No strong opinion though ...
I just had a quick look at the patch, it seems to be very complete  thanks!
We are currently slowly getting a large project into sage dealing with (the combinatorics of) cluster algebras and quivers, see #10298. In particular, we also have a class quiver (#10538). I think both classes should be merged as they both deal with acyclic quivers. To be more precice, we deal with skewsymmetrizable matrices and the corresponding labeled quivers, while you seem to focus on the simplylaced version.
I can definitely to the review for this patch, and I propose to sit down (virtually together) and merge both concepts. This means make one being dependent of the other.
I also want to remark that Franco Saliola has as well quite some code on quiver representations that we might want to merge (if it is not subsumed). We also have currently a project of implementing the knitting algorithm for quivers without cycles which is currently based on Franco's implementation.