arboles set graph

//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;
}

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;
}

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*/

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”;
}

#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 */