Boost Users :

schmoo2k_at_[hidden]

----
> /*
>  * This is a directional graph that inherits from the boost::graph
subgraph adjacent list template.
>  * Properties are internal, though public accessors are provided here that
can be used within any subgraph
>  * derived from this class via create_subgraph to access the base graph
properties.
>  * All graph mutators which affect these properties, are implemented as
methods.
>  */
> #include "dataGraph.h"
> #include <assert.h>
> #include <iostream>
> #include <utility>
> #include <algorithm>
> #include <iterator>
> #include <set>
> #include "pseudoClasses.h"
> #include "dfsVisitor.h"
>
> using namespace std;
> using boost::tie;
>
> DataGraph::DataGraph(DataGraphT& dataGraph)
>   : dataGraph_(dataGraph)
> {}
>
> DataGraph::DataGraph(DataGraphT& dataGraph,const DataVertices&
dataVertices)
>   : dataGraph_(dataGraph)
> {
>   for (DataVertices::const_iterator
iter=dataVertices.begin();iter!=dataVertices.end();++iter)
>     boost::add_vertex(*iter,dataGraph_);
> }
>
> DataGraph::VertexData::VertexData(DataGraphT& dataGraph)
>   : dataGraph_(dataGraph)
> {
> }
>
> DataGraph::EdgeData::EdgeData(DataGraphT& dataGraph)
>   : dataGraph_(dataGraph)
> {
> }
>
> Vertex_Datum&
> DataGraph::VertexData::operator[] (const DataVertex& index)
> {
>   return boost::get(boost::get(vertex_Datum,
dataGraph_.root()),dataGraph_.local_to_global(index));
> }
>
> Edge_Datum&
> DataGraph::EdgeData::operator[] (const DataEdge& index)
> {
>   return boost::get(boost::get(edge_Datum,
dataGraph_.root()),dataGraph_.local_to_global(index));
> }
>
> DataEdge
> DataGraph::add_edge(LayoutEdge* pLayoutEdge,DataVertex source,DataVertex
target)
> {
>   typedef pair<DataEdge,bool> Result;
>   Result result = boost::add_edge(source,target,dataGraph_);
>   assert(result.second == true);
>
boost::put(boost::get(edge_Datum,dataGraph_.root()),dataGraph_.local_to_glob
al(result.first),Edge_Datum(pLayoutEdge));
>   return result.first;
> }
>
> DataEdge
> DataGraph::add_edge(PseudoEdge* pPseudoEdge,DataVertex source,DataVertex
target)
> {
>   typedef pair<DataEdge,bool> Result;
>   Result result = boost::add_edge(source,target,dataGraph_);
>   assert(result.second == true);
>
boost::put(boost::get(edge_Datum,dataGraph_.root()),dataGraph_.local_to_glob
al(result.first),Edge_Datum(pPseudoEdge));
>   return result.first;
> }
>
> DataEdge
> DataGraph::add_edge(const Edge_Datum& edgeDatum,DataVertex
source,DataVertex target)
> {
>   typedef pair<DataEdge,bool> Result;
>   Result result = boost::add_edge(source,target,dataGraph_);
>   assert(result.second == true);
>
boost::put(boost::get(edge_Datum,dataGraph_.root()),dataGraph_.local_to_glob
al(result.first),edgeDatum);
>   return result.first;
> }
>
> DataVertex
> DataGraph::add_vertex(LayoutVertex *pLayoutVertex)
> {
>   assert(pLayoutVertex > (LayoutVertex*)100);
>   DataVertex vertex = boost::add_vertex(dataGraph_);
>
boost::put(boost::get(vertex_Datum,dataGraph_.root()),dataGraph_.local_to_gl
obal(vertex),Vertex_Datum(pLayoutVertex));
>   return vertex;
> }
>
> DataVertex
> DataGraph::add_vertex(PseudoVertex *pPseudoVertex)
> {
>   assert(pPseudoVertex > (PseudoVertex*)100);
>   DataVertex vertex = boost::add_vertex(dataGraph_);
>
boost::put(boost::get(vertex_Datum,dataGraph_.root()),dataGraph_.local_to_gl
obal(vertex),Vertex_Datum(pPseudoVertex));
>   return vertex;
> }
>
> void
> DataGraph::remove_edge(DataEdge edge)
> {
>   boost::remove_edge(edge,dataGraph_);
> }
>
> void
> DataGraph::remove_vertex(DataVertex vertex)
> {
>   boost::remove_vertex(vertex,dataGraph_);
> }
> struct ltSubgraph : public std::binary_function<DataEdge,DataEdge,bool>
> {
>   bool operator() (const DataEdge& s1, const DataEdge& s2) const
>   {
>         return s1.m_source < s2.m_source || (!(s2.m_source < s1.m_source)
&& s1.m_target < s2.m_target);
>   }
> };
>
> typedef set<DataEdge,ltSubgraph> SetEdges;
>
> struct insert : public unary_function<SetEdges::value_type,void>
> {
>   insert(const DataGraphT& subGraph,SetEdges& container) :
subGraph_(subGraph),container_(container) {}
>   void operator() (const SetEdges::value_type& x)
>   {
>     container_.insert(subGraph_.local_to_global(x));
>   }
> public:
>   const DataGraphT& subGraph_;
>   SetEdges& container_;
> };
>
> struct InternalEdgeCantidate : public unary_function<DataEdge,bool>
> {
>   enum Edge_Type { in, out};
>   InternalEdgeCantidate(Edge_Type edge_type, DataGraphT& subGraph) :
edge_type_(edge_type),subGraph_(subGraph) {}
>   bool operator()(const DataEdge& x) const
>   {
>     return (edge_type_==in)  ?
!subGraph_.parent().find_vertex(x.m_source).second :
!subGraph_.parent().find_vertex(x.m_target).second;
>   }
> private:
>   Edge_Type edge_type_;
>   DataGraphT&  subGraph_;
> };
>
> /* Return the external Edges (using global descriptors) */
> void
> DataGraph::handleExternalEdges(DataGraph::Edges&
in_external_edges,DataGraph::Edges& out_external_edges)
> {
>   DataVertexIterator vi,vi_end;
>   {
>     SetEdges local_edges,global_edges;
>     for (tie(vi,vi_end)=boost::vertices(dataGraph_);vi!=vi_end;++vi) {
>       boost::graph_traits<DataGraphT>::in_edge_iterator ei, ei_end;
>           tie(ei,ei_end)=boost::in_edges(*vi,dataGraph_);
>       for_each(ei,ei_end,insert(dataGraph_,local_edges));
>
tie(ei,ei_end)=boost::in_edges(dataGraph_.local_to_global(*vi),dataGraph_.ro
ot());
>       for_each(ei,ei_end,insert(dataGraph_.root(),global_edges));
>     }
>
set_difference(global_edges.begin(),global_edges.end(),local_edges.begin(),l
ocal_edges.end(),insert_iterator<DataGraph::Edges>(in_external_edges,in_exte
rnal_edges.end()),ltSubgraph());
>
in_external_edges.erase(remove_if(in_external_edges.begin(),in_external_edge
s.end(),InternalEdgeCantidate(InternalEdgeCantidate::in,dataGraph_)),in_exte
rnal_edges.end());
>   }
>   {
>     SetEdges local_edges,global_edges;
>     for (tie(vi,vi_end)=boost::vertices(dataGraph_);vi!=vi_end;++vi) {
>       boost::graph_traits<DataGraphT>::out_edge_iterator ei, ei_end;
>           tie(ei,ei_end)=boost::out_edges(*vi,dataGraph_);
>       for_each(ei,ei_end,insert(dataGraph_,local_edges));
>
tie(ei,ei_end)=boost::out_edges(dataGraph_.local_to_global(*vi),dataGraph_.r
oot());
>       for_each(ei,ei_end,insert(dataGraph_.root(),global_edges));
>     }
>
set_difference(global_edges.begin(),global_edges.end(),local_edges.begin(),l
ocal_edges.end(),insert_iterator<DataGraph::Edges>(out_external_edges,out_ex
ternal_edges.end()),ltSubgraph());
>
out_external_edges.erase(remove_if(out_external_edges.begin(),out_external_e
dges.end(),InternalEdgeCantidate(InternalEdgeCantidate::out,dataGraph_)),out
_external_edges.end());
>   }
> }
>
> void
> DataGraph::handleParallelEdges(void)
> {
>   typedef multiset<DataEdge,ltSubgraph> Edges;
>   Edges edges;
>   boost::graph_traits<DataGraphT>::edge_iterator ei,ei_end;
>   for (tie(ei,ei_end)=boost::edges(dataGraph_);ei!=ei_end;++ei)
>     edges.insert(*ei);
>   for (Edges::const_iterator iter1 = edges.begin(); iter1 != edges.end();
advance(iter1,edges.count(*iter1)))
>     if (edges.count(*iter1)>1) {
>       Edge_Datum edgeDatum(new ParallelEdge());
>       for (Edges::const_iterator
iter2=edges.lower_bound(*iter1);iter2!=edges.upper_bound(*iter1);++iter2) {
>         Edge_Datum& existing_datum = getEdgeData()[*iter2];
>         existing_datum.setDeleted(true);
>
edgeDatum.setOmega(edgeDatum.getOmega()+existing_datum.getOmega());
>       }
>       add_edge(edgeDatum,iter1->m_source,iter1->m_target);
>     }
> }
>
> class back_edge_recorder : public boost::default_dfs_visitor
> {
> public:
>   back_edge_recorder(DataGraph& dataGraph)
>     : dataGraph_(dataGraph) {}
>   void back_edge(DataEdge e, const DataGraphT &)
>   {
>     dataGraph_.getEdgeData()[e].setReversed(true);
>   }
> private:
>   DataGraph& dataGraph_;
> };
>
> void
> DataGraph::markBackEdges(void)
> {
>   dfsVisitor(dataGraph_,back_edge_recorder(*this));
> }
>
> string
> DataGraph::label(DataVertex v)
> {
>   const LayoutVertex *pInterface;
>   if (!getVertexData()[v].isPseudo()) {
>     pInterface = getVertexData()[v].getLayoutInterface();
>     assert(pInterface  != NULL);
>         return pInterface->getLabel();
>   } else
>     return string();
> }
>
>
----------------------------------------------------------------------------
----
> #ifndef dataGraph_H
> #define dataGraph_H
> #include <set>
> #include <vector>
> #include <boost/graph/property_iter_range.hpp>
> #include "graphtype.h"
>
> class DataGraph
> {
> public:
>   typedef std::vector<DataEdge> Edges;
>   enum DescriptorType {local,global};
>   DataGraph(DataGraphT& dataGraph);
>   DataGraph(DataGraphT& dataGraph, const DataVertices& dataVertices);
>   // Graph Data accessor methods
>   struct VertexData
>   {
>     typedef boost::graph_property_iter_range
<DataGraphT,vertex_Datum_t>::iterator iterator;
>     typedef boost::graph_property_iter_range
<DataGraphT,vertex_Datum_t>::const_iterator const_iterator;
>     typedef Vertex_Datum value_type;
>
>     VertexData(DataGraphT& dataGraph);
>     iterator begin(void) {return
boost::get_property_iter_range(dataGraph_,vertex_Datum).first;}
>     const_iterator begin(void) const {return
boost::get_property_iter_range(const_cast<const
DataGraphT&>(dataGraph_),vertex_Datum).first;}
>     iterator end(void) {return
boost::get_property_iter_range(dataGraph_,vertex_Datum).second;}
>     const_iterator end(void) const {return
boost::get_property_iter_range(const_cast<const
DataGraphT&>(dataGraph_),vertex_Datum).second;}
>     Vertex_Datum& operator[] (const DataVertex& index);
>   private:
>     DataGraphT& dataGraph_;
>   };
>   struct EdgeData
>   {
>     typedef boost::graph_property_iter_range
<DataGraphT,edge_Datum_t>::iterator iterator;
>     typedef boost::graph_property_iter_range
<DataGraphT,edge_Datum_t>::const_iterator const_iterator;
>     typedef Edge_Datum value_type;
>     EdgeData(DataGraphT& subgraph);
>     iterator begin(void) {return
boost::get_property_iter_range(dataGraph_,edge_Datum).first;}
>     const_iterator begin(void) const {return
boost::get_property_iter_range(const_cast<const
DataGraphT&>(dataGraph_),edge_Datum).first;}
>     iterator end(void) {return
boost::get_property_iter_range(dataGraph_,edge_Datum).second;}
>     const_iterator end(void) const {return
boost::get_property_iter_range( const_cast<const
DataGraphT&>(dataGraph_),edge_Datum).second;}
>     Edge_Datum& operator[] (const DataEdge& index);
>   private:
>     DataGraphT& dataGraph_;
>   };
>   VertexData getVertexData(DescriptorType type = local) {return (type ==
local) ? VertexData(dataGraph_) : VertexData(dataGraph_.root());}
>   EdgeData getEdgeData(DescriptorType type = local) {return (type ==
local) ? EdgeData(dataGraph_) : EdgeData(dataGraph_.root());}
>   // access to held subgraph
>   DataGraphT& getGraph(void) {return dataGraph_;}
>
>   // Max/Min Rank Set manipulator methods.
>   typedef std::set<DataVertex> SameRank;
>   const SameRank& getMinRanks(void) const {return minRanks_;}
>   SameRank& getMinRanks(void) {return minRanks_;}
>   const SameRank& getMaxRanks(void) const {return maxRanks_;}
>   SameRank& getMaxRanks(void) {return maxRanks_;}
>
>   // graph mutator methods
>   DataEdge add_edge(LayoutEdge* pLayoutEdge,DataVertex source,DataVertex
target);
>   DataEdge add_edge(PseudoEdge* pPseudoEdge,DataVertex source,DataVertex
target);
>   DataEdge add_edge(const Edge_Datum& edgeDatum,DataVertex
source,DataVertex target);
>   DataVertex add_vertex(LayoutVertex *pLayoutVertex);
>   DataVertex add_vertex(PseudoVertex *pPseudoVertex);
>   void remove_edge(DataEdge edge);
>   void remove_vertex(DataVertex vertex);
>   void handleExternalEdges(DataGraph::Edges&
in_external_edges,DataGraph::Edges& out_external_edges);
>   void handleParallelEdges(void);
>   void markBackEdges(void);
>
> private:
>   std::string label(DataVertex v);
>   DataGraphT& dataGraph_;
>   SameRank  minRanks_;
>   SameRank  maxRanks_;
> };
>
> /*
>  * This should be a template that has overloaded operator() methods.
>  */
> struct FindViaInterface : std::unary_function<DataVertex,bool>
> {
>   FindViaInterface(DataGraph& dataGraph, const void *pPointer) :
dataGraph_(dataGraph),pPointer_(pPointer) {}
>   bool operator() (const DataVertex& x) const
>   {
>     if (dataGraph_.getVertexData(DataGraph::global)[x].isPseudo()) {
>       return
dataGraph_.getVertexData(DataGraph::global)[x].getPseudoInterface() ==
pPointer_;
>     } else
>       return
dataGraph_.getVertexData(DataGraph::global)[x].getLayoutInterface() ==
pPointer_;
> }
> private:
>   DataGraph& dataGraph_;
>   const void *pPointer_;
> };
>
> template< typename T1>
> struct IsPseudo : std::unary_function<typename T1::value_type,bool>
> {
>   bool operator()(typename T1::value_type& x) const
>   {
>     return x.isPseudo();
>   }
> };
>
> template< typename T1>
> struct IsDeleted : std::unary_function<typename T1::value_type,bool>
> {
>   bool operator()(typename T1::value_type& x) const
>   {
>     return x.isDeleted();
>   }
> };
>
> struct IsReversed :
std::unary_function<DataGraph::EdgeData::value_type,bool>
> {
>   bool operator()(DataGraph::EdgeData::value_type& x) const
>   {
>     return x.isReversed();
>   }
> };
>
> template< typename T1, typename T2>
> struct IsType : public std::unary_function<typename T1::value_type,bool>
> {
>   IsType(typename T2::type type) : type_(type) {}
>   bool operator() (typename T1::value_type x) const;
> private:
>   typename T2::type type_;
> };
>
> template<> inline bool
IsType<DataGraph::VertexData,PseudoVertex>::operator()(DataGraph::VertexData
::value_type x) const
> {
>   if (x.isPseudo())
>     return type_ == x.getPseudoInterface()->getType();
>   else
>     return false;
> }
>
> template<> inline bool
IsType<DataGraph::VertexData,LayoutVertex>::operator()(DataGraph::VertexData
::value_type x) const
> {
>   if (!x.isPseudo())
>     return type_ == x.getLayoutInterface()->getType();
>   else
>     return false;
> }
>
> template<> inline bool
IsType<DataGraph::EdgeData,PseudoEdge>::operator()(DataGraph::EdgeData::valu
e_type x) const
> {
>   if (x.isPseudo())
>     return type_ == x.getPseudoInterface()->getType();
>   else
>     return false;
> }
>
> template<> inline bool
IsType<DataGraph::EdgeData,LayoutEdge>::operator()(DataGraph::EdgeData::valu
e_type x) const
> {
>   if (!x.isPseudo())
>     return type_ == x.getLayoutInterface()->getType();
>   else
>     return false;
> }
>
> #endif
>
----------------------------------------------------------------------------
----
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users