00001 #ifndef GRAPHGENERATORS_H 00002 #define GRAPHGENERATORS_H 00003 00004 #include <Utilities/mersenneTwister.h> 00005 00006 00007 00008 template<typename GraphType> 00009 class GraphGenerator 00010 { 00011 public: 00012 GraphGenerator() 00013 { 00014 } 00015 00016 virtual void generate( GraphType& G) 00017 { 00018 } 00019 protected: 00020 }; 00021 00022 00023 template<typename GraphType> 00024 class RandomGenerator : public GraphGenerator<GraphType> 00025 { 00026 public: 00027 typedef typename GraphType::SizeType SizeType; 00028 typedef typename GraphType::NodeIterator NodeIterator; 00029 typedef typename GraphType::NodeDescriptor NodeDescriptor; 00030 typedef typename GraphType::EdgeIterator EdgeIterator; 00031 typedef typename GraphType::EdgeDescriptor EdgeDescriptor; 00032 00033 RandomGenerator( const SizeType& numNodes, const SizeType& numEdges):m_numNodes(numNodes),m_numEdges(numEdges) 00034 { 00035 } 00036 00037 void generate( GraphType& G) 00038 { 00039 NodeIterator u,v; 00040 NodeDescriptor uD; 00041 EdgeIterator e; 00042 EdgeDescriptor eD; 00043 00044 std::stringstream nodestream; 00045 nodestream << "Generating " << m_numNodes << " random nodes"; 00046 ProgressBar node_progress( m_numNodes,nodestream.str()); 00047 for( SizeType i = 0; i < m_numNodes; ++i) 00048 { 00049 uD = G.insertNode(); 00050 u = G.getNodeIterator(uD); 00051 u->setId( i); 00052 ++node_progress; 00053 } 00054 00055 std::stringstream edgestream; 00056 edgestream << "Generating " << m_numEdges << " random edges"; 00057 ProgressBar edge_progress( m_numEdges,edgestream.str()); 00058 for( SizeType i = 0; i < m_numEdges; ++i) 00059 { 00060 u = G.chooseNode(); 00061 v = G.chooseNode(); 00062 while( G.edgeExists( u->getDescriptor(),v->getDescriptor()) || u == v) 00063 { 00064 u = G.chooseNode(); 00065 v = G.chooseNode(); 00066 } 00067 eD = G.insertEdge( u->getDescriptor(),v->getDescriptor()); 00068 e = G.getEdgeIterator(eD); 00069 e->setId(i); 00070 ++edge_progress; 00071 } 00072 } 00073 00074 private: 00075 const typename GraphType::SizeType& m_numNodes; 00076 const typename GraphType::SizeType& m_numEdges; 00077 }; 00078 00079 00080 template<typename GraphType> 00081 class RandomWeightedGenerator : public GraphGenerator<GraphType> 00082 { 00083 public: 00084 typedef typename GraphType::SizeType SizeType; 00085 typedef typename GraphType::NodeIterator NodeIterator; 00086 typedef typename GraphType::NodeDescriptor NodeDescriptor; 00087 typedef typename GraphType::EdgeIterator EdgeIterator; 00088 typedef typename GraphType::EdgeDescriptor EdgeDescriptor; 00089 00090 RandomWeightedGenerator( const SizeType& numNodes, const SizeType& numEdges, unsigned int maxWeight):m_numNodes(numNodes),m_numEdges(numEdges),m_maxWeight(maxWeight) 00091 { 00092 } 00093 00094 void generate( GraphType& G) 00095 { 00096 NodeIterator u,v; 00097 NodeDescriptor uD; 00098 EdgeIterator e; 00099 EdgeDescriptor eD; 00100 00101 std::stringstream nodestream; 00102 nodestream << "Generating " << m_numNodes << " random nodes"; 00103 ProgressBar node_progress( m_numNodes,nodestream.str()); 00104 for( SizeType i = 0; i < m_numNodes; ++i) 00105 { 00106 uD = G.insertNode(); 00107 u = G.getNodeIterator(uD); 00108 u->setId( i); 00109 ++node_progress; 00110 } 00111 00112 std::stringstream edgestream; 00113 edgestream << "Generating " << m_numEdges << " random edges"; 00114 ProgressBar edge_progress( m_numEdges,edgestream.str()); 00115 for( SizeType i = 0; i < m_numEdges; ++i) 00116 { 00117 u = G.chooseNode(); 00118 v = G.chooseNode(); 00119 while( G.edgeExists( u->getDescriptor(),v->getDescriptor()) || u == v) 00120 { 00121 u = G.chooseNode(); 00122 v = G.chooseNode(); 00123 } 00124 eD = G.insertEdge( u->getDescriptor(),v->getDescriptor()); 00125 e = G.getEdgeIterator(eD); 00126 e->setId(i); 00127 00128 double random = m_random.getRandomNormalizedDouble(); 00129 e->weight = m_maxWeight * random + 1; 00130 ++edge_progress; 00131 } 00132 } 00133 00134 private: 00135 const typename GraphType::SizeType& m_numNodes; 00136 const typename GraphType::SizeType& m_numEdges; 00137 unsigned int m_maxWeight; 00138 MersenneTwister m_random; 00139 }; 00140 00141 #endif //GRAPHGENERATORS_H