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
> --
> 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
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
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
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
I have now seen three other terms (besides the admittedly sloppy
"adjacency matrix") for this: transfer matrix, biadjacency matrix,
and reduced adjacency matrix.
>
> Rob
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
You remember correctly a discussion on IRC. I offered to put a scan of
the relevant page on line.
Jaap
> Thanks,
>
> Jason
>
>
I'm interested. Please do.
>
> Jaap
>
>
>
>> Thanks,
>>
>> Jason
Hold on. I'm scanning.
Jaap
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
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
>
>
By the way, in enumerative combinatorics "transfer matrix" means
something totally different.
Dima
- Ryan
On Feb 27, 1:45 pm, Robert Bradshaw <rober...@math.washington.edu>
wrote:
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