On Wed, Mar 28, 2012 at 01:36:11AM -0700, Frédéric Chapoton wrote:
> I have found the following wrong behaviour on sage 4.8, without
> sage-combinat
>
> sage: P=DiGraph([[0,1]])
> sage: Q=P.cartesian_product(P)
> sage: len(Q.edges())
> 0
>
> The result is a disconnected union of 4 points.
> This should be a directed square, with 4 edges.
Definitely a bug! Please open a ticket.
In the loop used to create the edges in the cartesian_product method,
only forward edges are considered, which is wrong for directed graphs:
for i in range(len(verts)):
for j in range(i): # j should range through all of verts!!!!!
Once the graph G is created, the whole end of this method would be
best rewritten as something like:
G.add_vertices( (u,v) for u in self.vertex_iterator() for v in
other.vertex_iterator() )
G.add_edges( ((u,v), (u1,v)) for (u,u1) in self .edge_iterator() for v
in other.vertex_iterator() )
G.add_edges( ((u,v), (u,v1)) for (v,v1) in other.edge_iterator() for u
in self .vertex_iterator() )
By the way: should cartesian_product handle labels?
> By the way, I would like to use that to define the product of posets, by
> taking the product of hasse diagrams. This may be useful to somebody else?
That's a rather fundamental operation on posets, so yes, definitely. I
am just not 100% sure about the name, since there are several possible
product orders (this one, lex, ...).
Note also that posets are parents. So they already are endowed with a
cartesian product construction, though at the moment the construction
is done only at the level of the category Sets:
sage: P = Poset([[0,1], [[0,1]]])
sage: Q = P.cartesian_product(P,P); Q
The cartesian product of (Finite poset containing 2 elements, Finite poset
containing 2 elements)
sage: Q.category()
Category of Cartesian products of sets
sage: Q.__class__
<class 'sage.sets.cartesian_product.CartesianProduct_with_category'>
It would be natural to implement the construction for posets too (by
adding a CartesianProducts nested class in the Posets category, and
implementing the comparison methods there). To get a full featured
poset, we probably want this method to return a FinitePoset; but this
is getting a bit tricky.
Hmm. For the moment, just implement cartesian_product as you meant to,
but either use another name for the method, or implement the n-ary
product, so as not to remove features from the current
cartesian_product.
Cheers,
Nicolas
--
Nicolas M. Thiéry "Isil" <[email protected]>
http://Nicolas.Thiery.name/
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
