You are viewing a plain text version of this content. The canonical link for it is here.

Posted to issues@commons.apache.org by "Marco Speranza (JIRA)" <ji...@apache.org> on 2011/07/02 20:10:22 UTC

[jira] [Created] (SANDBOX-337) Wrong value for Vertex degree

Wrong value for Vertex degree
-----------------------------

                 Key: SANDBOX-337
                 URL: https://issues.apache.org/jira/browse/SANDBOX-337
             Project: Commons Sandbox
          Issue Type: Bug
          Components: Graph
            Reporter: Marco Speranza
            Priority: Minor


Hi folk, I'm doing a tests case for the class BaseMutableGraph, in order to upgrade our testcase suite. I think that our implementation of vertex degree is wrong.

according with http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Adjacency_and_degree

"The degree, or valency, dG(v) of a vertex v in a graph G is the number of edges incident to v, with loops being counted twice. A vertex of degree 0 is an isolated vertex. A vertex of degree 1 is a leaf. In the labelled simple graph example, vertices 1 and 3 have a degree of 2, vertices 2, 4 and 5 have a degree of 3, and vertex 6 has a degree of 1. If E is finite, then the total sum of vertex degrees is equal to twice the number of edges."

so for a complete graph with 5 nodes, each vertex has a degree of 4. Instead our implementation returns 8. 
IMHO this is wrong. WDYT?

Have a nice week end

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

[jira] [Commented] (SANDBOX-337) Wrong value for Vertex degree

Posted by "Simone Tripodi (JIRA)" <ji...@apache.org>.

    [ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13059251#comment-13059251 ] 

Simone Tripodi commented on SANDBOX-337:
----------------------------------------

Thanks for the patch! :)

I'm not sure the modification you are proposing is 100% right, looks like for Directed graphs there are different opinions: take a look at this [article|http://www.utm.edu/departments/math/graph/glossary.html]:

{quote}
*degree*

The degree (or valence) of a vertex is the number of edge ends at that vertex. For example, in this graph all of the vertices have degree three.

In a digraph (directed graph) the degree is usually divided into the in-degree and the out-degree (*whose sum is the degree* of the vertex in the underlying undirected graph).
{quote}

Take also a look at this [samples|http://reference.wolfram.com/mathematica/ref/VertexDegree.html] with directed graphs: for Vertex {{2}}, that has {{deg+ = 2}} and {{deg- = 1}}, the degree is {{2}}

In the [book|http://www.algoritmica.org/] I'm reading (sorry, in Italian only) it is reported the following:

{quote}
Il grado in uscita di un nodo è pari al numero di archi uscenti da esso, mentre il grado in ingresso e dato dal numero di archi entranti. Il grado è la somma del grado d'ingresso e di quello d'uscita
{quote}

> Wrong value for Vertex degree
> -----------------------------
>
>                 Key: SANDBOX-337
>                 URL: https://issues.apache.org/jira/browse/SANDBOX-337
>             Project: Commons Sandbox
>          Issue Type: Bug
>          Components: Graph
>            Reporter: Marco Speranza
>            Priority: Minor
>         Attachments: VertexDegreeTestCase.patch
>
>
> Hi folk, I'm doing a tests case for the class BaseMutableGraph, in order to upgrade our testcase suite. I think that our implementation of vertex degree is wrong.
> according with http://en.wikipedia.org/wiki/Glossary_of_graph_theory#Adjacency_and_degree
> "The degree, or valency, dG(v) of a vertex v in a graph G is the number of edges incident to v, with loops being counted twice. A vertex of degree 0 is an isolated vertex. A vertex of degree 1 is a leaf. In the labelled simple graph example, vertices 1 and 3 have a degree of 2, vertices 2, 4 and 5 have a degree of 3, and vertex 6 has a degree of 1. If E is finite, then the total sum of vertex degrees is equal to twice the number of edges."
> so for a complete graph with 5 nodes, each vertex has a degree of 4. Instead our implementation returns 8. 
> IMHO this is wrong. WDYT?
> Have a nice week end

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira