[sage-devel] Re: graph theory: clarify the purpose of keyword "directed" in degree() of CGraphBackend

[Nathann Cohen]

In Sage, the "degree" of a vertex in a directed graph is the degree of
the same vertex in the undirected version of the graph. It is the
number of edges "touching" this vertex. If you just want the out-
degree (number of edges leaving the vertex), then it is out_degree
(resp in-degree, in_degree).

When a graph is undirected, sage remembers the edges in both
directions, so returning the out_degree is fine :-)

A circuit has an in_degree equal to its out_degree equal to 1. The
degree is 2, though :-)

Nathann

--
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

[Nathan O'Treally]

On 22 Apr., 10:52, Nathann Cohen <nathann.co...@gmail.com> wrote:
> In Sage, the "degree" of a vertex in a directed graph is the degree of
> the same vertex in the undirected version of the graph. It is the
> number of edges "touching" this vertex. If you just want the out-
> degree (number of edges leaving the vertex), then it is out_degree
> (resp in-degree, in_degree).
>
> When a graph is undirected, sage remembers the edges in both
> directions, so returning the out_degree is fine :-)
>
> A circuit has an in_degree equal to its out_degree equal to 1. The
> degree is 2, though :-)

I would say this is not consistent:

If the edges are a sub*set* of V x V, the degree of a node of a
directed graph might differ from its corresponding undirected graph's
(and vice versa).

E.g. V={v1,v2} E={(v1,v2),(v2,v1)}
directed: two edges, indegree=outdegree=1 and indegree+outdegree=2 for
both => degree=2 for both
undirected: one edge, indegree=outdegree=1 and indegree+outdegree=2 !=
1 for both => degree=1 for both
i.e. the number of "touching edges" of a node differs between the
graphs.

And for the single-node undirected circular graph: there's only one
edge, so degree can't be larger than 1.


-Leif

[Nathan O'Treally]

On 23 Apr., 04:28, Minh Nguyen <nguyenmi...@gmail.com> wrote:
> [...] The above demonstrates a bug in
> the implementation of degree() as it doesn't handle self-loops
> consistently. I understand that the total degree of any graph is twice
> the number of edges.

If we only consider directed or undirected, cyclic or acyclic graphs
with E \subseteq V \times V, I agree. ;-)

DAGs are nicer anyway...

[Nathann Cohen]

Hmmm.... I am sorry but for once, I do not think this is really a
matter of mathematical justification....

For undirected graph, we settled recently on saying that the degree of
a single vertex with a loop is equal to 2, because we do not want the
inequality (sum of the degrees) = 2* (number of edges) broken.

Short on this, the following are currently well defined in Sage :
- in_degree of a directed graph
- out_degree of a directed graph
- degree of a directed graph

As I never met any definition of the degree of a vertex in a directed
graph (when this is not an alias for in_degree or out_degree), I do
not see the problem in defining in Sage that it is equal to the sum,
which is anyway natural : a digraph having no natural definition of
the "degree" of a vertex, let's define it as the degree in the
undirected version.

To Nathan O'Treally :

Of course it is consistent. But our misunderstanding comes from the
fact that my answer was a bit more "technical" that you seemed to
think :

> When a graph is undirected, sage remembers the edges in both
> directions, so returning the out_degree is fine :-)

I meant by this that Sage remembers an Undirected Graph as a directed
graph in which edges are present in both direction. So if you have two
vertices joined by an edge, Sage will remember vertex 1 has an edge
toward 2 and 2 has an edge toward 1. This way, each edge is at the
same time going out of each vertex (and going in, too). So returning
the degree of vertex1 in this graph amounts to returning the number of
edges leaving it, hence the out_degree, which is exactly the degree.
As I said, it will return 2 for each vertex of a circuit (directed :
in + out) or each vertex of an cycle (undirected : out or in)

Nathann

[Nathan O'Treally]

On 23 Apr., 08:37, Nathann Cohen <nathann.co...@gmail.com> wrote:
> For undirected graph, we settled recently on saying that the degree of
> a single vertex with a loop is equal to 2, because we do not want the
> inequality (sum of the degrees) = 2* (number of edges) broken.

Equality, I guess :-)

This unfortunately breaks the common definition degree(v)=#{ w | (v,w)
in E, w in V }
(# for cardinality; (v,w) in E <=> (w,v) in E for undirected graphs)

I.e., you'd have to add 1 iff (v,v) in E.

> Of course it is consistent. But our misunderstanding comes from the
> fact that my answer was a bit more "technical" that you seemed to
> think :

I understood this; by converting an undirected graph to a directed one
simply all edges are "doubled" (to pairs with opposite directions).

>
> > When a graph is undirected, sage remembers the edges in both
> > directions, so returning the out_degree is fine :-)

This doesn't hold for self-loops, because a self-loop in an undirected
graph is represented by a *single* edge in the directed one.
When talking about the number of (touching) edges, we're talking about
the cardinality of sets.

> In Sage, the "degree" of a vertex in a directed graph [...]

> is the number of edges "touching" this vertex.

So the degree of a vertex with only a self-loop is 2, while it has
only 1 touching edge (and indegree+outdegree=2 in the directed case).

It's better to use formal definitions than prose. ;-)

-Leif

[ablondin]

Hello, everyone !

If I may add some comments.

N. O'Trealy is right when he says that the best approach is to look
at the mathematical definitions of objects. On the other hand, one
needs to be careful. For instance, the set E of a graph G = (V,E), a
directed graph G = (V,E) and a multigraph G = (V,E) are all different.
For a directed graph, E is a subset of the cartesian product of V.
For an undirected one, E is a subset of all unordered pairs of V.
For a multigraph, E is a submultiset of the cartesian product of V
(multisets are unordered collections of elements with possible
repetition, also sometimes called bags).
Therefore, the degree function is well defined for all three kinds
of graphs, but has different meaning. A vertex having only a
self-loop in a directed graph will have in-degree 1, out-degree 1 and
degree 2. For undirected graph, in general, we do not define
in- and out-degree, just degree, which would be 2 for a self-loop and
it seems reasonable to set the in- and out-degree both to 2 as well.
As for multigraphs (which may be directed or not), the in-, out- and
normal degree are obtained with the definitions:
in_degree(v) = #{ u | (u,v) \in E}
out_degree(v) = #{ u | (v,u) \in E}
degree(v) = in_degree(v) + out_degree(v) if directed,
otherwise degree(v) = #{ u | {u,v} \in E}.

I guess I did not bring much to the discussion, but I wanted to
underline
that 'directed' vs 'undirected' is distinguished by forcing elements
of E to
be either couples (ordered) or pairs (unordered), while 'multigraph'
vs 'not
multigraph' is mathematically dstinguished by forcing E to be either a
multiset (or bag) or a regular set.

Alex

[Fidel]

Hello everyone!

Just a side question to this discussion and after looking at #8395.

http://trac.sagemath.org/sage_trac/ticket/8395

Given a graph G, with a loop at vertex j. What is the convention
followed in sage for entry j,j of the adjacency matrix?

sage: G=Graph({0:[0],1:[1]},allow_loops=True);G.am()
[1 0]
[0 1]

Just wandering if it is a bug or a feature.

Cheers,
Fidel


On Apr 24, 9:25 pm, ablondin <alexandre.blondin.ma...@gmail.com>
wrote:

[Nathan O'Treally]

On 5 Mai, 23:20, Fidel <fidel.barr...@gmail.com> wrote:
> Given a graph G, with a loop at vertex j. What is the convention
> followed in sage for entry j,j of the adjacency matrix?
>
> sage: G=Graph({0:[0],1:[1]},allow_loops=True);G.am()
> [1 0]
> [0 1]
>
> Just wandering if it is a bug or a feature.

What do you think is wrong with it? There's a difference between the
"number of edges touching a vertex" and its degree, so imho the matrix
is correct. (As long as the edges are represented by a set rather than
a multiset, i.e. multiedges=False, the matrix elements are actually
boolean.)

-Leif

--
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

[Nathann Cohen]

Three years later I got bitten by this again, and I now believe that the degree of a vertex incident with a loop should be 1. Because it is rather pleasant to be sure that the degree of a vertex is equal to the number of its neighbors O_o

Nathann

[leif]

Nathann Cohen wrote:
> Three years later I got bitten by this again, and I now believe that the
> degree of a vertex incident with a loop should be 1.

\o/

> Because it is
> rather pleasant to be sure that the degree of a vertex is equal to the
> number of its neighbors O_o

Although that in turn makes me wonder whether being neighbouring is
(ir)reflexive...

(Some of my alter egos agree, while some of course don't, depending on
whether they know each other and/or themselves.)


-leif

--
() The ASCII Ribbon Campaign
/\ Help Cure HTML E-Mail