• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

orium

Grafos

5 mensagens neste tópico

Esta e' uma class de grafos bastante simples, que eu fiz a' pouco tempo.

Não passou por testes intensivos, portanto e' possivel que tenha algum problema.

Tem um pequeno exemplo na funcao main() e web().

O resulado devolvido pelo membro add_node e' um id do no' (um pouco como o int também e' usado nos file descriptors).

Nota: Faltam ainda algums metedos importantes a' class!

graph.h:

/*
*  GPL
*
*  graph - Written by Diogo Sousa aka orium
*  Copyright (C) 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef GRAPH_H_
#define GRAPH_H_

#include <iostream>
#include <vector>
#include <set>

class graph
{
private:

struct node_info
{
	void *data;

	int node_no;

	struct neighbour_info
	{
		node_info *node;
		double weight;
		bool walkable;
	};

	std::vector<struct neighbour_info> neighbour;

	int neighbours;
};

std::set<node_info *> main_node;
int main_nodes;

int total_nodes;
int nodes_seq_no;

void (*for_each_node_free_callback)(void *);

node_info *depth_first_search_recursive(node_info *node,
					std::set<int> &visited,
					bool (*cmp)(const node_info *, const void *),
					const void *needle) const;

node_info *depth_first_search(bool (*cmp)(const node_info *, const void *),
			      const void *needle) const;
node_info *depth_first_search_in_sub_graph(graph::node_info *node,
					   bool (*cmp)(const node_info *, const void *),
					   const void *needle) const;

bool are_nodes_in_connected_graph(node_info *node1, int node2) const;
bool are_nodes_adjacent(node_info *node1, int node2) const;

void set_node_in_main_graphs(node_info *node);

void link_node(node_info *n1, node_info *n2, bool walkable, double weight);
void unlink_node(node_info *node1, node_info *node2);

void print_graph_recursive(std::ostream &out, graph::node_info *node, std::set<int> &visited) const;

void free_everything_recursive(node_info *node, std::set<node_info *> &visited);


static bool search_by_node_no(const node_info *node, const void *needle);

public:
enum link_type
{
	UNIDIRECTIONAL,
	BIDIRECTIONAL
};

graph(void);
graph(void (*for_each_node_callback)(void *));
~graph(void);

int add_node(void *data=NULL);
int link_nodes(int node1, int node2, enum link_type link_type=BIDIRECTIONAL, double weight=0.0);
int unlink_nodes(int node1, int node2);

void print_graph(std::ostream &out=std::cout) const;
bool are_nodes_in_connected_graph(int node1, int node2) const;
bool are_nodes_adjacent(int node1, int node2) const;
};

#endif

graph.h:

/*
*  GPL
*
*  graph - Written by Diogo Sousa aka orium
*  Copyright (C) 2008 Diogo Sousa
*
*  This program is free software: you can redistribute it and/or modify
*  it under the terms of the GNU General Public License as published by
*  the Free Software Foundation, either version 3 of the License, or
*  (at your option) any later version.
*
*  This program is distributed in the hope that it will be useful,
*  but WITHOUT ANY WARRANTY; without even the implied warranty of
*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
*  GNU General Public License for more details.
*
*  You should have received a copy of the GNU General Public License
*  along with this program.  If not, see <http://www.gnu.org/licenses/>.
*/

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

#include "graph.h"

graph::graph(void)
{
main_nodes=0;
total_nodes=0;
nodes_seq_no=0;

for_each_node_free_callback=NULL;
}

graph::graph(void (*for_each_node_free_callback)(void *))
{
main_nodes=0;
total_nodes=0;
nodes_seq_no=0;

this->for_each_node_free_callback=for_each_node_free_callback;
}

graph::~graph(void)
{
std::set<node_info *> visited;
std::set<node_info *>::const_iterator i;

for (i=main_node.begin(); i != main_node.end(); i++)
{
	visited.erase(visited.begin(),visited.end()); // This is an independent graph
	visited.insert(*i);

	free_everything_recursive(*i,visited);

	if (for_each_node_free_callback)
		for_each_node_free_callback((*i)->data);

	delete *i;
}
}

void graph::free_everything_recursive(node_info *node,
			      std::set<node_info *> &visited)
{
std::vector<node_info::neighbour_info>::const_iterator i;

for (i=node->neighbour.begin(); i != node->neighbour.end(); i++)
	if (!binary_search(visited.begin(),visited.end(),i->node))
	{
		visited.insert(i->node);
		free_everything_recursive(i->node,visited);

		if (for_each_node_free_callback)
			for_each_node_free_callback(i->node->data);

		delete i->node;
	}
}

graph::node_info *graph::depth_first_search_recursive(node_info *node,
					      std::set<int> &visited,
					      bool (*cmp)(const node_info *, const void *),
					      const void *needle) const
{
std::vector<node_info::neighbour_info>::const_iterator i;
node_info *r;

for (i=node->neighbour.begin(); i != node->neighbour.end(); i++)
{
	if (cmp(i->node,needle))
		return i->node;

	if (!binary_search(visited.begin(),visited.end(),i->node->node_no))
	{
		visited.insert(i->node->node_no);
		if ((r=depth_first_search_recursive(i->node,visited,cmp,needle)))
			return r;
	}
}

return NULL;
}

graph::node_info *graph::depth_first_search(bool (*cmp)(const node_info *, const void *),
				    const void *needle) const 
{
std::set<int> visited;
std::set<node_info *>::const_iterator i;
node_info *r;

for (i=main_node.begin(); i != main_node.end(); i++)
{
	visited.erase(visited.begin(),visited.end()); // This is an independent graph
	visited.insert((*i)->node_no);

	if (cmp(*i,needle))
		return *i;

	if ((r=depth_first_search_recursive(*i,visited,cmp,needle)))
		return r;
}

return NULL;
}

graph::node_info *graph::depth_first_search_in_sub_graph(graph::node_info *node,
						 bool (*cmp)(const node_info *, const void *),
						 const void *needle) const
{
std::set<int> visited;
node_info *r;

visited.erase(visited.begin(),visited.end());
visited.insert(node->node_no);

if (cmp(node,needle))
	return node;

if ((r=depth_first_search_recursive(node,visited,cmp,needle)))
	return r;

return NULL;
}

bool graph::search_by_node_no(const node_info *node, const void *needle)
{
return node->node_no == *static_cast<const int *>(needle);
}

bool graph::are_nodes_in_connected_graph(node_info *node1, int node2) const
{
return depth_first_search_in_sub_graph(node1,&search_by_node_no,(const void *)&node2);
}

bool graph::are_nodes_in_connected_graph(int node1, int node2) const
{
node_info *n1;

n1=depth_first_search(&search_by_node_no,(const void *)&node1);

return are_nodes_in_connected_graph(n1,node2);
}

// Links node1 to node2 
// Ex:
//   node1 -------> node2
//   node2 - ||| -> node1
void graph::link_node(node_info *n1, node_info *n2, bool walkable, double weight)
{
node_info::neighbour_info neighbour;

if (are_nodes_adjacent(n1,n2->node_no))
	return;

neighbour.node=n2;
neighbour.weight=weight;
neighbour.walkable=walkable;

n1->neighbour.push_back(neighbour);

n1->neighbours++;
}

void graph::set_node_in_main_graphs(node_info *node)
{
main_node.insert(node);

main_nodes++;
}

int graph::add_node(void *data)
{
node_info *new_node;

new_node=new node_info;

new_node->data=data;
new_node->node_no=nodes_seq_no;
new_node->neighbours=0;

set_node_in_main_graphs(new_node);

total_nodes++;

return nodes_seq_no++;
}

int graph::link_nodes(int node1, int node2, enum link_type link_type, double weight)
{
node_info *n1;
node_info *n2;

n1=depth_first_search(&search_by_node_no,(const void *)&node1);
n2=depth_first_search(&search_by_node_no,(const void *)&node2);

if (!n1 || !n2)
	return -1;

if (!are_nodes_in_connected_graph(n1,node2))
{
	// The graph n2 must be in one of the main graphs
	std::set<node_info *>::iterator i;

	for (i=main_node.begin(); i != main_node.end(); i++)
		if (depth_first_search_in_sub_graph(*i,&search_by_node_no,(const void *)&node2))
		{
                                // We can remove the entire graph because it will now be all connected to node1
			main_node.erase(i);
			main_nodes--;

			break;
		}
}

link_node(n1,n2,link_type == UNIDIRECTIONAL || link_type == BIDIRECTIONAL,weight);
link_node(n2,n1,link_type == BIDIRECTIONAL,weight);

return 0;
}

bool graph::are_nodes_adjacent(node_info *node1, int node2) const
{
std::vector<node_info::neighbour_info>::const_iterator i;

for (i=node1->neighbour.begin(); i != node1->neighbour.end(); i++)
	if (i->node->node_no == node2)
		return true;

return false;
}

bool graph::are_nodes_adjacent(int node1, int node2) const
{
return are_nodes_adjacent(depth_first_search(&search_by_node_no,(const void *)&node1),node2);
}

// Unlinks node1 from node2 
// Ex:
//   node1 - ||| -> node2
//   node2 -------> node1
void graph::unlink_node(node_info *node1, node_info *node2)
{
std::vector<node_info::neighbour_info>::iterator i;

for (i=node1->neighbour.begin(); i != node1->neighbour.end(); i++)
	if (i->node == node2)
	{
		node1->neighbour.erase(i);
		node1->neighbours--;
		break;
	}
}

int graph::unlink_nodes(int node1, int node2)
{
node_info *n1;
node_info *n2;

n1=depth_first_search(&search_by_node_no,(const void *)&node1);
n2=depth_first_search(&search_by_node_no,(const void *)&node2);

if (!n1 || !n2)
	return -1;

if (!are_nodes_adjacent(n1,node2))
	return 0; // If you want to make this an error return -1 instead

unlink_node(n1,n2);
unlink_node(n2,n1);

if (!depth_first_search(&search_by_node_no,(const void *)&node1))
	set_node_in_main_graphs(n1);

if (!depth_first_search(&search_by_node_no,(const void *)&node2))
	set_node_in_main_graphs(n2);

return 0;
}

void graph::print_graph_recursive(std::ostream &out, graph::node_info *node, std::set<int> &visited) const
{
std::vector<node_info::neighbour_info>::const_iterator i;

if (!node->neighbours)
	std::cout << "Node " << node->node_no << " links nowhere" << std::endl;

for (i=node->neighbour.begin(); i != node->neighbour.end(); i++)
{
	std::cout << "Node " << node->node_no << " links to " << i->node->node_no << std::endl;

	if (!binary_search(visited.begin(),visited.end(),i->node->node_no))
	{
		visited.insert(i->node->node_no);			
		print_graph_recursive(out,i->node,visited);
	}
}
}

void graph::print_graph(std::ostream &out) const
{
std::set<int> visited;
std::set<node_info *>::const_iterator i;

for (i=main_node.begin(); i != main_node.end(); i++)
{
	visited.erase(visited.begin(),visited.end()); // This is an independent graph
	visited.insert((*i)->node_no);

	print_graph_recursive(out,*i,visited);
}
}

void web(void) // Just for fun
{
graph my_graph;
std::vector<int> n;
int i;

for (i=0; i < 11; i++)
	n.push_back(my_graph.add_node());

for (i=1; i <= 5; i++) // A web 
{
	my_graph.link_nodes(n[0],n[i]);
	my_graph.link_nodes(n[i],n[i%5+1]);
	my_graph.link_nodes(n[i],n[i+5]);
	my_graph.link_nodes(n[i+5],n[(i+5)%10+1]);
}

my_graph.print_graph();
}

int main(void)
{
graph my_graph;
int a;
int b;
int c;
int d;
int e;
int f;
int g;
int h;
int i;

a=my_graph.add_node();
b=my_graph.add_node();
c=my_graph.add_node();
d=my_graph.add_node();
e=my_graph.add_node();
f=my_graph.add_node();
g=my_graph.add_node();
h=my_graph.add_node();
i=my_graph.add_node();

my_graph.link_nodes(a,b,graph::BIDIRECTIONAL,7.0);
my_graph.link_nodes(b,c,graph::BIDIRECTIONAL,8.0);
my_graph.link_nodes(a,d,graph::BIDIRECTIONAL,5.0);
my_graph.link_nodes(d,b,graph::BIDIRECTIONAL,9.0);
my_graph.link_nodes(b,e,graph::BIDIRECTIONAL,7.0);
my_graph.link_nodes(c,e,graph::BIDIRECTIONAL,5.0);
my_graph.link_nodes(d,e,graph::BIDIRECTIONAL,15.0);
my_graph.link_nodes(d,f,graph::BIDIRECTIONAL,6.0);
my_graph.link_nodes(e,f,graph::BIDIRECTIONAL,8.0);
my_graph.link_nodes(e,g,graph::BIDIRECTIONAL,9.0);
my_graph.link_nodes(f,g,graph::BIDIRECTIONAL,11.0);

my_graph.unlink_nodes(f,g);

my_graph.link_nodes(h,i);

my_graph.unlink_nodes(h,i);

my_graph.print_graph();

return 0;
}

Modificação:

Destrutor liberta a memória alocada

Adicionado graph::unlink_nodes()

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Um bocado de texto a explicar o código ajudava, e dava um bom tópico, é que assim não me diz nada...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Um bocado de texto a explicar o código ajudava, e dava um bom tópico, é que assim não me diz nada...

De qualquer maneira este código esta' francamente mau, um muito mais elegante e facil de perceber esta na wiki (e no armazem de codigo em C), basicamente foi reescrito em C, tentado ser mais rápido, elegante e coerente. Este esta' uma salganhada...

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora