Re: [Boost-users] [BGL] add_edge also adds a vertex

Subject: Re: [Boost-users] [BGL] add_edge also adds a vertex
From: Olivier Tournaire (olitour_at_[hidden])
Date: 2010-02-07 18:21:56

Thank you for your replies.

2010/2/7 Andrew Sutton <andrew.n.sutton_at_[hidden]>

>
>
>> >     std::pair< graph_traits<Graph>::edge_descriptor, bool > p = add_edge
>> > (*vertices(g).first, *vertices(g).second, g);
>>
>> The function vertices returns an iterator range. In my understanding an
>> iterator range is a pair of iterators [first, second) so that second
>> can be reached from first with increment operations, _but_ is not part
>> of the iterator range itself. It could be an iterator like one returned
>> by the end-function of a stl-vector. It shall not be dereferenced!
>>
>>
> I'll also add that adjacency_list with vecS as a vertex set will add
> vertices in add_edge if an invalid vertex descriptor is given -- of which
> vertices(g).second is an invalid itetator. It's equivalent to
> end(vertices(g)) if you're using Boost.Range.
>

I understand. Obviously, dereferencing a past the end iterator is a bad
idea.
I am now facing another problem using kolmogorov_max_flow algorithm.

Here is the code:

#include <iostream>
#include <vector>
using namespace std;

#include <boost/graph/kolmogorov_max_flow.hpp>
#include <boost/graph/adjacency_list.hpp>
using namespace boost;

typedef adjacency_list_traits < vecS, vecS, directedS > Traits;
typedef adjacency_list < vecS, vecS, directedS,
property < vertex_index_t, long,
property < vertex_color_t, boost::default_color_type,
property < vertex_distance_t, long,
property < vertex_potential_t, long, // stores the unary energy associated
to each vertex
property < vertex_predecessor_t, Traits::edge_descriptor > > > > >,
property < edge_capacity_t, long, // stores the binary energy associated to
each edge
property < edge_residual_capacity_t, long,
property < edge_reverse_t, Traits::edge_descriptor > > > > Graph;

int main(int argc, char** argv)
{
    Graph g;

    property_map<Graph, edge_capacity_t>::type capacity = get(edge_capacity,
g);
    property_map<Graph, edge_reverse_t>::type rev = get(edge_reverse, g);

    graph_traits<Graph>::vertex_iterator v_first, v_second, v_third;
    v_first = vertices(g).first;
    v_second = v_first;
    ++v_second;
    v_third = v_second;
    ++v_third;

    std::pair< graph_traits<Graph>::edge_descriptor, bool > p =
add_edge(*v_first, *v_second, g);
    capacity[p.first] = 10;
    std::pair< graph_traits<Graph>::edge_descriptor, bool > p_reverse =
add_edge(*v_second, *v_first, g);
    rev[p.first] = p_reverse.first;
    capacity[p_reverse.first] = -10;

    std::pair< graph_traits<Graph>::edge_descriptor, bool > p2 =
add_edge(*v_second, *v_third, g);
    capacity[p2.first] = 11;
    std::pair< graph_traits<Graph>::edge_descriptor, bool > p2_reverse =
add_edge(*v_third, *v_second, g);
    rev[p2.first] = p2_reverse.first;
    capacity[p2_reverse.first] = -11;

    std::cout << "num_vertices = " << num_vertices(g) << std::endl;
    std::cout << "num_edges = " << num_edges(g) << std::endl;

    long flow = kolmogorov_max_flow(g , *v_first, *v_third);
    std::cout << "flow = " << flow << std::endl;
    return 0;
}

The code below crashes (segfault) in the max_flow() function. Could you tell
me what am I doing wrong ?
It seems to work when I set a capacity capacity[p2.first] with a value
smaller than 10 (capacity[p.first]). Am I missing something? Do I correctly
use the reverse property_map?

Hope you could help.
Regards,

Olivier

>
> Andrew Sutton
> andrew.n.sutton_at_[hidden]
>
> _______________________________________________
> Boost-users mailing list
> Boost-users_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/boost-users
>