1 #include "adjacency_list/graph.h"
2 #include <stdlib.h>
3 
4 #ifndef GRAPHBUILDER_H
5 #define GRAPHBUILDER_H
6 
7 namespace vcg {
8 namespace tri {
9 
10 //the class is templated also on the FunctorType, that is used to compute edge weights
11 //so the dual graph can be built assigning other weight values.
12 template<class MeshType, class FunctorType>
13 class GraphBuilder
14 {
15 public:
16     typedef typename MeshType::VertexType VertexType;
17     typedef typename MeshType::VertexPointer VertexPointer;
18     typedef typename MeshType::FaceType FaceType;
19     typedef typename MeshType::FacePointer FacePointer;
20     typedef typename MeshType::EdgePointer EdgePointer;
21     typedef typename MeshType::VertexIterator VertexIterator;
22     typedef typename MeshType::FaceIterator FaceIterator;
23     typedef typename MeshType::CoordType Point3f;
24     typedef typename MeshType::ScalarType ScalarType;
25     typedef typename face::Pos<FaceType>    PosType;
26 
27     /*main function to be called from outside: builds the graph and fires the maxflow/mincut alogrith*/
Compute(MeshType & m,FunctorType & wf,FacePointer startFace,FacePointer endFace)28     static void Compute(MeshType &m, FunctorType &wf, FacePointer startFace, FacePointer endFace)
29     {
30         assert(startFace!=NULL && endFace!=NULL && !startFace->IsD() && !endFace->IsD());
31         Graph *g = GraphBuilder<MeshType, FunctorType>::BuildGraph(m, wf, startFace, endFace);
32         double flowVal = g->maxflow();
33         qDebug("Flow %f",flowVal);
34         GraphBuilder<MeshType, FunctorType>::ColorFaces(m, *g, startFace, endFace);
35         assert(vcg::tri::HasPerFaceAttribute(m,"NodeID"));
36         vcg::tri::Allocator<MeshType>::DeletePerFaceAttribute(m,"NodeID");
37         delete g;
38     }
39 
40     /* Builds the dual graph.
41      * the startFace will be connected to the source
42      * the endFace will be connected to the sink
43      * wf is used to compute edge weights
44     */
BuildGraph(MeshType & m,FunctorType & wf,FacePointer startFace,FacePointer endFace)45     static Graph * BuildGraph(MeshType &m, FunctorType &wf, FacePointer startFace, FacePointer endFace)
46     {
47         vcg::tri::UpdateFlags<MeshType>::FaceClearV(m);
48         tri::Allocator<MeshType>::CompactEveryVector(m);
49         Graph *g = new Graph();
50         std::vector<FacePointer> faceVec;
51 
52         //use a per-face attribute to keep the face-node mapping
53         //and initialize to NULL
54         typename  MeshType::template PerFaceAttributeHandle <Graph::node_id>  nfH
55                 = tri::Allocator<MeshType>::template AddPerFaceAttribute<Graph::node_id>(m, std::string("NodeID"));
56         for(FaceIterator fit = m.face.begin(); fit!=m.face.end(); fit++)
57             nfH[fit] = NULL;
58         /*
59         * Surf the mesh face by face and build the graph
60         * using FF adiacency and marking a face when visiting it
61         * Start adding nodes to the graph:
62         * link upper face to the source
63         * link lower face to the sink
64         */
65         nfH[startFace] = g->add_node();
66         g->set_tweights(nfH[startFace], std::numeric_limits<ScalarType>::max(), 0);
67         //link lower face to the sink
68         nfH[endFace] = g->add_node();
69         g->set_tweights(nfH[endFace], 0, std::numeric_limits<ScalarType>::max());
70         faceVec.push_back(endFace);
71         //push startFace in the vector: begin visiting the mesh from there
72         faceVec.push_back(startFace);
73         startFace->SetV();
74 
75         //add a node for each face
76         for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
77         {
78             if(nfH[fi] == NULL)
79                 nfH[fi] = g->add_node();
80         }
81 
82         //add edges
83         for(FaceIterator fi=m.face.begin();fi!=m.face.end();++fi)
84         {
85             for (int i=0; i<3; i++)
86             {
87                 if(!face::IsBorder(*fi,i))
88                 {
89                     PosType pf(&*fi, i);
90                     //using the functor operator () to compute edge capability
91                     double cap = wf(pf);
92                     assert(cap>=0);
93                     //add edges (in the dual graph) between adjacent faces
94                     //an edge is added in both directions with "cap" and "rev_cap"=0 flow capacities
95                     g->add_edge(nfH[fi], nfH[fi->FFp(i)], cap, 0);
96                 }
97             }
98         }
99         return g;
100     }
101 
102     /*
103      Red-coloring Source faces and
104      Green-coloring Sink faces
105     */
ColorFaces(MeshType & m,Graph & g,FacePointer startFace,FacePointer endFace)106     static void ColorFaces(MeshType &m, Graph &g, FacePointer startFace, FacePointer endFace){
107 
108         assert(vcg::tri::HasPerFaceAttribute(m,"NodeID"));
109 
110         typename MeshType:: template PerFaceAttributeHandle<Graph::node_id> nfH
111                 = vcg::tri::Allocator<MeshType>::template FindPerFaceAttribute<Graph::node_id>(m,"NodeID");
112 
113         for(FaceIterator fit=m.face.begin(); fit!=m.face.end(); fit++)
114         {
115             assert(nfH[fit]!=NULL);
116             if(!fit->IsD()){
117                 if(g.what_segment(nfH[fit]) == Graph::SOURCE){
118                     fit->C()=Color4b::Red;
119                 }
120                 else if(g.what_segment(nfH[fit]) == Graph::SINK)
121                     fit->C()=Color4b::Green;
122             }
123         }
124     }
125 };
126 
127 
128 } //end namespace
129 } //end namespace
130 
131 
132 #endif // GRAPHBUILDER_H
133