Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 21.12.2022, 16:50   #1
Шляпадляменя
Пользователь
 
Регистрация: 01.12.2022
Сообщений: 18
По умолчанию Создание полного графа

Помогите создать случайный полный неориентированный граф, где граф представлен:
Код:
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;
		}
	}

Последний раз редактировалось Шляпадляменя; 21.12.2022 в 17:09.
Шляпадляменя вне форума Ответить с цитированием
Старый 21.12.2022, 18:17   #2
Шляпадляменя
Пользователь
 
Регистрация: 01.12.2022
Сообщений: 18
По умолчанию

У меня получилось создать ребра от одной вершины к остальным, а как теперь провести их от каждой вершины к другим
Код:
for (int i = 0; i < N+1; i++) {
        start = 1;
        end = rand() % N+1;
        if (start != end)
            g.add_edge(start, end, rand() % 210 / 10.f);
}
Шляпадляменя вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Создание динамического графа Дмитрий Семиахин PHP 1 15.11.2016 21:22
Создание истории обновления ячеек до полного заполнения листа qwerty456 Microsoft Office Excel 4 24.10.2015 10:46
создание графа по матрице и поиск кратчайшего пути из одного графа в другой lexflax Общие вопросы C/C++ 1 06.09.2012 07:32
VBA создание графа Silant Microsoft Office Excel 1 26.04.2012 04:06
Матрица полного графа (Pascal) dream1k Помощь студентам 0 19.10.2011 10:24