Uploaded image for project: 'Commons Sandbox'
  1. Commons Sandbox
  2. SANDBOX-337

Wrong value for Vertex degree

    XMLWordPrintableJSON

    Details

    • Type: Bug
    • Status: Resolved
    • Priority: Minor
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: None
    • Component/s: Graph
    • Labels:
      None

      Description

      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

        Attachments

        1. CheckVertexDegreeTestCase.patch
          4 kB
          Marco Speranza

          Activity

            People

            • Assignee:
              simone.tripodi Simone Tripodi
              Reporter:
              marco.speranza Marco Speranza
            • Votes:
              0 Vote for this issue
              Watchers:
              0 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved: