Skip to content

Instantly share code, notes, and snippets.

@caotic123

caotic123/basic_graphs.cpp

Last active December 15, 2019 00:13
Show Gist options
  • Save caotic123/d6b3d502ace458c9547c31a06cafc164 to your computer and use it in GitHub Desktop.
Save caotic123/d6b3d502ace458c9547c31a06cafc164 to your computer and use it in GitHub Desktop.
Download ZIP
Graph datatype - Krustal and Prim Implementation
Raw
basic_graphs.cpp
#include <iostream>
#include <functional>
#include <map>
#include <list>
#include <vector>
#include <tuple>
#include <algorithm>
struct Empyth {
enum { isEmyth = 1 };
};
template <typename T>
struct graph {
graph(T x)
: a(x)
{
em_ = 1;
}
graph operator[](unsigned int x)
{
std::get<0>(self) = x;
return *this;
}
std::pair<unsigned int, std::list<graph<T>*> > self;
T a;
int em_;
};
template <>
struct graph<Empyth> {
graph() { em_ = 0; }
graph operator[](unsigned int x)
{
std::get<0>(self) = x;
return *this;
}
std::pair<unsigned int, std::list<graph<Empyth>*> > self;
int em_;
};
template <typename T>
using graph_s = std::vector<graph<T>*>;
template <typename T>
struct graph_ {
graph_s<T> __;
graph_<T> InsertVertex(graph_<T> G, graph<T>* graf_)
{
(*graf_) = (*graf_)[G.__.size()];
G.__.push_back(graf_);
return G;
}
graph_<T> insertEdge(graph_<T> G, int v, int w)
{
auto f = [](graph_<T> G, int v, int w) {
std::get<1>(G.__[v]->self).push_back(G.__[w]);
return G;
};
return f(f(G, w, v), v, w);
}
std::list<unsigned int> search_d(graph<T> _, std::vector<bool> __t,
std::list<unsigned int> __)
{
using list_graph = std::list<graph<T>*>;
__t[std::get<0>(_.self)] = true;
list_graph t = (std::get<1>(_.self));
__.push_back(std::get<0>(_.self));
for (auto i = t.begin(); i != t.end(); i++) {
if (!__t[std::get<0>((*i)->self)]) {
return search_d((**i), __t, __);
}
}
return __;
};
std::function<std::list<unsigned int>(graph<T>, std::list<unsigned int>)>
search_l = [&](graph<T> _, std::list<unsigned int> __t) {
using d = typename std::list<std::pair<graph<T>, bool> >::iterator;
std::function<d(d, d, graph<T>)> p = [&](
typename std::list<std::pair<graph<T>, bool> >::iterator x_,
typename std::list<std::pair<graph<T>, bool> >::iterator e_,
graph<T> y_) {
return (x_ == e_) ? e_ : (((*x_).first.self).first == y_.self.first)
? x_
: p(++x_, e_, y_);
};
typename std::list<std::pair<graph<T>, bool> > f_list = {
std::make_pair(_, false)
};
typename std::list<std::pair<graph<T>, bool> >::iterator x__ = f_list.begin();
using list_graph = std::list<graph<T>*>;
list_graph __;
typename std::list<std::pair<graph<T>, bool> >::iterator p__;
while (x__ != f_list.end()) {
__ = (((*x__).first).self).second;
__t.push_back((((*x__).first).self).first);
for (auto i = __.begin(); i != __.end() && (*x__).second == false;
i++) {
p__ = p(f_list.begin(), f_list.end(), (*(*i)));
if (p__ == f_list.end() || (std::get<1>(*p__) != true && ((((*x__).first).self).first) == (((**i).self).first))) {
f_list.push_back(std::make_pair(*(*i), false));
}
}
std::get<1>(*x__) = true;
x__++;
}
return __t;
};
void printDFS(graph_<T> t)
{
std::list<unsigned int> s_ = search_d(*t.__[0], std::vector<bool>(t.__.size(), false),
std::list<unsigned int>());
for_each(s_.begin(), s_.end(),
[](unsigned int x) { std::cout << x << " "; });
std::cout << std::endl;
}
void printBFS(graph_<T> t)
{
std::list<unsigned int> s_ = search_l(*t.__[0], std::list<unsigned int>());
for_each(s_.begin(), s_.end(),
[](unsigned int x) { std::cout << x << " "; });
std::cout << std::endl;
}
auto removeVertex(graph_<T> t, int v) -> typename std::list<
typename decltype(std::declval<decltype(t)>().__)::value_type>::iterator
{
typename std::list<typename decltype(
std::declval<decltype(t)>().__)::value_type>::iterator d;
t.__.erase(t.__.begin() + v);
for (typename std::vector<graph<T>*>::iterator i = t.__.begin();
i != t.__.end(); i++) {
d = std::remove_if((((**i).self).second).begin(),
(((**i).self).second).end(),
[&](graph<T>* _) { return ((*_).self).first == v; });
}
return d;
}
auto removeEdge(graph_<T> t, int v) -> typename std::list<
typename decltype(std::declval<decltype(t)>().__)::value_type>::iterator
{
typename std::list<typename decltype(
std::declval<decltype(t)>().__)::value_type>::iterator d;
for (typename std::vector<graph<T>*>::iterator i = t.__.begin();
i != t.__.end(); i++) {
d = std::remove_if((((**i).self).second).begin(),
(((**i).self).second).end(),
[&](graph<T>* _) { return ((*_).self).first == v; });
}
return d;
}
std::list<graph<T>*> EndVertice(graph_<T> t, int v)
{
std::list<graph<T>*> f;
for (typename std::vector<graph<T>*>::iterator i = t.__.begin();
i != t.__.end(); i++) {
std::for_each(((**i).self).second.begin(), (((**i).self).second).end(),
[&](graph<T>* _) {
if (((*_).self).first == v) {
f.push_back(_);
}
});
}
return f;
}
bool areAdjacent(graph_<T> t, int v, int w)
{
std::pair<bool, bool> fx = std::make_pair(false, false);
std::for_each(((*t.__[v]).self).second.begin(),
(((*t.__[v]).self).second).end(), [&](graph<T>* _) {
if (((*_).self).first == w) {
std::get<0>(fx) = true;
}
});
std::for_each(((*t.__[w]).self).second.begin(),
((*t.__[w]).self).second.end(), [&](graph<T>* _) {
if (((*_).self).first == v) {
std::get<1>(fx) = true;
}
});
return std::get<0>(fx) == true && std::get<1>(fx) == true;
}
graph<T>* opposite(graph_<T> t, graph<T> v, int w)
{
graph<T>* op;
std::for_each((v.self).second.begin(), ((v.self).second).end(),
[&](graph<T>* _) {
if (((*_).self).first == w) {
op = _;
}
});
return op;
}
};
int main()
{
graph_<Empyth> t; // Cria um grafo "vazio" sem pesos ou informação
graph_<int> d; // Cria um grafo que armazena um inteiro
graph_<std::string> graph_str; // Grafico de String
graph_<std::string> bolo;
t = t.InsertVertex(
t.InsertVertex(t.InsertVertex(t.InsertVertex(t, new graph<Empyth>()),
new graph<Empyth>()),
new graph<Empyth>()),
new graph<Empyth>()); // Cria um grafo com tamanho de 4 vertices
t = t.insertEdge(t, 0, 1); // Liga o 0 -> 1 (Arestas)
t = t.insertEdge(t, 1, 3); // Liga 1 -> 3
t = t.insertEdge(t, 3, 0); // Liga 3 -> 0
t.printBFS(t); // Printa o grafo t usando a largura
t.removeVertex(t, 1); // Remove o vertice e arestas correspondetes (1)
d = d.InsertVertex(
d.InsertVertex(d.InsertVertex(d, new graph<int>(4)), new graph<int>(4)),
new graph<int>(10));
d = d.insertEdge(d, 2, 1);
d = d.insertEdge(d, 0, 1);
d.printDFS(d); // Printa usando profundidade
graph_str = graph_str.InsertVertex(graph_str, new graph<std::string>("Ovo"));
graph_str = graph_str.InsertVertex(graph_str, new graph<std::string>("Clara"));
bolo = bolo.insertEdge(graph_str, 0, 1);
bolo.printDFS(bolo);
}
Raw
krustal_and_prim.cpp
#include <iostream>
#include <fstream>
#include <list>
#include "dirent.h"
#include <chrono>
#include <vector>
#include <thread>
#include <algorithm>
#include <array>
#include <tuple>
#include <stack>
struct graph__ {
std::list<std::pair<graph__*, int>> fx;
int d_;
};
graph__* new__graph() {
return new graph__;
}
int getGraphAmoung(std::string t) {
std::ifstream file(t);
std::string s;
int d;
while(s != "contains") {
file >> s;
}
file >> d;
return d;
}
std::list<std::string> all_file_graph() {
DIR* dir;
struct dirent* ent;
std::ifstream file;
std::list<std::string> files_;
if ((dir = opendir("./graph")) != NULL) {
while ((ent = readdir(dir)) != NULL) {
file.open(("graph/" + std::string(ent->d_name)).c_str());
if (file.is_open() && std::string(ent->d_name).length() > 6) {
files_.push_back(("graph/" + std::string(ent->d_name)).c_str());
}
file.close();
}
closedir(dir);
}
return files_;
}
bool cicle(std::vector<graph__*> graph_s, int l) {
auto dfs_ = [](std::vector<graph__*> graph_s, int n, int len) {
using T = decltype(std::declval<graph__>().fx);
std::stack<int> stack__;
bool visited[n], pilha_rec[n];
bool found;
T::iterator it;
for (int i = 1; i <= len; i++) {
visited[i] = false;
pilha_rec[i] = false;
}
while(true) {
found = true;
if (!visited[n]) {
stack__.push(n);
visited[n] = true;
pilha_rec[n] = true;
}
for (it = graph_s[n]->fx.begin(); it != graph_s[n]->fx.end(); it++) {
if (pilha_rec[(*it).first->d_]) {return true;}
else if (visited[(*it).first->d_]) {found = true; break;}
}
if (!found) {
std::cout << stack__.top() << std::endl;
pilha_rec[stack__.top()] = false;
stack__.pop();
if (stack__.empty()) {
break;
}
n = stack__.top();
}
if (it == graph_s[n]->fx.end()) {return false;}
else {n = (*it).first->d_;}
}
return false;
};
for (int i=1; i <= l; i++) {
if (dfs_(graph_s, graph_s[i]->d_, l)) {return true;}
}
return false;
}
void krustal__(std::vector<graph__*> f_, int n) {
using T = decltype(std::declval<graph__>().fx);
std::vector<graph__*> new_graph(n);
for (int i=0; i <= n; i++) {
new_graph[i] = new__graph();
new_graph[i]->d_ = i;
}
std::vector<bool> v_(n, false);
auto less_path = [&](std::vector<graph__*> f_, int n) {
auto l_path = [](graph__* x){
T::iterator _ = x->fx.begin();
for (T::iterator i = x->fx.begin(); i != x->fx.end(); i++) {
if ((*i).second > (*_).second) {
_ = i;
}
}
return (*_);
};
T::value_type min = *(f_[1]->fx.begin());
T::value_type dd_;
int w;
for (int i=1; i <=n-1; i++) {
std::cout << i << std::endl;
dd_ = l_path(f_[i]);
if (min.second > dd_.second && !v_[dd_.first->d_]) {
v_[dd_.first->d_] = true;
min = dd_;
w = f_[i]->d_;
}
}
return make_pair(min, w);
};
std::cout << cicle(f_, n) << std::endl;
auto f = less_path(f_, n);
while(!cicle(new_graph, n)) {
std::cout << std::get<1>(f) << std::endl;
new_graph[std::get<1>(f)]->fx.push_back(std::get<0>(f));
f = less_path(f_, n);
}
}
void primm__(graph__* actual, int n_) {
auto f = std::vector<std::tuple<bool, bool, int, graph__*>>(n_, std::make_tuple(false, false, 0, (graph__*)NULL));
f[actual->d_] = std::make_tuple(true, false, 0, actual);
decltype(f)::value_type s_ = f[actual->d_];
using T = decltype(std::declval<graph__>().fx);
auto walk_path = [&](graph__* a_) {
std::get<1>(f[a_->d_]) = true; // has been visited
for (T::iterator ___i = a_->fx.begin(); ___i != a_->fx.end(); ___i++) {
f[(*___i).first->d_] = std::make_tuple(true, std::get<1>(f[(*___i).first->d_]), (*___i).second, (*___i).first);
}
return f[a_->d_];
};
bool b;
while (b) {
s_ = walk_path(std::get<3>(s_));
b = false;
std::for_each(f.begin(), f.end(), [&](decltype(f)::value_type __f){if ((std::get<0>(__f) && !std::get<1>(__f) && (std::get<2>(s_) > std::get<2>(__f))) || (std::get<1>(s_) && std::get<0>(__f) && !std::get<1>(__f))) {b = true; s_ = __f;} });
}
}
int main() {
std::list<std::string> graph_ = all_file_graph();
std::vector<std::vector<graph__*>> data__;
std::vector<graph__*> f_;
std::ifstream file_graph;
std::string f_s;
int d[3];
for (std::list<std::string>::iterator i = graph_.begin(); i != graph_.end(); i++) {
for (int _ = (getGraphAmoung(*i)+1); _ >= 0; _--) {
f_.push_back(new__graph());
}
file_graph.open(*i);
while(file_graph >> f_s) {
if (f_s == "a") {
file_graph >> d[1];
file_graph >> d[2];
file_graph >> d[3];
f_[d[1]]->fx.push_back(std::make_pair(f_[d[2]], d[3]));
(*f_[d[1]]).d_ = d[1];
}
}
file_graph.close();
primm__(f_[1], getGraphAmoung(*i)+1);
krustal__(f_, getGraphAmoung(*i)+1);
f_.clear();
break;
// std::this_thread::sleep_for(std::chrono::milliseconds(1000*2));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment