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 |
[ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13059117#comment-13059117 ] Simone Tripodi commented on SANDBOX-337: ---------------------------------------- Thanks for reporting! It sounds something it has definitively be fixed ;) fixed on r1142289, can you please update and confirm that it works now? please resolve the issue once verified! > 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 |
In reply to this post by ASF GitHub Bot (Jira)
[ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13059230#comment-13059230 ] Marco Speranza commented on SANDBOX-337: ---------------------------------------- Hi Simo, I checked out the trunk and for Undirect graph seems ok. IMHO we have to modify in the same way also DirectMutableGraph: {code} /** * {@inheritDoc} */ public final int getDegree( V v ) { return getInDegree( v ); } {code} WDYT? I added also a little patch with the test case and this modify. ciao ;) > 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 |
In reply to this post by ASF GitHub Bot (Jira)
[ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Marco Speranza updated SANDBOX-337: ----------------------------------- Attachment: VertexDegreeTestCase.patch > 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 |
In reply to this post by ASF GitHub Bot (Jira)
[ 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 |
In reply to this post by ASF GitHub Bot (Jira)
[ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Marco Speranza updated SANDBOX-337: ----------------------------------- Attachment: (was: VertexDegreeTestCase.patch) > 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 |
In reply to this post by ASF GitHub Bot (Jira)
[ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13059282#comment-13059282 ] Marco Speranza commented on SANDBOX-337: ---------------------------------------- OK I agree with you. So, I removed the patch and tomorrow I'll finish the test case, in that way. bye bye > 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 |
In reply to this post by ASF GitHub Bot (Jira)
[ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Marco Speranza updated SANDBOX-337: ----------------------------------- Attachment: CheckVertexDegreeTestCase.patch Here is the new patch. It is a simple test case that check the 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 > Attachments: CheckVertexDegreeTestCase.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 |
In reply to this post by ASF GitHub Bot (Jira)
[ https://issues.apache.org/jira/browse/SANDBOX-337?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ] Simone Tripodi resolved SANDBOX-337. ------------------------------------ Resolution: Fixed Assignee: Simone Tripodi TestCase added in [r1142964|http://svn.apache.org/viewvc?view=revision&revision=1142964], thanks for the patch! :) > 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 > Assignee: Simone Tripodi > Priority: Minor > Attachments: CheckVertexDegreeTestCase.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 |
Free forum by Nabble | Edit this page |