42#ifndef VIGRA_PYTHON_GRAPH_HXX
43#define VIGRA_PYTHON_GRAPH_HXX
46#include <boost/python.hpp>
47#include <boost/iterator/transform_iterator.hpp>
50#include <vigra/graphs.hxx>
51#include <vigra/numpy_array.hxx>
52#include <vigra/multi_gridgraph.hxx>
53#include <vigra/graph_generalization.hxx>
54#include <vigra/multi_array.hxx>
55#include <vigra/graphs.hxx>
56#include <vigra/priority_queue.hxx>
57#include <vigra/merge_graph_adaptor.hxx>
66struct GraphMapTypeTraits;
68template<
unsigned int DIM,
class T>
69struct GraphMapTypeTraits<NumpyArray<DIM,T> >{
71 typedef Value & Reference;
72 typedef const Value & ConstReference;
78struct NodeHolder : GRAPH::Node
80 typedef typename GRAPH::Node Node;
81 NodeHolder(
const lemon::Invalid & = lemon::INVALID)
82 : Node(lemon::INVALID),
85 NodeHolder(
const GRAPH & g ,
const Node & item)
90 typename GRAPH::index_type id()
const{
91 return graph_->id(*
this);
94 typename GraphDescriptorToMultiArrayIndex<GRAPH>::IntrinsicNodeMapShape
95 intrinsicNodeCoordinate()
const{
96 return GraphDescriptorToMultiArrayIndex<GRAPH>::intrinsicNodeCoordinate(*graph_,*
this);
105struct EdgeHolder : GRAPH::Edge
108 typedef typename GRAPH::Edge Edge;
109 EdgeHolder(
const lemon::Invalid & = lemon::INVALID)
110 : Edge(lemon::INVALID),
113 EdgeHolder(
const GRAPH & g ,
const Edge & item)
118 typename GRAPH::index_type id()
const{
119 return graph_->id(*
this);
122 NodeHolder<GRAPH> u()
const{
123 return NodeHolder<GRAPH>(*graph_,graph_->u(*
this));
125 NodeHolder<GRAPH> v()
const{
126 return NodeHolder<GRAPH>(*graph_,graph_->v(*
this));
129 typename GraphDescriptorToMultiArrayIndex<GRAPH>::IntrinsicEdgeMapShape
130 intrinsicEdgeCoordinate()
const{
131 return GraphDescriptorToMultiArrayIndex<GRAPH>::intrinsicEdgeCoordinate(*graph_,*
this);
134 const GRAPH * graph_;
140struct ArcHolder: GRAPH::Arc {
141 typedef typename GRAPH::Arc Arc;
142 ArcHolder(
const lemon::Invalid & = lemon::INVALID)
143 : Arc(lemon::INVALID),
146 ArcHolder(
const GRAPH & g ,
const Arc & item)
151 typename GRAPH::index_type id()
const{
152 return graph_->id(*
this);
155 typename GraphDescriptorToMultiArrayIndex<GRAPH>::IntrinsicArcMapShape
156 intrinsicArcCoordinate()
const{
157 return GraphDescriptorToMultiArrayIndex<GRAPH>::intrinsicArcCoordinate(*graph_,*
this);
161 const GRAPH * graph_;
165namespace detail_python_graph{
168struct ArcToTargetNodeHolder{
169 typedef typename GRAPH::Node Node;
170 typedef typename GRAPH::Arc Arc;
171 ArcToTargetNodeHolder(
const GRAPH & graph)
174 NodeHolder<GRAPH> operator()(
const Arc & arc)
const{
175 return NodeHolder<GRAPH>(*graph_,graph_->target(arc));
177 const GRAPH * graph_;
181struct ArcToEdgeHolder{
182 typedef typename GRAPH::Edge Edge;
183 typedef typename GRAPH::Arc Arc;
184 ArcToEdgeHolder(
const GRAPH & graph)
187 EdgeHolder<GRAPH> operator()(
const Arc & arc)
const{
188 const Edge edge(arc);
189 return EdgeHolder<GRAPH>(*graph_,edge);
191 const GRAPH * graph_;
195struct ArcToArcHolder{
196 typedef typename GRAPH::Edge Edge;
197 typedef typename GRAPH::Arc Arc;
198 ArcToArcHolder(
const GRAPH & graph)
201 ArcHolder<GRAPH> operator()(
const Arc & arc)
const{
202 return ArcHolder<GRAPH>(*graph_,arc);
204 const GRAPH * graph_;
209struct NodeToNodeHolder{
210 typedef typename GRAPH::Node Node;
211 NodeToNodeHolder(
const GRAPH & graph)
214 NodeHolder<GRAPH> operator()(
const Node & node)
const{
215 return NodeHolder<GRAPH>(*graph_,node);
217 const GRAPH * graph_;
221struct EdgeToEdgeHolder{
222 typedef typename GRAPH::Edge Edge;
223 EdgeToEdgeHolder(
const GRAPH & graph)
226 EdgeHolder<GRAPH> operator()(
const Edge & edge)
const{
227 return EdgeHolder<GRAPH>(*graph_,edge);
229 const GRAPH * graph_;
237struct NodeIteratorHolder{
238 typedef typename GRAPH::Node Node;
239 typedef typename GRAPH::NodeIt Iter;
240 typedef detail_python_graph::NodeToNodeHolder<GRAPH> Transform;
241 typedef boost::transform_iterator<Transform ,Iter ,NodeHolder<GRAPH>, NodeHolder<GRAPH> > const_iterator;
242 NodeIteratorHolder(
const GRAPH & graph,
const Node & node = Node(lemon::INVALID) )
246 const_iterator begin()
const{
248 Iter iter = GraphIteratorAccessor<GRAPH>::nodesBegin(*graph_);
249 return const_iterator(iter,Transform(*graph_));
251 const_iterator end()
const{
252 Iter iter = GraphIteratorAccessor<GRAPH>::nodesEnd(*graph_);
253 return const_iterator(iter,Transform(*graph_));
255 const GRAPH * graph_;
260struct EdgeIteratorHolder{
261 typedef typename GRAPH::Edge Edge;
262 typedef typename GRAPH::EdgeIt Iter;
263 typedef detail_python_graph::EdgeToEdgeHolder<GRAPH> Transform;
264 typedef boost::transform_iterator<Transform ,Iter ,EdgeHolder<GRAPH>, EdgeHolder<GRAPH> > const_iterator;
265 EdgeIteratorHolder(
const GRAPH & graph,
const Edge & edge = Edge(lemon::INVALID) )
269 const_iterator begin()
const{
271 Iter iter = GraphIteratorAccessor<GRAPH>::edgesBegin(*graph_);
272 return const_iterator(iter,Transform(*graph_));
274 const_iterator end()
const{
275 Iter iter = GraphIteratorAccessor<GRAPH>::edgesEnd(*graph_);
276 return const_iterator(iter,Transform(*graph_));
278 const GRAPH * graph_;
284struct NeighbourNodeIteratorHolder{
285 typedef typename GRAPH::Node Node;
286 typedef typename GRAPH::OutArcIt Iter;
287 typedef detail_python_graph::ArcToTargetNodeHolder<GRAPH> Transform;
288 typedef boost::transform_iterator<Transform ,Iter ,NodeHolder<GRAPH>, NodeHolder<GRAPH> > const_iterator;
289 NeighbourNodeIteratorHolder(
const GRAPH & graph,
const Node & node)
293 const_iterator begin()
const{
294 Iter iter = GraphIteratorAccessor<GRAPH>::outArcBegin(*graph_,node_);
295 return const_iterator(iter,Transform(*graph_));
297 const_iterator end()
const{
298 Iter iter = GraphIteratorAccessor<GRAPH>::outArcEnd(*graph_,node_);
299 return const_iterator(iter,Transform(*graph_));
301 const GRAPH * graph_;
307struct IncEdgeIteratorHolder{
308 typedef typename GRAPH::Node Node;
309 typedef typename GRAPH::Edge Edge;
310 typedef typename GRAPH::OutArcIt Iter;
311 typedef detail_python_graph::ArcToArcHolder<GRAPH> Transform;
312 typedef boost::transform_iterator<Transform ,Iter ,ArcHolder<GRAPH>, ArcHolder<GRAPH> > const_iterator;
313 IncEdgeIteratorHolder(
const GRAPH & graph,
const Node & node)
317 const_iterator begin()
const{
318 Iter iter = GraphIteratorAccessor<GRAPH>::outArcBegin(*graph_,node_);
319 return const_iterator(iter,Transform(*graph_));
321 const_iterator end()
const{
322 Iter iter = GraphIteratorAccessor<GRAPH>::outArcEnd(*graph_,node_);
323 return const_iterator(iter,Transform(*graph_));
325 const GRAPH * graph_;
330template<
class G,
class AV>
331class NumpyScalarEdgeMap{
335 typedef AV ArrayView;
336 typedef typename Graph::Edge Key;
337 typedef typename ArrayView::value_type Value;
338 typedef typename ArrayView::reference Reference;
339 typedef typename ArrayView::const_reference ConstReference;
341 typedef typename Graph::Edge key_type;
342 typedef typename ArrayView::value_type value_type;
343 typedef typename ArrayView::reference reference;
344 typedef typename ArrayView::const_reference const_reference;
351 NumpyScalarEdgeMap(
const Graph & graph,ArrayView array)
356 Reference operator[](
const Key & key){
357 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
359 ConstReference operator[](
const Key & key)
const{
360 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
366 const Graph * graph_;
367 MultiArrayView<IntrinsicGraphShape<Graph>::IntrinsicEdgeMapDimension,Value> array_;
371template<
class G,
class AV>
372class NumpyScalarNodeMap{
376 typedef AV ArrayView;
377 typedef typename Graph::Node Key;
378 typedef typename ArrayView::value_type Value;
379 typedef typename ArrayView::reference Reference;
380 typedef typename ArrayView::const_reference ConstReference;
382 typedef typename Graph::Node key_type;
383 typedef typename ArrayView::value_type value_type;
384 typedef typename ArrayView::reference reference;
385 typedef typename ArrayView::const_reference const_reference;
394 NumpyScalarNodeMap(
const Graph & graph,ArrayView array)
399 Reference operator[](
const Key & key){
400 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
402 ConstReference operator[](
const Key & key)
const{
403 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
409 const Graph * graph_;
410 MultiArrayView<IntrinsicGraphShape<Graph>::IntrinsicNodeMapDimension,Value> array_;
415template<
class G,
class AV>
416class NumpyMultibandNodeMap{
420 typedef AV ArrayView;
421 typedef typename Graph::Node Key;
422 typedef typename Graph::Node key_type;
428 typedef MultiArray<1,typename AV::value_type> Value;
429 typedef MultiArrayView<1,typename AV::value_type> Reference;
430 typedef MultiArrayView<1,typename AV::value_type> ConstReference;
431 typedef MultiArray<1,typename AV::value_type> value_type;
432 typedef MultiArrayView<1,typename AV::value_type> reference;
433 typedef MultiArrayView<1,typename AV::value_type> const_reference;
437 NumpyMultibandNodeMap()
442 NumpyMultibandNodeMap(
const Graph & graph,ArrayView array)
447 Reference operator[](
const Key & key){
448 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
450 ConstReference operator[](
const Key & key)
const{
451 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
457 const Graph * graph_;
463template<
class G,
class AV>
464class NumpyMultibandEdgeMap{
468 typedef AV ArrayView;
469 typedef typename Graph::Edge Key;
470 typedef typename Graph::Edge key_type;
476 typedef MultiArray<1,typename AV::value_type> Value;
477 typedef MultiArrayView<1,typename AV::value_type> Reference;
478 typedef MultiArrayView<1,typename AV::value_type> ConstReference;
479 typedef MultiArray<1,typename AV::value_type> value_type;
480 typedef MultiArrayView<1,typename AV::value_type> reference;
481 typedef MultiArrayView<1,typename AV::value_type> const_reference;
485 NumpyMultibandEdgeMap()
490 NumpyMultibandEdgeMap(
const Graph & graph,ArrayView array)
495 Reference operator[](
const Key & key){
496 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
498 ConstReference operator[](
const Key & key)
const{
499 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
505 const Graph * graph_;
518class TaggedGraphShape{
521 const static unsigned int ND = IntrinsicGraphShape<Graph>::IntrinsicNodeMapDimension;
522 const static unsigned int ED = IntrinsicGraphShape<Graph>::IntrinsicEdgeMapDimension;
523 const static unsigned int AD = IntrinsicGraphShape<Graph>::IntrinsicArcMapDimension;
524 static TaggedShape taggedNodeMapShape(
const Graph & graph){
525 return NumpyArray<ND,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicNodeMapShape(graph),
"n");
527 static TaggedShape taggedEdgeMapShape(
const Graph & graph){
528 return NumpyArray<ED,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicEdgeMapShape(graph),
"e");
530 static TaggedShape taggedArcMapShape(
const Graph & graph){
531 return NumpyArray<AD,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicArcMapShape(graph),
"e");
534 static AxisInfo axistagsNodeMap(
const Graph & ){
535 return AxisInfo(
"n");
537 static AxisInfo axistagsEdgeMap(
const Graph & ){
538 return AxisInfo(
"e");
540 static AxisTags axistagsArcMap(
const Graph & ){
541 return AxisInfo(
"e");
547#define VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(DIM,tn,te,ta) \
548template<class BOOST_DIRECTED_TAG> \
549class TaggedGraphShape<GridGraph<DIM,BOOST_DIRECTED_TAG> >{ \
551 typedef GridGraph<DIM,BOOST_DIRECTED_TAG> Graph; \
552 const static unsigned int ND = IntrinsicGraphShape<Graph>::IntrinsicNodeMapDimension; \
553 const static unsigned int ED = IntrinsicGraphShape<Graph>::IntrinsicEdgeMapDimension; \
554 const static unsigned int AD = IntrinsicGraphShape<Graph>::IntrinsicArcMapDimension; \
555 static TaggedShape taggedNodeMapShape(const Graph & graph){ \
556 return NumpyArray<ND,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicNodeMapShape(graph),tn); \
558 static TaggedShape taggedEdgeMapShape(const Graph & graph){ \
559 return NumpyArray<ED,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicEdgeMapShape(graph),te); \
561 static TaggedShape taggedArcMapShape(const Graph & graph){ \
562 return NumpyArray<AD,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicArcMapShape(graph),ta); \
564 static AxisInfo axistagsNodeMap(const Graph & ){ \
565 return AxisInfo(tn); \
567 static AxisInfo axistagsEdgeMap(const Graph & ){ \
568 return AxisInfo(te); \
570 static AxisTags axistagsArcMap(const Graph & ){ \
571 return AxisInfo(ta); \
575VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(1,
"x",
"xe",
"xe");
576VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(2,
"xy",
"xye",
"xye");
577VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(3,
"xyz",
"xyze",
"xyze");
578VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(4,
"xyzt",
"xyzte",
"xyzte");
580#undef VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO
620template<
class G,
class T>
624 IsMultiband<T>::value,
625 NumpyMultibandNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> > ,
626 NumpyScalarNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T> >
630 typedef typename IfBool<
631 IsMultiband<T>::value,
632 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> ,
633 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T>
634 >::type NumpyArrayType;
637 typedef typename IfBool<
638 IsMultiband<T>::value,
639 NumpyMultibandNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> > ,
640 NumpyScalarNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T> >
643 NumpyNodeMap(
const G & g, NumpyArrayType numpyArray)
644 :BaseType(g,numpyArray){
650template<
class G,
class T>
654 IsMultiband<T>::value,
655 NumpyMultibandEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> > ,
656 NumpyScalarEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T> >
660 typedef typename IfBool<
661 IsMultiband<T>::value,
662 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> ,
663 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T>
664 >::type NumpyArrayType;
667 typedef typename IfBool<
668 IsMultiband<T>::value,
669 NumpyMultibandEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> > ,
670 NumpyScalarEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T> >
673 NumpyEdgeMap(
const G & g, NumpyArrayType numpyArray)
674 :BaseType(g,numpyArray){
681template<
class G,
class T>
682struct PyEdgeMapTraits{
683 typedef NumpyEdgeMap<G,T> Map;
684 typedef typename IfBool<
685 IsMultiband<T>::value,
686 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> ,
687 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T>
694template<
class G,
class T>
695struct PyNodeMapTraits{
696 typedef NumpyNodeMap<G,T> Map;
697 typedef typename IfBool<
698 IsMultiband<T>::value,
699 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> ,
700 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T>
705namespace cluster_operators{
707template<
class MERGE_GRAPH>
710 typedef PythonOperator<MERGE_GRAPH > SelfType;
714 typedef float WeightType;
715 typedef MERGE_GRAPH MergeGraph;
716 typedef typename MergeGraph::Graph Graph;
717 typedef typename Graph::Edge GraphEdge;
718 typedef typename Graph::Node GraphNode;
719 typedef typename MergeGraph::Edge Edge;
720 typedef typename MergeGraph::Node Node;
721 typedef typename MergeGraph::EdgeIt EdgeIt;
722 typedef typename MergeGraph::NodeIt NodeIt;
723 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
724 typedef typename MergeGraph::index_type index_type;
725 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
726 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
729 typedef NodeHolder<MERGE_GRAPH> NodeHolderType;
730 typedef EdgeHolder<MERGE_GRAPH> EdgeHolderType;
733 MergeGraph & mergeGraph,
734 boost::python::object
object,
735 const bool useMergeNodeCallback,
736 const bool useMergeEdgesCallback,
737 const bool useEraseEdgeCallback
739 : mergeGraph_(mergeGraph),
742 if(useMergeNodeCallback){
743 typedef typename MergeGraph::MergeNodeCallBackType Callback;
744 Callback cb(Callback:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
745 mergeGraph_.registerMergeNodeCallBack(cb);
748 if(useMergeEdgesCallback){
749 typedef typename MergeGraph::MergeEdgeCallBackType Callback;
750 Callback cb(Callback:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
751 mergeGraph_.registerMergeEdgeCallBack(cb);
753 if(useEraseEdgeCallback){
754 typedef typename MergeGraph::EraseEdgeCallBackType Callback;
755 Callback cb(Callback:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
756 mergeGraph_.registerEraseEdgeCallBack(cb);
763 retVal = boost::python::extract<bool>(object_.attr(
"done")());
765 catch(std::exception & e){
766 std::cout<<
"reason: "<<e.what()<<
"\n";
767 throw std::runtime_error(
"error while calling cluster_operators PythonOperator::done");
771 void mergeEdges(
const Edge & a,
const Edge & b){
773 const EdgeHolderType aa(mergeGraph_,a);
774 const EdgeHolderType bb(mergeGraph_,b);
775 object_.attr(
"mergeEdges")(aa,bb);
777 catch(std::exception & e){
778 std::cout<<
"reason: "<<e.what()<<
"\n";
779 throw std::runtime_error(
"error while calling cluster_operators PythonOperator::mergeEdges");
782 void mergeNodes(
const Node & a,
const Node & b){\
784 const NodeHolderType aa(mergeGraph_,a);
785 const NodeHolderType bb(mergeGraph_,b);
786 object_.attr(
"mergeNodes")(aa,bb);
788 catch(std::exception & e){
789 std::cout<<
"reason: "<<e.what()<<
"\n";
790 throw std::runtime_error(
"error while calling cluster_operators PythonOperator::mergeNodes");
793 void eraseEdge(
const Edge & e){
795 const EdgeHolderType ee(mergeGraph_,e);
796 object_.attr(
"eraseEdge")(ee);
798 catch(std::exception & e){
799 std::cout<<
"reason: "<<e.what()<<
"\n";
800 throw std::runtime_error(
"error while calling cluster_operators PythonOperator::eraseEdge");
803 Edge contractionEdge(){
806 eh = boost::python::extract<EdgeHolderType>(object_.attr(
"contractionEdge")());
808 catch(std::exception & e){
809 std::cout<<
"reason: "<<e.what()<<
"\n";
810 throw std::runtime_error(
"error while calling cluster_operators PythonOperator::contractionEdge");
814 WeightType contractionWeight()
const{
817 w = boost::python::extract<WeightType>(object_.attr(
"contractionWeight")());
819 catch(std::exception & e){
820 std::cout<<
"reason: "<<e.what()<<
"\n";
821 throw std::runtime_error(
"error while calling cluster_operators PythonOperator::contractionWeight");
826 MergeGraph & mergeGraph(){
830 MergeGraph & mergeGraph_;
831 boost::python::object object_;
view_type::value_type value_type
Definition: numpy_array.hxx:735