Opened 12 years ago
Closed 11 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: |
Description (last modified by )
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)
Change History (10)
comment:1 Changed 11 years ago by
- Cc jason ncohen added
- Description modified (diff)
comment:2 Changed 11 years ago by
- Description modified (diff)
Changed 11 years ago by
comment:3 Changed 11 years ago by
- Description modified (diff)
- Status changed from new to needs_review
Changed 11 years ago by
comment:4 Changed 11 years ago by
Minh,
Your patch looks good to me. If you approve of mine, please set this to positive review.
Thanks!
comment:5 Changed 11 years ago by
- Reviewers set to Robert Miller, Minh Van Nguyen
- Status changed from needs_review to positive_review
comment:6 Changed 11 years ago by
- Description modified (diff)
comment:7 Changed 11 years ago by
- Milestone changed from sage-4.6.1 to sage-4.6.2
comment:8 Changed 11 years ago by
- Merged in set to sage-4.6.2.alpha0
- Resolution set to fixed
- Status changed from positive_review to closed
apply after previous patch