davidp wrote:
>> I haven't seen a definition of the laplacian matrix for looped digraphs,
>> but sure, okay, I assume this is standard, then? I don't think the
>> laplacian_matrix function calculates this quantity for digraphs. This
>> might be a bug, then.
>
> It is standard to take the Laplacian to be D - A where D is the
> diagonal matrix of out-degrees (or sometimes in-degrees---I much
> prefer the former) and A is the adjacency matrix. Thus, the Laplacian
> does not see loops.
Okay, D-A is the definition that I use, but I usually am dealing with
simple (undirected, no loops) graphs, so these issues don't come up. I
imagine that the laplacian function was written with this in mind, but
was then just applied to digraphs as well. So this is the third bug
this thread is bringing up. Thanks! (Is someone creating trac tickets
for all of these? :)
>
>> So is this laplacian matrix wrong?
>
> Yes. The 1,1 entry of the adjacency matrix is 1, the out-degree of
> the first vertex is 2, and 2-1=1. So the 1,1 entry of
> G.laplacian_matrix() is wrong.
>
>> sage: G = DiGraph({1:{1: 1, 2: 1}, 2:{1:1}})
>> sage: G
>> Looped digraph on 2 vertices
>> sage: G.laplacian_matrix()
>>
>> [ 2 -1]
>> [-1 1]
>>
>
>> Why do you expect that DiGraph(G.laplacian_matrix())
>> should give you back the same graph?
>>
>
> Except for loops, I can reconstruct a graph from its Laplacian. So I
> expect DiGraph(G.laplacian_matrix()) to return the graph, removing
> loops if present.
The problem here is that when Sage is constructing the DiGraph, it has
no idea that the matrix you are handing it is a laplacian matrix from
another graph. It just sees the matrix. Should we make it try to
determine if the arbitrary matrix it is given could be interpreted as a
laplacian matrix? Already, if we have a non-square matrix, Sage tries
to guess that it is an incidence matrix, but if the matrix is square,
nonnegative, then we have multiple edges, but square and a negative
entry gives a non-multiple-edge graph with weights. Already things are
getting confusing; adding one more special case where a matrix that
happens to look like a laplacian matrix gives yet a different graph
seems to be pushing things farther in a confusing direction. We've
already had other bug reports (from William even!) that are exactly like
yours, where the auto-guessing was either doing too much or not enough,
and it was confusing.
Rather, I'd suggest that we introduce explicit functions that declare
the intent. Maybe something like:
DiGraph(laplacian=my_matrix)
or
DiGraph.from_laplacian(my_matrix)
which then interprets the matrix as a laplacian matrix.
What do you think? Any other graph theorists want to chime in?
We could have:
DiGraph(incidence_matrix=my_matrix)
DiGraph(laplacian_matrix=my_matrix)
DiGraph(adjacency_matrix=my_matrix)
and they would all do exactly what it looks like: make the graph so that
the incidence, laplacian, or adjacency matrices are the same as the
input matrix.
>
> About the edge labels: the negative entries in the Laplacian come from
> subtracting the adjacency matrix. They are the negatives of the
> number of edges connecting a vertex to adjacent vertices. The edge
> labels should tell me how many edges connect two vertices. This is
> pretty standard, and I have never seen the other convention (negative
> labels) in mathematical papers.
Of course, weights can mean many, many different things, not just the
number of edges between two vertices (think floating point weights, for
example, in a distance graph). DiGraph tries to make sense of this
arbitrary matrix it was given, and we certainly don't want to say that
negative weights are impossible for someone to use. If some entries are
negative, then it doesn't make sense to view it as the number of edges,
unless you are going to encode in a guess that the matrix just might be
a laplacian matrix.
Thanks,
Jason
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to
sage-devel-unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
