Re: Bipartite graphs in Sage
David Joyner
Robert Miller says instead of me, since he
knows the code much much better. I'm cc'ing this
back to sage-devel; hope you don't mind.
There are several places where bipartite graphs
differ (at least in the literature) from regular graphs.
For example, usually the bipartite graph's adjacency matrix
is not square. Also, the vertices are usually drawn
using 2 colors, so the plot methods might be
different. Neither of these seem to be implemented
in Sage. (Also, the docstring has my favorite
self-reference:
sage: BipartiteGraph?
yields:
...
Docstring:
Create a bipartite graph. See documentation: BipartiteGraph?
...
Also, the EXAMPLE is not formatted correctly.)
As for usage, the Tanner graph of a binary code is
the bipartite graph whose adjacency matrix is the
check matrix of the code. I'm sure there are many other
applications but that is the one that first springs to mind.
On Sat, Feb 27, 2010 at 8:49 AM, Nathann Cohen <nathan...@gmail.com> wrote:
> Hello everybody !!!
>
> I followed your conversation on Sage-devel (http://bit.ly/bHTOHm), and
> I felt a bit as an outsider as I never used this class.. Could you
> tell me what you expect from it, or what you use it for ? I can not
> dream of a situation in which I would prefer it to the usual Graph
> class.....
>
> Thank you :-)
>
> Nathann
>
Robert Bradshaw
rather than descend from it. This way at least one wouldn't ever
accidently get incorrect answers when calling graph methods that have
different definitions in the bipartite case (including methods that
may in the future get added to Graph).
- Robert
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
Rob Beezer
> There are several places where bipartite graphs
> differ (at least in the literature) from regular graphs.
> For example, usually the bipartite graph's adjacency matrix
> is not square.
I think an "adjacency matrix" should always be square. But for a
bipartite graph if you order the vertices consecutively within the two
parts of the bipartition, then you get a block matrix with zero
matrices in the northwest and southeast corners. And the other two
corners are transposes of each other (but not square when the
bipartite sets are different sizes).
This is in the BipartiteGraph class as "reduced_adjacency_matrix()."
I can't recall ever seeing this matrix given a name, so I don't know
if this is how one would expect to find it. In the research for your
graph theory book have you learned what others call it?
Rob
Jason Grout
There was some discussion several years ago about what this should be
called. I believe this term came from Richard Brualdi's combinatorial
matrix theory book (I remember running down the hall to my advisor's
office to look it up! :), but my memory may be inaccurate.
Thanks,
Jason
David Joyner
<jason...@creativetrax.com> wrote:
> On 02/27/2010 01:41 PM, Rob Beezer wrote:
>>
>> On Feb 27, 6:37 am, David Joyner<wdjoy...@gmail.com> wrote:
>>>
>>> There are several places where bipartite graphs
>>> differ (at least in the literature) from regular graphs.
>>> For example, usually the bipartite graph's adjacency matrix
>>> is not square.
>>
>> I think an "adjacency matrix" should always be square. But for a
>> bipartite graph if you order the vertices consecutively within the two
>> parts of the bipartition, then you get a block matrix with zero
>> matrices in the northwest and southeast corners. And the other two
>> corners are transposes of each other (but not square when the
>> bipartite sets are different sizes).
>>
>> This is in the BipartiteGraph class as "reduced_adjacency_matrix()."
>> I can't recall ever seeing this matrix given a name, so I don't know
>> if this is how one would expect to find it. In the research for your
>> graph theory book have you learned what others call it?
Some also call it the transfer matrix, but I don't know if that is standard.
>
>
> There was some discussion several years ago about what this should be
> called. I believe this term came from Richard Brualdi's combinatorial
> matrix theory book (I remember running down the hall to my advisor's office
> to look it up! :), but my memory may be inaccurate.
This is correct. It is defined that way on page 107 of
Brualdi-Ryser, Combinatorial Matrix Theory. The literature I am
referring to is that of coding theorists who work with graphs,
but maybe they are using non-standard terms.
>
> Thanks,
>
> Jason
David Joyner
I have now seen three other terms (besides the admittedly sloppy
"adjacency matrix") for this: transfer matrix, biadjacency matrix,
and reduced adjacency matrix.
>
> Rob
Rob Beezer
Thanks for the education. "transfer matrix" is the most evocative to
me, but I didn't bring it up to suggest any changes - simply curious.
Rob
Jaap Spies
You remember correctly a discussion on IRC. I offered to put a scan of
the relevant page on line.
Jaap
> Thanks,
>
> Jason
>
>
David Joyner
>>
>> There was some discussion several years ago about what this should be
>> called. I believe this term came from Richard Brualdi's combinatorial
>> matrix theory book (I remember running down the hall to my advisor's
>> office to look it up! :), but my memory may be inaccurate.
>>
>
> You remember correctly a discussion on IRC. I offered to put a scan of
> the relevant page on line.
I'm interested. Please do.
>
> Jaap
>
>
>
>> Thanks,
>>
>> Jason
Jaap Spies
>>>
>>>
>>> There was some discussion several years ago about what this should be
>>> called. I believe this term came from Richard Brualdi's combinatorial
>>> matrix theory book (I remember running down the hall to my advisor's
>>> office to look it up! :), but my memory may be inaccurate.
>>>
>>
>> You remember correctly a discussion on IRC. I offered to put a scan of
>> the relevant page on line.
>
> I'm interested. Please do.
Hold on. I'm scanning.
Jaap
Jaap Spies
>>>
>>>
>>> There was some discussion several years ago about what this should be
>>> called. I believe this term came from Richard Brualdi's combinatorial
>>> matrix theory book (I remember running down the hall to my advisor's
>>> office to look it up! :), but my memory may be inaccurate.
>>>
>>
>> You remember correctly a discussion on IRC. I offered to put a scan of
>> the relevant page on line.
>
> I'm interested. Please do.
>
I will not put this scan in the open. My lady friend who happens to be a lawyer,
advised me so. I'll send it by email.
Jaap
David Joyner
> Actually, I've considered dropping back to the Graph class. I'm working
> with error correcting codes whose decoding algorithms are naturally
> described as message passing on an associated graph (LDPC codes). And the
> associated graphs are bipartite. So naturally I used the BipartiteGraph
> class!
Aahh, very interesting. If you have coding theory patches to add,
I would be happy to try to referee them.
>
> Personally, the only bipartite "feature" I use are the partition sets. I
> often want to iterate over all of a certain node type. I have the
> information nodes on the left and constraint nodes on the right. In fact,
> it would probably be less work for me to use a Graph and maintain these sets
> manually.
>
Eventually, it would be nice if someone in your situration could just use the
BipartiteGraph class, since that is what is most natural.
> In general, the bipartite nature of a graph can be exploited for matching
> and coloring, planarity, etc. So there are opportunities for optimized
> algorithms. Take a look at trac #1941 for the big picture, and #8329,
> #8330, #8331, and #8350 (all linked from #1941) for attacks on a few
> specific issues.
>
> Enjoy!
>
> - Ryan
>
> Nathann Cohen wrote:
>>
>> Hello everybody !!!
>>
>> I followed your conversation on Sage-devel (http://bit.ly/bHTOHm), and
>> I felt a bit as an outsider as I never used this class.. Could you
>> tell me what you expect from it, or what you use it for ? I can not
>> dream of a situation in which I would prefer it to the usual Graph
>> class.....
>>
>> Thank you :-)
>>
>> Nathann
>
> ---
> Ryan Hinton
> iob...@email.com
>
>
Dima Pasechnik
To avoid confusion, I called such things "vertex-vertex incidence
matrix" in
the graph theory class I taught last term.
By the way, in enumerative combinatorics "transfer matrix" means
something totally different.
Dima
Ryan Hinton
option. (See my comments on the original thread, <http://
groups.google.com/group/sage-devel/browse_thread/thread/
bff3af2a3c77b4b6>.)
- Ryan
On Feb 27, 1:45 pm, Robert Bradshaw <rober...@math.washington.edu>
wrote:
William Stein
> Incidentally, this is my option (A). I agree it is the cleanest
> option. (See my comments on the original thread, <http://
> groups.google.com/group/sage-devel/browse_thread/thread/
> bff3af2a3c77b4b6>.)
I had the impression taht Robert Miller has made an extremely
compelling case that this (A) is not a clean option at all.f It is
only a good way to duplicate lots of code, maintenance work, etc.
-- William
>
> - Ryan
>
> On Feb 27, 1:45 pm, Robert Bradshaw <rober...@math.washington.edu>
> wrote:
>> Perhaps the correct thing to do is have BipartiteGraph wrap a Graph
>> rather than descend from it. This way at least one wouldn't ever
>> accidently get incorrect answers when calling graph methods that have
>> different definitions in the bipartite case (including methods that
>> may in the future get added to Graph).
>>
>> - Robert
>
> --
> To post to this group, send an email to sage-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-devel
> URL: http://www.sagemath.org
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org