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