C++

Forum

 
Implementing Adjacency Matrix

closed account Sz6592yv (64)
SO I know what the adjacency matrix does, but I am stuck on how to implement to check to see if each nodes are an adjacent and return as true if they are in terms of rows and columns. I would like to get some help on how to set it up easier. Here is what is being provided.

Prompt:
Write a C++ 11 function named is_connected() to determine whether an undirected unweighted graph is connected when the graph is stored in the adjacency matrix format using the class.

Write a main program that hard-codes the entries of the adjacency matrix and then passes the matrix to the is_connected function. Every graph has vertices labeled with consecutive unsigned integers starting at 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
 
  #ifndef MATRIX_H
#define MATRIX_H

#include <cassert>

/**
 * A generic 2-dimensional array class
 
 */
template <class Object>
class Matrix
{
 public:
  /**
   * Constructor, specifying number of both rows and columns
   * @param rows the number of rows
   * @param cols the number of columns
   */
  Matrix( uint16_t rows, uint16_t cols );

  /**
   * Access to an element to allow modification
   * @param row the row index
   * @param col the column index
   * @return reference to the element at that position
   */
  Object & at( uint16_t row, uint16_t col );

  /**
   * Constant access to an element
   * @param row the row index
   * @param col the column index
   * @return constant reference to the element at that position
   */
  const Object & at( uint16_t row, uint16_t col ) const;

  /**
   * Destructor to free allocated memory
   */
  ~Matrix();

  /**
   * Copy constructor to make 1-1 copy of existing matrix
   * @param m the existing matrix to be copied
   */
  Matrix( const Matrix<Object> & m ); // Copy constructor

  /**
   * Disallow the rvalue copy constructor
   */
  Matrix( const Matrix<Object> && m ) = delete;

  /**
   * Assignment operator to make 1-1 copy of existing matrix
   * @param m the existing matrix to be copied
   */
  Matrix & operator= ( const Matrix<Object> & m ); // Assignment operator

  /**
   * Disallow the rvalue assignment operator
   */
  Matrix & operator= ( const Matrix<Object> && m ) = delete;

  /**
   * Accessor to determine how many rows are in the matrix
   * @return the number of rows in the matrix
   */
  uint16_t numrows() const;

  /**
   * Accessor to determine how many columns are in the matrix
   * @return the number of columns in the matrix
   */
  uint16_t numcols() const;

 private:
  uint16_t rows;
  uint16_t cols;
  Object* data;
};

template <class Object>
Matrix<Object>::Matrix( uint16_t rows, uint16_t cols )
: rows( rows ), cols( cols )
{
  data = new Object[ rows * cols ];
}

template <class Object>
Matrix<Object>::~Matrix()
{
  delete[] data;
}

template <class Object>
Object & Matrix<Object>::at( uint16_t row, uint16_t col )
{
  assert( row < rows && col < cols );
  return data[ cols * row + col ];
}

template <class Object>
const Object & Matrix<Object>::at( uint16_t row, uint16_t col ) const
{
  assert( row < rows && col < cols );
  return data[ cols * row + col ];
}

template <class Object>
uint16_t Matrix<Object>::numrows() const
{
  return rows;
}

template <class Object>
uint16_t Matrix<Object>::numcols() const
{
  return cols;
}
//implement this method
//bool is_connected method
bool is_connected(const vector< list< uint8_t >> & graph)
{
vector<bool> reached(graph.size(), false);
   bool visited;//boolean variable to check the nodes
   //if both row and col index are not empty then check for adjacency
   if(!(rows[].empty() && cols[].empty()))
   {
      
   }
}

#endif
Last edited on
Topic archived. No new replies allowed.