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>
66 struct GraphMapTypeTraits;
68 template<
unsigned int DIM,
class T>
69 struct GraphMapTypeTraits<NumpyArray<DIM,T> >{
70 typedef typename NumpyArray<DIM,T>::value_type Value;
71 typedef Value & Reference;
72 typedef const Value & ConstReference;
78 struct NodeHolder : GRAPH::Node
80 typedef typename GRAPH::Node Node;
81 NodeHolder(
const lemon::Invalid & iv = 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);
104 template<
class GRAPH>
105 struct EdgeHolder : GRAPH::Edge
108 typedef typename GRAPH::Edge Edge;
109 EdgeHolder(
const lemon::Invalid & iv = 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_;
139 template<
class GRAPH>
140 struct ArcHolder: GRAPH::Arc {
141 typedef typename GRAPH::Arc Arc;
142 ArcHolder(
const lemon::Invalid & iv = 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_;
165 namespace detail_python_graph{
167 template<
class GRAPH>
168 struct 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_;
180 template<
class GRAPH>
181 struct 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_;
194 template<
class GRAPH>
195 struct NodeToNodeHolder{
196 typedef typename GRAPH::Node Node;
197 NodeToNodeHolder(
const GRAPH & graph)
200 NodeHolder<GRAPH> operator()(
const Node & node)
const{
201 return NodeHolder<GRAPH>(*graph_,node);
203 const GRAPH * graph_;
206 template<
class GRAPH>
207 struct EdgeToEdgeHolder{
208 typedef typename GRAPH::Edge Edge;
209 EdgeToEdgeHolder(
const GRAPH & graph)
212 EdgeHolder<GRAPH> operator()(
const Edge &
edge)
const{
213 return EdgeHolder<GRAPH>(*graph_,
edge);
215 const GRAPH * graph_;
222 template<
class GRAPH>
223 struct NodeIteratorHolder{
224 typedef typename GRAPH::Node Node;
225 typedef typename GRAPH::NodeIt Iter;
226 typedef detail_python_graph::NodeToNodeHolder<GRAPH> Transform;
227 typedef boost::transform_iterator<Transform ,Iter ,NodeHolder<GRAPH>, NodeHolder<GRAPH> > const_iterator;
228 NodeIteratorHolder(
const GRAPH & graph,
const Node & node = Node(lemon::INVALID) )
232 const_iterator begin()
const{
234 Iter iter = GraphIteratorAccessor<GRAPH>::nodesBegin(*graph_);
235 return const_iterator(iter,Transform(*graph_));
237 const_iterator end()
const{
238 Iter iter = GraphIteratorAccessor<GRAPH>::nodesEnd(*graph_);
239 return const_iterator(iter,Transform(*graph_));
241 const GRAPH * graph_;
245 template<
class GRAPH>
246 struct EdgeIteratorHolder{
247 typedef typename GRAPH::Edge Edge;
248 typedef typename GRAPH::EdgeIt Iter;
249 typedef detail_python_graph::EdgeToEdgeHolder<GRAPH> Transform;
250 typedef boost::transform_iterator<Transform ,Iter ,EdgeHolder<GRAPH>, EdgeHolder<GRAPH> > const_iterator;
251 EdgeIteratorHolder(
const GRAPH & graph,
const Edge &
edge = Edge(lemon::INVALID) )
255 const_iterator begin()
const{
257 Iter iter = GraphIteratorAccessor<GRAPH>::edgesBegin(*graph_);
258 return const_iterator(iter,Transform(*graph_));
260 const_iterator end()
const{
261 Iter iter = GraphIteratorAccessor<GRAPH>::edgesEnd(*graph_);
262 return const_iterator(iter,Transform(*graph_));
264 const GRAPH * graph_;
269 template<
class GRAPH>
270 struct NeighbourNodeIteratorHolder{
271 typedef typename GRAPH::Node Node;
272 typedef typename GRAPH::OutArcIt Iter;
273 typedef detail_python_graph::ArcToTargetNodeHolder<GRAPH> Transform;
274 typedef boost::transform_iterator<Transform ,Iter ,NodeHolder<GRAPH>, NodeHolder<GRAPH> > const_iterator;
275 NeighbourNodeIteratorHolder(
const GRAPH & graph,
const Node & node)
279 const_iterator begin()
const{
280 Iter iter = GraphIteratorAccessor<GRAPH>::outArcBegin(*graph_,node_);
281 return const_iterator(iter,Transform(*graph_));
283 const_iterator end()
const{
284 Iter iter = GraphIteratorAccessor<GRAPH>::outArcEnd(*graph_,node_);
285 return const_iterator(iter,Transform(*graph_));
287 const GRAPH * graph_;
292 template<
class GRAPH>
293 struct IncEdgeIteratorHolder{
294 typedef typename GRAPH::Node Node;
295 typedef typename GRAPH::Edge Edge;
296 typedef typename GRAPH::OutArcIt Iter;
297 typedef detail_python_graph::ArcToEdgeHolder<GRAPH> Transform;
298 typedef boost::transform_iterator<Transform ,Iter ,EdgeHolder<GRAPH>, EdgeHolder<GRAPH> > const_iterator;
299 IncEdgeIteratorHolder(
const GRAPH & graph,
const Node & node)
303 const_iterator begin()
const{
304 Iter iter = GraphIteratorAccessor<GRAPH>::outArcBegin(*graph_,node_);
305 return const_iterator(iter,Transform(*graph_));
307 const_iterator end()
const{
308 Iter iter = GraphIteratorAccessor<GRAPH>::outArcEnd(*graph_,node_);
309 return const_iterator(iter,Transform(*graph_));
311 const GRAPH * graph_;
316 template<
class G,
class AV>
317 class NumpyScalarEdgeMap{
321 typedef AV ArrayView;
322 typedef typename Graph::Edge Key;
323 typedef typename ArrayView::value_type Value;
324 typedef typename ArrayView::reference Reference;
325 typedef typename ArrayView::const_reference ConstReference;
327 typedef typename Graph::Edge key_type;
328 typedef typename ArrayView::value_type value_type;
329 typedef typename ArrayView::reference reference;
330 typedef typename ArrayView::const_reference const_reference;
337 NumpyScalarEdgeMap(
const Graph & graph,ArrayView array)
342 Reference operator[](
const Key & key){
343 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
345 ConstReference operator[](
const Key & key)
const{
346 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
352 const Graph * graph_;
353 MultiArrayView<IntrinsicGraphShape<Graph>::IntrinsicEdgeMapDimension,Value> array_;
357 template<
class G,
class AV>
358 class NumpyScalarNodeMap{
362 typedef AV ArrayView;
363 typedef typename Graph::Node Key;
364 typedef typename ArrayView::value_type Value;
365 typedef typename ArrayView::reference Reference;
366 typedef typename ArrayView::const_reference ConstReference;
368 typedef typename Graph::Node key_type;
369 typedef typename ArrayView::value_type value_type;
370 typedef typename ArrayView::reference reference;
371 typedef typename ArrayView::const_reference const_reference;
380 NumpyScalarNodeMap(
const Graph & graph,ArrayView array)
385 Reference operator[](
const Key & key){
386 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
388 ConstReference operator[](
const Key & key)
const{
389 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
395 const Graph * graph_;
396 MultiArrayView<IntrinsicGraphShape<Graph>::IntrinsicNodeMapDimension,Value> array_;
401 template<
class G,
class AV>
402 class NumpyMultibandNodeMap{
406 typedef AV ArrayView;
407 typedef typename Graph::Node Key;
408 typedef typename Graph::Node key_type;
414 typedef MultiArray<1,typename AV::value_type> Value;
415 typedef MultiArrayView<1,typename AV::value_type> Reference;
416 typedef MultiArrayView<1,typename AV::value_type> ConstReference;
417 typedef MultiArray<1,typename AV::value_type> value_type;
418 typedef MultiArrayView<1,typename AV::value_type> reference;
419 typedef MultiArrayView<1,typename AV::value_type> const_reference;
423 NumpyMultibandNodeMap()
428 NumpyMultibandNodeMap(
const Graph & graph,ArrayView array)
433 Reference operator[](
const Key & key){
434 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
436 ConstReference operator[](
const Key & key)
const{
437 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicNodeCoordinate(*graph_,key)];
443 const Graph * graph_;
449 template<
class G,
class AV>
450 class NumpyMultibandEdgeMap{
454 typedef AV ArrayView;
455 typedef typename Graph::Edge Key;
456 typedef typename Graph::Edge key_type;
462 typedef MultiArray<1,typename AV::value_type> Value;
463 typedef MultiArrayView<1,typename AV::value_type> Reference;
464 typedef MultiArrayView<1,typename AV::value_type> ConstReference;
465 typedef MultiArray<1,typename AV::value_type> value_type;
466 typedef MultiArrayView<1,typename AV::value_type> reference;
467 typedef MultiArrayView<1,typename AV::value_type> const_reference;
471 NumpyMultibandEdgeMap()
476 NumpyMultibandEdgeMap(
const Graph & graph,ArrayView array)
481 Reference operator[](
const Key & key){
482 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
484 ConstReference operator[](
const Key & key)
const{
485 return array_[GraphDescriptorToMultiArrayIndex<Graph>::intrinsicEdgeCoordinate(*graph_,key)];
491 const Graph * graph_;
504 class TaggedGraphShape{
507 const static unsigned int ND = IntrinsicGraphShape<Graph>::IntrinsicNodeMapDimension;
508 const static unsigned int ED = IntrinsicGraphShape<Graph>::IntrinsicEdgeMapDimension;
509 const static unsigned int AD = IntrinsicGraphShape<Graph>::IntrinsicArcMapDimension;
510 static TaggedShape taggedNodeMapShape(
const Graph & graph){
511 return NumpyArray<ND,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicNodeMapShape(graph),
"n");
513 static TaggedShape taggedEdgeMapShape(
const Graph & graph){
514 return NumpyArray<ED,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicEdgeMapShape(graph),
"e");
516 static TaggedShape taggedArcMapShape(
const Graph & graph){
517 return NumpyArray<AD,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicArcMapShape(graph),
"e");
520 static AxisInfo axistagsNodeMap(
const Graph & graph){
521 return AxisInfo(
"n");
523 static AxisInfo axistagsEdgeMap(
const Graph & graph){
524 return AxisInfo(
"e");
526 static AxisTags axistagsArcMap(
const Graph & graph){
527 return AxisInfo(
"e");
533 #define VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(DIM,tn,te,ta) \
534 template<class BOOST_DIRECTED_TAG> \
535 class TaggedGraphShape<GridGraph<DIM,BOOST_DIRECTED_TAG> >{ \
537 typedef GridGraph<DIM,BOOST_DIRECTED_TAG> Graph; \
538 const static unsigned int ND = IntrinsicGraphShape<Graph>::IntrinsicNodeMapDimension; \
539 const static unsigned int ED = IntrinsicGraphShape<Graph>::IntrinsicEdgeMapDimension; \
540 const static unsigned int AD = IntrinsicGraphShape<Graph>::IntrinsicArcMapDimension; \
541 static TaggedShape taggedNodeMapShape(const Graph & graph){ \
542 return NumpyArray<ND,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicNodeMapShape(graph),tn); \
544 static TaggedShape taggedEdgeMapShape(const Graph & graph){ \
545 return NumpyArray<ED,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicEdgeMapShape(graph),te); \
547 static TaggedShape taggedArcMapShape(const Graph & graph){ \
548 return NumpyArray<AD,int>::ArrayTraits::taggedShape(IntrinsicGraphShape<Graph>::intrinsicArcMapShape(graph),ta); \
550 static AxisInfo axistagsNodeMap(const Graph & graph){ \
551 return AxisInfo(tn); \
553 static AxisInfo axistagsEdgeMap(const Graph & graph){ \
554 return AxisInfo(te); \
556 static AxisTags axistagsArcMap(const Graph & graph){ \
557 return AxisInfo(ta); \
561 VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(1,
"x",
"xe",
"xe");
562 VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(2,
"xy",
"xye",
"xye");
563 VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(3,
"xyz",
"xyze",
"xyze");
564 VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO(4,
"xyzt",
"xyzte",
"xyzte");
566 #undef VIGRA_MAKE_TAGGED_GRAPH_SHAPE_MACRO
606 template<
class G,
class T>
610 IsMultiband<T>::value,
611 NumpyMultibandNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> > ,
612 NumpyScalarNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T> >
616 typedef typename IfBool<
617 IsMultiband<T>::value,
618 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> ,
619 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T>
620 >::type NumpyArrayType;
623 typedef typename IfBool<
624 IsMultiband<T>::value,
625 NumpyMultibandNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> > ,
626 NumpyScalarNodeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T> >
629 NumpyNodeMap(
const G & g, NumpyArrayType numpyArray)
630 :BaseType(g,numpyArray){
636 template<
class G,
class T>
640 IsMultiband<T>::value,
641 NumpyMultibandEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> > ,
642 NumpyScalarEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T> >
646 typedef typename IfBool<
647 IsMultiband<T>::value,
648 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> ,
649 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T>
650 >::type NumpyArrayType;
653 typedef typename IfBool<
654 IsMultiband<T>::value,
655 NumpyMultibandEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> > ,
656 NumpyScalarEdgeMap< G , NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T> >
659 NumpyEdgeMap(
const G & g, NumpyArrayType numpyArray)
660 :BaseType(g,numpyArray){
667 template<
class G,
class T>
668 struct PyEdgeMapTraits{
669 typedef NumpyEdgeMap<G,T> Map;
670 typedef typename IfBool<
671 IsMultiband<T>::value,
672 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension+1,T> ,
673 NumpyArray<IntrinsicGraphShape<G>::IntrinsicEdgeMapDimension ,T>
680 template<
class G,
class T>
681 struct PyNodeMapTraits{
682 typedef NumpyNodeMap<G,T> Map;
683 typedef typename IfBool<
684 IsMultiband<T>::value,
685 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension+1,T> ,
686 NumpyArray<IntrinsicGraphShape<G>::IntrinsicNodeMapDimension ,T>
691 namespace cluster_operators{
693 template<
class MERGE_GRAPH>
694 class PythonOperator{
696 typedef PythonOperator<MERGE_GRAPH > SelfType;
700 typedef float WeightType;
701 typedef MERGE_GRAPH MergeGraph;
702 typedef typename MergeGraph::Graph Graph;
703 typedef typename Graph::Edge GraphEdge;
704 typedef typename Graph::Node GraphNode;
705 typedef typename MergeGraph::Edge Edge;
706 typedef typename MergeGraph::Node Node;
707 typedef typename MergeGraph::EdgeIt EdgeIt;
708 typedef typename MergeGraph::NodeIt NodeIt;
709 typedef typename MergeGraph::IncEdgeIt IncEdgeIt;
710 typedef typename MergeGraph::index_type index_type;
711 typedef MergeGraphItemHelper<MergeGraph,Edge> EdgeHelper;
712 typedef MergeGraphItemHelper<MergeGraph,Node> NodeHelper;
715 typedef NodeHolder<MERGE_GRAPH> NodeHolderType;
716 typedef EdgeHolder<MERGE_GRAPH> EdgeHolderType;
719 MergeGraph & mergeGraph,
720 boost::python::object
object,
721 const bool useMergeNodeCallback,
722 const bool useMergeEdgesCallback,
723 const bool useEraseEdgeCallback
725 : mergeGraph_(mergeGraph),
728 if(useMergeNodeCallback){
729 typedef typename MergeGraph::MergeNodeCallBackType Callback;
730 Callback cb(Callback:: template from_method<SelfType,&SelfType::mergeNodes>(
this));
731 mergeGraph_.registerMergeNodeCallBack(cb);
734 if(useMergeEdgesCallback){
735 typedef typename MergeGraph::MergeEdgeCallBackType Callback;
736 Callback cb(Callback:: template from_method<SelfType,&SelfType::mergeEdges>(
this));
737 mergeGraph_.registerMergeEdgeCallBack(cb);
739 if(useEraseEdgeCallback){
740 typedef typename MergeGraph::EraseEdgeCallBackType Callback;
741 Callback cb(Callback:: template from_method<SelfType,&SelfType::eraseEdge>(
this));
742 mergeGraph_.registerEraseEdgeCallBack(cb);
747 void mergeEdges(
const Edge & a,
const Edge & b){
748 const EdgeHolderType aa(mergeGraph_,a);
749 const EdgeHolderType bb(mergeGraph_,b);
750 object_.attr(
"mergeEdges")(aa,bb);
752 void mergeNodes(
const Node & a,
const Node & b){
753 const NodeHolderType aa(mergeGraph_,a);
754 const NodeHolderType bb(mergeGraph_,b);
755 object_.attr(
"mergeNodes")(aa,bb);
757 void eraseEdge(
const Edge & e){
758 const EdgeHolderType ee(mergeGraph_,e);
759 object_.attr(
"eraseEdge")(ee);
761 Edge contractionEdge(){
762 EdgeHolderType eh = boost::python::extract<EdgeHolderType>(object_.attr(
"contractionEdge")());
765 WeightType contractionWeight()
const{
766 return boost::python::extract<WeightType>(object_.attr(
"contractionWeight")());
769 MergeGraph & mergeGraph(){
773 MergeGraph & mergeGraph_;
774 boost::python::object object_;
782 #endif // VIGRA_PYTHON_GRAPH_HXX