math::AdjacencyMatrix Class Reference

Матрица смежности для алгоритма Литтла More...

#include <adjacency_matrix.h>

Collaboration diagram for math::AdjacencyMatrix:

Public Types
enum	Mins { Rows , Columns }

Public Member Functions
	AdjacencyMatrix (const AdjacencyMatrix &other)=default
void	CalculateData ()
void	ExtendTo (std::size_t num_of_flyers)
	Расширяет матрицу для нескольких коммивояжеров
double	GetBottomLineEvaluation () const
double	GetMatrixValue (std::size_t i, std::size_t j) const
std::pair< std::size_t, std::size_t >	GetSelectedEdge () const
std::pair< std::size_t, std::size_t >	GetSelectedValue () const
std::size_t	GetSize () const
AdjacencyMatrix	Minor (std::size_t i, std::size_t j)
	Создает минор матрицы
AdjacencyMatrix &	operator= (const AdjacencyMatrix &other)=default
AdjacencyMatrix	Reducted ()
	Создает редуцированную матрицы
void	SetMatrixValue (std::size_t i, std::size_t j, double num)
	Меняет элемент матрицы

Static Public Member Functions
static AdjacencyMatrix	WithExtraRowCol (const std::vector< std::vector< double > > &nums)
	Создает новый экземпляр AdjacencyMatrix с добавлением строки и столбца номеров точек

Private Member Functions
	AdjacencyMatrix (const std::vector< std::vector< double > > &nums)
	Создает новый экземпляр AdjacencyMatrix.
double	BottomLineEvaluation ()
	Находит нижнюю оценку для матрицы
Minimums	FindTwoMinimums (Mins type, std::size_t index) const
	Находит 2 минимума в строке или столбце
std::pair< std::size_t, std::size_t >	HighestPowerOfZero () const
	Находит позицию нуля с наибольшей степенью

Private Attributes
double	evaluation_ = 0
std::vector< std::vector< double > >	matrix_
std::vector< double >	min_numbers_
std::vector< std::vector< double > >	reducted_matrix_
std::pair< std::size_t, std::size_t >	selected_edge_
std::pair< std::size_t, std::size_t >	selected_value_
std::size_t	size_

Detailed Description

Матрица смежности для алгоритма Литтла

Member Enumeration Documentation

Mins

enum math::AdjacencyMatrix::Mins

Enumerator
Rows
Columns

{ Rows, Columns };

Constructor & Destructor Documentation

AdjacencyMatrix() [1/2]

math::AdjacencyMatrix::AdjacencyMatrix ( const AdjacencyMatrix & other )

default

AdjacencyMatrix() [2/2]

math::AdjacencyMatrix::AdjacencyMatrix ( const std::vector< std::vector< double > > & nums )

private

Создает новый экземпляр AdjacencyMatrix.

Parameters

nums	матрица смежности графа

Returns

AdjacencyMatrix: экземпляр AdjacencyMatrix по данной матрице смежности

    : size_{nums.size()}, matrix_{nums}, min_numbers_(size_ + size_) {}

Member Function Documentation

BottomLineEvaluation()

double math::AdjacencyMatrix::BottomLineEvaluation ( )

private

Находит нижнюю оценку для матрицы

Returns

double: нижняя оценку матрицы

                                             {
  reducted_matrix_ = matrix_;
  double mins_sum = 0;
  for (std::size_t i = 0; i < size_; ++i) {
    Minimums twoMins = FindTwoMinimums(Mins::Rows, i);
    double first_min = twoMins.first;
    double second_min = twoMins.second;
    for (std::size_t j = 0; j < size_; ++j) {
      reducted_matrix_[i][j] -= first_min;
    }
    second_min -= first_min;
    min_numbers_[i] = second_min;
    mins_sum += first_min;
  }
 
  for (std::size_t i = 0; i < size_; ++i) {
    Minimums twoMins = FindTwoMinimums(Mins::Columns, i);
    double first_min = twoMins.first;
    double second_min = twoMins.second;
    for (std::size_t j = 0; j < size_; ++j) {
      if (std::abs(reducted_matrix_[j][i] - min_numbers_[j]) <= precision)
        min_numbers_[j] -= first_min;
      reducted_matrix_[j][i] -= first_min;
    }
    second_min -= first_min;
    min_numbers_[size_ + i] = second_min;
    mins_sum += first_min;
  }
 
  return mins_sum;
}

Here is the call graph for this function:

Here is the caller graph for this function:

CalculateData()

void math::AdjacencyMatrix::CalculateData

(

)

                                    {
  evaluation_ = BottomLineEvaluation();
  selected_value_ = HighestPowerOfZero();
  selected_edge_ = std::make_pair(matrix_[selected_value_.first][size_],
                                  matrix_[size_][selected_value_.second]);
}

Here is the call graph for this function:

Here is the caller graph for this function:

ExtendTo()

void math::AdjacencyMatrix::ExtendTo

(

std::size_t

num_of_flyers

)

Расширяет матрицу для нескольких коммивояжеров

Parameters

num_of_flyers

количество коммивояжеров

                                                      {
  if (num_of_flyers < 2)
    throw std::runtime_error("dev: num_of_flyers < 2 in ExtendTo");
 
  for (std::size_t i = 1; i < num_of_flyers; ++i) {
    matrix_.insert(matrix_.begin() + size_, matrix_[0]);
    for (std::size_t j = 0; j < size_ + 1; ++j) {
      matrix_[j].insert(matrix_[j].begin() + size_, matrix_[j][0]);
    }
    matrix_[size_ + 1][size_] = (double)size_;
    matrix_[size_][size_ + 1] = (double)size_;
    matrix_[size_ + 1].push_back(0);
    ++size_;
    min_numbers_.resize(size_ + size_);
  }
  for (std::size_t i = 1; i < num_of_flyers; ++i) {
    for (std::size_t j = 1; j < num_of_flyers; ++j) {
      if (i != j) matrix_[size_ - i][size_ - j] = 0;
    }
    matrix_[0][size_ - i] = 0;
    matrix_[size_ - i][0] = 0;
  }
  CalculateData();
}

Here is the call graph for this function:

Here is the caller graph for this function:

FindTwoMinimums()

Minimums math::AdjacencyMatrix::FindTwoMinimums ( Mins type, std::size_t index ) const

private

Находит 2 минимума в строке или столбце

Parameters

type	тип поиска минимума(в строке или в столбце)
index	номер строки/столбца

Returns

Minimums: 2 найденных минимума

                                                                          {
  Minimums result;
  double first_min = inf;
  double second_min = inf;
  switch (type) {
    case Mins::Rows: {
      for (std::size_t j = 0; j < size_; ++j) {
        if (reducted_matrix_[index][j] < first_min) {
          second_min = first_min;
          first_min = reducted_matrix_[index][j];
        } else if (reducted_matrix_[index][j] < second_min) {
          second_min = reducted_matrix_[index][j];
        }
      }
      result.first = first_min;
      result.second = second_min;
      break;
    }
 
    case Mins::Columns: {
      for (std::size_t i = 0; i < size_; ++i) {
        if (reducted_matrix_[i][index] < first_min) {
          second_min = first_min;
          first_min = reducted_matrix_[i][index];
        } else if (reducted_matrix_[i][index] < second_min) {
          second_min = reducted_matrix_[i][index];
        }
      }
      result.first = first_min;
      result.second = second_min;
      break;
    }
 
    default: {
      result.first = first_min;
      result.second = second_min;
      break;
    }
  }
  return result;
}

Here is the caller graph for this function:

GetBottomLineEvaluation()

double math::AdjacencyMatrix::GetBottomLineEvaluation ( ) const

inline

{ return evaluation_; }

GetMatrixValue()

double math::AdjacencyMatrix::GetMatrixValue ( std::size_t i, std::size_t j ) const

inline

                                                        {
    return matrix_[i][j];
  }

Here is the caller graph for this function:

GetSelectedEdge()

std::pair< std::size_t, std::size_t > math::AdjacencyMatrix::GetSelectedEdge ( ) const

inline

                                                        {
    return selected_edge_;
  }

GetSelectedValue()

std::pair< std::size_t, std::size_t > math::AdjacencyMatrix::GetSelectedValue ( ) const

inline

                                                         {
    return selected_value_;
  }

GetSize()

std::size_t math::AdjacencyMatrix::GetSize ( ) const

inline

{ return size_; }

Here is the caller graph for this function:

HighestPowerOfZero()

std::pair< std::size_t, std::size_t > math::AdjacencyMatrix::HighestPowerOfZero ( ) const

private

Находит позицию нуля с наибольшей степенью

Returns

std::pair<std::size_t, std::size_t>: позицию нуля с наибольшей степенью

          {
  std::size_t row = 0, col = 0;
  double max = -1;
  for (std::size_t i = 0; i < size_; ++i) {
    for (std::size_t j = 0; j < size_; ++j) {
      if (std::abs(reducted_matrix_[i][j]) <= precision) {
        if ((min_numbers_[i] + min_numbers_[size_ + j]) > max) {
          max = min_numbers_[i] + min_numbers_[size_ + j];
          row = i;
          col = j;
        }
      }
    }
  }
  return std::make_pair(row, col);
}

Here is the caller graph for this function:

Minor()

AdjacencyMatrix math::AdjacencyMatrix::Minor	(	std::size_t	i,
		std::size_t	j )

Создает минор матрицы

Parameters

i	номер удаляемой строки
j	номер удаляемого столбца

Returns

AdjacencyMatrix: минор матрицы

                                                               {
  std::vector<std::vector<double>> minor_matrix = matrix_;
  minor_matrix.erase(minor_matrix.begin() + i);
  for (std::size_t k = 0; k < size_; ++k) {
    minor_matrix[k].erase(minor_matrix[k].begin() + j);
  }
  AdjacencyMatrix minor(minor_matrix);
  minor.size_--;
  minor.CalculateData();
  return minor;
}

Here is the call graph for this function:

Here is the caller graph for this function:

operator=()

AdjacencyMatrix & math::AdjacencyMatrix::operator= ( const AdjacencyMatrix & other )

default

Reducted()

AdjacencyMatrix math::AdjacencyMatrix::Reducted

(

)

Создает редуцированную матрицы

Returns

AdjacencyMatrix: редуцированная матрица

                                          {
  AdjacencyMatrix reducted = *this;
  reducted.matrix_ = reducted_matrix_;
  return reducted;
}

SetMatrixValue()

void math::AdjacencyMatrix::SetMatrixValue	(	std::size_t	i,
		std::size_t	j,
		double	num )

Меняет элемент матрицы

Parameters

i	номер строки элемента
j	номер столбца элемента
num	новое значение элемента

                                                                         {
  matrix_[i][j] = num;
  CalculateData();
}

Here is the call graph for this function:

Here is the caller graph for this function:

WithExtraRowCol()

AdjacencyMatrix math::AdjacencyMatrix::WithExtraRowCol ( const std::vector< std::vector< double > > & nums )

static

Создает новый экземпляр AdjacencyMatrix с добавлением строки и столбца номеров точек

Parameters

nums	матрица смежности графа

Returns

AdjacencyMatrix: экземпляр AdjacencyMatrix по данной матрице смежности

                                              {
  AdjacencyMatrix m(nums);
  m.matrix_.resize(m.size_ + 1);
  m.matrix_[m.size_].resize(m.size_ + 1);
  for (std::size_t i = 0; i < m.size_; ++i) {
    m.matrix_[i].resize(m.size_ + 1);
    m.matrix_[i][m.size_] = (double)i;
    m.matrix_[m.size_][i] = (double)i;
  }
  m.CalculateData();
  return m;
}

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

evaluation_

double math::AdjacencyMatrix::evaluation_ = 0

private

matrix_

std::vector<std::vector<double> > math::AdjacencyMatrix::matrix_

private

min_numbers_

std::vector<double> math::AdjacencyMatrix::min_numbers_

private

reducted_matrix_

std::vector<std::vector<double> > math::AdjacencyMatrix::reducted_matrix_

private

selected_edge_

std::pair<std::size_t, std::size_t> math::AdjacencyMatrix::selected_edge_

private

selected_value_

std::pair<std::size_t, std::size_t> math::AdjacencyMatrix::selected_value_

private

size_

std::size_t math::AdjacencyMatrix::size_

private

---

The documentation for this class was generated from the following files:

• math/littles_algorithm/adjacency_matrix.h
• math/littles_algorithm/adjacency_matrix.cpp