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
