phission: examples/cpp/GraphSegmentationDev/src/segment-graph.cpp Source File

00001 /*
00002  * Copyright (C) 2006 Pedro Felzenszwalb
00003  * 
00004  * This program is free software; you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation; either version 2 of the License, or
00007  * (at your option) any later version.
00008  * 
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  * 
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307 USA
00017 */
00018 
00019 /*
00020  * 05/27/2007
00021  * Edited by pthoren@cs.uml.edu:
00022  * This code is from the original segment-graph.h file.
00023  * Formating to my own crazy standards.
00024  */
00025 
00026 
00027 #include <segment-graph.h>
00028 
00029 bool operator<(const edge &a, const edge &b) {
00030     return a.w < b.w;
00031 }
00032 
00033 universe *segment_graph(int     num_vertices, 
00034                         int     num_edges, 
00035                         edge   *edges, 
00036                         float   c) 
00037 { 
00038     // sort edges by weight
00039     std::sort(edges, edges + num_edges);
00040 
00041     // make a disjoint-set forest
00042     universe *u = new universe(num_vertices);
00043 
00044     // init thresholds
00045     float *threshold = new float[num_vertices];
00046     for (int i = 0; i < num_vertices; i++)
00047         threshold[i] = THRESHOLD(1,c);
00048 
00049     // for each edge, in non-decreasing weight order...
00050     for (int i = 0; i < num_edges; i++) {
00051         edge *pedge = &edges[i];
00052 
00053         // components connected by this edge
00054         int a = u->find(pedge->a);
00055         int b = u->find(pedge->b);
00056         if (a != b) {
00057             if ((pedge->w <= threshold[a]) &&
00058                     (pedge->w <= threshold[b])) {
00059                 u->join(a, b);
00060                 a = u->find(a);
00061                 threshold[a] = pedge->w + THRESHOLD(u->size(a), c);
00062             }
00063         }
00064     }
00065 
00066     // free up
00067     delete threshold;
00068     return u;
00069 }