[Boost-users] Re: BGL + Subgraph + Propertymap issue...

ok - just to clarify - I am not having any issues with vertex or edge properties, I am having an issue with graph properties, (hence the specific example). Gordon. "Jeffrey Holle" wrote in message news:42094DDB.9090802@verizon.net...

Excuse me, I don't use graph properties, though I suspect they behave the same as edge and vertex properties as far as subgraphs go.

What I can provide is the class that I used to wrap subgraphs. The inner VertexData and EdgeData classes provide operator[] and iterator interfaces. Look at the implementation of these methods to see the boost::get usage.

This was developed for boost 1.31.1. I know that things have improved somewhat in this area, but believe the subgraph/property things remain the same.

Gordon Smith wrote:

...

I am not sure I follow - I am specifically talking about "graph_name_t" type properties (not vertex or edge properties) - can show a code snippet of how you get a reference to one for a specific subgraph?

TIA,

Gordon.

"Jeffrey Holle" wrote in message news:cubfff$8mt$1@sea.gmane.org...

...

The answer is no. The way I had to employ internal properties with subgraph is to use the

root.

...

method of the subgraph class to access the properties of the root graph. Note that the local to global vertex/edge index methods must also be used.

The subgraph does have properties, just not the same as the roots.

Gordon Smith wrote:

...

The following example produces the following (unexpected results): name: graph name: subgraph 1 name sg2: subgraph 2 name sg: subgraph 2

Do subgraphs share the same property_map?

Gordon.

// SubGraphPropertyTest.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include <string> #include <iostream> #include #include #include int main() { using namespace boost; using std::string; typedef adjacency_list, property > graph_t; graph_t g; get_property(g, graph_name) = "graph"; std::cout << "name: " << get_property(g, graph_name) << std::endl; typedef subgraph subgraph_t; subgraph_t sg; get_property(sg, graph_name) = "subgraph 1"; std::cout << "name: " << get_property(sg, graph_name) << std::endl; subgraph_t sg2 = sg.create_subgraph(); get_property(sg2, graph_name) = "subgraph 2"; std::cout << "name sg2: " << get_property(sg2, graph_name) << std::endl; std::cout << "name sg: " << get_property(sg, graph_name) << std::endl; return exit_success; }

/* * 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 #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 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 Result; Result result = boost::add_edge(source,target,dataGraph_); assert(result.second == true);

return result.first; }

DataEdge DataGraph::add_edge(const Edge_Datum& edgeDatum,DataVertex

boost::put(boost::get(edge_Datum,dataGraph_.root()),dataGraph_.local_to_glob al(result.first),Edge_Datum(pPseudoEdge)); source,DataVertex target)

{ typedef pair 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 { 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 SetEdges;

struct insert : public unary_functionSetEdges::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 { 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_iteratorDataGraph::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_iteratorDataGraph::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 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 #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 ::iterator iterator; typedef boost::graph_property_iter_range ::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(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(dataGraph_),vertex_Datum).second;} Vertex_Datum& operator[] (const DataVertex& index); private: DataGraphT& dataGraph_; }; struct EdgeData { typedef boost::graph_property_iter_range ::iterator iterator; typedef boost::graph_property_iter_range ::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(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(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

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 { 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() ==

---------------------------------------------------------------------------- ---- source,DataVertex target); pPointer_;

} else return

dataGraph_.getVertexData(DataGraph::global)[x].getLayoutInterface() == pPointer_;

} private: DataGraph& dataGraph_; const void *pPointer_; };

template< typename T1> struct IsPseudo : std::unary_function { bool operator()(typename T1::value_type& x) const { return x.isPseudo(); } };

template< typename T1> struct IsDeleted : std::unary_function { bool operator()(typename T1::value_type& x) const { return x.isDeleted(); } };

struct IsReversed : std::unary_functionDataGraph::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 { IsType(typename T2::type type) : type_(type) {} bool operator() (typename T1::value_type x) const; private: typename T2::type type_; };

template<> inline bool IsTypeDataGraph::VertexData,PseudoVertex::operator()(DataGraph::VertexData ::value_type x) const { if (x.isPseudo()) return type_ == x.getPseudoInterface()->getType(); else return false; }

template<> inline bool IsTypeDataGraph::VertexData,LayoutVertex::operator()(DataGraph::VertexData ::value_type x) const { if (!x.isPseudo()) return type_ == x.getLayoutInterface()->getType(); else return false; }

template<> inline bool IsTypeDataGraph::EdgeData,PseudoEdge::operator()(DataGraph::EdgeData::valu e_type x) const { if (x.isPseudo()) return type_ == x.getPseudoInterface()->getType(); else return false; }

template<> inline bool IsTypeDataGraph::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@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users