Adjacency matrix on undirected graph

Question

Please review my Adjacency Matrix class based on this code.

• Since I use std::vector to create the matrix, I would like to store as many nodes as possible. Is it OK to use std::size_t all over the code?

• Are using 1 for connected and 0 for not connected a bad idea?

---

class AdjMatrix {
public:
    AdjMatrix(const std::size_t& vertsize);
    std::size_t Vertices() const;
    std::size_t Edges() const;
    void addEdge(const std::size_t& a, const std::size_t& b);
    std::size_t degree(const std::size_t& v) const;
    std::size_t maxDegree() const;
    std::size_t minDegree() const;
private:
    std::size_t vertices;
    std::size_t edges;
    std::vector<std::vector<std::size_t>> matrix;
};

AdjMatrix::AdjMatrix(const std::size_t& vertsize) :vertices{vertsize < 0? throw std::out_of_range{"necgative values"} : vertsize}, edges{0}, matrix{vertsize} {
    for (auto& v : matrix) {
        v.resize(vertsize);
    }
}

std::size_t AdjMatrix::Vertices() const {
    return vertices;
}

std::size_t AdjMatrix::Edges() const {
    return edges;
}

void AdjMatrix::addEdge(const std::size_t& a, const std::size_t& b) {
    if (a < 0 || b < 0) {
        throw std::out_of_range{"negative values"};
    }
    if (matrix[a][b] == 0) {
        edges++;
    }
    matrix[a][b] = 1;
    matrix[b][a] = 1;
}

std::size_t AdjMatrix::degree(const std::size_t& v) const {
    std::size_t d = 0;
    for (std::size_t i = 0; i < matrix[v].size(); ++i) {
        if (matrix[v][i] == 1) {
            d++;
        }
    }
    return d;
}

std::size_t AdjMatrix::maxDegree() const {
    std::size_t max = 0;
    for (std::size_t i = 0; i < matrix.size(); i++) {
        std::size_t d = degree(i);
        max = d > max ? d : max;
    }
    return max;
}

std::size_t AdjMatrix::minDegree() const {
    std::size_t min;
    for (std::size_t i = 0; i < matrix.size(); i++) {
        std::size_t d = degree(i);
        if (i == 0) {
            min = d;
        } else {
            min = min < d ? min : d;
        }
    }
    return min;
}

How can I improve this code?

Answer 1

• Using std::size_t. You asked:

  Is it ok to use std::size_t all over the code?

  I think that's perfectly alright.

• Use of const std::size_t

  Using const std::size_t for the type of an argument has no advantage over using just std::size_t. It adds unnecessary verbosity. I would change them all to use std::size_t.

• Inconsistent member function names.

  Function names are better that start with a verb, such as addEdge. However, all other member functions don't follow that naming convention.

  I would recommend the following changes:

    Vertices  -> getNumVertices
    Edges     -> getNumEdges
    degree    -> getDegree
    maxDegree -> getMaxDegree
    minDegree -> getMinDegree
  

• Variable names

  I think it's more appropriate to use numVertice and numEdges instead of vertices and edges.

• Checking for negative inputs

  An object of std::size_t will never have a negative value. It's pointless to check whether an input is negative when it is of type std::size_t. I would recommend removing those checks altogether.

• Range checking

  In addEdge, you have:

  if (a < 0 || b < 0) {
      throw std::out_of_range{"negative values"};
  }
  

  The check for negative values is not necessary. However, it is necessary to check whether those are within the upper bound. I would replace that check with:

  if (a >= numVertices || b >= numVertices ) {
  

• Better initialization of matrix.

  I would change the constructor to:

  AdjMatrix::AdjMatrix(std::size_t& vertsize) : numVertices{vertsize},
                                                edges{0},
                                                matrix{vertsize, std::vector<std::size_t>{vertsize, 0}}
  {
  }
  

• Using std namespace in member function implementations.

  If the member functions are implemented in a .cpp file, I would add

  using std::size_t;
  using std::vector;
  

  in the .cpp file to reduce the amount of typing.

• Remove if/else from minDegree().

  Initialize min to std::numeric_limits<std::size_t>::max. Then, you don't need the if/else check. You can replace the lines:

  if (i == 0) {
      min = d;
  } else {
      min = min < d ? min : d;
  }
  

  with

  min = min < d ? min : d;
  

Answer 2

Is it OK to use std::size_t all over the code?

Sure. std::size_t should be used whenever you need to represent a size in bytes/elements or non-zero indexes. Just remember that it is a type alias to an unsigned integer (can't represent negative values) with implementation defined byte width (usually 4 or 8 bytes).

Are using 1 for connected and 0 for not connected a bad idea?

I'd say yes. 0 and 1 convey no meaning other than a magic number. Most people will guess that if the value range is always 0/1 the variable is being used to represent a boolean. In such case, then a bool would be better. However, you can give even more context than just true or false by using an enumeration:

enum class EdgeState
{
    Connected, 
    NotConnected
};

Since I use std::vector to create the matrix, I would like to store as many nodes as possible.

Yep, that looks great to me. Automatic memory management and flexible size. Good choice. You are only limited by the amount of memory your process can allocate.

Other details:

This line is way too long:

 AdjMatrix::AdjMatrix(const std::size_t& vertsize) :vertices{vertsize < 0? throw std::out_of_range{"necgative values"} : vertsize}, edges{0}, matrix{vertsize} {

You could have split that into a few shorter ones. Also, you have misspelled "necgative" -> negative.

AdjMatrix::AdjMatrix(const std::size_t& vertsize) 
    : vertices{vertsize < 0 ? throw std::out_of_range{"negative values"} : vertsize}
    , edges{0}
    , matrix{vertsize} 
{
    ...
}

---

You have mixed naming convention for the methods. E.g.: Vertices() and addEdge(). My suggestion would be to name Vertices() as getVerticesCount() (same for Edges), since those are lightweight accessors and related to the sizes/counts.

Answer 3

Efficiency

Because the graph is undirected, the adjacency matrix can be represented in 0.5 * (square (num_vertices)) space if there are no redundant edges, i.e. matrix is triangular. A one dimensional array with accessors could serve as simple data structure.

As you probably know, if the typical graph is sparse, then an adjacency matrix may be space inefficient and an adjacency list

Representation

Are using 1 for connected and 0 for not connected a bad idea?

It depends on what operations will be performed on the graph and what the graph represents. If the graph represents something which might have redundant edges between vertices, then 0 and 1 don't capture the real world object and operations such as minimum cut cannot be performed accurately. Similar issues arise if edges have variable costs.

In the end, just as adjacency matrices are a good choice for dense graphs and maybe not so good for sparse graphs, other aspects of the procedural representation of mathematical graphs come with tradeoffs that should be dictated by the intended use.