Re: [sage-support] ordering of edges in incidence_matrix vs edges methods are difference
On 18/05/15 14:06, David Joyner wrote:
On Mon, May 18, 2015 at 7:51 AM, Vincent Delecroix
20100.delecr...@gmail.com wrote:
Moreover, for non oriented graph the Sage definition does not fit with
wikipedia... I opened the trac ticket
http://trac.sagemath.org/ticket/18440
Thank you.
In case it's of any interest, the code I've been using privately
allows for an arbitrary edge orientation (following Biggs). See below:
Your code does not follow wikipedia definition where the entries belong
to {0, 1, 2} when the graph is not oriented.
Vincent
--
You received this message because you are subscribed to the Google Groups
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] ordering of edges in incidence_matrix vs edges methods are difference
On Mon, May 18, 2015 at 7:51 AM, Vincent Delecroix 20100.delecr...@gmail.com wrote: Moreover, for non oriented graph the Sage definition does not fit with wikipedia... I opened the trac ticket http://trac.sagemath.org/ticket/18440 Thank you. In case it's of any interest, the code I've been using privately allows for an arbitrary edge orientation (following Biggs). See below: def incidence_value(Gamma, v, e, eo): This computes the incidence value of a vertex and edge of a graph Gamma with edge-orientation vector eo. INPUT: Gamma - graph v - vertex of Gamma e - edge of Gamma eo - a vector of 1's and -1's whose length is the number of edges in Gamma EXAMPLES: sage: Gamma = graphs.PaleyGraph(9) sage: E = Gamma.edges() sage: V = Gamma.vertices() sage: eo = [1]*len(E) sage: incidence_value(Gamma, V[2], E[3], eo) 0 sage: incidence_value(Gamma, V[8], E[3], eo) -1 E = Gamma.edges() if v in e: if v == e[0]: k = E.index(e) return eo[k] elif v == e[1]: k = E.index(e) return -eo[k] else: return 0 return 0 def incidence_matrix(Gamma, eo): This computes the incidence matrix (whose rows are indexed by edges and whose columns are indexed by vertices) of a graph Gamma with edge-orientation vector eo. The ordering of the edges and of the vertices is the same as Sage's vertices and edges methods. INPUT: Gamma - graph eo - a vector of 1's and -1's whose length is the number of edges in Gamma (ie, the size of Gamma, M) EXAMPLES: sage: Gamma = graphs.PaleyGraph(9) sage: E = Gamma.edges() sage: V = Gamma.vertices() sage: eo = [1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1] sage: B = incidence_matrix(Gamma, eo); B [ 1 -1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [-1 0 0 0 -1 -1 1 0 0 0 0 0 0 0 0 0 0 0] [ 0 1 0 0 1 0 0 -1 1 0 0 0 0 0 0 0 0 0] [ 0 0 0 0 0 0 0 1 0 1 -1 -1 0 0 0 0 0 0] [ 0 0 -1 0 0 0 0 0 0 -1 0 0 1 -1 0 0 0 0] [ 0 0 0 0 0 1 0 0 0 0 1 0 -1 0 1 0 0 0] [ 0 0 0 0 0 0 -1 0 0 0 0 0 0 0 -1 1 -1 0] [ 0 0 0 0 0 0 0 0 -1 0 0 1 0 0 0 -1 0 -1] [ 0 0 0 -1 0 0 0 0 0 0 0 0 0 1 0 0 1 1] sage: B.transpose()*B == Gamma.laplacian_matrix() True E = Gamma.edges() V = Gamma.vertices() IG = [[incidence_value(Gamma, v, e, eo) for v in V] for e in E] return matrix(QQ, IG).transpose() Vincent -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout. -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] ordering of edges in incidence_matrix vs edges methods are difference
On Mon, May 18, 2015 at 8:30 AM, Vincent Delecroix
20100.delecr...@gmail.com wrote:
On 18/05/15 14:06, David Joyner wrote:
On Mon, May 18, 2015 at 7:51 AM, Vincent Delecroix
20100.delecr...@gmail.com wrote:
Moreover, for non oriented graph the Sage definition does not fit with
wikipedia... I opened the trac ticket
http://trac.sagemath.org/ticket/18440
Thank you.
In case it's of any interest, the code I've been using privately
allows for an arbitrary edge orientation (following Biggs). See below:
Your code does not follow wikipedia definition where the entries belong
to {0, 1, 2} when the graph is not oriented.
I always use edge-oriented graphs for the calculations I need (which I
view as slightly different from directed graphs). What wikipedia
refers to as an oriented incidence matrix is what I use. It needs to
be fixed to follow the more general wikipedia definition.
Also, to be clear, I think what you are calling a graph in your
sagetrac ticket, some people call a multi-graph. And what you are
calling an oriented graph in your sagetrac ticket, includes
edge-oriented graphs, signed graphs, and directed graphs. If that is
incorrect, please let me know.
Vincent
--
You received this message because you are subscribed to the Google Groups
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an
email to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
--
You received this message because you are subscribed to the Google Groups
sage-support group.
To unsubscribe from this group and stop receiving emails from it, send an email
to sage-support+unsubscr...@googlegroups.com.
To post to this group, send email to sage-support@googlegroups.com.
Visit this group at http://groups.google.com/group/sage-support.
For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] ordering of edges in incidence_matrix vs edges methods are difference
Hello, This looks like a bug in the method incidence_matrix itself def incidence_matrix(...): ... cols.sort() return matrix(cols, sparse=sparse).transpose() In other words, the matrix is sorted before being returned and there is no correspondance with anything! Vincent PS: BTW, this method is very badly implemented... On 18/05/15 13:05, David Joyner wrote: Hi all: This issue is undocumented and seems odd to me. I could not find it mentioned in sage-support before. sage: Gamma1 = graphs.CompleteGraph(4); Gamma1 Complete graph: Graph on 4 vertices sage: V1 = Gamma1.vertices(); V1 [0, 1, 2, 3] sage: E1 = Gamma1.edges(); E1 [(0, 1, None), (0, 2, None), (0, 3, None), (1, 2, None), (1, 3, None), (2, 3, None)] sage: Gamma1.incidence_matrix() [-1 -1 -1 0 0 0] [ 0 0 1 -1 -1 0] [ 0 1 0 0 1 -1] [ 1 0 0 1 0 1] In other words, if you look at the ordering of the edges of Gamma1 determined by the incidence matrix that Sage returns, the first edge (indicated by the first column) is (0,3). However, if you look at the ordering of the edges of Gamma1 determined by the edges method, the first edge is (0,1). Maybe not a bug but an unusual feature? - David Joyner -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
Re: [sage-support] ordering of edges in incidence_matrix vs edges methods are difference
Moreover, for non oriented graph the Sage definition does not fit with wikipedia... I opened the trac ticket http://trac.sagemath.org/ticket/18440 Vincent -- You received this message because you are subscribed to the Google Groups sage-support group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-support+unsubscr...@googlegroups.com. To post to this group, send email to sage-support@googlegroups.com. Visit this group at http://groups.google.com/group/sage-support. For more options, visit https://groups.google.com/d/optout.
