Ferramentas de Utilizador

Ferramentas de Site


dev_geral:cpp:grafos

Classe de Grafos

FIXME este tutorial precisa de revisão para estar de acordo com as Regras de Estilo e Formatação

Esta é uma classe de grafos bastante simples. Tem um pequeno exemplo na função web() e main().

O resulado devolvido pelo membro add_node é um id do nó (um pouco como o int é usado nos file descriptors).

Nota: Faltam ainda alguns métodos importantes da classe.

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 *));
	// Copy constructor
	// List of lastest nodes to be used as cache
	~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);
	//* rm_node(int node);
	int unlink_nodes(int node1, int node2);
 
	// operator =
	// operator ==
	// operator !=
 
	//std::vector<int> &get_shortest_path(int node1, int node2, float &distance) const;
	//std::vector<int> &get_shortest_path(int node1, int node2) const;
	//+ get_node_data(int node) const;
	//get_shortest_distance(int node1, int node2) const;
	//+ std::set get_adjacent_nodes(int node) const;
	//+ get_node_degree(int node) const;
	//+ get_node_by_data(void *data, bool (*cmp)(void *d1, void *d2)) const;
	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.cc:

/*
 *  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;
}
dev_geral/cpp/grafos.txt · Esta página foi modificada pela última vez em: 2018/05/14 21:37 (Edição externa)