Помогите создать случайный полный неориентированный граф, где граф представлен:
Код:
Graph.cpp
#include "graph.h"
#include <stdexcept>
using namespace std;
Graph::Graph(initializer_list<tuple<int, int, double>> edges) {
for (const auto& e : edges) {
add_edge(get<0>(e), get<1>(e), get<2>(e));
}
}
void Graph::add_vertex(int vertex) {
if (!has_vertex(vertex)) {
vertices[vertex] = std::map<int, double>();
}
}
void Graph::add_edge(int start_vertex, int end_vertex, double weight) {
add_vertex(start_vertex);
add_vertex(end_vertex);
vertices[start_vertex][end_vertex] = weight;
vertices[end_vertex][start_vertex] = weight;
}
std::vector<int> Graph::get_vertices() const {
std::vector<int> result;
for (const auto& p : vertices) {
result.push_back(p.first);
}
return result;
}
std::vector<int> Graph::get_adjacent_vertices(int src_vertex) const {
const auto it = vertices.find(src_vertex);
if (it == vertices.end()) {
return std::vector<int> {};
}
vector<int> result;
for (const auto& p : it->second) {
result.push_back(p.first);
}
return result;
}
vector<pair<int, double>> Graph::get_adjacent_edges(int src_vertex) const {
const auto it = vertices.find(src_vertex);
if (it == vertices.end()) {
return vector<pair<int, double>> {};
}
vector<pair<int, double>> result;
for (const auto& p : it->second) {
result.push_back(make_pair(p.first, p.second));
}
return result;
}
bool Graph::has_vertex(int vertex) const {
return (vertices.find(vertex) != vertices.end());
}
bool Graph::has_edge(int start_vertex, int end_vertex) const {
const auto it = vertices.find(start_vertex);
if (it == vertices.end()) {
return false;
}
return (it->second.find(end_vertex) != it->second.end());
}
double Graph::edge_weight(int start_vertex, int end_vertex) const {
const auto it_s = vertices.find(start_vertex);
if (it_s == vertices.end()) {
throw invalid_argument("Edge doesn't exist");
}
const auto it_e = it_s->second.find(end_vertex);
if (it_e == it_s->second.end()) {
throw invalid_argument("Edge doesn't exist");
}
return it_e->second;
}
void Graph::remove_vertex(int vertex) {
/// Remove adjacent edges.
auto adjacent_vertices = get_adjacent_vertices(vertex);
for (const auto& adj_v : adjacent_vertices) {
remove_edge(adj_v, vertex);
}
/// Remove the vertex itself.
vertices.erase(vertex);
}
void Graph::remove_edge(int start_vertex, int end_vertex) {
auto it_s = vertices.find(start_vertex);
if (it_s != vertices.end()) {
it_s->second.erase(end_vertex);
}
auto it_e = vertices.find(end_vertex);
if (it_e != vertices.end()) {
it_e->second.erase(start_vertex);
}
}
Graph.h
Код:
#include <map>
#include <vector>
#include <tuple>
#include <initializer_list>
/**
* Non-oriented weighted graph.
**/
class Graph {
public:
Graph() {}
Graph(std::initializer_list<std::tuple<int, int, double>> edges);
/// Add single vertex to the graph.
void add_vertex(int vertex);
/// Add vertices (if necessary) and an edge between them to the graph.
void add_edge(int start_vertex, int end_vertex, double weight = 1.0);
/// Return all vertices of the graph.
std::vector<int> get_vertices() const;
/// Return all adjacent by edges vertices for the specified vertex.
std::vector<int> get_adjacent_vertices(int src_vertex) const;
/// Get adjacent edges for the vertex as vector of (end vertex, edge weight).
std::vector<std::pair<int, double>> get_adjacent_edges(int src_vertex) const;
/// Return true if the vertex exists in the graph, false otherwise.
bool has_vertex(int vertex) const;
/// Return true if vertices exist and have an edge between them, false otherwise.
bool has_edge(int start_vertex, int end_vertex) const;
/// Return weight of an edge between vertices (if there is any), throw an exception otherwise.
double edge_weight (int start_vertex, int end_vertex) const;
/// Remove the vertex and all its adjacent edges from the graph.
void remove_vertex(int vertex);
/// Remove the edge from the graph (but not the vertices).
void remove_edge(int start_vertex, int end_vertex);
private:
std::map<int, std::map<int, double>> vertices;
};
Можно ли переделать эту функцию под полный граф?
Код:
int main(int argc, char* argv[]) {
srand(time(NULL));
Graph g;
int start, end, N = 5;
for (int i = 0; i < N; i++) {
start = rand() % N+1;
end = rand() % N+1;
if (start != end)
g.add_edge(start, end, rand() % 210 / 10.f);
}
vector<int> verts = g.get_vertices();
}
for (int v1 : verts) {
vector<pair<int, double>> edges = g.get_adjacent_edges(v1);
for (pair<int, double> e : edges) {
int v2 = e.first;
double w = e.second;
}
}