Opened 5 years ago

Closed 3 years ago

Last modified 3 years ago

#12630 closed enhancement (fixed)

Add representations of quivers and quiver algebras to sage

Reported by: JStarx Owned by: AlexGhitza
Priority: major Milestone: sage-6.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 Guay-Paquet, Aladin Virmaux Reviewers: Simon King, Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: f3402ef (Commits) Commit:
Dependencies: #12412, #12413, #14806, #15491, #15623, #15810 Stopgaps:

Description (last modified by SimonKing)

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.

Attachments (10)

12630_quivers.patch (266.6 KB) - added by JStarx 5 years ago.
trac_12630_quivers_v2.patch (266.7 KB) - added by chapoton 4 years ago.
quiver_distributed_code.patch (486.1 KB) - added by SimonKing 4 years ago.
Non-finished patch
trac_12630_fix_import_statement.patch (44.7 KB) - added by virmaux 4 years ago.
trac_12630_fix_some_errors.patch (3.8 KB) - added by virmaux 4 years ago.
trac12630_fix_import_statement_sk.patch (40.3 KB) - added by SimonKing 4 years ago.
Rebased patch. Fixes import statements, adds Quiver to global namespace
trac12630_refactor_code.2.patch (484.2 KB) - added by virmaux 4 years ago.
trac_12630_refactor.patch (11.0 KB) - added by virmaux 4 years ago.
trac12630_refactor_code.patch (483.2 KB) - added by SimonKing 4 years ago.
Combined refactoring patch
trac12630-quiver_representation.patch (127.9 KB) - added by SimonKing 4 years ago.
Sage infrastructure for Quiver representations, their homspaces and morphisms

Change History (284)

comment:1 Changed 5 years ago by JStarx

  • Status changed from new to needs_review

comment:2 Changed 5 years ago by stumpc5

  • Cc stumpc5 saliola added
  • Dependencies changed from 12412, 12413 to #12412, #12413
  • Description modified (diff)

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.

comment:3 Changed 5 years ago by SimonKing

  • Cc SimonKing added

comment:4 Changed 5 years ago by saliola

JStarx, are you coming to Sage Days 38? One of the themes is this sort of thing.

comment:5 follow-ups: Changed 5 years ago by JStarx

  • Description modified (diff)

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.

comment:6 in reply to: ↑ 5 Changed 5 years ago by stumpc5

Replying to 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

comment:7 follow-up: Changed 5 years ago by 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.

comment:8 in reply to: ↑ 7 Changed 5 years ago by SimonKing

Replying to 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.

comment:9 in reply to: ↑ 5 Changed 5 years ago by saliola

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 5 years ago by davidloeffler

  • 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/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.

comment:11 Changed 5 years ago by JStarx

  • Authors changed from JStarx to Jim Stark
  • 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 5 years ago by chapoton

  • 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:13 Changed 5 years ago by JStarx

  • Status changed from needs_work to needs_review

Done and done.

comment:14 Changed 5 years ago by chapoton

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 5 years ago by JStarx

comment:15 Changed 5 years ago by JStarx

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 5 years ago by SimonKing

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 follow-up: Changed 5 years ago by JStarx

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

comment:18 in reply to: ↑ 17 Changed 5 years ago by SimonKing

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

comment:19 Changed 5 years ago by JStarx

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 5 years ago by JStarx

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 5 years ago by saliola

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

comment:22 Changed 5 years ago by gmoose05

  • 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 4 years ago by chapoton

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

apply trac_12630_quivers_v2.patch

comment:24 Changed 4 years ago by chapoton

apply trac_12630_quivers_v2.patch

comment:25 Changed 4 years ago by gmoose05

  • Cc d.rupel@… added

comment:26 Changed 4 years ago by gmoose05

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.

comment:27 Changed 4 years ago by chapoton

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 4 years ago by chapoton

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 4 years ago by chapoton

comment:29 Changed 4 years ago by chapoton

new patch

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

comment:30 Changed 4 years ago by chapoton

for the bot:

apply trac_12630_quivers_v2.patch

comment:31 Changed 4 years ago by SimonKing

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

comment:32 Changed 4 years ago by SimonKing

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.

comment:33 follow-up: Changed 4 years ago by SimonKing

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.

comment:34 in reply to: ↑ 33 Changed 4 years ago by SimonKing

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

comment:35 Changed 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

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

comment:38 Changed 4 years ago by SimonKing

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.

Last edited 4 years ago by SimonKing (previous) (diff)

comment:39 Changed 4 years ago by SimonKing

  • 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, 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().

comment:40 follow-up: Changed 4 years ago by 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? ?

comment:41 in reply to: ↑ 40 Changed 4 years ago by SimonKing

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

comment:42 Changed 4 years ago by SimonKing

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

comment:43 Changed 4 years ago by SimonKing

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 4 years ago by vbraun

+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 4 years ago by SimonKing

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 follow-up: Changed 4 years ago by vbraun

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 4 years ago by SimonKing

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

I thought plural is good, because we have sage.algebras, sage.modules, sage.graphs, sage.categories, sage.rings, etc.

comment:48 Changed 4 years ago by vbraun

There is also sage.matrix, sage.geometry, sage.plot, sage.structure`, etc. As I said, totally inconsistent.

comment:49 Changed 4 years ago by SimonKing

  • Authors changed from Jim Stark to Jim Stark, Simon King
  • 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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • Cc mguaypaq added

comment:52 follow-up: Changed 4 years ago by SimonKing

  • Cc nthiery added

Some comments from a discussion with Nicolas:

  • Currently, we say FreeSmallCategory. Isn't it simply a semi-group?
  • If it is a semi-group (in particular, if it is declared in the category of semi-groups, 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 is Semigroups.Algebras.
  • Slight problem: Currently, the invalid path is not mentioned in the list of elements of the free small category / semi-group 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 4 years ago by virmaux

  • Cc virmaux added

comment:54 Changed 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

Currently, if a quiver Q1 is a sub-digraph (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 ; follow-up: Changed 4 years ago by saliola

Replying to SimonKing:

Some comments from a discussion with Nicolas:

  • Currently, we say FreeSmallCategory. Isn't it simply a semi-group?

If you add the zero element to your set of paths.

  • If it is a semi-group (in particular, if it is declared in the category of semi-groups, 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 is Semigroups.Algebras.
  • Slight problem: Currently, the invalid path is not mentioned in the list of elements of the free small category / semi-group 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 ; follow-up: Changed 4 years ago by SimonKing

Replying to saliola:

Replying to SimonKing:

Some comments from a discussion with Nicolas:

  • Currently, we say FreeSmallCategory. Isn't it simply a semi-group?

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?

Changed 4 years ago by SimonKing

Non-finished patch

comment:59 Changed 4 years ago by SimonKing

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 sub-digraphs) 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 4 years ago by saliola

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 semi-group?

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 4 years ago by SimonKing

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 follow-up: Changed 4 years ago by nthiery

+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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • Work issues changed from Split into different modules. Use parents and elements. to Fix doctests. Use existing infrastructure for homspace/morphism.

Changed 4 years ago by virmaux

comment:65 Changed 4 years ago by virmaux

  • 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 4 years ago by SimonKing

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 4 years ago by SimonKing

... which probably means you should add your names to the Author(s) field. We can then perhaps cross-review.

Changed 4 years ago by virmaux

comment:68 Changed 4 years ago by virmaux

  • Authors changed from Jim Stark, Simon King to Jim Stark, Simon King, Mathieu Guay-Paquet, Aladin Virmaux
  • 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 follow-up: Changed 4 years ago by 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 create QuiverRep (this is the preferred way), or import QuiverRep explicitly.

comment:70 in reply to: ↑ 69 Changed 4 years ago by saliola

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 create QuiverRep (this is the preferred way), or import QuiverRep explicitly.

I agree with this. The documentation for Quiver should then include pointers and examples on the other functions.

comment:71 Changed 4 years ago by SimonKing

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 4 years ago by SimonKing

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

Changed 4 years ago by SimonKing

Rebased patch. Fixes import statements, adds Quiver to global namespace

comment:73 Changed 4 years ago by SimonKing

  • 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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • 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

Last edited 4 years ago by SimonKing (previous) (diff)

Changed 4 years ago by virmaux

comment:76 Changed 4 years ago by virmaux

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 4 years ago by SimonKing

  • Description modified (diff)

Please post the little patch---for reviewing.

Moreover, on Trac, one can only replace patches (with the same name) that one has posted oneself. Hence, the name of the patch-to-be-applied has changed. So, we now have

Apply trac_12630_quivers_v2.patch 12630_refactor_code.2.patch

Changed 4 years ago by virmaux

comment:78 Changed 4 years ago by virmaux

Ok, sorry for that. So here is the little patch based on trac_12630_refactor_code.patch

comment:79 Changed 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

Another thing we might want to fix:

sage: show(Q2)
Traceback (most recent call last):
...
/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/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 4 years ago by SimonKing

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 4 years ago by virmaux

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 follow-up: Changed 4 years ago by 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):
Last edited 4 years ago by virmaux (previous) (diff)

comment:85 in reply to: ↑ 84 Changed 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • 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 4 years ago by SimonKing

Some random remarks on QuiverRep_generic:

  • My personal preference is to use UniqueRepresentation, not UniqueFactory, but personal preferences may be negotiable. I worry about pickling, since in fact there is no loads(dumps(...))==... test in the sources, and no TestSuite(...).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 some sage.categories.homset.Homset (or HomsetWithBase, because we have a base?)
  • sage.modules.module.Module has a base_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() and R.gens() do not return instances of R.element_class. So, TestSuite(R) will complain.
  • It seems that hom() and Hom() are not needed, since the default implementation would work (since there is _Hom_ implemented).

comment:90 Changed 4 years ago by SimonKing

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 4 years ago by SimonKing

  • 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 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • 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 sub-class 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.

Last edited 4 years ago by SimonKing (previous) (diff)

comment:95 Changed 4 years ago by SimonKing

  • 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 or QuiverRepHom. Instead, the user is supposed to first create a quiver Q, and then use R = Q.representation(...) or R.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 method natural_map() for the homset R.Hom(S). And this homset should be returned by a method R._Hom_(S). Caching is actually not needed, because this is done in sage.categories.homset.Hom. Hence, TODO: Remove the UniqueFactory!!
  • 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__ for FreeSmallCategory, because it needs to extend what DiGraph.__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 than self._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 with self.zero() and then change it in-place. That's of course not allowed with a cached element, and hence I had to replace self.zero() with a non-cached self().

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 trac12630-quiver_representation.patch

Last edited 4 years ago by SimonKing (previous) (diff)

comment:96 Changed 4 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to Coverage, doctest continuation

The patchbot was quite fast! Some plugins failed:

startup-modules

+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 start-up, 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.

Changed 4 years ago by SimonKing

Combined refactoring patch

comment:97 Changed 4 years ago by SimonKing

  • 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 trac12630-quiver_representation.patch

comment:98 Changed 4 years ago by SimonKing

I am sure that the doctest error found by the patchbot is unrelated with this ticket.

comment:99 Changed 4 years ago by SimonKing

  • Work issues changed from Coverage, doctest continuation to Remove UniqueFactory of Homspace, Homspace.__contains__, make TestSuite work

comment:100 follow-up: Changed 4 years ago by SimonKing

  • 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 4 years ago by SimonKing

Replying to SimonKing:

And part of the problem: QuiverHomspace does not inherit from Homset!!

But making it inherit means that one needs to overload __call__. Alas.

comment:102 follow-up: Changed 4 years ago by 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.

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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • 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 trac12630-quiver_representation.patch

comment:105 Changed 4 years ago by SimonKing

  • 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)
<ipython-input-10-4ebac6f179dc> in <module>()
----> 1 loads(dumps(S))

/home/simon/SAGE/prerelease/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/structure/sage_object.so in sage.structure.sage_object.loads (sage/structure/sage_object.c:11044)()

/home/simon/SAGE/prerelease/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/structure/factory.so in sage.structure.factory.lookup_global (sage/structure/factory.c:3123)()

AttributeError: ("'module' object has no attribute 'QuiverRep'", <built-in function lookup_global>, ('QuiverRep',))
Last edited 4 years ago by SimonKing (previous) (diff)

comment:106 Changed 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • 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 a TestSuite 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, because A.basis() (which is a free small category) is not initialised as an object of FiniteEnumeratedsets()---perhaps it should be. I'll check how difficult this would be.

comment:111 Changed 4 years ago by SimonKing

  • 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 4 years ago by SimonKing

  • 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 4 years ago by SimonKing

  • 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 4 years ago by SimonKing

Sage infrastructure for Quiver representations, their homspaces and morphisms

comment:114 Changed 4 years ago by SimonKing

  • 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. Hence self.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 trac12630-quiver_representation.patch

comment:115 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:116 Changed 4 years ago by SimonKing

Why is the patchbot trying to apply patches from the dependencies, even though they are closed since ages?

2013-08-21 23:04:31 +0100
Sage Patchbot 1.3.1
/mnt/storage2TB/patchbot/Sage/sage-5.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
    trac12630-quiver_representation.patch#6609dfb0c03f73fd66d83a15015064e5
hg qpop -a
no patches applied
hg qimport http://trac.sagemath.org/sage_trac/raw-attachment/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 sage-5.0!!!

comment:117 Changed 4 years ago by SimonKing

I opened a follow-up ticket, namely #15086 for a partial cythonification.

comment:118 follow-up: Changed 4 years ago by 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?

comment:119 in reply to: ↑ 118 Changed 4 years ago by SimonKing

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 only Quiver, but not all the other stuff such as FreeSmallCategory or QuiverRep) into the global namespace
  • make the modules in sage.quivers part of the documentation.

Best regards, Simon

comment:120 follow-up: Changed 4 years ago by chapoton

The patches seem to be completely broken right now. Tested on 5.12.beta5, and nothing works !

comment:121 in reply to: ↑ 120 Changed 4 years ago by SimonKing

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 follow-up: Changed 4 years ago by chapoton

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 4 years ago by SimonKing

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 4 years ago by SimonKing

  • Status changed from needs_review to needs_work

comment:125 Changed 4 years ago by SimonKing

  • 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 have---again by #14806---immutable 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 follow-up: Changed 3 years ago by SimonKing

  • Cc ncohen added

Hi Nathann!

I think you are the person to answer the questions I raised in my previous post and on sage-combinat-devel:

  • 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 sub-class Quiver of DiGraph providing these methods?

comment:127 in reply to: ↑ 126 ; follow-up: Changed 3 years ago by ncohen

Helloooooooo !!

I think you are the person to answer the questions I raised in my previous post and on sage-combinat-devel:

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 sub-class Quiver of DiGraph 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 ; follow-up: Changed 3 years ago by SimonKing

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" (non-underscore) 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 non-underscore method, then I'd say we can't work with digraph (and need a sub-class 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 non-underscore 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 non-underscore 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 ; follow-up: Changed 3 years ago by ncohen

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" (non-underscore) 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 non-underscore method, then I'd say we can't work with digraph (and need a sub-class 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 non-immutable 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 non-underscore 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 non-underscore 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 non-underscore methods?

You can definitely do that if the graph has mutable edge labels. In this case the non-underscore 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 ; follow-up: Changed 3 years ago by SimonKing

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 non-immutable 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 non-underscore methods.

That's not what I meant. You can of course obtain the edge label by non-underscore 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 not---if 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 sage-combinat-devel 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 short-cuts for creating a quiver representation. For example, the vertices of the quiver/digraph are in one-to-one 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 a memcpy of size g.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 low-dimensional 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 short-cut.

comment:131 in reply to: ↑ 130 ; follow-up: Changed 3 years ago by ncohen

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 backend-level. 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 not---if 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 sage-combinat-devel 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 short-cuts for creating a quiver representation. For example, the vertices of the quiver/digraph are in one-to-one 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 from UniqueRepresentation, and then G.free_small_category() should return FreeSmallCategory(G) if G is immutable, but FreeSmallCategory(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 ; follow-up: Changed 3 years ago by SimonKing

Hi Nathann,

I had recently focused on different things, but now want to resume work here---and 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 category

What 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 pre-existing 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 from UniqueRepresentation, and then G.free_small_category() should return FreeSmallCategory(G) if G is immutable, but FreeSmallCategory(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 cmp-classes of the graph"?

Note that I don't care about the possibility to have mutable labels and change these in-place. 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 ; follow-up: Changed 3 years ago by nthiery

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 category

What 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 pre-existing 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 3 years ago by ncohen

Hellooooooo Simon !

I had recently focused on different things, but now want to resume work here---and 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 cmp-classes 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 C-level 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 in-place. 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 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?

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 C-level 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 non-static 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 follow-up: Changed 3 years ago by SimonKing

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 follow-up: Changed 3 years ago by ncohen

+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 3 years ago by SimonKing

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 3 years ago by SimonKing

For the record: #15278 deals with hash and equality check of graphs.

comment:139 in reply to: ↑ 135 Changed 3 years ago by nthiery

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 3 years ago by SimonKing

  • 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 3 years ago by SimonKing

  • 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
ff82cf0Implementation of quivers as associative magmas
4cbb1b0trac #12630 Add representations of quivers and quiver algebras
Last edited 3 years ago by SimonKing (previous) (diff)

comment:142 in reply to: ↑ 133 ; follow-up: Changed 3 years ago by SimonKing

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 ; follow-up: Changed 3 years ago by nthiery

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 3 years ago by SimonKing

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 follow-up: Changed 3 years ago by 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.

comment:146 in reply to: ↑ 145 Changed 3 years ago by SimonKing

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 follow-up: Changed 3 years ago by 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.

comment:148 in reply to: ↑ 147 Changed 3 years ago by nthiery

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 3 years ago by git

  • Commit changed from fda4012f91c357f3db86fb07271573886ad0da74 to 72fb2eb71459f4ac76b0d922a7ad788c660a8017

Branch pushed to git repo; I updated commit sha1. New commits:

b6ed038trac #15623: Immutable graph backend for Posets
ee8c395Trac 15623: Let to_graph return an immutable graph
dcb8a0btrac #15623: rebase on 6.1.beta4
3531566trac #15623: Rebase on updated #15622
95cecd1trac #15623: Removing the hack from #15622, update a variable's name
dae53afMerge branch 'develop' into ticket/15623
c5b6d59Re-insert a bit of code that had been erroneously deleted in the previous merge commit
72fb2ebMerge branch 'ticket/15623' into ticket/12630

comment:150 Changed 3 years ago by SimonKing

  • 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 3 years ago by SimonKing

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 follow-up: Changed 3 years ago by SimonKing

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 paths-with-composition, and
  • .algebra(), that would be a short-cut 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 field k
  • Create a representation of P via P.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 follow-up: Changed 3 years ago by SimonKing

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 3 years ago by ncohen

  • .semigroup(),that returns the (partial) semigroup formed by the paths-with-composition, and
  • .algebra(), that would be a short-cut 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 ; follow-up: Changed 3 years ago by ncohen

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 3 years ago by ncohen

sinks and sources can make sense, though.

Nathann

comment:157 follow-up: Changed 3 years ago by nthiery

  • 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 ; follow-up: Changed 3 years ago by ncohen

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

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 3 years ago by nthiery

  • 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 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:161 in reply to: ↑ 158 ; follow-up: Changed 3 years ago by SimonKing

Replying to ncohen:

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

No problem with that.

OK, the names make sense, and Q.path_algebra(QQ) wouldn't be more than a short-cut 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 3 years ago by SimonKing

Replying to ncohen:

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.

OK, that makes sense.

comment:163 in reply to: ↑ 161 ; follow-up: Changed 3 years ago by 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 ?...

comment:164 in reply to: ↑ 163 ; follow-up: Changed 3 years ago by SimonKing

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 path-semigroup: After all, these are the elements of the path-semigroup.

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 ; follow-up: Changed 3 years ago by ncohen

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 path-semigroup: After all, these are the elements of the path-semigroup.

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 semi-group 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 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.

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 user-friendliness 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 ; follow-up: Changed 3 years ago by SimonKing

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 semi-group 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" path-semigroup.

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 user-friendliness 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 path-semigroup relies on the latter.

So, let me re-formulate my question to you.

  1. Do you want a new method called, say, DiGraph.all_quiver_paths() or DiGraph.all_arrow_sequences() that returns what the path semigroup needs?
  2. Do you want me to replace the current DiGraph.all_paths() so that it returns what the path semigroup needs?
  3. 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 ; follow-up: Changed 3 years ago by ncohen

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 path-semigroup relies on the latter.

So, let me re-formulate my question to you.

  1. Do you want a new method called, say, DiGraph.all_quiver_paths() or DiGraph.all_arrow_sequences() that returns what the path semigroup needs?

What about DiGraph.all_paths(edges=True) ?

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

  1. 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 semi-group 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 ; follow-up: Changed 3 years ago by SimonKing

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 sub-path 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 ; follow-up: Changed 3 years ago by ncohen

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 sub-path 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 3 years ago by SimonKing

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 itself O_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 follow-up: Changed 3 years ago by SimonKing

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 ; follow-up: Changed 3 years ago by ncohen

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 of all_paths. But in fact, the generic all_paths relies on neighbor_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 the all_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 follow-up: Changed 3 years ago by SimonKing

... 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 ; follow-up: Changed 3 years ago by ncohen

Hellooooo !

... or perhaps add a new method neighbor_out_arrows_iterator, that is to be used by all_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 self-intersect.

This being said, an iterator *IS* enough.

Nathann

Last edited 3 years ago by ncohen (previous) (diff)

comment:175 in reply to: ↑ 172 Changed 3 years ago by SimonKing

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 paths-of-arrows, but it currently gives paths-of-vertices.

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 ; follow-up: Changed 3 years ago by SimonKing

Replying to ncohen:

Paths. Not Walks. Paths do not self-intersect.

Paths, in the sense used by algebraists (path algebra) and topologists (fundamental group), do self-intersect.

comment:177 in reply to: ↑ 176 Changed 3 years ago by ncohen

Paths, in the sense used by algebraists (path algebra) and topologists (fundamental group), do self-intersect.

Oh. Well, they don't in graph theory.

Nathann

comment:178 Changed 3 years ago by ncohen

http://en.wikipedia.org/wiki/Longest_path_problem

This would be polynomial otherwise :-P

Nathann

comment:179 follow-ups: Changed 3 years ago by 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 "self-intersecting-arrow-paths-iterator" in this spot.

comment:180 in reply to: ↑ 179 ; follow-up: Changed 3 years ago by ncohen

Good news: all_paths is essentially used in only one spot in the quiver code. Hence, it would certainly be possible to have an "self-intersecting-arrow-paths-iterator" 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 ; follow-up: Changed 3 years ago by SimonKing

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 "self-intersecting-arrow-paths-iterator" 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 ; follow-up: Changed 3 years ago by ncohen

... 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 self-intersecting paths you will not get them by calling all_paths, and the current code is wrong ?..

Nathann

comment:183 in reply to: ↑ 180 ; follow-up: Changed 3 years ago by SimonKing

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 this all_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: arrow-paths versus vertex-paths, and simple versus self-intersecting.

comment:184 in reply to: ↑ 182 Changed 3 years ago by SimonKing

Replying to ncohen:

The bad news is that if you wanted self-intersecting 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 sub-class "Quiver" of DiGraph, and this sub-class overrides the all_paths method. But now, the plan is to not have a sub-class, since mathematically a quiver is a digraph (with multiple edges and loops).

comment:185 in reply to: ↑ 183 Changed 3 years ago by ncohen

Right. Spoiling the all_paths_iterator method with an optional argument would be an option. The all_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: arrow-paths versus vertex-paths, and simple versus self-intersecting.

Well... That's the kind of stuff that happens at Python-level... 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 3 years ago by SimonKing

  • Dependencies changed from #12412, #12413, #14806, #15491, #15623 to #12412, #12413, #14806, #15491, #15623, #15810

comment:187 Changed 3 years ago by git

  • Commit changed from 72fb2eb71459f4ac76b0d922a7ad788c660a8017 to dc973b43b0e24a8fc1c7446d296c743f9b9c630f

Branch pushed to git repo; I updated commit sha1. New commits:

e9796a1trac #15810: Immutable directed graphs should know that they are directed
d6ca86ctrac #15810: The graph data structures may have a ._directed but no .directed
a16f59fMerge branch 'ticket/15810' into ticket/12630, to make acyclicity tests work for immutable directed graphs
200b04bDo not introduce a separate class for quivers (use immutable DiGraph)
dc973b4Do not use "invalid path" for quivers. Fix all doctests.

comment:188 follow-up: Changed 3 years ago by SimonKing

  • 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 multi-digraph. We need it to be immutable, but meanwhile Sage provides immutable digraphs. So, we can use DiGraph 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 called path 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 sub-modules.

To be done in a follow-up 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 quotients---specifically 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 ; follow-up: Changed 3 years ago by JStarx

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 3 years ago by SimonKing

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 follow-up 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 3 years ago by darij

  • Branch changed from u/SimonKing/ticket/12630 to public/combinat/quivers
  • Commit changed from dc973b43b0e24a8fc1c7446d296c743f9b9c630f to edb52dfad756d6dceb3e97dc97fe665c36912b87

New commits:

edb52dfmostly grammatical fixes to documentation; not a review at all

comment:192 follow-up: Changed 3 years ago by 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 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 3 years ago by SimonKing

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 3 years ago by git

  • Commit changed from edb52dfad756d6dceb3e97dc97fe665c36912b87 to 461e1ed956a1b1623fa0e5d4a68e6c5379af4d68

Branch pushed to git repo; I updated commit sha1. New commits:

3542d37Merge branch 'develop' into quivers
461e1edupdate doctests

comment:195 Changed 3 years ago by git

  • Commit changed from 461e1ed956a1b1623fa0e5d4a68e6c5379af4d68 to f7fc2eca6347a5abbebcad50bc7abe41a73a60e2

Branch pushed to git repo; I updated commit sha1. New commits:

f7fc2ecallowed empty quiver; made homogeneous components work for quivers with cycles; fixed various places in doc

comment:196 Changed 3 years ago by darij

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

Last edited 3 years ago by darij (previous) (diff)

comment:197 Changed 3 years ago by SimonKing

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 search-replace 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 3 years ago by SimonKing

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 non-empty quiver fails with an "empty set error". So, in the commit to come I'll also try to fix that corner case.

comment:199 follow-up: Changed 3 years ago by SimonKing

I think the problem with conversion of the path semigroup of the empty quiver into the path algebra of a non-empty 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 3 years ago by SimonKing

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 3 years ago by SimonKing

  • 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 3 years ago by SimonKing

  • Commit changed from f7fc2eca6347a5abbebcad50bc7abe41a73a60e2 to 823fff5635870f31cb6308b3ecb371b6899b5101

I have just pushed my changes (sorry, I keep forgetting how to push to a specific public branch---unfortunately, 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:

823fff5Some more doc fixes

comment:203 in reply to: ↑ 199 Changed 3 years ago by nthiery

Replying to SimonKing:

I think the problem with conversion of the path semigroup of the empty quiver into the path algebra of a non-empty 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 3 years ago by darij

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.

Last edited 3 years ago by darij (previous) (diff)

comment:205 Changed 3 years ago by darij

  • Branch changed from u/SimonKing/ticket/12630 to public/combinat/quivers
  • Commit changed from 823fff5635870f31cb6308b3ecb371b6899b5101 to a6b04c6c57b2362cbfa2e300a5d592ef79757fc8

New commits:

a6b04c6a few more doc improvements

comment:206 follow-up: Changed 3 years ago by darij

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 well-documented enough: 1) what "path" means in the context of quivers; 2) what "partial semigroup" means and that the path semigroup is a such? By "well-documented 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 ; follow-up: Changed 3 years ago by SimonKing

  • 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 3 years ago by chapoton

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 3 years ago by SimonKing

In my command history, I also found that git branch --set-upstream-to=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 3 years ago by SimonKing

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 3 years ago by SimonKing

PS: Meanwhile cached methods are available for special python methods (including __len__). Hence, we could easily cache the number of elements of a path semigroup---we don't need to enumerate it repeatedly when we ask for the length repeatedly.

comment:212 Changed 3 years ago by SimonKing

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 3 years ago by darij

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 3 years ago by darij

  • Status changed from needs_work to needs_review
  • Work issues fix or delete "all_paths()" deleted

comment:215 Changed 3 years ago by git

  • Commit changed from a6b04c6c57b2362cbfa2e300a5d592ef79757fc8 to 50eb7bde26c2a0c688e0500918597591097aa0cb

Branch pushed to git repo; I updated commit sha1. New commits:

50eb7bdsimplifying all_paths and improving more doc

comment:216 follow-up: Changed 3 years ago by darij

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 double-check 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())
Last edited 3 years ago by darij (previous) (diff)

comment:217 in reply to: ↑ 216 Changed 3 years ago by SimonKing

  • Status changed from needs_review to needs_work
  • Work issues set to Fix QuiverRepElement.__init__

Replying to darij:

Also, please double-check 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 3 years ago by SimonKing

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 3 years ago by SimonKing

It gets stranger and stranger.

sage: R.has_coerce_map_from(M)
True
sage: R.coerce_map_from(M)
Homomorphism of representations of Multi-digraph on 1 vertex
sage: phi = _
sage: phi(M.zero())
Element of quiver representation

What else is happening in Parent.__call__?

comment:220 Changed 3 years ago by SimonKing

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 3 years ago by SimonKing

  • 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 well-implemented 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 3 years ago by SimonKing

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 3 years ago by SimonKing

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 3 years ago by git

  • Commit changed from 50eb7bde26c2a0c688e0500918597591097aa0cb to b550c5013bef54098cc28c7a8ab34cf0f9fccdf9

Branch pushed to git repo; I updated commit sha1. New commits:

50b0f84Trac 12630: Fix QuiverRepHom by renaming __call__ to _call_
b550c50Trac 12630: Fix coercion for path algebras

comment:225 Changed 3 years ago by SimonKing

  • Status changed from needs_work to needs_review
  • Work issues QuiverRepHom must not implement __call__ deleted

I have fixed and doc-tested the two remaining issues.

comment:226 follow-up: Changed 3 years ago by darij

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 3 years ago by SimonKing

  • 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 3 years ago by SimonKing

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 3 years ago by SimonKing

... which boils down to

sage: A1._from_dict({b:A1.base_ring().one()})
b

comment:230 Changed 3 years ago by git

  • Commit changed from b550c5013bef54098cc28c7a8ab34cf0f9fccdf9 to 380ec0083cf4cfecd5ccd1317103ffd714ae94c9

Branch pushed to git repo; I updated commit sha1. New commits:

380ec00Trac 12630: Monomials of path algebras must belong to the underlying quiver

comment:231 Changed 3 years ago by SimonKing

  • 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 3 years ago by git

  • Commit changed from 380ec0083cf4cfecd5ccd1317103ffd714ae94c9 to d8071d2de99458efcb8c7168b7bf6e260103156b

Branch pushed to git repo; I updated commit sha1. New commits:

5d6f2fdminor optimization, one() twice as fast
d8071d2minor edits to doc again

comment:233 Changed 3 years ago by SimonKing

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 3 years ago by git

  • Commit changed from d8071d2de99458efcb8c7168b7bf6e260103156b to b2248e0da6dcd8b6c07ff91db00491ce673576e8

Branch pushed to git repo; I updated commit sha1. New commits:

b2248e0fixes, mostly decorative

comment:235 Changed 3 years ago by darij

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 set-element 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 well-documented code here; this certainly will be a very nice update to Sage.

comment:236 Changed 3 years ago by SimonKing

  • 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 3 years ago by SimonKing

Speaking about mutability: I just see that quiver representation elements are hashable---inheriting 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 3 years ago by SimonKing

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 3 years ago by SimonKing

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 3 years ago by git

  • Commit changed from b2248e0da6dcd8b6c07ff91db00491ce673576e8 to 877777682486865f1bb401a70fc66260ff6e4094

Branch pushed to git repo; I updated commit sha1. New commits:

8777776Trac #12630: make "set_element" a private method and implement hash

comment:241 Changed 3 years ago by SimonKing

  • 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:

8777776Trac #12630: make "set_element" a private method and implement hash

comment:242 Changed 3 years ago by git

  • Commit changed from 877777682486865f1bb401a70fc66260ff6e4094 to c5dd56af126669e380f5a9fbb1680447123d22cc

Branch pushed to git repo; I updated commit sha1. New commits:

c5dd56atrying to be clearer about mutability in the doc

comment:243 Changed 3 years ago by darij

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 follow-up: Changed 3 years ago by nthiery

+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 from ElementWrapper? 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 than UniqueRepresentation?
  • _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 ; follow-up: Changed 3 years ago by SimonKing

Replying to nthiery:

  • Maybe QuiverRepElement could inherit from ElementWrapper? That would give it e.g. the hash for free.

No idea about this. I don't know how it works.

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 free-lists, 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 than UniqueRepresentation?

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 time-critical 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 3 years ago by SimonKing

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 3 years ago by git

  • Commit changed from c5dd56af126669e380f5a9fbb1680447123d22cc to 48a8fed2d0503ea4bf4312c9a942c1fd024b0917

Branch pushed to git repo; I updated commit sha1. New commits:

48a8fedTrac 12630: Remove mutating _iadd_ from QuiverRepElement

comment:248 Changed 3 years ago by SimonKing

I have checked that _iadd_ and _isub_ have been the last places in which ._elems is changed on an existing element.


New commits:

48a8fedTrac 12630: Remove mutating _iadd_ from QuiverRepElement

comment:249 in reply to: ↑ 245 Changed 3 years ago by nthiery

Replying to SimonKing:

Replying to nthiery:

  • Maybe QuiverRepElement could inherit from ElementWrapper? 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 free-lists, 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 than UniqueRepresentation?

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

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 3 years ago by SimonKing

Could someone please finish the review of this contribution? It already took more than 2 years from the original contribution to now.

comment:251 follow-up: Changed 3 years ago by tscrim

What else needs to be reviewed?

comment:252 in reply to: ↑ 251 Changed 3 years ago by SimonKing

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 3 years ago by tscrim

In the good news department, all test pass on all added and modified files.

comment:254 follow-ups: Changed 3 years ago by git

  • Commit changed from 48a8fed2d0503ea4bf4312c9a942c1fd024b0917 to b628ce36bc8f5f67a8eae6db125064a85cd85229

Branch pushed to git repo; I updated commit sha1. New commits:

81b351cMerge branch 'public/combinat/quivers' of trac.sagemath.org:sage into public/combinat/quivers
16fa7c8Added files to documentation.
9658528Formatting and documentation tweaks, first pass.
a36d50bAdded title to morphisms and added tracking on conf.py for docbuild.
7330878Minor tweaks. Moved data from __init__.py to representation.py.
14b73aeSome more doc tweaks.
5338d69Fixed multichar edge labels in all_paths.
2b26654Added an __iter__() for algebra over nonzero graded components.
b628ce3Added simple, injective, and projective for S, I, P resp.

comment:255 follow-up: Changed 3 years ago by tscrim

  • 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:

  1. There was a bug in the all_paths() method would consider a single edge from 1 -> 2 with label 'abc' as 3 edges. Fixed.
  2. For a path algebra A, the A[1] worked. So list(A) would not error out (in fact, it would run for forever). I added an __iter__() so that it would iterate over the non-zero graded components.
  3. I made alias for S as simple for a more natural name. Similarly injective and projective for I and P 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 3 years ago by SimonKing

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 re-test it?

comment:257 in reply to: ↑ 254 Changed 3 years ago by SimonKing

Replying to git:

Branch pushed to git repo; I updated commit sha1. New commits:

81b351cMerge 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 3 years ago by SimonKing

Replying to git:

16fa7c8Added files to documentation.

Is this how modules are added to the docs nowadays (:doc:`Quviers <quivers/index>`)? I didn't know that.

comment:259 Changed 3 years ago by SimonKing

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 3 years ago by SimonKing

I get this error when building the doc ('make doc-clean' followed by 'make').

OSError: [quivers  ] /home/king/Sage/git/sage/local/lib/python2.7/site-packages/sage/quivers/representation.py:docstring of sage.quivers.representation:13: ERROR: Unknown target name: "e".

comment:261 Changed 3 years ago by SimonKing

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 3 years ago by SimonKing

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 3 years ago by git

  • Commit changed from b628ce36bc8f5f67a8eae6db125064a85cd85229 to f3402ef849622e1f5a7d88205c2911ecd6d03ffa

Branch pushed to git repo; I updated commit sha1. New commits:

f3402efMake documentation of quivers/representation.py build

comment:264 Changed 3 years ago by SimonKing

Documentation does build, hence, I pushed the (presumably final) commit and will now wait for the test results.


New commits:

f3402efMake documentation of quivers/representation.py build

comment:265 Changed 3 years ago by SimonKing

  • 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 3 years ago by nthiery

Yeah! Congratulations Simon!

comment:267 Changed 3 years ago by tscrim

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 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:269 Changed 3 years ago by vbraun

  • Branch changed from public/combinat/quivers to f3402ef849622e1f5a7d88205c2911ecd6d03ffa
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:270 Changed 3 years ago by nthiery

  • 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 Multi-digraph on 3 vertices over Rational Field
sage: M.base_ring()
Rational Field

Question: which one do we want to change?

Cheers,

Nicolas

comment:271 follow-up: Changed 3 years ago by SimonKing

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 3 years ago by nthiery

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 3 years ago by darij

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.

Last edited 3 years ago by darij (previous) (diff)

comment:274 Changed 3 years ago by nthiery

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 Sage-Combinat 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 ...

Note: See TracTickets for help on using tickets.