00001 /******************************************************************************* 00002 + 00003 + rm3_simple_graph.h 00004 + 00005 + This file is part of GDToolkit. It can be 00006 + used free of charge in academic research and teaching. 00007 + Any direct or indirect commercial use of this software is illegal 00008 + without a written authorization of 00009 + the Dipartimento di Informatica e Automazione 00010 + Universita' di Roma Tre, Roma, ITALIA 00011 + 00012 + 00013 *******************************************************************************/ 00016 #ifndef SIMPLE_GRAPH_H 00017 #define SIMPLE_GRAPH_H 00018 00019 00020 #include<iostream> 00021 #include<GDT/gdtlist.h> 00022 #include<GDT/gdt_error.h> 00023 #include<GDT/rm3_undi_graph.h> 00024 00025 using namespace std; 00026 00027 class struct_node; 00028 class struct_edge; 00029 00030 typedef struct_node* node; 00031 typedef struct_edge* edge; 00032 00033 class simple_graph; 00034 00036 // Class Node 00038 00039 class struct_node 00040 { 00041 friend class simple_graph; 00042 friend class undi_graph; 00043 00044 private: 00045 gdt::gdtlist<edge> incident_edges; 00046 int index; 00047 gdt::list_item position_in_nodelist; 00048 00049 public: 00050 struct_node() 00051 { 00052 position_in_nodelist=NULL; 00053 }; 00054 00055 struct_node(int id) 00056 { 00057 index=id; 00058 position_in_nodelist=NULL; 00059 }; 00060 00061 int get_index() const {return index;} 00062 int degree() const {return incident_edges.length();} 00063 00064 }; // end of class node 00065 00066 ostream& operator<<(ostream& oo, const struct_node* n); 00067 00068 00069 00071 // Class Edge 00073 00074 class struct_edge 00075 { 00076 friend class simple_graph; 00077 friend class undi_graph; 00078 00079 private: 00080 int index; 00081 node _start; 00082 node _end; 00083 gdt::list_item position_in_edgelist; 00084 gdt::list_item position_in_startnode; 00085 gdt::list_item position_in_endnode; 00086 00087 int weight; 00088 00089 public: 00090 struct_edge(int id) 00091 { 00092 index=id; 00093 _start=NULL; 00094 _end=NULL; 00095 position_in_edgelist=NULL; 00096 position_in_startnode=NULL; 00097 position_in_endnode=NULL; 00098 }; 00099 00100 struct_edge() 00101 { 00102 _start=NULL; 00103 _end=NULL; 00104 position_in_edgelist=NULL; 00105 position_in_startnode=NULL; 00106 position_in_endnode=NULL; 00107 } 00108 00109 struct_edge(node n1, node n2, int id); 00110 00111 int get_index() const {return index;}; 00112 int get_weight(){return weight;}; 00113 void set_weight(int w) {weight=w;} 00114 node start() const {return _start;} 00115 node end() const {return _end;}; 00116 00117 }; // end of class edge 00118 00119 00120 ostream& operator<<(ostream& oo, const struct_edge* n); 00121 00122 00124 // Class simple_graph 00126 00127 00128 class simple_graph 00129 { 00130 00131 friend class undi_graph; 00132 private: 00133 00134 int _max_node_id; 00135 int _max_edge_id; 00136 00137 bool check(); 00138 00139 public: 00140 00141 gdt::gdtlist<node> _nodes; 00142 gdt::gdtlist<edge> _edges; 00143 00144 simple_graph(); 00145 ~simple_graph(); 00146 00147 simple_graph(undi_graph& G); 00148 00149 node new_node(int id=-1); 00150 00151 00152 00153 edge new_edge(node n1, node n2, int id=-1); 00154 00155 void del_node(node& n); 00156 void del_edge(edge& e); 00157 00158 int number_of_nodes() const; 00159 int number_of_edges() const; 00160 00161 void contract(edge&,node); 00162 bool is_empty(); 00163 }; 00164 00165 00166 ostream& operator<<(ostream& oo, const simple_graph& g); 00167 00168 00169 00170 #endif