GraphIterator.h
Go to the documentation of this file.
00001 /***************************************************************************** 00002 * Copyright (C) 2011 by Benjamin Hadorn (b_hadorn@bluewin.ch) 00003 ***************************************************************************** 00004 * Project : Zeus Math Library 00005 * Module : GraphIterator 00006 * Package : Zeus.ZeusMath.System 00007 * Author : Benjamin Hadorn 00008 * Date : 27.12.2011 00009 * System : Zeus-Framework 00010 ***************************************************************************** 00011 * Licence: * 00012 * This library is free software; you can redistribute it and/or modify * 00013 * it under the terms of the GNU Lesser General Public License as * 00014 * published by the Free Software Foundation; either version * 00015 * 2.1 of the License, or (at your option) any later version. * 00016 * * 00017 * This library is distributed in the hope that it will be useful, * 00018 * but WITHOUT ANY WARRANTY; without even the implied warranty of * 00019 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * 00020 * GNU Lesser General Public License for more details. * 00021 * * 00022 * You should have received a copy of the GNU Lesser General Public * 00023 * License along with this library; if not, write to the Free Software * 00024 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110, USA * 00025 *****************************************************************************/ 00026 00027 /***************************************************************************** 00028 * Changes: 00029 * 27.12.2011 bha: created zeus 2.0 00030 *****************************************************************************/ 00031 00032 #ifndef GraphIteratorH 00033 #define GraphIteratorH 00034 00035 #include <zeusmath/Config/PlatformDefines.hpp> 00036 #include <zeusbase/System/ZObject.h> 00037 #include <zeusbase/System/Queue.hpp> 00038 #include <zeusbase/System/Set.hpp> 00039 #include <zeusbase/System/SingleLinkedList.hpp> 00040 #include <zeusbase/System/Stack.hpp> 00041 00042 BEGIN_NAMESPACE_Zeus 00043 00044 class TGraph; 00045 class TVertice; 00046 00047 /****************************************************************************/ 00050 /****************************************************************************/ 00051 zeusmath_class TGraphIterator : public TZObject 00052 { 00053 public: 00054 TGraphIterator(TGraph& rGraph); 00055 00056 void startWith(Uint uiVertice) const; 00057 virtual void reset() = 0; 00058 virtual Retval getNextVertice(TVertice*& rpVertice) = 0; 00059 00060 inline Retval getNextVerticeConst(TVertice*& rpVertice) const 00061 { 00062 TGraphIterator* pThis = (TGraphIterator*)this; 00063 return pThis->getNextVertice(rpVertice); 00064 } 00065 00066 protected: 00067 virtual ~TGraphIterator(); 00068 00070 TGraph& m_rGraph; 00072 TVertice* m_pStartVertice; 00073 }; 00074 00075 /****************************************************************************/ 00079 /****************************************************************************/ 00080 zeusmath_class TGraphDepthIterator : public TGraphIterator 00081 { 00082 public: 00083 TGraphDepthIterator(TGraph& rGraph); 00084 00085 virtual void reset(); 00086 virtual Retval getNextVertice(TVertice*& rpVertice); 00087 00088 protected: 00089 virtual ~TGraphDepthIterator(); 00090 00091 private: 00092 //Search variables -> only one search at the time is allowed 00094 TSet<Uint> m_setVisited; 00096 TStack<TVertice*> m_stackVertices; 00098 TStack<TSingleLinkedList<Uint> > m_stackNextVertices; 00100 TStack<IListIterator<Uint>*> m_stackNextIterator; 00101 00102 void releaseSearchInstances(); 00103 00104 }; 00105 00106 /****************************************************************************/ 00110 /****************************************************************************/ 00111 zeusmath_class TGraphBreathIterator : public TGraphIterator 00112 { 00113 public: 00114 TGraphBreathIterator(TGraph& rGraph); 00115 00116 virtual void reset(); 00117 virtual Retval getNextVertice(TVertice*& rpVertice); 00118 00119 protected: 00120 virtual ~TGraphBreathIterator(); 00121 00122 private: 00123 //Search variables -> only one search at the time is allowed 00125 TSet<Uint> m_setVisited; 00127 TQueue<TVertice*> m_queueVertices; 00128 00129 void releaseSearchInstances(); 00130 }; 00131 00132 00133 END_NAMESPACE_Zeus 00134 00135 //--------------------------------------------------------------------------- 00136 #endif