Graph.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 : Graph 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 GraphH 00033 #define GraphH 00034 00035 #include <zeusmath/System/Vertice.h> 00036 #include <zeusmath/System/GraphIterator.h> 00037 #include <zeusbase/System/ZObject.h> 00038 #include <zeusbase/System/Map.hpp> 00039 #include <zeusbase/System/Set.hpp> 00040 #include <zeusbase/System/Pair.hpp> 00041 #include <zeusbase/System/SingleLinkedList.hpp> 00042 00043 BEGIN_NAMESPACE_Zeus 00044 00045 class IMatrix; 00046 00047 /****************************************************************************/ 00050 /****************************************************************************/ 00051 zeusmath_class TGraph : public TZObject 00052 { 00053 public: 00054 typedef TPair<Uint, Uint> TMappedPair; 00055 00056 00057 TGraph(bool bDirected = true); 00058 TGraph(const IMatrix& rMatrix, bool bDirected = true); 00059 00061 //Methods to overwrite for special graphs 00062 virtual Retval addEdge(Uint uiVertice1, Uint uiVertice2, Float fWeight = 1.0); 00063 virtual Retval addVertice(Uint uiID, IZUnknown* pObject = NULL); 00065 00066 void assignMatrix(const IMatrix& rMatrix); 00067 00068 void clearEdges(); 00069 void clearVertices(); 00070 Retval getCompleteGraph(TGraph*& rpGraph) const; 00071 Retval getMinimumCostTree(TGraph*& rpGraph) const; 00072 Retval getMinimumCostTree(Uint uiStartVertice, TGraph*& rpGraph) const; 00073 Retval getComplementGraph(TGraph*& rpGraph) const; 00074 Retval getIsomorphicMatches(const TGraph& rGraphToMatch, TSet<TPair<Uint, Uint> >& rMatches) const; 00075 Retval getAdjazentMatrix(IMatrix& rMatrix) const; 00076 00077 Int getEdgeCount() const; 00078 Int getVerticeCount() const; 00079 00080 const TEdge& getEdge(Int iIndex) const; 00081 Retval getVertice(Int iIndex, TVertice*& rpVertice) const; 00082 Retval getVerticeByID(Uint uiID, TVertice*& rpVertice) const; 00083 Float getWeightSum(Uint uiFromID, Uint uiToID) const; 00084 00085 bool equals(const TGraph& rGraph, bool bIsomorphism = false) const; 00086 bool hasCylce() const; 00087 bool hasEdge(Uint uiVertice1, Uint uiVertice2) const; 00088 bool hasEdge(Uint uiVertice1, Uint uiVertice2, Float fWeight) const; 00089 bool hasVertice(Uint uiID) const; 00090 bool isConnected(Uint uiVertice1, Uint uiVertice2) const; 00091 bool isDirected() const; 00092 bool isEmpty() const; 00093 00094 Retval removeEdge(Uint uiVertice1, Uint uiVertice2); 00095 Retval removeEdge(Uint uiVertice1, Uint uiVertice2, Float fWeight); 00096 00097 //Iterators 00098 inline TGraphIterator* getIterator() { return this->getDepthFirstIterator(); } 00099 inline const TGraphIterator* getConstIterator() const { return this->getConstDepthFirstIterator(); } 00100 TGraphIterator* getDepthFirstIterator(); 00101 const TGraphIterator* getConstDepthFirstIterator() const; 00102 TGraphIterator* getBreathFirstIterator(); 00103 const TGraphIterator* getConstBreathFirstIterator() const; 00104 00105 00106 protected: 00107 virtual ~TGraph(); 00108 00109 //protected methods for internal use only 00110 Retval addEdge(TEdge& rEdge); 00111 Retval addVertice(TVertice& rVertice); 00112 bool hasEdge(TEdge& rEdge, bool bIgnoreWeight) const; 00113 Retval removeEdge(TEdge& rEdge, bool bIgnoreWeight); 00114 00115 void cloneVerticesOfGraph(const TGraph& rGraph); 00116 00117 private: 00119 TMap<Uint, TVertice*> m_mapVertices; 00121 TSingleLinkedList<TVertice*> m_lstVertices; 00123 TSingleLinkedList<TEdge> m_lstEdges; 00125 bool m_bDirected; 00126 00127 void releaseInstances(); 00128 void removeEdgesOfVertice(TVertice& rVertice); 00129 00130 static bool matchSubgraph(const TGraph& rG1, 00131 const TGraph& rG2, 00132 TVertice& rV1, 00133 TVertice& rV2, 00134 TSet<TPair<Uint, Uint> >& rSetMapped, 00135 TSet<Uint>& rSetMarked1, 00136 TSet<Uint>& rSetMarked2); 00137 }; 00138 00139 00140 /****************************************************************************/ 00149 /****************************************************************************/ 00150 inline Retval TGraph::addEdge(Uint uiVertice1, Uint uiVertice2, Float fWeight /*= 1.0*/) 00151 { 00152 TEdge Edge(uiVertice1, uiVertice2, fWeight); 00153 return addEdge(Edge); 00154 } 00155 00156 /****************************************************************************/ 00163 /****************************************************************************/ 00164 inline Retval TGraph::addVertice(Uint uiID, IZUnknown* pObject /* = NULL*/) 00165 { 00166 TAutoPtr<TVertice> ptrVertice = new TVertice(uiID, pObject); 00167 return addVertice(*ptrVertice); 00168 } 00169 00170 /****************************************************************************/ 00173 /****************************************************************************/ 00174 inline Retval TGraph::getMinimumCostTree(TGraph*& rpGraph) const 00175 { 00176 Retval retValue = RET_REQUEST_FAILED; 00177 if (!m_lstVertices.isEmpty()) 00178 { 00179 retValue = getMinimumCostTree(m_lstVertices.getItemConst(0)->getID(), rpGraph); 00180 } 00181 return retValue; 00182 } 00183 00184 00185 /****************************************************************************/ 00188 /****************************************************************************/ 00189 inline Int TGraph::getEdgeCount() const 00190 { 00191 return m_lstEdges.getCount(); 00192 } 00193 00194 /****************************************************************************/ 00197 /****************************************************************************/ 00198 inline Int TGraph::getVerticeCount() const 00199 { 00200 return m_lstVertices.getCount(); 00201 } 00202 00203 /****************************************************************************/ 00206 /****************************************************************************/ 00207 inline const TEdge& TGraph::getEdge(Int iIndex) const 00208 { 00209 return m_lstEdges.getItemConst(iIndex); 00210 } 00211 00212 /****************************************************************************/ 00216 /****************************************************************************/ 00217 inline bool TGraph::hasEdge(Uint uiVertice1, Uint uiVertice2) const 00218 { 00219 TEdge Edge(uiVertice1, uiVertice2, 0); 00220 return hasEdge(Edge, true); 00221 } 00222 00223 /****************************************************************************/ 00227 /****************************************************************************/ 00228 inline bool TGraph::hasEdge(Uint uiVertice1, Uint uiVertice2, Float fWeight) const 00229 { 00230 TEdge Edge(uiVertice1, uiVertice2, fWeight); 00231 return hasEdge(Edge, false); 00232 } 00233 00234 /****************************************************************************/ 00237 /****************************************************************************/ 00238 inline bool TGraph::hasVertice(Uint uiID) const 00239 { 00240 return m_mapVertices.hasItem(uiID); 00241 } 00242 00243 /****************************************************************************/ 00246 /****************************************************************************/ 00247 inline bool TGraph::isDirected() const 00248 { 00249 return m_bDirected; 00250 } 00251 00252 /****************************************************************************/ 00255 /****************************************************************************/ 00256 inline bool TGraph::isEmpty() const 00257 { 00258 return m_lstVertices.isEmpty(); 00259 } 00260 00261 /****************************************************************************/ 00271 /****************************************************************************/ 00272 inline Retval TGraph::removeEdge(Uint uiVertice1, Uint uiVertice2) 00273 { 00274 TEdge Edge(uiVertice1, uiVertice2, 0); 00275 return removeEdge(Edge, true); 00276 } 00277 00278 /****************************************************************************/ 00287 /****************************************************************************/ 00288 inline Retval TGraph::removeEdge(Uint uiVertice1, Uint uiVertice2, Float fWeight) 00289 { 00290 TEdge Edge(uiVertice1, uiVertice2, fWeight); 00291 return removeEdge(Edge, false); 00292 } 00293 00294 /****************************************************************************/ 00297 /****************************************************************************/ 00298 inline const TGraphIterator* TGraph::getConstDepthFirstIterator() const 00299 { 00300 TGraph* pThis = (TGraph*)this; 00301 return pThis->getDepthFirstIterator(); 00302 } 00303 00304 /****************************************************************************/ 00307 /****************************************************************************/ 00308 inline const TGraphIterator* TGraph::getConstBreathFirstIterator() const 00309 { 00310 TGraph* pThis = (TGraph*)this; 00311 return pThis->getBreathFirstIterator(); 00312 } 00313 00314 END_NAMESPACE_Zeus 00315 00316 #endif