1 // $Id: mmdb_math_graph.h $ 2 // ================================================================= 3 // 4 // CCP4 Coordinate Library: support of coordinate-related 5 // functionality in protein crystallography applications. 6 // 7 // Copyright (C) Eugene Krissinel 2000-2013. 8 // 9 // This library is free software: you can redistribute it and/or 10 // modify it under the terms of the GNU Lesser General Public 11 // License version 3, modified in accordance with the provisions 12 // of the license to address the requirements of UK law. 13 // 14 // You should have received a copy of the modified GNU Lesser 15 // General Public License along with this library. If not, copies 16 // may be downloaded from http://www.ccp4.ac.uk/ccp4license.php 17 // 18 // This program is distributed in the hope that it will be useful, 19 // but WITHOUT ANY WARRANTY; without even the implied warranty of 20 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 21 // GNU Lesser General Public License for more details. 22 // 23 // ================================================================= 24 // 25 // 12.09.13 <-- Date of Last Modification. 26 // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 27 // ----------------------------------------------------------------- 28 // 29 // **** Module : mmdb_math_graph <interface> 30 // ~~~~~~~~~ 31 // **** Namespace: mmdb::math:: 32 // ~~~~~~~~~~ 33 // **** Classes : Vertex ( graph vertex ) 34 // ~~~~~~~~~ Edge ( graph edge ) 35 // Graph ( structural graph ) 36 // Match ( match of structural graphs ) 37 // GraphMatch ( CSIA algorithms for graphs matching ) 38 // 39 // (C) E. Krissinel 2000-2013 40 // 41 // When used, please cite: 42 // 43 // Krissinel, E. and Henrick, K. (2004) 44 // Common subgraph isomorphism detection by backtracking search. 45 // Software - Practice and Experience, 34, 591-607. 46 // 47 // ================================================================= 48 // 49 50 #ifndef __MMDB_MATH_Graph__ 51 #define __MMDB_MATH_Graph__ 52 53 #include <time.h> 54 55 #include "mmdb_atom.h" 56 57 namespace mmdb { 58 59 namespace math { 60 61 // ========================= Vertex ========================== 62 63 DefineClass(Vertex); 64 65 enum GRAPH_FLAG { 66 CHIRAL_RIGHT = 0x10000000, 67 CHIRAL_LEFT = 0x20000000, 68 ATOM_LEAVING = 0x40000000, 69 HYDROGEN_BOND = 0x0F000000, 70 SYMREL_MASK = 0x00FF0000, 71 CHIRAL_MASK = 0xCFFFFFFF, 72 TYPE_MASK = 0x00FFFFFF 73 }; 74 75 class Vertex : public io::Stream { 76 77 friend class Graph; 78 friend class GraphMatch; 79 80 public: 81 82 Vertex (); 83 Vertex ( io::RPStream Object ); 84 Vertex ( int vtype, cpstr vname ); 85 Vertex ( int vtype ); 86 Vertex ( cpstr chem_elem ); 87 Vertex ( cpstr chem_elem, cpstr name ); 88 ~Vertex(); 89 90 void SetVertex ( cpstr chem_elem ); 91 void SetVertex ( int vtype, cpstr vname ); 92 void SetVertex ( int vtype ); 93 void SetType ( int vtype ); 94 void SetTypeExt ( int typeExt ); 95 96 void RemoveChirality(); 97 void LeaveChirality ( int eltype ); 98 99 void SetName ( cpstr vname ); 100 void SetProperty ( int vprop ); 101 void SetID ( int vid ); 102 void AddBond (); 103 void CopyNBonds ( PVertex V ); SetUserID(int vid)104 inline void SetUserID ( int vid ) { user_id = vid; } GetProperty()105 inline int GetProperty () { return property; } GetID()106 inline int GetID () { return id; } GetUserID()107 inline int GetUserID () { return user_id; } GetName()108 inline cpstr GetName () { return name; } GetType()109 inline int GetType () { return type; } GetTypeExt()110 inline int GetTypeExt () { return type_ext; } 111 int GetNBonds (); 112 113 void SaveType (); // in userid 114 void RestoreType (); // from userid 115 void CopyType ( PVertex V ); 116 117 virtual void Print ( int PKey ); 118 119 virtual void Copy ( PVertex V ); 120 121 void read ( io::RFile f ); 122 void write ( io::RFile f ); 123 124 void mem_read ( cpstr S, int & l ); 125 void mem_write ( pstr S, int & l ); 126 127 protected: 128 pstr name; // name may be general, "C", "Hg", "Cl" etc. 129 int type; // type of vertex, see comments in 130 // mmdb_math_graph.cpp 131 int type_ext; // vertex type extention 132 int property; // flagwise properties -- user-defined 133 int id; // a graph-defined vertex id 134 int user_id; // a user-defined vertex id 135 136 void InitVertex(); 137 138 }; 139 140 DefineStreamFunctions(Vertex); 141 142 143 // ========================== Edge =========================== 144 145 enum GRAPH_BOND { 146 BOND_SINGLE = 1, 147 BOND_DOUBLE = 2, 148 BOND_AROMATIC = 3, 149 BOND_TRIPLE = 4 150 }; 151 152 DefineClass(Edge); 153 154 class Edge : public io::Stream { 155 156 friend class Graph; 157 friend class CGMatch; 158 159 public: 160 161 Edge (); 162 Edge ( io::RPStream Object ); 163 Edge ( int vx1, int vx2, int btype ); // vx1,vx2 are numbered 164 // as 1,2,3 on and refer 165 // to vertices in the order 166 // as they were added to 167 // the graph; btype>0 168 ~Edge(); 169 170 void SetEdge ( int vx1, int vx2, cpstr btype ); 171 void SetEdge ( int vx1, int vx2, int btype ); // btype>0 172 173 void SetType ( int btype ); 174 void SetProperty ( int eprop ); 175 void SaveType (); // in property 176 void RestoreType (); // from property 177 GetVertex1()178 inline int GetVertex1 () { return v1; } GetVertex2()179 inline int GetVertex2 () { return v2; } GetType()180 inline int GetType () { return type; } GetProperty()181 inline int GetProperty () { return property; } 182 183 virtual void Print ( int PKey ); 184 185 virtual void Copy ( PEdge G ); 186 187 void read ( io::RFile f ); 188 void write ( io::RFile f ); 189 190 void mem_read ( cpstr S, int & l ); 191 void mem_write ( pstr S, int & l ); 192 193 protected: 194 int v1,v2; // >=1 195 int type; 196 int property; 197 198 void InitEdge(); 199 200 }; 201 202 DefineStreamFunctions(Edge); 203 204 205 // ========================== Graph ============================ 206 207 enum GRAPH_RC { 208 MKGRAPH_Ok = 0, 209 MKGRAPH_NoAtoms = -1, 210 MKGRAPH_ChangedAltLoc = 1, 211 MKGRAPH_MaxOccupancy = 2 212 }; 213 214 DefineClass(Graph); 215 216 class Graph : public io::Stream { 217 218 friend class GraphMatch; 219 friend class CSBase0; 220 221 public : 222 223 Graph (); 224 Graph ( PResidue R, cpstr altLoc=NULL ); 225 Graph ( io::RPStream Object ); 226 ~Graph(); 227 228 void Reset (); 229 void SetName ( cpstr gname ); GetName()230 inline pstr GetName() { return name; } 231 232 // AddVertex(..) and AddEdge(..) do not copy the objects, but 233 // take them over. This means that application should forget 234 // about pointers to V and G once they were given to Graph. 235 // Vertices and edges must be allocated newly prior each call 236 // to AddVertex(..) and AddEdge(..). 237 void AddVertex ( PVertex V ); 238 void AddEdge ( PEdge G ); 239 void SetVertices ( PPVertex V, int vlen ); 240 void SetEdges ( PPEdge G, int glen ); 241 242 void RemoveChirality(); 243 void LeaveChirality ( int eltype ); 244 245 // MakeGraph(..) makes a graph corresponding to residue R. 246 // The graphs vertices then correspond to the residue's atoms 247 // (Vertex::userid points to atom R->atom[Vertex::userid]), 248 // edges are calculated as chemical bonds between atoms basing 249 // on the table of cut-off distances. 250 // altCode specifies a particular conformation that should be 251 // used for making the graph. If it is set to "" or NULL ("empty" 252 // altcode) but the residue does not have conformation which 253 // contains *only* ""-altcode atoms, a conformation corresponding 254 // to maximal occupancy will be used. The same will happen if 255 // altcode information in residue is not correct, whatever altCode 256 // is specified. 257 // After making the graph, Build(..) should be called as usual 258 // before graph matching. 259 // Non-negative return means that graph has been made. 260 // MakeGraph(..) may return: 261 // MKGRAPH_Ok everything is Ok 262 // MKGRAPH_NoAtoms residue does not have atoms, graph 263 // is not made 264 // MKGRAPH_ChangedAltLoc a different altcode was used because 265 // the residue has only one altcode and 266 // that is different of 267 // MKGRAPH_MaxOccupancy a maximal-occupancy conformation has 268 // been chosen because of default 269 // ""-altcode supplied or incorrect 270 // altcode information in the residue 271 int MakeGraph ( PResidue R, cpstr altLoc=NULL ); 272 273 int MakeGraph ( PPAtom atom, int nAtoms ); 274 275 void HideType ( int bond_vx_type ); 276 void ExcludeType ( int type ); 277 278 void MakeSymmetryRelief ( bool noCO2 ); 279 void IdentifyRings (); 280 int IdentifyConnectedComponents(); // returns their number >= 1 281 282 int Build ( bool bondOrder ); // returns 0 if Ok 283 284 void MakeVertexIDs (); // simply numbers vertices as 1.. on 285 int GetVertexID ( int vertexNo ); 286 int GetVertexNo ( cpstr vname ); 287 // GetBondedVertexID(..) works after MoveType(..) 288 int GetNBondedVertices ( int vertexNo ); 289 int GetBondedVertexID ( int vertexNo, int bond_vx_type, 290 int bondNo ); 291 292 PVertex GetVertex ( int vertexNo ); // 1<=vertexNo<=nVertices GetNofVertices()293 inline int GetNofVertices() { return nVertices; } 294 295 PEdge GetEdge ( int edgeNo ); // 1<=edgeNo<=nEdges GetNofEdges()296 inline int GetNofEdges() { return nEdges; } 297 298 void GetVertices ( PPVertex & V, int & nV ); 299 void GetEdges ( PPEdge & E, int & nE ); 300 301 virtual void Print(); 302 void Print1(); 303 304 virtual void Copy ( PGraph G ); 305 306 void read ( io::RFile f ); 307 void write ( io::RFile f ); 308 309 void mem_read ( cpstr S, int & l ); 310 void mem_write ( pstr S, int & l ); 311 312 protected : 313 pstr name; 314 int nVertices,nEdges, nAllVertices,nAllEdges; 315 PPVertex vertex; 316 PPEdge edge; 317 imatrix graph; 318 319 void InitGraph (); 320 void FreeMemory(); 321 322 void markConnected ( int vno, int cno ); 323 324 private : 325 int nVAlloc,nEAlloc,nGAlloc; 326 327 }; 328 329 DefineStreamFunctions(Graph); 330 331 332 // ========================= GMatch ========================== 333 334 DefineClass(GMatch); 335 DefineStreamFunctions(GMatch); 336 337 class GMatch : public io::Stream { 338 339 friend class GraphMatch; 340 341 public : 342 343 GMatch (); 344 GMatch ( io::RPStream Object ); 345 GMatch ( ivector FV1, ivector FV2, int nv, int n, int m ); 346 ~GMatch(); 347 348 // FV1[] and FV2[] are copied into internal buffers 349 void SetMatch ( ivector FV1, ivector FV2, int nv, int n, int m ); 350 351 bool isMatch ( ivector FV1, ivector FV2, int nv ); 352 bool isCombination ( ivector FV1, ivector FV2, int nv ); 353 354 // do not allocate or dispose FV1 and FV2 in application! 355 void GetMatch ( ivector & FV1, ivector & FV2, int & nv, 356 realtype & p1, realtype & p2 ); 357 358 void read ( io::RFile f ); 359 void write ( io::RFile f ); 360 361 void mem_read ( cpstr S, int & l ); 362 void mem_write ( pstr S, int & l ); 363 364 protected : 365 int n1,n2,mlength; 366 ivector F1,F2; 367 368 void InitGMatch(); 369 370 private : 371 int nAlloc; 372 373 }; 374 375 376 // ======================= GraphMatch ========================= 377 378 #define _UseRecursion 379 380 enum GRAPH_MATCH_FLAG { 381 GMF_UniqueMatch = 0x00000001, 382 GMF_NoCombinations = 0x00000002 383 }; 384 385 enum VERTEX_EXT_TYPE { 386 EXTTYPE_Ignore = 0, 387 EXTTYPE_Equal = 1, 388 EXTTYPE_AND = 2, 389 EXTTYPE_OR = 3, 390 EXTTYPE_XOR = 4, 391 EXTTYPE_NotEqual = 5, 392 EXTTYPE_NotAND = 6, 393 EXTTYPE_NotOR = 7 394 }; 395 396 DefineClass(GraphMatch); 397 398 class GraphMatch : public io::Stream { 399 400 public : 401 402 GraphMatch (); 403 GraphMatch ( io::RPStream Object ); 404 ~GraphMatch(); 405 406 void SetFlag ( word flag ); 407 void RemoveFlag ( word flag ); 408 void SetMaxNofMatches ( int maxNofMatches, bool stopOnMaxN ); 409 void SetTimeLimit ( int maxTimeToRun=0 ); GetStopSignal()410 inline bool GetStopSignal() { return Stop; } 411 412 void Reset(); 413 414 // MatchGraphs looks for maximal common subgraphs of size 415 // not less than minMatch. The number of found subgraphs 416 // is returned by GetNofMatches(), the subgraph vertices 417 // are returned by GetMatch(..). Control parameters: 418 // vertexType true if vertex type should be taken 419 // into account and False otherwise 420 // vertexExt key to use extended vertex types (defined 421 // as type_ext in Vertex). 422 void MatchGraphs ( PGraph Gh1, PGraph Gh2, int minMatch, 423 bool vertexType=true, 424 VERTEX_EXT_TYPE vertexExt=EXTTYPE_Ignore ); 425 void PrintMatches (); GetNofMatches()426 inline int GetNofMatches () { return nMatches; } GetMaxMatchSize()427 inline int GetMaxMatchSize() { return maxMatch; } 428 429 // do not allocate or dispose FV1 and FV2 in application! 430 // FV1/p1 will always correspond to Gh1, and FV2/p2 - 431 // to Gh2 as specified in MatchGraphs(..) 432 void GetMatch ( int MatchNo, ivector & FV1, ivector & FV2, 433 int & nv, realtype & p1, realtype & p2 ); 434 435 void read ( io::RFile f ); 436 void write ( io::RFile f ); 437 438 void mem_read ( cpstr S, int & l ); 439 void mem_write ( pstr S, int & l ); 440 441 protected : 442 PGraph G1,G2; 443 PPVertex V1; 444 PPVertex V2; 445 imatrix c1,c2; 446 bool swap; 447 #ifndef _UseRecursion 448 ivector jj; 449 #endif 450 int n,m; 451 452 imatrix3 P; 453 imatrix iF1; 454 ivector F1,F2,ix; 455 456 int nMatches,maxNMatches; 457 PPGMatch Match; 458 bool wasFullMatch,Stop,stopOnMaxNMathches; 459 word flags; 460 int maxMatch,timeLimit; 461 462 void InitGraphMatch(); 463 void FreeMemory (); 464 void FreeRecHeap (); 465 void GetMemory (); 466 void GetRecHeap (); 467 int Initialize ( bool vertexType, int vertexExt ); 468 #ifdef _UseRecursion 469 void Backtrack ( int i ); // exact matching 470 #else 471 void Ullman (); 472 #endif 473 void Backtrack1 ( int i, int k0 ); // exact/partial matching 474 void CollectMatch ( int nm ); 475 476 private : 477 int nAlloc,mAlloc,nMAlloc; 478 time_t startTime; 479 480 }; 481 482 DefineStreamFunctions(GraphMatch); 483 484 extern void SetGraphAllocPortion ( int alloc_portion ); 485 486 /* 487 extern void TestGraphMatch(); 488 */ 489 490 } // namespace math 491 492 } // namespace mmdb 493 494 #endif 495