00001 #ifndef DYNAMICGRAPH_H
00002 #define DYNAMICGRAPH_H
00003
00004 #include <Structs/Arrays/packedMemoryArray.h>
00005 #include <Utilities/mersenneTwister.h>
00006 #include <Utilities/graphIO.h>
00007 #include <Utilities/graphGenerators.h>
00008 #include <vector>
00009 #include <algorithm>
00010
00011
00012 class DefaultGraphItem
00013 {
00014 public:
00015 DefaultGraphItem()
00016 {
00017 }
00018
00019 void print( std::ofstream& out)
00020 {
00021 return;
00022 }
00023
00024 static unsigned int memUsage()
00025 {
00026 return sizeof( DefaultGraphItem);
00027 }
00028
00029 void setProperty( const std::string& name, const std::string& value)
00030 {
00031
00032 }
00033
00034 void writeProperties( std::ofstream& out, const std::string& propertyDelimiter = "\n", const std::string& valueDelimiter = " ")
00035 {
00036 }
00037
00038 void writeJSON( std::ofstream& out)
00039 {
00040 }
00041 };
00042
00043
00056 template<template <typename vtype,typename etype> class GraphImplementation, typename Vtype = DefaultGraphItem, typename Etype = DefaultGraphItem >
00057 class DynamicGraph
00058 {
00059 public:
00060
00061 typedef typename GraphImplementation<Vtype,Etype>::SizeType SizeType;
00062 typedef typename GraphImplementation<Vtype,Etype>::NodeDescriptor NodeDescriptor;
00063 typedef typename GraphImplementation<Vtype,Etype>::EdgeDescriptor EdgeDescriptor;
00064 typedef typename GraphImplementation<Vtype,Etype>::NodeIterator NodeIterator;
00065 typedef typename GraphImplementation<Vtype,Etype>::EdgeIterator EdgeIterator;
00066 typedef typename GraphImplementation<Vtype,Etype>::InEdgeIterator InEdgeIterator;
00067 typedef Vtype NodeData;
00068 typedef Etype EdgeData;
00069 typedef unsigned int PropertyType;
00070
00071 DynamicGraph()
00072 {
00073 impl = new GraphImplementation<Vtype,Etype>();
00074 }
00075
00076 ~DynamicGraph()
00077 {
00078 delete impl;
00079 }
00080
00081
00089 EdgeIterator beginEdges( const NodeIterator& u) const
00090 {
00091 return impl->beginEdges( u);
00092 }
00093
00101 InEdgeIterator beginInEdges( const NodeIterator& u) const
00102 {
00103 return impl->beginInEdges(u);
00104 }
00105
00111 NodeIterator beginNodes() const
00112 {
00113 return impl->beginNodes();
00114 }
00115
00121 NodeIterator chooseNode() const
00122 {
00123 return impl->chooseNode();
00124 }
00125
00129 void clear()
00130 {
00131 impl->clear();
00132 m_numNodes = 0;
00133 m_numEdges = 0;
00134 }
00135
00142 SizeType degree( NodeIterator& u) const
00143 {
00144 return indeg(u) + outdeg(u);
00145 }
00146
00153 bool edgeExists( const EdgeDescriptor& descriptor)
00154 {
00155 return impl->edgeExists( descriptor);
00156 }
00157
00165 EdgeIterator endEdges( const NodeIterator& u) const
00166 {
00167 return impl->endEdges( u);
00168 }
00169
00177 InEdgeIterator endInEdges( const NodeIterator& u) const
00178 {
00179 return impl->endInEdges(u);
00180 }
00181
00187 NodeIterator endNodes() const
00188 {
00189 return impl->endNodes();
00190 }
00191
00197 void eraseEdge( EdgeDescriptor descriptor)
00198 {
00199 assert( edgeExists(descriptor));
00200 impl->eraseEdge( getEdgeIterator(descriptor));
00201 --m_numEdges;
00202 }
00203
00209 void eraseNode( NodeDescriptor descriptor)
00210 {
00211 assert( hasNode(descriptor));
00212 NodeIterator u = getNodeIterator(descriptor);
00213 EdgeIterator e;
00214 InEdgeIterator k;
00215
00216 while( hasEdges(u))
00217 {
00218 e = beginEdges(u);
00219 impl->eraseEdge(e);
00220 }
00221
00222 while( hasInEdges(u))
00223 {
00224 k = beginInEdges(u);
00225 impl->eraseEdge( k);
00226 }
00227
00228 impl->eraseNode( u);
00229 --m_numNodes;
00230 assert(hasValidInEdges());
00231 }
00232
00238 void generateFrom( GraphGenerator< DynamicGraph>* generator)
00239 {
00240 this->clear();
00241 generator->generate(*this);
00242 }
00243
00251 EdgeDescriptor getEdgeDescriptor( const NodeDescriptor& uD, const NodeDescriptor& vD)
00252 {
00253 assert( hasEdge(uD,vD));
00254 return getEdgeDescriptor( getNodeIterator(uD),getNodeIterator(vD) );
00255 }
00256
00264 EdgeDescriptor getEdgeDescriptor( const NodeIterator& u, const NodeIterator& v)
00265 {
00266 assert( hasEdge(u,v));
00267 return getEdgeDescriptor(getEdgeIterator(u,v));
00268 }
00269
00276 EdgeDescriptor getEdgeDescriptor( const EdgeIterator& e)
00277 {
00278 return impl->getDescriptor(e);
00279 }
00280
00287 EdgeDescriptor getEdgeDescriptor( const InEdgeIterator& k)
00288 {
00289 return impl->getDescriptor(k);
00290 }
00291
00298 EdgeIterator getEdgeIterator( const EdgeDescriptor& descriptor)
00299 {
00300 return impl->getEdgeIterator(descriptor);
00301 }
00302
00310 EdgeIterator getEdgeIterator( const NodeIterator& u, const NodeIterator& v) const
00311 {
00312 EdgeIterator e, end;
00313 NodeIterator neigh;
00314 for( e = beginEdges(u), end = endEdges(u); e != end; ++e)
00315 {
00316 neigh = target(e);
00317 if( neigh == v)
00318 {
00319 break;
00320 }
00321 }
00322 return e;
00323 }
00324
00331 EdgeIterator getEdgeIterator( const InEdgeIterator& k) const
00332 {
00333 return impl->getEdgeIterator(k);
00334 }
00335
00342 InEdgeIterator getInEdgeIterator( const EdgeIterator& e) const
00343 {
00344 return impl->getInEdgeIterator(e);
00345 }
00346
00353 NodeDescriptor getNodeDescriptor( const NodeIterator& u)
00354 {
00355 return impl->getDescriptor(u);
00356 }
00357
00364 NodeIterator getNodeIterator( const NodeDescriptor& descriptor)
00365 {
00366 return impl->getNodeIterator(descriptor);
00367 }
00368
00375 NodeIterator getNodeIterator( const void* descriptor)
00376 {
00377 return impl->getNodeIterator( (NodeDescriptor)descriptor);
00378 }
00379
00385 SizeType getNumEdges() const
00386 {
00387 return m_numEdges;
00388 }
00389
00395 SizeType getNumNodes() const
00396 {
00397 return m_numNodes;
00398 }
00399
00405 SizeType getRelativePosition( const NodeIterator& u) const
00406 {
00407 return impl->getId(u);
00408 }
00409
00417 bool hasEdge( const NodeDescriptor& uD, const NodeDescriptor& vD)
00418 {
00419 assert( hasNode( uD) && hasNode( vD));
00420 return hasEdge( getNodeIterator( uD), getNodeIterator( vD));
00421 }
00422
00430 bool hasEdge( const NodeIterator& u, const NodeIterator& v)
00431 {
00432 EdgeIterator e, end;
00433 NodeIterator neigh;
00434 for( e = beginEdges(u), end = endEdges(u); e != end; ++e)
00435 {
00436 if( target(e) == v) return true;
00437 }
00438 return false;
00439 }
00440
00447 bool hasEdges( const NodeIterator& u) const
00448 {
00449 return impl->hasEdges(u);
00450 }
00451
00458 bool hasInEdges( const NodeIterator& u) const
00459 {
00460 return impl->hasInEdges(u);
00461 }
00462
00469 bool hasNode( const NodeDescriptor& descriptor)
00470 {
00471 return impl->hasNode( descriptor);
00472 }
00473
00479 bool hasValidInEdges()
00480 {
00481 NodeIterator u, end_nodes;
00482 EdgeIterator e, end_edges;
00483 for( u = beginNodes(), end_nodes = endNodes(); u != end_nodes; ++u)
00484 {
00485 for( e = beginEdges(u), end_edges = endEdges(u); e != end_edges; ++e)
00486 {
00487 if( getEdgeDescriptor(e) != getEdgeDescriptor(getInEdgeIterator(e)))
00488 {
00489 return false;
00490 }
00491 }
00492 }
00493 return true;
00494 }
00495
00502 SizeType indeg( NodeIterator& u) const
00503 {
00504 return impl->indeg(u);
00505 }
00506
00515 EdgeDescriptor insertEdge( const NodeDescriptor& uD, const NodeDescriptor& vD)
00516 {
00517
00518 assert( uD != vD);
00519 assert( hasNode(uD));
00520 assert( hasNode(vD));
00521 if( hasEdge( uD, vD)) return getEdgeDescriptor( uD, vD);
00522 ++m_numEdges;
00523 return impl->insertEdge( uD, vD);
00524 }
00525
00531 NodeDescriptor insertNode()
00532 {
00533 ++m_numNodes;
00534 return impl->insertNode();
00535 }
00536
00542 SizeType memUsage() const
00543 {
00544 return impl->memUsage() + 2 * sizeof(SizeType) + 2 * sizeof (std::vector< std::string>);
00545 }
00546
00552 NodeDescriptor nilNodeDescriptor() const
00553 {
00554 return 0;
00555 }
00556
00563 SizeType outdeg( NodeIterator& u) const
00564 {
00565 return impl->outdeg(u);
00566 }
00567
00574 void printInternalDot(const std::string& filename)
00575 {
00576 std::ofstream out( filename.c_str());
00577 impl->printDot( out);
00578 out.close();
00579 }
00580
00586 void read( GraphReader< DynamicGraph>* reader)
00587 {
00588 this->clear();
00589 reader->read(*this);
00590 }
00591
00598 void reserve( const SizeType& numNodes, const SizeType& numEdges)
00599 {
00600 impl->reserve( numNodes, numEdges);
00601 }
00602
00609 NodeIterator source( EdgeIterator& e) const
00610 {
00611 return impl->getAdjacentNodeIterator( getInEdgeIterator(e));
00612 }
00613
00620 NodeIterator source( InEdgeIterator& k) const
00621 {
00622 return impl->getAdjacentNodeIterator( k);
00623 }
00624
00631 NodeIterator target( EdgeIterator& e) const
00632 {
00633 return impl->getAdjacentNodeIterator( e);
00634 }
00635
00642 NodeIterator target( InEdgeIterator& k) const
00643 {
00644 return impl->getAdjacentNodeIterator( getEdgeIterator(k) );
00645 }
00646
00652 void write( GraphWriter< DynamicGraph>* writer)
00653 {
00654 writer->write(*this);
00655 }
00656
00657 private:
00658 GraphImplementation<Vtype,Etype>* impl;
00659 SizeType m_numNodes;
00660 SizeType m_numEdges;
00661 };
00662
00663
00664
00665 template<typename DataType, typename DescriptorType, typename PropertyType = unsigned int>
00666 class GraphElement : public DataType
00667 {
00668 public:
00669 GraphElement():m_descriptor( 0)
00670 {
00671 }
00672
00673 GraphElement( DescriptorType descriptor):m_descriptor( descriptor)
00674 {
00675 }
00676
00677 DescriptorType getDescriptor() const
00678 {
00679 return m_descriptor;
00680 }
00681
00682 bool operator ==( const GraphElement& other) const
00683 {
00684 return ( m_descriptor == other.m_descriptor );
00685 }
00686
00687 bool operator !=( const GraphElement& other) const
00688 {
00689 return (m_descriptor != other.m_descriptor);
00690 }
00691
00692 static unsigned int memUsage()
00693 {
00694 return sizeof( GraphElement);
00695 }
00696
00697 void setDescriptor( const DescriptorType& descriptor)
00698 {
00699 m_descriptor = descriptor;
00700 }
00701
00702 protected:
00703 DescriptorType m_descriptor;
00704 };
00705
00706
00707 #endif // DYNAMICGRAPH_H