#8372: split up incidence_matrix() over graph.py and digraph.py
-------------------------------+--------------------------------------------
Reporter: mvngu | Owner: rlm
Type: enhancement | Status: needs_info
Priority: major | Milestone: sage-4.3.4
Component: graph theory | Keywords:
Author: Minh Van Nguyen | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
-------------------------------+--------------------------------------------
Changes (by rbeezer):
* status: needs_review => needs_info
Comment:
Hi Minh,
This looks real nice on a first pass. You are the king of documentation.
Two questions.
Columns of the matrix get sorted (as column vectors) once they are all
built. I recognize this is the current behavior, and that this makes a
"pretty" matrix, highlighting structure. But now it is much harder to
connect columns back to the edges they correspond to.
For example, some of your tests work with vertex degrees. You don't need
to sort the outputs before checking equality because you know the results
are in the order given by the vertex iterator. Why not preserve that
quality with respect to the columns/edges? Anybody who wants sorted
columns can do it themselves, but it strikes me it'll be harder to get the
edges back from the adjacencies as written.
Second question. I'm uncertain about putting a "2" into the incidence
matrix for a loop. I'd prefer to think of a loop in a digraph (one
without multiple edges) as a directed edge back to the same vertex, so I'd
sum +1 and -1 at that vertex (to get zero).
You can construct a {{{DiGraph}}} from an incidence matrix, and this form
of construction explicitly checks for a single +1 and a single -1 in each
column. So the (hopefully) inverse processes below don't work. My
suggestion of a zero breaks also. Maybe throw an error for a
{{{DiGraph}}} with loops? Using a zero preserves the property that the
sum of the rows of the matrix is the all-zeros vector, which I think is as
important some of the column-sum properties. Haven't thought about how
all this affects getting the Laplacian as the product of the incidence
matrix with its transpose (which might make a nice doctest).
{{{
sage: D=DiGraph({0:[0], 1:[2]})
sage: D.incidence_matrix()
[ 0 2]
[-1 0]
[ 1 0]
sage: E=DiGraph(D.incidence_matrix())
<BOOM>
ValueError: Non-symmetric or non-square matrix assumed to be an incidence
matrix: There must be two nonzero entries (-1 & 1) per column.
}}}
Rob
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8372#comment:2>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
