main
#include <iostream>
#include "graph.hpp"
#include "set.hpp"
#include <fstream>
//stack<int> dfs(graph)
int main() {
srand((unsigned) time(nullptr));
int order = 10;
nodeset U(order);
nodeset V(order);
graph T(order);
for (int i = 1; i <= order; i++) U.ins(i);
int u = U.select(rand() % U.size() + 1);
U.del(u);
V.ins(u);
while (!U.empty()) {
int u = U.select(rand() % U.size() + 1);
int v = V.select(rand() % V.size() + 1);
T.set(u,v);
U.del(u);
V.ins(u);
}
T.print();
T.dot("arbol");
//graph covertree(T.order());
return 0;
}
set.cpp
#include "set.hpp"
nodeset::nodeset(int cap): n(cap), s(0){
r = nullptr;
}
nodeset::~nodeset() {}
void nodeset::ins(int x) {
assert(!full());
if (empty()){
r = new node(x);
s++;
}else {
node *p = r;
node *q = nullptr;
while (p and p -> data() != x){
q = p;
p = x < p -> data() ? p -> left() : p -> right();
}
if (p == nullptr) {
if (x < q -> data()) q -> left(new node(x));
else q -> right(new node(x));
s++;
}
}
}
void nodeset::del(int x) {
cout << "del " << x << endl;
node *p = r;
node *q = nullptr;
while (p && p -> data() !=x) {
q = p;
if(x < p -> data()) {
p = p ->left()
}
}
}
void nodeset::print() {
cout << "[ ";
order(r);
cout << "]\n";
}
void nodeset::order(node *p) {
cout << "order" << endl;
if (p == nullptr) return;
order(p -> left());
order(p -> right());
cout << p -> data() << " ";
}
void nodeset::order(node *p, int &k, int &n) {
if (p == nullptr or k == 0) return;
k--;
if (k == 0) n = p -> data();
order(p -> left(), k, n);
order(p -> right(), k, n);
}
int nodeset::select(int k){
cout << "select" << endl;
int n;
order(r,k,n);
return n;
}
set.hpp
#ifndef set_hpp
#define set_hpp
#include<iostream>
#include<cassert>
using namespace std;
class nodeset{
class node {
int _data;
node *lft;
node *rgt;
public:
node(int x): lft(nullptr), rgt(nullptr) { _data = x; }
int data() const { return _data; }
node *left() const { return lft; }
node *right() const { return rgt; }
void left(node *p) { lft = p; }
void right(node *p) { rgt = p; }
};
node *r;
int n; //Capacidad
int s; //Tamaño
void order(node *);
void order(node *, int &, int &);
public:
nodeset(int);
~nodeset(int);
int select(int k);
void ins(int);
void del(int);
int capacity() const { return n; }
int size() const { return s;}
bool empty() const { return s == 0; }
bool full() const { return s == n; }
void print();
};
#endif /* btree_hpp*/
graph.cpp
#include "graph.hpp"
bool graph::valid(int i, int j){
assert(0 < i and i <= n);
assert(0 < j and j <= n);
//assert(i != j);
return true;
}
int graph::f(int i, int j) {
valid(i,j);
if (i < j) {
int k = i;
i = j;
j = k;
}
return (i - 1) * (i - 2) / 2 + j - 1;
}
graph::graph(int ord): n(ord) {
m = n * (n - 1) / 2;
T = new bool[m];
for (int i = 0; i < m; i++) T[i] = false;
}
graph::~graph() {
delete [ ] T;
}
void graph::set(int i, int j, bool e) {
valid(i,j);
if (i != j) T[f(i,j)] = e;
}
bool graph::get(int i, int j) {
valid(i,j);
return i == j ? false : T[f(i,j)];
}
void graph::print() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) cout << false << " ";
else cout << T[f(i,j)] << " ";
}
cout << endl;
}
}
void graph::dot(string fname) {
ofstream file(fname);
file << "graph {\n";
cout << "graph {\n";
for (int i = 2; i <= n; i++)
for (int j = 1; j < i; j++)
if (T[f(i,j)]){
file << i << " -- " << j << endl;
cout << i << " -- " << j << endl;
}
file << "}\n";
cout << "}\n";
}
graph.hpp
#ifndef graph_hpp
#define graph_hpp
#include <iostream>
#include <fstream>
#include <cassert>
using namespace std;
class graph {
int n; // orden del grafo, cantidad de vertices
int m; // tamaño máximo del grafo, cantidad de aristas
//int s; // tamaño del grafo, cantidad de nodos
bool *T;
int f(int, int);
bool valid(int, int);
public:
graph(int);
~graph();
void set(int, int, bool = true); // vamos a quitar depende del get
bool get(int, int); // hay o no hay arista
int order() const { return n; }
//int size() const { return s; }
void print();
void dot(string);
};
#endif /* graph_hpp */
Top comments (0)