Класс графа (может быть взвешенным и ориентированным). More...

#include <graph.hpp>

Collaboration diagram for Graph< vert_t, weight_t >:

[legend]

Classes
class	Edge

Public Member Functions
	Graph ()
	Инициализирует новый экземпляр Graph.

	Graph (const Graph &other)=default
	Копирующий конструктор.

	Graph (Graph &&other) noexcept
	Перемещающий конструктор. Перемещает ресурсы из другого графа.

void	AddEdge (const std::pair< vert_t, vert_t > &edge_pair, bool ignore_warning=false)

void	AddEdge (const std::tuple< vert_t, vert_t, weight_t > &edge_tuple, bool ignore_warning=false)

void	AddVert (const vert_t &vert)

bool	ContainsEdge (const std::pair< vert_t, vert_t > &edge) const
	Проверяет, содержится ли ребро в графе (НЕВЗВЕШЕННЫЙ).

bool	ContainsEdge (const std::tuple< vert_t, vert_t, weight_t > &edge) const
	Проверяет, содержится ли ребро в графе (ВЗВЕШЕННЫЙ).

bool	ContainsVert (const vert_t &vert) const
	Проверяет, содержится ли вершина в графе.

std::vector< std::tuple< vert_t, vert_t, weight_t > >	Edges () const

size_t	EdgesAmount () const

std::unordered_map< vert_t, std::vector< vert_t > >	GetAdjList () const

std::vector< std::vector< vert_t > >	GetAdjListWithoutKeys () const

std::vector< std::vector< weight_t > >	GetAdjMatrix () const

weight_t	GetEdgeWeight (const std::pair< vert_t, vert_t > &edge) const
	Находит вес ребра в взвешенном графе.

bool	IsDirected () const
	Проверяет, направлен ли граф.

bool	IsWeighted () const
	Проверяет, взвешен ли граф.

void	MakeDirected ()
	Делает граф направленным (ничего).

void	MakeUndirected ()
	Делает граф ненаправленным (удаляет лишние ребра).

Graph &	operator= (const Graph &other)=default
	Оператор копирующего присваивания.

Graph &	operator= (Graph &&other) noexcept
	Оператор перемещающего присваивания. Перемещает ресурсы из другого. графа.

std::ostream &	PrintAdjList (std::ostream &os=std::cout) const
	Выводит в поток список смежности.

std::ostream &	PrintEdges (std::ostream &os=std::cout) const
	Выводит в поток список ребер.

std::ostream &	PrintVerts (std::ostream &os=std::cout) const
	Выводит в поток список вершин.

void	RemoveEdge (const std::pair< vert_t, vert_t > &edge_pair)

void	RemoveEdge (const std::tuple< vert_t, vert_t, weight_t > &edge_tuple)

void	RemoveVert (const vert_t &vert)

void	SetEdgeWeight (const std::pair< vert_t, vert_t > &edge, weight_t new_weight)
	Меняет вес ребра в взвешенном графе.

const std::vector< vert_t > &	Verts () const

size_t	VertsAmount () const

Static Public Member Functions
static Graph	GraphFromAdjList (const std::unordered_map< vert_t, std::vector< vert_t > > &adj_list_dict)
	Создает новый экземпляр Graph. по списку смежности с указанием вершины-ключа (НЕВЗВЕШЕННЫЙ).

static Graph	GraphFromAdjList (const std::vector< std::vector< vert_t > > &adj_list)
	Создает новый экземпляр Graph. по списку смежности (НЕВЗВЕШЕННЫЙ).

static Graph	GraphFromAdjMatrix (const std::vector< std::vector< weight_t > > &adj_matrix, bool is_weighted=false)
	Создает новый экземпляр Graph по матрице смежности.

static Graph	GraphFromMap (const std::unordered_map< std::string, weight_t > &edges_dict)
	Создает новый экземпляр Graph по ребрам. представленными словарем из std::string и weight_t (ВЗВЕШЕННЫЙ).

static Graph	GraphFromStrs (const std::vector< std::string > &edges_strs)
	Создает новый экземпляр Graph по ребрам. представленными вектором std::string (НЕВЗВЕШЕННЫЙ).

static Graph	GraphNonWeighted (const std::vector< std::pair< vert_t, vert_t > > &edges_pairs)
	Создает новый экземпляр Graph по ребрам, представленными вектором std::pair (НЕВЗВЕШЕННЫЙ).

static Graph	GraphWeighted (const std::vector< std::pair< vert_t, vert_t > > &edges_pairs, const std::vector< weight_t > &weights)
	Создает новый экземпляр Graph по ребрам, представленными вектором std::pair и weight_t (ВЗВЕШЕННЫЙ).

static Graph	GraphWeighted (const std::vector< std::tuple< vert_t, vert_t, weight_t > > &edges_tuples)
	Создает новый экземпляр Graph по ребрам. представленными вектором std::tuple (ВЗВЕШЕННЫЙ).

Private Member Functions
	Graph (const std::vector< Edge > &edges)

void	AddEdge_ (const Edge &edge)

auto	GetEdgeIter_ (const std::pair< vert_t, vert_t > &edge)

auto	GetEdgeIter_ (const std::pair< vert_t, vert_t > &edge) const

auto	GetEdgeIter_ (const std::tuple< vert_t, vert_t, weight_t > &edge) const

Static Private Member Functions
static std::pair< vert_t, vert_t >	ParseEdgeString_ (const std::string &edge_str)

Private Attributes
std::vector< Edge >	edges_

bool	is_direct_ = true

bool	is_weighted_ = false

std::vector< vert_t >	verts_

Friends
std::ostream &	operator<< (std::ostream &os, const Graph< vert_t, weight_t >::Edge &edge)

Detailed Description

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>
class Graph< vert_t, weight_t >

Класс графа (может быть взвешенным и ориентированным).

Template Parameters

vert_t	тип вершин.
weight_t	тип весов.

Constructor & Destructor Documentation

◆ Graph() [1/4]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

Graph< vert_t, weight_t >::Graph ( )

inline

Инициализирует новый экземпляр Graph.

47: edges_(), verts_() {}

Graph::edges_

std::vector< Edge > edges_

Definition graph.hpp:736

Graph::verts_

std::vector< vert_t > verts_

Definition graph.hpp:737

Here is the caller graph for this function:

◆ Graph() [2/4]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

Graph< vert_t, weight_t >::Graph ( const Graph< vert_t, weight_t > & other )

default

Копирующий конструктор.

Parameters

other граф, который нужно скопировать.

◆ Graph() [3/4]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

Graph< vert_t, weight_t >::Graph ( Graph< vert_t, weight_t > && other )

inlinenoexcept

Перемещающий конструктор. Перемещает ресурсы из другого графа.

Parameters

other граф, ресурсы которого нужно переместить.

      : edges_(std::move(other.edges_)),
        verts_(std::move(other.verts_)),
        is_direct_{other.is_direct_} {}

◆ Graph() [4/4]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

Graph< vert_t, weight_t >::Graph ( const std::vector< Edge > & edges )

inlineprivate

                                      {
    if (edges.empty()) return;
 
    for (const auto& edge : edges) {
      if (edge.IsWeighted()) is_weighted_ = true;
      AddEdge_(edge);
    }
 
    if constexpr (std::is_arithmetic_v<vert_t>) {
      // кол-во вершин = максимальная вершина среди ребер, т.е. в этом случае
      // происходит заполнение вершин до наибольшей из них в списке ребер
      vert_t max_vert = edges[0].StartVert();
 
      for (const auto& edge : edges_) {
        max_vert = std::max(max_vert, edge.StartVert());
        max_vert = std::max(max_vert, edge.EndVert());
      }
 
      verts_.resize(max_vert + 1);
      std::iota(verts_.begin(), verts_.end(), 0);
 
    } else if constexpr (std::is_same_v<vert_t, std::string>)
      for (const auto& edge : edges_) {
        if (!Contains(Verts(), edge.StartVert()))
          verts_.push_back(edge.StartVert());
 
        if (!Contains(Verts(), edge.EndVert()))
          verts_.push_back(edge.EndVert());
      }
  }

Here is the call graph for this function:

Member Function Documentation

◆ AddEdge() [1/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::AddEdge	(	const std::pair< vert_t, vert_t > &	edge_pair,
		bool	ignore_warning = false )

inline

Warning: "AddEdge: weighted graph must consist of weighted edges.

                                            {
    if (IsWeighted() && !ignore_warning)
      std::cerr << "Warning! AddEdge: weighted graph should consist of "
                   "weighted edges."
                << std::endl;
 
    AddEdge_(Edge(edge_pair.first, edge_pair.second, static_cast<weight_t>(0)));
  }

Here is the call graph for this function:

◆ AddEdge() [2/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::AddEdge	(	const std::tuple< vert_t, vert_t, weight_t > &	edge_tuple,
		bool	ignore_warning = false )

inline

Warning: "AddEdge: weighted graph must consist of weighted edges.

                                            {
    if (WeightFromTuple(edge_tuple) == 0)
      AddEdge({StartVertFromTuple(edge_tuple), EndVertFromTuple(edge_tuple)},
              ignore_warning);
    else
      AddEdge_(edge_tuple);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddEdge_()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::AddEdge_ ( const Edge & edge )

inlineprivate

                                  {
    AddVert(edge.StartVert());
    AddVert(edge.EndVert());
 
    if (!Contains(edges_, edge)) edges_.emplace_back(edge);
 
    if (edge.Weight() != 0) is_weighted_ = true;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ AddVert()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::AddVert ( const vert_t & vert )

inline

                                   {
    if (!Contains(verts_, vert)) verts_.push_back(vert);
  }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ContainsEdge() [1/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

bool Graph< vert_t, weight_t >::ContainsEdge ( const std::pair< vert_t, vert_t > & edge ) const

inline

Проверяет, содержится ли ребро в графе (НЕВЗВЕШЕННЫЙ).

Parameters

edge ребро.

Returns: true: содержится.; false: не содержится.

                                                               {
    return GetEdgeIter_(edge) != edges_.end();
  }

Here is the call graph for this function:

◆ ContainsEdge() [2/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

bool Graph< vert_t, weight_t >::ContainsEdge ( const std::tuple< vert_t, vert_t, weight_t > & edge ) const

inline

Проверяет, содержится ли ребро в графе (ВЗВЕШЕННЫЙ).

Parameters

edge ребро.

Returns: true: содержится.; false: не содержится.

Exceptions

`std::logic_error("ContainsEdge graph is not weighted.")`.

                                                                          {
    if (!IsWeighted())
      throw std::logic_error("ContainsEdge: graph is not weighted.");
 
    return GetEdgeIter_(edge) != edges_.end();
  }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ ContainsVert()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

bool Graph< vert_t, weight_t >::ContainsVert ( const vert_t & vert ) const

inline

Проверяет, содержится ли вершина в графе.

Parameters

vert вершина.

Returns: true: содержится.; false: не содержится.

                                              {
    return std::find(Verts().begin(), Verts().end(), vert) != Verts().end();
  }

Here is the call graph for this function:

◆ Edges()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::vector< std::tuple< vert_t, vert_t, weight_t > > Graph< vert_t, weight_t >::Edges ( ) const

inline

Returns: std::vector<std::tuple<vert_t, vert_t, weight_t>>: ребра.

                                                              {
    if (edges_.empty()) return {};
 
    std::vector<std::tuple<vert_t, vert_t, weight_t>> edges_tuples(
        edges_.size());
    std::transform(edges_.begin(), edges_.end(), edges_tuples.begin(),
                   [](const Edge& edge) {
                     return std::make_tuple(edge.StartVert(), edge.EndVert(),
                                            edge.Weight());
                   });
 
    return edges_tuples;
  }

◆ EdgesAmount()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

size_t Graph< vert_t, weight_t >::EdgesAmount ( ) const

inline

Returns: vert_t: кол-во ребер.

323{ return edges_.size(); }

Here is the caller graph for this function:

◆ GetAdjList()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::unordered_map< vert_t, std::vector< vert_t > > Graph< vert_t, weight_t >::GetAdjList ( ) const

inline

Returns: std::unordered_map<vert_t, std::vector<vert_t>>: список смежности с указанием вершины-ключа.

                                                                 {
    auto adj_list_dict = std::unordered_map<vert_t, std::vector<vert_t>>();
 
    for (const auto& edge : edges_) {
      adj_list_dict[edge.StartVert()].push_back(edge.EndVert());
      if (!IsDirected())
        adj_list_dict[edge.EndVert()].push_back(edge.StartVert());
    }
 
    return adj_list_dict;
  }

Here is the call graph for this function:

◆ GetAdjListWithoutKeys()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::vector< std::vector< vert_t > > Graph< vert_t, weight_t >::GetAdjListWithoutKeys ( ) const

inline

Returns: std::vector<std::vector<vert_t>>: список смежности.

Exceptions

`std::logic_error("GetAdjListWithoutKeys this method is deleted for std::string.")`.

                                                             {
    if constexpr (std::is_arithmetic_v<vert_t>) {
      std::vector<std::vector<vert_t>> adj_list(
          *std::max_element(Verts().begin(), Verts().end()) + 1);
 
      for (const auto& edge : edges_) {
        adj_list[edge.StartVert()].push_back(edge.EndVert());
        if (!IsDirected()) adj_list[edge.EndVert()].push_back(edge.StartVert());
      }
 
      return adj_list;
    }
 
    else if constexpr (std::is_same_v<vert_t, std::string>)
      throw std::logic_error(
          "GetAdjListWithoutKeys: this method is deleted for std::string.");
  }

Here is the call graph for this function:

◆ GetAdjMatrix()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::vector< std::vector< weight_t > > Graph< vert_t, weight_t >::GetAdjMatrix ( ) const

inline

Returns: std::vector<std::vector<vert_t>>: матрица смежности.

Exceptions

`std::logic_error("GetAdjMatrix this method is deleted for std::string.")`.

                                                      {
    if constexpr (std::is_arithmetic_v<vert_t>) {
      std::vector<std::vector<weight_t>> adj_matrix(
          VertsAmount(), std::vector<weight_t>(VertsAmount(), 0));
 
      for (const auto& edge : edges_)
        if (edge.IsWeighted()) {
          adj_matrix[edge.StartVert()][edge.EndVert()] = edge.Weight();
          if (!IsDirected())
            adj_matrix[edge.EndVert()][edge.StartVert()] = edge.Weight();
        } else {
          adj_matrix[edge.StartVert()][edge.EndVert()] = 1;
          if (!IsDirected()) adj_matrix[edge.EndVert()][edge.StartVert()] = 1;
        }
 
      return adj_matrix;
    }
 
    else if constexpr (std::is_same_v<vert_t, std::string>)
      throw std::logic_error(
          "GetAdjMatrix: this method is deleted for std::string.");
  }

Here is the call graph for this function:

◆ GetEdgeIter_() [1/3]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

auto Graph< vert_t, weight_t >::GetEdgeIter_ ( const std::pair< vert_t, vert_t > & edge )

inlineprivate

                                                         {
    auto [start_vert, end_vert] = edge;
 
    return std::find_if(
        edges_.begin(), edges_.end(),
        [start_vert, end_vert, this](const auto& e) {
          return (e.StartVert() == start_vert && e.EndVert() == end_vert) ||
                 (!IsDirected() && e.StartVert() == end_vert &&
                  e.EndVert() == start_vert);
        });
  }

◆ GetEdgeIter_() [2/3]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

auto Graph< vert_t, weight_t >::GetEdgeIter_ ( const std::pair< vert_t, vert_t > & edge ) const

inlineprivate

                                                               {
    auto [start_vert, end_vert] = edge;
 
    return std::find_if(
        edges_.begin(), edges_.end(),
        [start_vert, end_vert, this](const auto& e) {
          return (e.StartVert() == start_vert && e.EndVert() == end_vert) ||
                 (!IsDirected() && e.StartVert() == end_vert &&
                  e.EndVert() == start_vert);
        });
  }

Here is the caller graph for this function:

◆ GetEdgeIter_() [3/3]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

auto Graph< vert_t, weight_t >::GetEdgeIter_ ( const std::tuple< vert_t, vert_t, weight_t > & edge ) const

inlineprivate

                                                                          {
    auto [start_vert, end_vert, weight] = edge;
 
    return std::find_if(
        edges_.begin(), edges_.end(),
        [start_vert, end_vert, weight, this](const auto& e) {
          return (e.StartVert() == start_vert && e.EndVert() == end_vert &&
                  e.Weight() == weight) ||
                 (!IsDirected() && e.StartVert() == end_vert &&
                  e.EndVert() == start_vert && e.Weight() == weight);
        });
  }

◆ GetEdgeWeight()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

weight_t Graph< vert_t, weight_t >::GetEdgeWeight ( const std::pair< vert_t, vert_t > & edge ) const

inline

Находит вес ребра в взвешенном графе.

Parameters

edge ребро.

Returns: weight_t: вес.

Exceptions

`std::logic_error("GetEdgeWeight graph is not weighted.")`. @throw `std::invalid_argument("GetEdgeWeight: there is no such edge:")`.

                                                                    {
    if (!IsWeighted())
      throw std::logic_error("GetEdgeWeight: graph is not weighted.");
 
    auto it = GetEdgeIter_(edge);
 
    if (it == edges_.end())
      throw std::invalid_argument("GetEdgeWeight: there is no such edge: " +
                                  Edge(edge).Name());
 
    return it->Weight();
  }

Here is the call graph for this function:

◆ GraphFromAdjList() [1/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphFromAdjList ( const std::unordered_map< vert_t, std::vector< vert_t > > & adj_list_dict )

inlinestatic

Создает новый экземпляр Graph. по списку смежности с указанием вершины-ключа (НЕВЗВЕШЕННЫЙ).

Parameters

adj_list_dict список смежности с указанием вершины-ключа.

Returns: Graph: новый экземпляр Graph.

                                                                        {
    if (adj_list_dict.empty()) return Graph();
 
    std::vector<Edge> edges{};
 
    for (const auto& vert_str_pair : adj_list_dict) {
      auto vert = vert_str_pair.first;
      for (const auto& vert_2 : vert_str_pair.second)
        edges.push_back(Edge(vert, vert_2));
    }
 
    return Graph(edges);
  }

Here is the call graph for this function:

◆ GraphFromAdjList() [2/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphFromAdjList ( const std::vector< std::vector< vert_t > > & adj_list )

inlinestatic

Создает новый экземпляр Graph. по списку смежности (НЕВЗВЕШЕННЫЙ).

Parameters

adj_list список смежности.

Returns: Graph: новый экземпляр Graph.

Exceptions

std::logic_error("GraphFromAdjList this method (constructor) is deleted for std::string.").

                                                    {
    if constexpr (std::is_arithmetic_v<vert_t>) {
      if (adj_list.empty()) return Graph();
 
      std::vector<Edge> edges{};
 
      for (size_t row = 0; row < adj_list.size(); row++)
        for (size_t col = 0; col < adj_list[row].size(); col++)
          edges.push_back(Edge(row, adj_list[row][col]));
 
      return Graph(edges);
 
    } else if constexpr (std::is_same_v<vert_t, std::string>)
      throw std::logic_error(
          "GraphFromAdjList: this method (constructor) "
          "is deleted for std::string.");
  }

Here is the call graph for this function:

◆ GraphFromAdjMatrix()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphFromAdjMatrix	(	const std::vector< std::vector< weight_t > > &	adj_matrix,
		bool	is_weighted = false )

inlinestatic

Создает новый экземпляр Graph по матрице смежности.

Parameters

adj_matrix	матрица смежности.
is_weighted	взвешен ли граф.

Returns: Graph: новый экземпляр Graph.

Exceptions

`std::invalid_argument("GraphFromAdjMatrix AdjacencyMatrix is not squared.")`. @throw `std::invalid_argument("GraphFromAdjMatrix: AdjacencyMatrix is not squared [row problem].")`. @throw `std::logic_error("GraphFromAdjMatrix: this method (constructor) is deleted for std::string.")`.

                                {
    if constexpr (std::is_arithmetic_v<vert_t>) {
      if (adj_matrix.empty()) return Graph();
 
      std::vector<Edge> edges{};
 
      if (adj_matrix.size() != adj_matrix[0].size())
        throw std::invalid_argument(
            "GraphFromAdjMatrix: AdjacencyMatrix is not squared.");
 
      for (size_t row = 0; row < adj_matrix.size(); row++) {
        if (row != 0)
          if (adj_matrix[row].size() != adj_matrix[row - 1].size())
            throw std::invalid_argument(
                "GraphFromAdjMatrix: AdjacencyMatrix is not squared [row "
                "problem].");
 
        for (size_t col = 0; col < adj_matrix[row].size(); col++) {
          if (adj_matrix[row][col] == 0) continue;
 
          if (is_weighted)
            edges.push_back(Edge(col, row, adj_matrix[col][row]));
          else
            edges.push_back(Edge(col, row));
        }
      }
 
      return Graph(edges);
 
    } else if constexpr (std::is_same_v<vert_t, std::string>)
      throw std::logic_error(
          "GraphFromAdjMatrix: this method (constructor) "
          "is deleted for std::string.");
  }

Here is the call graph for this function:

◆ GraphFromMap()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphFromMap ( const std::unordered_map< std::string, weight_t > & edges_dict )

inlinestatic

Создает новый экземпляр Graph по ребрам. представленными словарем из std::string и weight_t (ВЗВЕШЕННЫЙ).

Parameters

edges_dict ребра графа.

Returns: Graph: новый экземпляр Graph.

                                                               {
    if (edges_dict.empty()) return Graph();
 
    std::vector<Graph<vert_t, weight_t>::Edge> edges;
 
    for (const auto& [edge_str, weight] : edges_dict) {
      vert_t start_vert, end_vert;
      std::tie(start_vert, end_vert) = ParseEdgeString_(edge_str);
 
      edges.emplace_back(start_vert, end_vert, weight);
    }
 
    return Graph(edges);
  }

Here is the call graph for this function:

◆ GraphFromStrs()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphFromStrs ( const std::vector< std::string > & edges_strs )

inlinestatic

Создает новый экземпляр Graph по ребрам. представленными вектором std::string (НЕВЗВЕШЕННЫЙ).

Parameters

edges_strs ребра графа.

Returns: Graph: новый экземпляр Graph.

                                                                     {
    if (edges_strs.empty()) return Graph();
 
    std::vector<Graph<vert_t, weight_t>::Edge> edges;
 
    for (const auto& edge_str : edges_strs) {
      vert_t start_vert, end_vert;
      std::tie(start_vert, end_vert) = ParseEdgeString_(edge_str);
 
      edges.emplace_back(start_vert, end_vert);
    }
 
    return Graph(edges);
  }

Here is the call graph for this function:

◆ GraphNonWeighted()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphNonWeighted ( const std::vector< std::pair< vert_t, vert_t > > & edges_pairs )

inlinestatic

Создает новый экземпляр Graph по ребрам, представленными вектором std::pair (НЕВЗВЕШЕННЫЙ).

Parameters

edges_pairs ребра графа.

Returns: Graph: новый экземпляр Graph.

                                                             {
    if (edges_pairs.empty()) return Graph();
 
    std::vector<Edge> edges{};
    edges.reserve(edges_pairs.size());
 
    for (const auto& edge : edges_pairs) edges.push_back(edge);
 
    return Graph(edges);
  }

Here is the call graph for this function:

◆ GraphWeighted() [1/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphWeighted	(	const std::vector< std::pair< vert_t, vert_t > > &	edges_pairs,
		const std::vector< weight_t > &	weights )

inlinestatic

Создает новый экземпляр Graph по ребрам, представленными вектором std::pair и weight_t (ВЗВЕШЕННЫЙ).

Parameters

edges_pairs	ребра графа.
weights	веса ребер.

Returns: Graph: новый экземпляр Graph.

Exceptions

`std::invalid_argument("GraphWeighted the sizes of the edges and weights vectors do not match.")`.

                                          {
    if (edges_pairs.empty() && weights.empty()) return Graph();
 
    std::vector<Edge> edges{};
    edges.reserve(edges_pairs.size());
 
    if (edges_pairs.size() != weights.size())
      throw std::invalid_argument(
          "GraphWeighted: the sizes of the edges and weights vectors do not "
          "match.");
 
    for (size_t i = 0; i < weights.size(); i++)
      edges.push_back(Edge(edges_pairs[i], weights[i]));
 
    return Graph(edges);
  }

Here is the call graph for this function:

◆ GraphWeighted() [2/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static Graph Graph< vert_t, weight_t >::GraphWeighted ( const std::vector< std::tuple< vert_t, vert_t, weight_t > > & edges_tuples )

inlinestatic

Создает новый экземпляр Graph по ребрам. представленными вектором std::tuple (ВЗВЕШЕННЫЙ).

Parameters

edges_tuples ребра графа.

Returns: Graph: новый экземпляр Graph.

                                                                         {
    if (edges_tuples.empty()) return Graph();
 
    std::vector<Edge> edges;
 
    for (const auto& [start, end, weight] : edges_tuples)
      edges.emplace_back(start, end, weight);
 
    return Graph(edges);
  }

Here is the call graph for this function:

◆ IsDirected()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

bool Graph< vert_t, weight_t >::IsDirected ( ) const

inline

Проверяет, направлен ли граф.

417{ return is_direct_; }

Here is the caller graph for this function:

◆ IsWeighted()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

bool Graph< vert_t, weight_t >::IsWeighted ( ) const

inline

Проверяет, взвешен ли граф.

317{ return is_weighted_; }

Here is the caller graph for this function:

◆ MakeDirected()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::MakeDirected ( )

inline

Делает граф направленным (ничего).

414{ is_direct_ = true; }

◆ MakeUndirected()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::MakeUndirected ( )

inline

Делает граф ненаправленным (удаляет лишние ребра).

                        {
    std::unordered_set<size_t> seen_edges;
    std::vector<Edge> unique_edges;
    unique_edges.reserve(EdgesAmount());
 
    for (size_t i = 0; i < EdgesAmount(); i++) {
      if (seen_edges.count(i) != 0) continue;
 
      for (size_t j = i + 1; j < EdgesAmount(); j++)
        if (edges_[i].StartVert() == edges_[j].EndVert() &&
            edges_[j].StartVert() == edges_[i].EndVert()) {
          seen_edges.insert(j);
          break;
        }
 
      unique_edges.push_back(edges_[i]);
    }
 
    edges_ = std::move(unique_edges);
    is_direct_ = false;
  }

Here is the call graph for this function:

◆ operator=() [1/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

Graph & Graph< vert_t, weight_t >::operator= ( const Graph< vert_t, weight_t > & other )

default

Оператор копирующего присваивания.

Parameters

other граф, значения которого нужно присвоить.

Returns: Graph&: ссылка на текущий объект.

◆ operator=() [2/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

Graph & Graph< vert_t, weight_t >::operator= ( Graph< vert_t, weight_t > && other )

inlinenoexcept

Оператор перемещающего присваивания. Перемещает ресурсы из другого. графа.

Parameters

other граф, ресурсы которого нужно переместить.

Returns: Graph&: ссылка на текущий объект.

                                           {
    if (this != &other) {
      edges_ = std::move(other.edges_);
      verts_ = std::move(other.verts_);
      is_direct_ = other.is_direct_;
    }
 
    return *this;
  }

◆ ParseEdgeString_()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

static std::pair< vert_t, vert_t > Graph< vert_t, weight_t >::ParseEdgeString_ ( const std::string & edge_str )

inlinestaticprivate

                                 {
    const size_t pos = edge_str.find("->");
    vert_t start_vert;
    vert_t end_vert;
 
    if (pos == std::string::npos)
      throw std::invalid_argument("EdgeString: invalid edge string format: " +
                                  edge_str);
 
    if constexpr (std::is_arithmetic_v<vert_t>) {
      try {
        start_vert = std::stoul(edge_str.substr(0, pos));
        end_vert = std::stoul(edge_str.substr(pos + 2));
      }
 
      catch (const std::exception&) {
        throw std::invalid_argument(
            "EdgeString: invalid edge string format "
            "(vertices should be numbers): " +
            edge_str);
      }
    }
 
    else if constexpr (std::is_same_v<vert_t, std::string>) {
      start_vert = edge_str.substr(0, pos);
      end_vert = edge_str.substr(pos + 2);
    }
 
    return {start_vert, end_vert};
  }

Here is the caller graph for this function:

◆ PrintAdjList()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::ostream & Graph< vert_t, weight_t >::PrintAdjList ( std::ostream & os = std::cout ) const

inline

Выводит в поток список смежности.

Parameters

os	входной поток.

Returns: std::ostream&: выходной поток.

                                                           {
    for (const auto& vert : Verts()) {
      os << vert << ": ";
 
      for (const auto& neighbor : edges_) {
        if (neighbor.StartVert() == vert) os << neighbor.EndVert() << "; ";
        if (!IsDirected())
          if (neighbor.EndVert() == vert) os << neighbor.StartVert() << "; ";
      }
 
      os << "\n";
    }
 
    return os;
  }

Here is the call graph for this function:

◆ PrintEdges()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::ostream & Graph< vert_t, weight_t >::PrintEdges ( std::ostream & os = std::cout ) const

inline

Выводит в поток список ребер.

Parameters

os	входной поток.

Returns: std::ostream&: выходной поток.

                                                         {
    os << edges_;
    return os;
  }

Here is the caller graph for this function:

◆ PrintVerts()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::ostream & Graph< vert_t, weight_t >::PrintVerts ( std::ostream & os = std::cout ) const

inline

Выводит в поток список вершин.

Parameters

os	входной поток.

Returns: std::ostream&: выходной поток.

                                                         {
    os << Verts();
    return os;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

◆ RemoveEdge() [1/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::RemoveEdge ( const std::pair< vert_t, vert_t > & edge_pair )

inline

Exceptions

`std::invalid_argument("RemoveEdge there is no such edge:")`.

                                                            {
    if (!ContainsEdge(edge_pair))
      throw std::invalid_argument(
          "RemoveEdge: there is no such edge in graph: " +
          Edge(edge_pair).Name());
 
    edges_.erase(std::remove_if(edges_.begin(), edges_.end(),
                                [&edge_pair, this](const Edge& e) {
                                  return (e == Edge(edge_pair)) ||
                                         (!IsDirected() &&
                                          Edge(e.EndVert(), e.StartVert()) ==
                                              Edge(edge_pair));
                                }),
                 edges_.end());
  }

Here is the call graph for this function:

◆ RemoveEdge() [2/2]

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::RemoveEdge ( const std::tuple< vert_t, vert_t, weight_t > & edge_tuple )

inline

Exceptions

`std::invalid_argument("RemoveEdge there is no such edge:")`.

                                                                        {
    if (!ContainsEdge(edge_tuple))
      throw std::invalid_argument(
          "RemoveEdge: there is no such edge in graph: " +
          Edge(edge_tuple).Name());
 
    edges_.erase(
        std::remove_if(
            edges_.begin(), edges_.end(),
            [&edge_tuple, this](const Edge& e) {
              return (e == Edge(edge_tuple)) ||
                     (!IsDirected() &&
                      e == Edge(std::make_tuple(EndVertFromTuple(edge_tuple),
                                                StartVertFromTuple(edge_tuple),
                                                WeightFromTuple(edge_tuple))));
            }),
        edges_.end());
  }

Here is the call graph for this function:

◆ RemoveVert()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::RemoveVert ( const vert_t & vert )

inline

Exceptions

`std::invalid_argument("RemoveVert there is no such vert:")`.

                                      {
    if constexpr (std::is_arithmetic_v<vert_t>) {
      if (!Contains(Verts(), vert))
        throw std::invalid_argument(
            "RemoveVert: there is no such vert in graph: " +
            std::to_string(vert));
    }
 
    else if constexpr (std::is_same_v<vert_t, std::string>)
      if (!Contains(Verts(), vert))
        throw std::invalid_argument(
            "RemoveVert: there is no such vert in graph: " + vert);
 
    verts_.erase(std::remove(verts_.begin(), verts_.end(), vert), verts_.end());
 
    edges_.erase(std::remove_if(edges_.begin(), edges_.end(),
                                [vert](const Edge& edge) {
                                  return edge.StartVert() == vert ||
                                         edge.EndVert() == vert;
                                }),
                 edges_.end());
  }

Here is the call graph for this function:

◆ SetEdgeWeight()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

void Graph< vert_t, weight_t >::SetEdgeWeight	(	const std::pair< vert_t, vert_t > &	edge,
		weight_t	new_weight )

inline

Меняет вес ребра в взвешенном графе.

Parameters

edge	ребро.
new_weight	вес.

Exceptions

`std::logic_error("SetEdgeWeight graph is not weighted.")`. @throw `std::invalid_argument("SetEdgeWeight: there is no such edge:")`.

                                          {
    if (!IsWeighted())
      throw std::logic_error("SetEdgeWeight: graph is not weighted.");
 
    auto it = GetEdgeIter_(edge);
 
    if (it == edges_.end())
      throw std::invalid_argument("SetEdgeWeight: there is no such edge: " +
                                  Edge(edge).Name());
 
    it->SetWeight(new_weight);
  }

Here is the call graph for this function:

◆ Verts()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

const std::vector< vert_t > & Graph< vert_t, weight_t >::Verts ( ) const

inline

Returns: const std::vector<vert_t>&: вершины.

326{ return verts_; }

Here is the caller graph for this function:

◆ VertsAmount()

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

size_t Graph< vert_t, weight_t >::VertsAmount ( ) const

inline

Returns: size_t: кол-во вершин.

320{ return verts_.size(); }

Here is the caller graph for this function:

Friends And Related Symbol Documentation

◆ operator<<

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::ostream & operator<<	(	std::ostream &	os,
		const Graph< vert_t, weight_t >::Edge &	edge )

friend

                                                                           {
    os << edge.Name();
    return os;
  }

Member Data Documentation

◆ edges_

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::vector<Edge> Graph< vert_t, weight_t >::edges_

private

◆ is_direct_

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

bool Graph< vert_t, weight_t >::is_direct_ = true

private

◆ is_weighted_

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

bool Graph< vert_t, weight_t >::is_weighted_ = false

private

◆ verts_

template<AllowedVertType vert_t = std::string, AllowedWeightType weight_t = size_t>

std::vector<vert_t> Graph< vert_t, weight_t >::verts_

private

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

lib/src/graph.hpp

Classes

Public Member Functions

Static Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Friends

Detailed Description

Constructor & Destructor Documentation

◆ Graph() [1/4]

◆ Graph() [2/4]

◆ Graph() [3/4]

◆ Graph() [4/4]

Member Function Documentation

◆ AddEdge() [1/2]

◆ AddEdge() [2/2]

◆ AddEdge_()

◆ AddVert()

◆ ContainsEdge() [1/2]

◆ ContainsEdge() [2/2]

◆ ContainsVert()

◆ Edges()

◆ EdgesAmount()

◆ GetAdjList()

◆ GetAdjListWithoutKeys()

◆ GetAdjMatrix()

◆ GetEdgeIter_() [1/3]

◆ GetEdgeIter_() [2/3]

◆ GetEdgeIter_() [3/3]

◆ GetEdgeWeight()

◆ GraphFromAdjList() [1/2]

◆ GraphFromAdjList() [2/2]

◆ GraphFromAdjMatrix()

◆ GraphFromMap()

◆ GraphFromStrs()

◆ GraphNonWeighted()

◆ GraphWeighted() [1/2]

◆ GraphWeighted() [2/2]

◆ IsDirected()

◆ IsWeighted()

◆ MakeDirected()

◆ MakeUndirected()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ ParseEdgeString_()

◆ PrintAdjList()

◆ PrintEdges()

◆ PrintVerts()

◆ RemoveEdge() [1/2]

◆ RemoveEdge() [2/2]

◆ RemoveVert()

◆ SetEdgeWeight()

◆ Verts()

◆ VertsAmount()

Friends And Related Symbol Documentation

◆ operator<<

Member Data Documentation

◆ edges_

◆ is_direct_

◆ is_weighted_

◆ verts_