Update: the question forum somehow does not show some of my code at all, making
ID: 3883177 • Letter: U
Question
Update: the question forum somehow does not show some of my code at all, making it missing
So I have errors that I need help fixing for c++11. This deals with undirected graph in the format of adjacency matrix.
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.
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.
So I have those done already, and I need help with these compiler issues that make no sense. One of them is I already included the packages for them
Lin_0912.h: matrix class
#ifndef MATRIX_H
#define MATRIX_H
#include <cassert>
#include <cstdint>
#include <queue>
#include <vector>
#include <algorithm>
/**
* 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;
}
bool is_connected(Matrix<uint8_t> & graph)
{
vector< bool >reached(graph.size(),false);
queue< uint8_t > to_be_explored;
to_be_explored.push(0);
while(!to_be_explored.empty())
{
uint8_t current_node=to_be_explored.front();
to_be_explored.pop();
reached.at(current_node)=true;
for(uint8_t adjacent=0; adjacent<graph.numcols(); ++adjacent)
{
if(!reached.at(adjacent) && graph.at(current_node, adjacent))
{
to_be_explored.push(adjacent);
}
}
}
return find(reached.begin(), reached.end(), false) == reached.end();
}
#endif
Lin_0912.cpp:
Errors:
In file included from lin_0912.cpp:7:0:
lin_0912.h: In function ‘bool is_connected(Matrix<unsigned char>&)’:
lin_0912.h:129:6: error: ‘vector’ was not declared in this scope
vector< bool >reached(graph.size(),false);
^
lin_0912.h:129:6: note: suggested alternative:
In file included from /usr/include/c++/4.8/vector:64:0,
from lin_0912.cpp:4:
/usr/include/c++/4.8/bits/stl_vector.h:210:11: note: ‘std::vector’
class vector : protected _Vector_base<_Tp, _Alloc>
^
In file included from lin_0912.cpp:7:0:
lin_0912.h:129:14: error: expected primary-expression before ‘bool’
vector< bool >reached(graph.size(),false);
^
lin_0912.h:129:14: error: expected ‘;’ before ‘bool’
lin_0912.h:130:7: error: ‘queue’ was not declared in this scope
queue< uint8_t > to_be_explored;
^
lin_0912.h:130:7: note: suggested alternative:
In file included from /usr/include/c++/4.8/queue:64:0,
from lin_0912.cpp:5:
/usr/include/c++/4.8/bits/stl_queue.h:93:11: note: ‘std::queue’
class queue
^
In file included from lin_0912.cpp:7:0:
lin_0912.h:130:22: error: expected primary-expression before ‘>’ token
queue< uint8_t > to_be_explored;
^
lin_0912.h:130:24: error: ‘to_be_explored’ was not declared in this scope
queue< uint8_t > to_be_explored;
^
lin_0912.h:137:9: error: ‘reached’ was not declared in this scope
reached.at(current_node)=true;
^
lin_0912.h:146:19: error: ‘reached’ was not declared in this scope
return find(reached.begin(), reached.end(), false) == reached.end();
^
lin_0912.h:146:56: error: ‘find’ was not declared in this scope
return find(reached.begin(), reached.end(), false) == reached.end();
^
lin_0912.h:146:56: note: suggested alternative:
In file included from /usr/include/c++/4.8/algorithm:62:0,
from lin_0912.h:9,
from lin_0912.cpp:7:
/usr/include/c++/4.8/bits/stl_algo.h:4432:5: note: ‘std::find’
find(_InputIterator __first, _InputIterator __last,
^
lin_0912.cpp: In function ‘int main()’:
lin_0912.cpp:23:28: error: invalid initialization of reference of type ‘Matrix<unsigned char>&’ from expression of type ‘Matrix<bool>’
cout<<is_connected(graph)<<endl;
^
In file included from lin_0912.cpp:7:0:
lin_0912.h:126:9: error: in passing argument 1 of ‘bool is_connected(Matrix<unsigned char>&)’
bool is_connected(Matrix<uint8_t> & graph)
^
lin_0912.h: In function ‘bool is_connected(Matrix<unsigned char>&)’:
lin_0912.h:147:4: warning: control reaches end of non-void function [-Wreturn-type]
Explanation / Answer
#ifndef MATRIX_H
#define MATRIX_H
#include <cassert>
#include <cstdint>
#include <queue>
#include <vector>
#include <algorithm>
/**
* 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;
}
bool is_connected(Matrix<uint8_t> & graph)
{
vector< bool >reached(graph.size(),false);
queue< uint8_t > to_be_explored;
to_be_explored.push(0);
while(!to_be_explored.empty())
{
uint8_t current_node=to_be_explored.front();
to_be_explored.pop();
reached.at(current_node)=true;
for(uint8_t adjacent=0; adjacent<graph.numcols(); ++adjacent)
{
if(!reached.at(adjacent) && graph.at(current_node, adjacent))
{
to_be_explored.push(adjacent);
}
}
}
return find(reached.begin(), reached.end(), false) == reached.end();
}
#endif
Lin_0912.cpp:
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.