Opened 11 years ago

Closed 10 years ago

#8395 closed defect (fixed)

degree() reports the degree of a self-loop vertex as contributing 1 to total degree

Reported by: mvngu Owned by: rlm
Priority: minor Milestone: sage-4.6.2
Component: graph theory Keywords:
Cc: jason, ncohen Merged in: sage-4.6.2.alpha0
Authors: Minh Van Nguyen Reviewers: Robert Miller, Minh Van Nguyen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by mvngu)

Note: When this ticket is closed, make sure to also close ticket #9809.

From sage-devel:

[mvngu@sage mvngu]$ sage
----------------------------------------------------------------------
| Sage Version 4.3.3, Release Date: 2010-02-21                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: G = Graph({1:[1]}); G
Looped graph on 1 vertex
sage: sum(G.degree())
1
sage: G.size()
0
sage: G = Graph({1:[1]}, loops=True); G
Looped graph on 1 vertex
sage: sum(G.degree())
1
sage: G.size()
0
sage: G = Graph({1:[1]}, loops=True, multiedges=True); G
Looped multi-graph on 1 vertex
sage: sum(G.degree())
1
sage: G.size()
0

The size of G is 1 because there is one edge, i.e. the single
self-loop. As shown by the above session, Sage reports the size of G
as 0. I believe this is a bug. 

See also the discussion at this other sage-devel thread. This also happens in the C graph backends for sparse and dense graphs:

[mvngu@sage ~]$ sage
----------------------------------------------------------------------
| Sage Version 4.3.5, Release Date: 2010-03-28                       |
| Type notebook() for the GUI, and license() for information.        |
----------------------------------------------------------------------
sage: from sage.graphs.base.sparse_graph import SparseGraphBackend
sage: S = SparseGraphBackend(7)
sage: S.loops(True)
sage: S.add_edge(1, 1, None, directed=False)
sage: S.has_edge(1, 1, None)
True
sage: list(S.iterator_edges(range(7), None))
[(1, 1)]
sage: S.degree(1, directed=False)
1
sage: 
sage: reset()
sage: 
sage: 
sage: from sage.graphs.base.dense_graph import DenseGraphBackend
sage: D = DenseGraphBackend(78)
sage: D = DenseGraphBackend(7)
sage: D.loops(True)
sage: D.add_edge(1, 1, None, directed=False)
sage: D.has_edge(1, 1, None)
True
sage: list(D.iterator_edges(range(7), None))
[(1, 1)]
sage: D.degree(1, directed=False)
1

Notice that degree() reports the degree of a self-loop as one, when in fact it should be 2. That's because both SparseGraphBackend and DenseGraphBackend inherit the same degree() function from CGraphBackend. I think the implementation of degree() in CGraphBackend needs to take into account the existence of self-loops.

Attachments (2)

trac-8395_degree.patch (6.4 KB) - added by mvngu 10 years ago.
trac_8395-part2.patch (4.2 KB) - added by rlm 10 years ago.
apply after previous patch

Download all attachments as: .zip

Change History (10)

comment:1 Changed 11 years ago by mvngu

  • Cc jason ncohen added
  • Description modified (diff)

comment:2 Changed 10 years ago by mvngu

  • Description modified (diff)

Changed 10 years ago by mvngu

comment:3 Changed 10 years ago by mvngu

  • Authors set to Minh Van Nguyen
  • Description modified (diff)
  • Status changed from new to needs_review

Changed 10 years ago by rlm

apply after previous patch

comment:4 Changed 10 years ago by rlm

Minh,

Your patch looks good to me. If you approve of mine, please set this to positive review.

Thanks!

comment:5 Changed 10 years ago by mvngu

  • Reviewers set to Robert Miller, Minh Van Nguyen
  • Status changed from needs_review to positive_review

comment:6 Changed 10 years ago by mvngu

  • Description modified (diff)

comment:7 Changed 10 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:8 Changed 10 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.