RE: [Boost-Users] Linking Problem with GCC

From: Wayne Hartell (whar_at_[hidden])
Date: 2002-04-17 08:43:45

Hi Jeff,
 
o Platform : Win32 (WinXP/2000)
o GCC -- mingw port.
 
o Command lines for the compiler and linker, with path names removed for
clarity. (Compiling a DLL)
Compiling files :
C:\gcc -c -DBUILDING_DLL=1 -I. "maindll.cpp"  -s -mwindows
-ftemplate-depth-30 -IC:\Include\ -IC:\LIBSTD~1 -LC:\Lib\ -BC:\Bin\
-Ic:\BOOST_~1
Linking files :
C:\dllwrap --export-all --output-def C:\dll.def --implib
"C:\libHminet~1.a" -o c:\Hminet~1.dll "c:\maindll.o"
 
Note that when compiling an exe, the command line uses g++ for both the
compile and link steps. 
 
I've attached the source for the edge connectivity example in Chapter
8.2 of the text book.
 
The only compiler that doesn't bite it on the attached code (that I've
tried) is GCC compiling as an EXE, so I'm sure my problem with compiling
a DLL is environment related.
 
Kind Regards,
Wayne.

        -----Original Message-----
        From: Jeff Garland [mailto:jeff_at_[hidden]]   
        Sent: Tuesday, April 16, 2002 4:30 PM
        To: Boost-Users_at_[hidden]
        Subject: RE: [Boost-Users] Linking Problem with GCC
        
        
        
	> I agree that latest problem is possibly an STL/environment
problem
	> specifically related to linking a DLL. An exe compiles and
links fine.
	> I'm only new to GCC and am using v2.95. I tried updating to
the 3.0.4
	> libraries but that didn't seem to help any.
        
        Which platform/environment are you using GCC under cygwin,
linux, dos?  In any case, the cout and
        endl symbols shoud be in the library.  Also, it would be nice to
know the exact line you are using
        to invoke both the compile and link step.
        
	> Anyway, I only got into this bind because VC7 and VC6 both run
into
	> Internal Compiler Errors when trying to compile (only a select
part) of
	> the BGL. I got a work around from Microsoft for one compiler
bug, made a
	> fix to the BGL code to get past another, then hit yet another
internal
	> compiler error. Where does all this happen? Specifically with
examples
	> from the BGL text book including the edge connectivity example
in
	> section 8.2.
        
        That's not helping because I don't have the BGL book yet.
        
	> Thank you for your kind response.
        
        Sure.
        
        Jeff
        
        
        
Yahoo! Groups Sponsor	
ADVERTISEMENT
Click Here!
<http://rd.yahoo.com/M=194081.1994012.3473453.1261774/D=egroupweb/S=1705
006788:HM/A=1036972/R=0/*http://www.ediets.com/start.cfm?code=3466> 	
 
<http://us.adserver.yahoo.com/l?M=194081.1994012.3473453.1261774/D=egrou
pmail/S=1705006788:HM/A=1036972/rand=613311184> 	

        Info: <http://www.boost.org>
        Wiki: <
http://www.crystalclearsoftware.com/cgi-bin/boost_wiki/wiki.pl>
        Unsubscribe: <mailto:boost-users-unsubscribe_at_[hidden]>
        
        
        Your use of Yahoo! Groups is subject to the Yahoo! Terms of
Service <http://docs.yahoo.com/info/terms/> . 
        

  ----------

#include <algorithm>
#include <utility>
#include <boost/graph/edmunds_karp_max_flow.hpp>
#include <boost/graph/push_relabel_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

namespace boost
{

        template <typename VertexListGraph, typename OutputIterator>
        typename graph_traits<VertexListGraph>::degree_size_type
        edge_connectivity(VertexListGraph& g, OutputIterator disconnecting_set)
        {
                
                // Type definitions
                typedef typename graph_traits<VertexListGraph>::vertex_descriptor vertex_descriptor;
                typedef typename graph_traits<VertexListGraph>::degree_size_type degree_size_type;
                typedef color_traits<default_color_type> Color;
                typedef typename adjacency_list_traits<vecS, vecS, directedS>::edge_descriptor 
                        edge_descriptor;
                typedef adjacency_list<vecS, vecS, directedS, no_property, 
                        property<edge_capacity_t, degree_size_type,
                        property<edge_residual_capacity_t, degree_size_type,
                        property<edge_reverse_t, edge_descriptor> > > > FlowGraph; 

                // Variable declarations
                vertex_descriptor u, v, p, k;
                edge_descriptor e1, e2;
                bool inserted;

                typename graph_traits<VertexListGraph>::vertex_iterator vi, vi_end;
                degree_size_type delta, alpha_star, alpha_S_k;
                std::set<vertex_descriptor> S, neighbor_S;
                std::vector<vertex_descriptor> S_star, nonneighbor_S;
                std::vector<default_color_type> color(num_vertices(g));
                std::vector<edge_descriptor> pred(num_vertices(g));

                // Create a network-flow graph out of the undirected graph
                FlowGraph flow_g(num_vertices(g));
                typename property_map<FlowGraph, edge_capacity_t>::type
                        cap = get(edge_capacity, flow_g);
                typename property_map<FlowGraph, edge_residual_capacity_t>::type
                        res_cap = get(edge_residual_capacity, flow_g);
                typename property_map<FlowGraph, edge_reverse_t>::type
                        rev_edge = get(edge_reverse, flow_g);

                typename graph_traits<VertexListGraph>::edge_iterator ei, ei_end;
                for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
                {
                        u = source(*ei, g), v = target(*ei, g);
                        tie(e1, inserted) = add_edge(u, v, flow_g);
                        cap[e1]=1;
                        tie(e2, inserted) = add_edge(v, u, flow_g);
                        cap[e2]=1;
                        rev_edge[e1] = e2;
                        rev_edge[e2] = e1;
                }

                // Find minimum degree vertex and compute neighbors of S and nonneighbors of S
                tie(p, delta) = min_degree_vertex(g);
                S_star.push_back(p);
                alpha_star = delta;
                S.insert(p);
                neighbor_S.insert(p);
                neighbors(g, S.begin(), S.end(), std::inserter(neighbor_S, neighbor_S.begin()));
                std::set_difference(vertices(g).first, vertices(g).second,
                        neighbor_S.begin(), neighbor_S.end(), std::back_inserter(nonneighbor_S));

                // Main loop
                while (!nonneighbor_S.empty())
                {
                        k = nonneighbor_S.front();
                        alpha_S_k = edmunds_karp_max_flow
                                (flow_g, p, k, capacity_map(cap).residual_capacity_map(res_cap).
                                reverse_edge_map(rev_edge).color_map(&color[0]).predecessor_map(&pred[0]));
                        if (alpha_S_k < alpha_star)
                        {
                                alpha_star = alpha_S_k;
                                S_star.clear();
                                for (tie(vi, vi_end) = vertices(flow_g); vi != vi_end; ++vi)
                                        if (color[*vi] != Color::white())
                                                S_star.push_back(*vi);
                        }
                        S.insert(k);
                        neighbor_S.insert(k);
                        neighbors(g, k, std::inserter(neighbor_S, neighbor_S.begin()));
                        nonneighbor_S.clear();
                        std::set_difference(vertices(g).first, vertices(g).second, neighbor_S.begin(), 
                                neighbor_S.end(), std::back_inserter(nonneighbor_S));
                }

                // Compute forward edges of the cut [S*, S|*]

                std::vector<bool> in_S_star(num_vertices(g), false);
                typename std::vector<vertex_descriptor>::iterator si;
                for (si = S_star.begin(); si != S_star.end(); ++si)
                        in_S_star[*si] = true;
                degree_size_type c = 0;
                for (si = S_star.begin(); si != S_star.end(); ++si)
                {
                        typename graph_traits<VertexListGraph>::out_edge_iterator ei, ei_end;
                        for (tie(ei, ei_end) = out_edges(*si, g); ei != ei_end; ++ei)
                                if (!in_S_star[target(*ei, g)])
                                {
                                        *disconnecting_set = *ei;
                                        ++c;
                                }
                }

        }

        template <typename Graph>
                std::pair<typename graph_traits<Graph>::vertex_descriptor,
                typename graph_traits<Graph>::degree_size_type>
                min_degree_vertex(Graph &g)
        {
                typename graph_traits<Graph>::vertex_descriptor p;
                typedef typename graph_traits<Graph>::degree_size_type size_type;
                size_type delta = std::numeric_limits<size_type>::max();
                typename graph_traits<Graph>::vertex_iterator i, iend;

                for (tie(i, iend) = vertices(g); i != iend; ++i)
                        if (degree(*i, g) < delta)
                        {
                                delta = degree(*i, g);
                                p = *i;
                        }
                return std::make_pair(p, delta);
        }

        template <typename Graph, typename OutputIterator>
                void neighbors(const Graph& g, typename graph_traits<Graph>::vertex_descriptor u, 
                OutputIterator result)
        {
                typename graph_traits<Graph>::adjacency_iterator ai, aend;
                for (tie(ai, aend) = adjacent_vertices(u, g); ai != aend; ++ai)
                        *result++ = *ai;
        }

        template <typename Graph, typename VertexIterator, typename OutputIterator>
                void neighbors(const Graph& g, VertexIterator first, VertexIterator last, 
                OutputIterator result)
        {
                for (; first != last; ++first)
                        neighbors(g, *first, result);
        }
}

int main()
{
        using namespace boost;
        GraphvizGraph g;
        read_graphviz("figs/edge-connectivity.dot", g);

        typedef graph_traits<GraphvizGraph>::edge_descriptor edge_descriptor;
        typedef graph_traits<GraphvizGraph>::degree_size_type degree_size_type;
        std::vector<edge_descriptor> disconnecting_set;
        degree_size_type c = edge_connectivity(g, std::back_inserter(disconnecting_set));

        std::cout << "The edge connectivity is " << c << "." << std::endl;

        property_map<GraphvizGraph, vertex_attribute_t>::type
                attr_map = get(vertex_attribute, g);

        std::cout << "The disconnecting set is {";
        for (std::vector<edge_descriptor>::iterator i = disconnecting_set.begin();
                i != disconnecting_set.end(); ++i)
                std::cout << "(" << attr_map[source(*i, g)]["label"] << "," 
                << attr_map[target(*i, g)]["label"] << ") ";
        std::cout << "}." << std::endl;
        return (0);
}

[Non-text portions of this message have been removed]