From: Gordon Smith (schmoo2k_at_[hidden])
Date: 2005-02-09 08:00:33
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" <jeff.holle_at_[hidden]> wrote in message
news:42094DDB.9090802_at_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" <jeff.holle_at_[hidden]> wrote in message
> > news:cubfff$8mt$1_at_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 <boost/cstdlib.hpp>
> >>>#include <boost/graph/adjacency_list.hpp>
> >>>#include <boost/graph/subgraph.hpp>
> >>>int
> >>>main()
> >>>{
> >>>using namespace boost;
> >>>using std::string;
> >>>typedef adjacency_list<vecS, vecS, directedS,no_property,
> >>>property<edge_index_t, int>,
> >>>property<graph_name_t, string> > graph_t;
> >>>graph_t g;
> >>>get_property(g, graph_name) = "graph";
> >>>std::cout << "name: " << get_property(g, graph_name) << std::endl;
> >>>typedef subgraph<graph_t> 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 <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://listarchives.boost.org/mailman/listinfo.cgi/boost-users