Add representations of quivers and quiver algebras to sage

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

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 Auslander-Rieten 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.

Depends on #12412 Depends on #12413 Depends on #14806 Depends on #15491 Depends on #15623 Depends on #15810

CC: @jhpalmieri @williamstein @stumpc5 @saliola @simon-king-jena @sagetrac-gmoose05 @sagetrac-drupel @mguaypaq @nthiery @avirmaux @nathanncohen

Component: algebra

Keywords: algebra, quiver, module, days49

Author: Jim Stark, Simon King, Mathieu Guay-Paquet, Aladin Virmaux

Branch: f3402ef

Reviewer: Simon King, Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/12630

stumpc5 commented 12 years ago

comment:2

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 skew-symmetrizable matrices and the corresponding labeled quivers, while you seem to focus on the simply-laced 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.

stumpc5 commented 12 years ago

Description changed:

--- 
+++ 
@@ -3,3 +3,7 @@
 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 Auslander-Rieten 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.
+
+Let me know what you think,
+
+best, Christian

stumpc5 commented 12 years ago

Changed dependencies from 12412, 12413 to #12412, #12413

saliola commented 12 years ago

comment:4

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)

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:5

Correct me if I'm wrong, but my understanding is that a simply-laced 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 simply-laced 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.

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

Description changed:

--- 
+++ 
@@ -3,7 +3,3 @@
 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 Auslander-Rieten 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.
-
-Let me know what you think,
-
-best, Christian

stumpc5 commented 12 years ago

comment:6

Replying to @sagetrac-JStarx:

Correct me if I'm wrong, but my understanding is that a simply-laced 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 simply-laced 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 skew-symmetric 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 simply-laced. One can also think of quivers (like in type B) coming from a skew-symmetrizable matrix (i.e., M such that DM is skew-symmetric 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 skew-symmetrizable 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 Auslander-Reiten quiver -- we are also currently preparing a paper where we give an alternative combinatorial view on Auslander-Reiten translates in finite types -- any further ideas, maybe beyond finite types)?

Best, Christian

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:7

Unfortunately I'm no expert on Auslander-Reiten 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.

simon-king-jena commented 12 years ago

comment:8

Replying to @sagetrac-JStarx:

Unfortunately I'm no expert on Auslander-Reiten 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.

saliola commented 12 years ago

comment:9

Replying to @sagetrac-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?

11d1fc49-71a1-44e1-869f-76be013245a0 commented 12 years ago

Reviewer: PatchBot

11d1fc49-71a1-44e1-869f-76be013245a0 commented 12 years ago

Work Issues: doctest failure

11d1fc49-71a1-44e1-869f-76be013245a0 commented 12 years ago

comment:10

A doctest fails on 5.0.beta7:

sage -t  -force_lib devel/sage-12630/sage/modules/quiver_module.py
**********************************************************************
File "/storage/masiao/sage-5.0.beta7-patchbot/devel/sage-12630/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.

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:11

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.

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

Changed work issues from doctest failure to none

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

Changed author from JStarx to Jim Stark

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

Changed reviewer from PatchBot to none

fchapoton commented 12 years ago

comment:12

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..)

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:13

Done and done.

fchapoton commented 12 years ago

comment:14

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)

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:15

Attachment: 12630_quivers.patch.gz

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.

simon-king-jena commented 12 years ago

comment:16

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.

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:17

Innards of my code (line 1047). Why would only the first matter?

simon-king-jena commented 12 years ago

comment:18

Replying to @sagetrac-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 non-unique 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 non-ordered 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 non-unique string representation of the cache key). But if time is no problem, then using sorted tuples in the cache keys is fine.

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:19

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.

1c82297e-a663-493c-af7c-8b70b8865e38 commented 12 years ago

comment:20

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.

saliola commented 12 years ago

comment:21

Hello everyone,

I just want to point out that development of this patch is continuing on the sage-combinat 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_interface-fs.patch
12630_quivers_review-fs.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 re-organization 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

a9a57cdf-9183-46c4-a1f6-41c1b5271dce commented 12 years ago

comment:22

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

fchapoton commented 11 years ago

comment:23

Here is a new patch, where all tests pass on 5.6.

apply trac_12630_quivers_v2.patch

fchapoton commented 11 years ago

comment:24

apply trac_12630_quivers_v2.patch

a9a57cdf-9183-46c4-a1f6-41c1b5271dce commented 11 years ago

comment:26

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 vice-versa.

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.

fchapoton commented 11 years ago

comment:27

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

fchapoton commented 11 years ago

comment:28

Hello,

There is a problem here, found by pyflakes:

sage/modules/quiver_module.py:6655: 
local variable 'H' is assigned to but never used

fchapoton commented 11 years ago

Attachment: trac_12630_quivers_v2.patch.gz

fchapoton commented 11 years ago

comment:29

new patch

with correction of a small problem in the doc formatting
with unused local variable assignement being commented

fchapoton commented 11 years ago

comment:30

for the bot:

apply trac_12630_quivers_v2.patch

simon-king-jena commented 11 years ago

comment:31

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 sub-class of DiGraph) 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 a UniqueRepresentation 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 a QuiverPath is element of a Quiver.
Why do you use UniqueRepresentation on QuiverPath? 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 non-commutative 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 afore-mentioned 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 non-commutative 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 from DiGraph (this is what you do) and should inherit from Parent, being initialised in the category AssociativeMagmas() (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 n-adic 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...

simon-king-jena commented 11 years ago

comment:32

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 sub-class of DiGraph.

simon-king-jena commented 11 years ago

comment:33

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 quiver-the-associative-magma, then it should be put into the same section (sage.magmas or sage.monoids) and used as element_class of quiver-the-associative-magma; but even in this case, QuiverPath and quiver-the-associative-magma should be defined in different files, so that it will later be easier to change QuiverPath 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.

simon-king-jena commented 11 years ago

comment:34

Replying to @simon-king-jena:

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:

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 afore-mentioned paths), sage.quivers.representation (modules for acyclic quivers), sage.quivers.algebra (path algebras, not necessarily acyclic), and later modules for finite-dimensional quotient algebras, their elements and modules.

Would you mind if I provide a patch that changes the code accordingly?

simon-king-jena commented 11 years ago

comment:35

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)?

simon-king-jena commented 11 years ago

comment:36

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.

simon-king-jena commented 11 years ago

comment:37

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)
<ipython-input-7-82cae30af75f> in <module>()
----> 1 c.add_cycle

<ipython-input-5-2839f68577a9> 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

simon-king-jena commented 11 years ago

comment:38

I am now experimenting with the following setting:

I suggest to let Quiver inherit from UniqueRepresentation, DiGraph and Parent.
In your UniqueFactory, you create a key for caching by creating a DiGraph 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 a DiGraph (namely a quiver). So, we create a new Quiver instance Q, initialise Q as a DiGraph 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.

simon-king-jena commented 11 years ago

Changed dependencies from #12412, #12413 to #12412, #12413, #14535

simon-king-jena commented 11 years ago

comment:39

I suggest to add #14535 as a dependency. It allows to create immutable graphs.

If I understood correctly, sage-combinat-devel 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 sub-class "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 on DiGraph.
In contrast to Jim's code, QuiverPath should be an element, namely an element of the afore-mentioned 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 and QuiverAlgebra to the acyclic case.
"QuiverMonoid" should be a unique parent. I suggest using UniqueRepresentation, 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 a DiGraph. Of course, it can return the underlying quiver by M.quiver() (which could actually be identical with the graph used as a key when creating M), and M is uniquely determined by M.quiver().

simon-king-jena commented 11 years ago

Work Issues: Split into different modules. Use parents and elements.

fchapoton commented 11 years ago

comment:40

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 ?

simon-king-jena commented 11 years ago

comment:41

Replying to @fchapoton:

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 to-be-created 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?

simon-king-jena commented 11 years ago

comment:42

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 F-the-parent would be used for the paths in F, while F.element_class of F-the-category 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 "quiver-the-graph": 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 "quiver-the-associative-magma", 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.

sagemath / sage

Add representations of quivers and quiver algebras to sage #12630