00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #ifndef SH_GRAPH_H
00022 #define SH_GRAPH_H
00023
00024 #include <iostream>
00025 #include <list>
00026 #include <map>
00027 #include <queue>
00028 #include <vector>
00029
00030 #include "EdgeIterator.h"
00031 #include "SampleValueAdjacencyList.h"
00032 #include "common.h"
00033 #include "wrapper_hash_set.h"
00034
00035 class BitString ;
00036 class SampleOccurence ;
00037 class Selector ;
00038 class Vertex ;
00039 class VertexContent ;
00040 struct VertexContentsEqual ;
00041
00051 class Graph {
00052 public:
00058 Graph (CvrStgFile* cvr, const BitString& emb, Selector& sel) ;
00059
00063 ~Graph (void) ;
00064
00068 unsigned long getNumVertices (void) const
00069 { return Vertices.size() ; } ;
00070
00076 Vertex* getVertex (VertexLabel l) const
00077 { return Vertices[l] ; } ;
00078
00079 void unmarkDeletedAllVertices (void) ;
00080
00084 float getAvgVertexDegree (void) const ;
00085
00086 void printVerboseInfo (void) ;
00087
00092 bool check (bool verbose = false) const ;
00097 bool check_Vertices (bool verbose = false) const ;
00102 bool check_SampleValues (bool verbose = false) const ;
00108 bool check_SampleOccurences (bool verbose = false) const ;
00113 bool check_SVALists (bool verbose = false) const ;
00114
00115 #ifdef DEBUG
00116
00121 void print (void) const ;
00122
00123 void print_gml (std::ostream& out) const ;
00124 void printVertex_gml (std::ostream& out, Vertex* v, unsigned int recdepth, std::vector<bool>& nodeprinted, std::vector<bool>& edgesprinted, bool start = true) const ;
00125 void printPrologue_gml (std::ostream& out) const ;
00126 void printEpilogue_gml (std::ostream& out) const ;
00127
00128 void print_Vertices (unsigned short spc = 0) const ;
00129 #endif
00130
00131 private:
00132
00133
00134
00135 friend class WKSConstructionHeuristic ;
00136 friend class EdgeIterator ;
00137 friend class SampleValueAdjacencyList ;
00138 friend class Vertex ;
00139
00141 std::vector<Vertex*> Vertices ;
00142
00144 std::vector<SampleValue*> SampleValues ;
00145
00147 std::vector<SampleValueAdjacencyList*> SVALists ;
00148
00150 std::vector<std::list<SampleOccurence> > SampleOccurences ;
00151
00155 std::vector<UWORD32*> NumSampleOccurences ;
00156
00158 std::vector<std::list<SampleOccurence> > DeletedSampleOccurences ;
00159 std::vector<UWORD32*> NumDeletedSampleOccurences ;
00160
00161 std::list<SampleOccurence>::iterator markDeletedSampleOccurence (std::list<SampleOccurence>::iterator it) ;
00162 std::list<SampleOccurence>::iterator unmarkDeletedSampleOccurence (std::list<SampleOccurence>::iterator it) ;
00163
00164
00165
00166
00167
00168
00169
00176 void constructSamples (const std::vector<SamplePos*> &sposs, std::vector<SampleValue**>& svalues) ;
00177
00184 void constructVertices (std::vector<SamplePos*>& sposs, std::vector<SampleValue**>& svalues, const std::vector<EmbValue>& tvalues) ;
00185
00192 void constructEdges (void) ;
00193
00194 CvrStgFile *File ;
00195 EmbValue EmbValueModulus ;
00196 unsigned short SamplesPerVertex ;
00197
00198 bool check_SampleOccurences_size (bool verbose = false) const ;
00199 bool check_SampleOccurences_correctness (bool verbose = false) const ;
00200 bool check_SampleOccurences_completeness (bool verbose = false) const ;
00201
00202 bool check_SVALists_size (bool verbose = false) const ;
00203 bool check_SVALists_soundness (bool verbose = false) const ;
00204 bool check_SVALists_sorted (bool verbose = false) const ;
00205 bool check_SVALists_uniqueness (bool verbose = false) const ;
00206 bool check_SVALists_completeness (bool verbose = false) const ;
00207 } ;
00208
00209 #endif // ndef SH_GRAPH_H