Main Page Modules Namespace List Class Hierarchy Alphabetical List Compound List File List Namespace Members Compound Members File Members Related Pages

# graph_array.h

Go to the documentation of this file.

    00001 // graph_array.h: interface for the graph_array class.
    00002 //
    00003 //////////////////////////////////////////////////////////////////////
    00004 //
    00005 //  Copyright (C) 2002 Tanguy Fautré.
    00006 //
    00007 //  This software is provided 'as-is', without any express or implied
    00008 //  warranty.  In no event will the authors be held liable for any damages
    00009 //  arising from the use of this software.
    00010 //
    00011 //  Permission is granted to anyone to use this software for any purpose,
    00012 //  including commercial applications, and to alter it and redistribute it
    00013 //  freely, subject to the following restrictions:
    00014 //
    00015 //  1. The origin of this software must not be misrepresented; you must not
    00016 //     claim that you wrote the original software. If you use this software
    00017 //     in a product, an acknowledgment in the product documentation would be
    00018 //     appreciated but is not required.
    00019 //  2. Altered source versions must be plainly marked as such, and must not be
    00020 //     misrepresented as being the original software.
    00021 //  3. This notice may not be removed or altered from any source distribution.
    00022 //
    00023 //  Tanguy Fautré
    00024 //  softdev@pandora.be
    00025 //
    00026 //////////////////////////////////////////////////////////////////////
    00027 //
    00028 //                      Semi-dynamic directed graph
    00029 //                      ***************************
    00030 //
    00031 // Current version: 3.00 BETA 3 (04/12/2002)
    00032 //
    00033 // Comment: graph_array is equivalent to an array of nodes linked by
    00034 //          arcs.
    00035 //          This means you can't change the size (the number of nodes)
    00036 //          of the graph once you created it (setsize() will delete
    00037 //          any previous nodes and arcs).
    00038 //          But you can add or remove arcs.
    00039 //
    00040 // History: - 3.00 BETA 3 (04/12/2002) - Added empty()
    00041 //                                     - Changed some parameters from copy to reference
    00042 //                                     - Fixed a bug with erase_arc
    00043 //                                     - Un-inlined external functions
    00044 //                                     - Added "insert_arc" which is equivalent to "insert"
    00045 //          - 3.00 BETA 2 (16/11/2002) - Improved portability
    00046 //          - 3.00 BETA 1 (27/08/2002) - First public release
    00047 //
    00048 //////////////////////////////////////////////////////////////////////
    00049
    00050 #ifndef GRAPH_ARRAY_H
    00051 #define GRAPH_ARRAY_H
    00052
    00053 #include <cassert>
    00054 #include <cstdlib>
    00055
    00056 #include <algorithm>
    00057 #include <deque>
    00058 //#include <fstream>
    00059 //#include <iostream>
    00060 #include <list>
    00061 #include <map>
    00062 #include <string>
    00063 #include <vector>
    00064
    00065
    00066
    00067 // namespace common_structures
    00068 namespace common_structures {
    00069
    00070
    00071
    00072
    00073 // graph_array main class
    00074 template <class nodetype, class arctype>
    00075 class graph_array
    00076 {
    00077 public:
    00078
    00079     class arc;
    00080     class node;
    00081
    00082     // New types
    00083     typedef size_t                                      nodeid;
    00084     typedef typename std::vector<node>::iterator                node_iterator;
    00085     typedef typename std::vector<node>::const_iterator          const_node_iterator;
    00086     typedef typename std::vector<node>::reverse_iterator        node_reverse_iterator;
    00087     typedef typename std::vector<node>::const_reverse_iterator  const_node_reverse_iterator;
    00088
    00089 #ifdef __GNUC__
    00090     // cilcoder: This is weird..  Add the typename keyword and gcc gives an error.
    00091     // remove it and it will give you a warning because it's not there
    00092     typedef graph_array<nodetype, arctype> _mytype;
    00093 #else
    00094     typedef typename graph_array<nodetype, arctype> _mytype;
    00095 #endif
    00096
    00097
    00098     // graph_array::arc class
    00099     class arc
    00100     {
    00101     public:
    00102         arc & mark()                                    { m_Marker = true; return (* this); }
    00103         arc & unmark()                                  { m_Marker = false; return (* this); }
    00104         bool marked() const                             { return m_Marker; }
    00105
    00106         node_iterator initial() const                   { return m_Initial; }
    00107         node_iterator terminal() const                  { return m_Terminal; }
    00108
    00109         arctype & operator * ()                         { return m_Elem; }
    00110         arctype * operator -> ()                        { return &m_Elem; }
    00111         const arctype & operator * () const             { return m_Elem; }
    00112         const arctype * operator -> () const            { return &m_Elem; }
    00113
    00114     protected:
    00115         friend class graph_array<nodetype, arctype>;
    00116
    00117         arc(const node_iterator & Initial, const node_iterator & Terminal)
    00118             : m_Initial(Initial), m_Terminal(Terminal), m_Marker(false) { }
    00119
    00120         arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem)
    00121             : m_Initial(Initial), m_Terminal(Terminal), m_Elem(Elem), m_Marker(false) { }
    00122
    00123         node_iterator   m_Initial;
    00124         node_iterator   m_Terminal;
    00125         arctype         m_Elem;
    00126         bool            m_Marker;
    00127     };
    00128
    00129
    00130     // New types
    00131     typedef typename std::list<arc>::iterator           out_arc_iterator;
    00132     typedef typename std::list<arc>::const_iterator     const_out_arc_iterator;
    00133
    00134
    00135     // graph_array::node class
    00136     class node
    00137     {
    00138     public:
    00139         node & mark()                                   { m_Marker = true; return (* this); }
    00140         node & unmark()                                 { m_Marker = false; return (* this); }
    00141         bool marked() const                             { return m_Marker; }
    00142
    00143         bool out_empty() const                          { return m_OutArcs.empty(); }
    00144         size_t number_of_out_arcs() const               { return m_OutArcs.size(); }
    00145
    00146         out_arc_iterator out_begin()                    { return m_OutArcs.begin(); }
    00147         out_arc_iterator out_end()                      { return m_OutArcs.end(); }
    00148         const_out_arc_iterator out_begin() const        { return m_OutArcs.begin(); }
    00149         const_out_arc_iterator out_end() const          { return m_OutArcs.end(); }
    00150
    00151         nodetype & operator * ()                        { return m_Elem; }
    00152         nodetype * operator -> ()                       { return &m_Elem; }
    00153         const nodetype & operator * () const            { return m_Elem; }
    00154         const nodetype * operator -> () const           { return &m_Elem; }
    00155
    00156         nodetype & operator = (const nodetype & Elem)   { return (m_Elem = Elem); }
    00157
    00158     protected:
    00159         friend class graph_array<nodetype, arctype>;
    00160         friend class std::vector<node>;
    00161
    00162         node() : m_Marker(false) { }
    00163
    00164         std::list<arc>  m_OutArcs;
    00165         nodetype        m_Elem;
    00166         bool            m_Marker;
    00167     };
    00168
    00169
    00170     // Construction/Destruction
    00171     graph_array();
    00172     explicit graph_array(const size_t NbNodes);
    00173
    00174     // Node related member functions
    00175     void clear();
    00176     bool empty() const;
    00177     void setsize(const size_t NbNodes);
    00178     size_t size() const;
    00179
    00180     node & operator [] (const nodeid & i);
    00181     const node & operator [] (const nodeid & i) const;
    00182
    00183     node_iterator begin();
    00184     node_iterator end();
    00185     const_node_iterator begin() const;
    00186     const_node_iterator end() const;
    00187
    00188     node_reverse_iterator rbegin();
    00189     node_reverse_iterator rend();
    00190     const_node_reverse_iterator rbegin() const;
    00191     const_node_reverse_iterator rend() const;
    00192
    00193     // Arc related member functions
    00194     size_t number_of_arcs() const;
    00195
    00196     void erase_arcs();
    00197     void erase_arcs(const node_iterator & Initial);
    00198     out_arc_iterator erase_arc(const out_arc_iterator & Pos);
    00199
    00200     out_arc_iterator insert_arc(const nodeid & Initial, const nodeid & Terminal);
    00201     out_arc_iterator insert_arc(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem);
    00202     out_arc_iterator insert_arc(const node_iterator & Initial, const node_iterator & Terminal);
    00203     out_arc_iterator insert_arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem);
    00204
    00205     // Another interface for insert_arc
    00206     out_arc_iterator insert(const nodeid & Initial, const nodeid & Terminal)                                        { return insert_arc(Initial, Terminal); }
    00207     out_arc_iterator insert(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem)                  { return insert_arc(Initial, Terminal, Elem); }
    00208     out_arc_iterator insert(const node_iterator & Initial, const node_iterator & Terminal)                          { return insert_arc(Initial, Terminal); }
    00209     out_arc_iterator insert(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem)    { return insert_arc(Initial, Terminal, Elem); }
    00210
    00211     // Optimized (overloaded) functions
    00212     void swap(_mytype & Right);
    00213     friend void swap(_mytype & Left, _mytype & Right)   { Left.swap(Right); }
    00214
    00215 protected:
    00216     size_t              m_NbArcs;
    00217     std::vector<node>   m_Nodes;
    00218 };
    00219
    00220
    00221
    00222 // Additional "low level", graph related, functions
    00223 template <class nodetype, class arctype>
    00224 void unmark_nodes(graph_array<nodetype, arctype> & G);
    00225
    00226 template <class nodetype, class arctype>
    00227 void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N);
    00228
    00229 template <class nodetype, class arctype>
    00230 void unmark_arcs(graph_array<nodetype, arctype> & G);
    00231
    00232
    00233
    00234
    00235 //////////////////////////////////////////////////////////////////////////
    00236 // graph_array Inline functions
    00237 //////////////////////////////////////////////////////////////////////////
    00238
    00239 template <class nodetype, class arctype>
    00240 inline graph_array<nodetype, arctype>::graph_array() : m_NbArcs(0) { }
    00241
    00242
    00243 template <class nodetype, class arctype>
    00244 inline graph_array<nodetype, arctype>::graph_array(const size_t NbNodes) : m_NbArcs(0), m_Nodes(NbNodes)
    00245 { }
    00246
    00247
    00248 template <class nodetype, class arctype>
    00249 inline void graph_array<nodetype, arctype>::clear() {
    00250     m_NbArcs = 0;
    00251     m_Nodes.clear();
    00252 }
    00253
    00254
    00255
    00256 template <class nodetype, class arctype>
    00257 inline bool graph_array<nodetype, arctype>::empty() const {
    00258     return m_Nodes.empty();
    00259 }
    00260
    00261
    00262 template <class nodetype, class arctype>
    00263 inline size_t graph_array<nodetype, arctype>::size() const {
    00264     return m_Nodes.size();
    00265 }
    00266
    00267
    00268 template <class nodetype, class arctype>
    00269 inline void graph_array<nodetype, arctype>::setsize(const size_t NbNodes) {
    00270     clear();
    00271     m_Nodes.resize(NbNodes);
    00272 }
    00273
    00274
    00275 template <class nodetype, class arctype>
    00276 inline typename graph_array<nodetype, arctype>::node &
    00277 graph_array<nodetype, arctype>::operator [] (const nodeid & i) {
    00278     // Debug check
    00279     assert(i < size());
    00280
    00281     return m_Nodes[i];
    00282 }
    00283
    00284
    00285 template <class nodetype, class arctype>
    00286 inline const typename graph_array<nodetype, arctype>::node &
    00287 graph_array<nodetype, arctype>::operator [] (const nodeid & i) const {
    00288     // Debug check
    00289     assert(i < size());
    00290
    00291     return m_Nodes[i];
    00292 }
    00293
    00294
    00295 template <class nodetype, class arctype>
    00296 inline typename graph_array<nodetype, arctype>::node_iterator
    00297 graph_array<nodetype, arctype>::begin() {
    00298     return m_Nodes.begin();
    00299 }
    00300
    00301
    00302 template <class nodetype, class arctype>
    00303 inline typename graph_array<nodetype, arctype>::node_iterator
    00304 graph_array<nodetype, arctype>::end() {
    00305     return m_Nodes.end();
    00306 }
    00307
    00308
    00309 template <class nodetype, class arctype>
    00310 inline typename graph_array<nodetype, arctype>::const_node_iterator
    00311 graph_array<nodetype, arctype>::begin() const {
    00312     return m_Nodes.begin();
    00313 }
    00314
    00315
    00316 template <class nodetype, class arctype>
    00317 inline typename graph_array<nodetype, arctype>::const_node_iterator
    00318 graph_array<nodetype, arctype>::end() const {
    00319     return m_Nodes.end();
    00320 }
    00321
    00322
    00323 template <class nodetype, class arctype>
    00324 inline typename graph_array<nodetype, arctype>::node_reverse_iterator
    00325 graph_array<nodetype, arctype>::rbegin() {
    00326     return m_Nodes.rbegin();
    00327 }
    00328
    00329
    00330 template <class nodetype, class arctype>
    00331 inline typename graph_array<nodetype, arctype>::node_reverse_iterator
    00332 graph_array<nodetype, arctype>::rend() {
    00333     return m_Nodes.rend();
    00334 }
    00335
    00336
    00337 template <class nodetype, class arctype>
    00338 inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator
    00339 graph_array<nodetype, arctype>::rbegin() const {
    00340     return m_Nodes.rbegin();
    00341 }
    00342
    00343
    00344 template <class nodetype, class arctype>
    00345 inline typename graph_array<nodetype, arctype>::const_node_reverse_iterator
    00346 graph_array<nodetype, arctype>::rend() const {
    00347     return m_Nodes.rend();
    00348 }
    00349
    00350
    00351 template <class nodetype, class arctype>
    00352 inline size_t graph_array<nodetype, arctype>::number_of_arcs() const {
    00353     return m_NbArcs;
    00354 }
    00355
    00356
    00357 template <class nodetype, class arctype>
    00358 inline typename graph_array<nodetype, arctype>::out_arc_iterator
    00359 graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal) {
    00360     return (insert(begin() + Initial, begin() + Terminal));
    00361 }
    00362
    00363
    00364 template <class nodetype, class arctype>
    00365 inline typename graph_array<nodetype, arctype>::out_arc_iterator
    00366 graph_array<nodetype, arctype>::insert_arc(const nodeid & Initial, const nodeid & Terminal, const arctype & Elem) {
    00367     return (insert(begin() + Initial, begin() + Terminal, Elem));
    00368 }
    00369
    00370
    00371 template <class nodetype, class arctype>
    00372 inline typename graph_array<nodetype, arctype>::out_arc_iterator
    00373 graph_array<nodetype, arctype>::insert_arc(const node_iterator & Initial, const node_iterator & Terminal) {
    00374     ++m_NbArcs;
    00375     Initial->m_OutArcs.push_back(arc(Initial, Terminal));
    00376     return (--(Initial->m_OutArcs.end()));
    00377 }
    00378
    00379
    00380 template <class nodetype, class arctype>
    00381 inline typename graph_array<nodetype, arctype>::out_arc_iterator
    00382 graph_array<nodetype, arctype>::insert_arc(const node_iterator & Initial, const node_iterator & Terminal, const arctype & Elem) {
    00383     ++m_NbArcs;
    00384     Initial->m_OutArcs.push_back(arc(Initial, Terminal, Elem));
    00385     return (--(Initial->m_OutArcs.end()));
    00386 }
    00387
    00388
    00389 template <class nodetype, class arctype>
    00390 inline typename graph_array<nodetype, arctype>::out_arc_iterator
    00391 graph_array<nodetype, arctype>::erase_arc(const out_arc_iterator & Pos) {
    00392     --m_NbArcs;
    00393     return (Pos->initial()->m_OutArcs.erase(Pos));
    00394 }
    00395
    00396
    00397 template <class nodetype, class arctype>
    00398 inline void graph_array<nodetype, arctype>::erase_arcs(const node_iterator & Initial) {
    00399     m_NbArcs -= (Initial->m_OutArcs.size());
    00400     Initial->m_OutArcs.clear();
    00401 }
    00402
    00403
    00404 template <class nodetype, class arctype>
    00405 inline void graph_array<nodetype, arctype>::erase_arcs() {
    00406     m_NbArcs = 0;
    00407     for (nodeid i = 0; i < Size(); ++i)
    00408         m_Nodes[i].m_OutArcs.clear();
    00409 }
    00410
    00411
    00412 template <class nodetype, class arctype>
    00413 inline void graph_array<nodetype, arctype>::swap(_mytype & Right) {
    00414     std::swap(m_NbArcs, Right.m_NbArcs);
    00415     std::swap(m_Nodes, Right.m_Nodes);
    00416 }
    00417
    00418
    00419
    00420 //////////////////////////////////////////////////////////////////////////
    00421 // additional functions
    00422 //////////////////////////////////////////////////////////////////////////
    00423
    00424 template <class nodetype, class arctype>
    00425 void unmark_nodes(graph_array<nodetype, arctype> & G)
    00426 {
    00427     typedef graph_array<nodetype, arctype>::node_iterator node_it;
    00428
    00429     for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
    00430         NodeIt->unmark();
    00431 }
    00432
    00433
    00434 template <class nodetype, class arctype>
    00435 void unmark_arcs_from_node(typename graph_array<nodetype, arctype>::node & N)
    00436 {
    00437     typedef graph_array<nodetype, arctype>::out_arc_iterator arc_it;
    00438
    00439     for (arc_it ArcIt = N.out_begin(); ArcIt != N.out_end(); ++ArcIt)
    00440         ArcIt->unmark();
    00441 }
    00442
    00443
    00444 template <class nodetype, class arctype>
    00445 void unmark_arcs(graph_array<nodetype, arctype> & G)
    00446 {
    00447     typedef graph_array<nodetype, arctype>::node_iterator node_it;
    00448
    00449     for (node_it NodeIt = G.begin(); NodeIt != G.end(); ++NodeIt)
    00450         unmark_arcs_from_node(* NodeIt);
    00451 }
    00452
    00453
    00454
    00455
    00456 }; // namespace common_structures
    00457
    00458 #endif