graph.h

Go to the documentation of this file. Or view the newest version in sPHENIX GitHub for file graph.h

/* This software is distributed under the GNU Lesser General Public License */
//==========================================================================
//
//   graph.h
//
//==========================================================================
// $Id: graph.h,v 1.43 2002/11/06 08:49:35 raitner Exp $

#ifndef GTL_GRAPH_H
#define GTL_GRAPH_H

#include <GTL/GTL.h>
#include <GTL/node.h>
#include <GTL/edge.h>
#include <GTL/edge_map.h>
#include <GTL/node_map.h>
#include <GTL/gml_parser.h>

#include <iostream>
#include <string>

__GTL_BEGIN_NAMESPACE

class GTL_EXTERN graph
{
public:
    //================================================== Con-/Destructors

    graph();

    graph (const graph& G);
    
    graph (const graph& G, const list<node>& nodes);
    
    graph (const graph& G, 
        list<node>::const_iterator it, 
        list<node>::const_iterator end);
    
    virtual ~graph();
    
    //================================================== Directed/Undirected

    void make_directed();

    void make_undirected();

    //================================================== Tests / Information
    
    bool is_directed() const;

    bool is_undirected() const;

    bool is_bidirected(edge_map<edge>& rev) const;

    bool is_connected() const;

    bool is_acyclic() const;

    int number_of_nodes() const;

    int number_of_edges() const;

    node center() const;

    //================================================== Creation
    
    virtual node new_node();
    
    virtual edge new_edge(node s, node t);

    virtual edge new_edge(const list<node> &sources, const list<node> &targets);

    //================================================== Deletion

    void del_node(node n);

    void del_all_nodes(); 

    void del_edge(edge e);

    void del_all_edges(); 

    void clear();

    //================================================== Iterators

    typedef list<node>::const_iterator node_iterator;
    typedef list<edge>::const_iterator edge_iterator;
    
    node_iterator nodes_begin() const;
    
    node_iterator nodes_end() const;
    
    edge_iterator edges_begin() const;
    
    edge_iterator edges_end() const;

    //================================================== get nodes/edges

    list<node> all_nodes() const;

    list<edge> all_edges() const;
 
    node choose_node () const;
    
    //================================================== Hide / Restore

    void hide_edge (edge e);
    
    void restore_edge (edge e);

    list<edge> hide_node (node n);

    void restore_node (node n);

    void induced_subgraph (list<node>& subgraph_nodes);

    void restore_graph ();

    //================================================== Others

    list<edge> insert_reverse_edges();
    
    //================================================== I/O

    GML_error load (const string& filename, bool preserve_ids = false) 
        { return load (filename.c_str(), preserve_ids); }

    
    GML_error load (const char* filename, bool preserve_ids = false);

    int save (const char* filename) const;

    void save (ostream* file = &cout) const;

    //================================================== Node handlers
    
    virtual void pre_new_node_handler() {}

    virtual void post_new_node_handler(node n) {}

    virtual void pre_del_node_handler(node n) {}        

    virtual void post_del_node_handler() {}             

    virtual void pre_hide_node_handler(node n) {}          

    virtual void post_hide_node_handler(node n) {}         

    virtual void pre_restore_node_handler(node n) {}       
 
   virtual void post_restore_node_handler(node n) {}

   //================================================== Edge handlers

    virtual void pre_new_edge_handler(node s, node t) {}    

    virtual void post_new_edge_handler(edge e) {}          

    virtual void pre_del_edge_handler(edge e) {}           

    virtual void post_del_edge_handler(node, node) {}
    
    virtual void pre_hide_edge_handler(edge e) {}          

    virtual void post_hide_edge_handler(edge e) {}         

    virtual void pre_restore_edge_handler(edge e) {}       
 
   virtual void post_restore_edge_handler(edge e) {}

    //================================================== Global handlers
    
    virtual void pre_clear_handler()  {}

   virtual void post_clear_handler() {} 

    virtual void pre_make_directed_handler()  {}

    virtual void post_make_directed_handler()  {}

    virtual void pre_make_undirected_handler()  {}

    virtual void post_make_undirected_handler()  {}


    //================================================== I/O - Handler 

    virtual void pre_graph_save_handler (ostream* os) const { };

    virtual void save_graph_info_handler (ostream*) const { };
    
    virtual void save_node_info_handler (ostream*, node) const { };

    virtual void save_edge_info_handler (ostream*, edge) const { };

    virtual void after_graph_save_handler (ostream* ) const { };

    virtual void top_level_key_handler (GML_pair* list);

    virtual void load_node_info_handler (node n, GML_pair* list );
    
    virtual void load_edge_info_handler (edge e, GML_pair* list);

    virtual void load_graph_info_handler (GML_pair* list);

private:

    //================================================== Flags
    
    mutable bool directed;

    //================================================== Visible Nodes/Edges
    
    list<node> nodes;
    list<edge> edges;
    int nodes_count, edges_count;

    //================================================== Hidden Nodes/Edges
    
    list<node> hidden_nodes;
    list<edge> hidden_edges;
    int hidden_nodes_count, hidden_edges_count; 

    //================================================== Node/edge numbering

    int new_node_id();
    int new_edge_id();

    //================================================== Copy 
    
    void copy (const graph& G, 
        list<node>::const_iterator it, 
        list<node>::const_iterator end);

public: // needs to be public, because template friends are not possible
    int number_of_ids(node) const;
    
    int number_of_ids(edge) const;
    
private:
    list<int> free_node_ids;
    list<int> free_edge_ids;
    int free_node_ids_count, free_edge_ids_count;

    //================================================== utilities
    
    void del_list(list<node> &);
    void del_list(list<edge> &);

    GTL_EXTERN friend ostream& operator<< (ostream& os, const graph& G);
};

__GTL_END_NAMESPACE

//--------------------------------------------------------------------------
//   Iteration
//--------------------------------------------------------------------------

#define forall_nodes(v,g) GTL_FORALL(v,g,graph::node_iterator,nodes_)
#define forall_edges(v,g) GTL_FORALL(v,g,graph::edge_iterator,edges_)
    
#endif // GTL_GRAPH_H

//--------------------------------------------------------------------------
//   end of file
//--------------------------------------------------------------------------