[Boost-users] Accessing the edge through edge descriptor with bundled properties

[giridhar]

Hello All,

   I have to access an edge in a vector called border_edge through an edge descriptor. For example

for( vector<Edge>::iterator j=border_edge.begin();j!=border_edge.end();++j)

{

Edge e = t1[*j];  // I am getting error saying that No suitable conversion for Edge to Edgep exits

}

Details:

border_edge is of type std::vector<Edge> border_edge(10);

Graph as: typedef subgraph< adjacency_list<vecS, vecS, undirectedS,

   Vertexp, property< edge_index_t, unsigned int, Edgep > > > Graph;

typedef Graph::edge_descriptor Edge;

I have exterior Edge property defined as 

struct Edgep

{

int edge_index;

int edge_w;

std::string edge_name;

int capacity;

int residual_capcity;

int bandwidth_used;

};

Whenever I am adding edges into graph I am updating this border_edge vector. Say I am adding an edge from vertex 0 to 4 then I am doing this

border_edge[i] = (add_edge(0,4,t)).first; //i is an example index. It is actually running in the loop.

Can anyone please give some suggestions regarding this. How to access this edge which is inside vector? or what descriptor type should I use?

--
Regards,
Giridhar

[Jeremiah Willcock]

On Mon, 24 Oct 2011, giridhar wrote:

> Hello All,
> � �I have to access an edge in a vector called border_edge through an edge descriptor. For example
>
> for( vector<Edge>::iterator j=border_edge.begin();j!=border_edge.end();++j)
> {
> Edge e = t1[*j]; �// I am getting error saying that�No suitable conversion for Edge to Edgep exits
> }

Assuming your graph is named t1, it looks like you are getting your edge
property, but trying to put into a variable whose type is your edge
descriptor. The edge descriptor is just *j.

-- Jeremiah Willcock

[Christoph]

Hello,

this is an interesting example for me as a beginner. As far as i
understand the concept of a "descriptor" it does not matter if you use
descriptors for some edges or copies of these descriptors in a container
like "border_edge".
Am i right? That is why we call it descriptor. It describes the edge but
it is not the edge, like a pointer points to an object but is not the
object. So it doesn't matter if we use descriptor A, B or C if they all
describe the same edge.

Are there any situations in which i have to care about the copies? For
instance what if I delete the edge of descriptor A (while B and C being
descriptors of the same edge). Will the descriptors B and C become
invalid in the way that they both will point to some kind of "Null"-edge
or do I have to deal with some kind of undefined behaviour?

best regards
Christoph

> _______________________________________________ Boost-users mailing list Boost...@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users

_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users

[Christoph]

Why do you not correct me if i state stupid things?

On Tue, 2011-10-25 at 12:22 +0200, Christoph wrote:
> Hello,
>
> this is an interesting example for me as a beginner. As far as i
> understand the concept of a "descriptor" it does not matter if you use
> descriptors for some edges or copies of these descriptors in a container
> like "border_edge".
> Am i right? That is why we call it descriptor. It describes the edge but
> it is not the edge, like a pointer points to an object but is not the
> object. So it doesn't matter if we use descriptor A, B or C if they all
> describe the same edge.
>
> Are there any situations in which i have to care about the copies? For
> instance what if I delete the edge of descriptor A (while B and C being
> descriptors of the same edge). Will the descriptors B and C become
> invalid in the way that they both will point to some kind of "Null"-edge
> or do I have to deal with some kind of undefined behaviour?

Because there are no other responses i would like to point out that the
pointer analogy was a bad thing because the descriptor ist not something
like a pointer. The iterator ist something like a pointer but not the
edge descriptor. With

typedef boost::adjacency_list <
boost::listS,boost::vecS,boost::undirectedS> Graph;

typedef boost::graph_traits<Graph> gt;

sizeof (gt::edge_descriptor) is 12 and the
sizeof (gt::edge_iterator) is 4 on my machine

So if you do

Graph g(5);

gt::edge_descriptor a,b,c;
a = b = c = add_edge (0,1,g);

then you actually have 4 distinct copies of edge_descriptors
a = (0,1)
b = (0,1)
c = (0,1)
and the edge added into the graph (0,1)

if you now change one edge_descriptor for instance b:

b.m_source = 2;

then

a = (0,1)
b = (2,1)
c = (0,1)
and the edge added into the graph (0,1)

only one copy (b) is changed. A

remove_edge (a, g);

just removes the edge from the graph. Then we still have

a = (0,1)
b = (2,1)
c = (0,1)

best regards
Christoph

[Jeremiah Willcock]

On Tue, 25 Oct 2011, Christoph wrote:

> Hello,
>
> this is an interesting example for me as a beginner. As far as i
> understand the concept of a "descriptor" it does not matter if you use
> descriptors for some edges or copies of these descriptors in a container
> like "border_edge".

Yes -- copying a descriptor keeps the same value and is valid to refer to
the same vertex or edge.

> Am i right? That is why we call it descriptor. It describes the edge but
> it is not the edge, like a pointer points to an object but is not the
> object. So it doesn't matter if we use descriptor A, B or C if they all
> describe the same edge.

Yes, but there often isn't an object that you can say "is" the edge. An
edge might logically be two entries in different vectors, and the edge
descriptor is an index into those vectors; what is the edge in that case?

> Are there any situations in which i have to care about the copies? For
> instance what if I delete the edge of descriptor A (while B and C being
> descriptors of the same edge). Will the descriptors B and C become
> invalid in the way that they both will point to some kind of "Null"-edge
> or do I have to deal with some kind of undefined behaviour?

That depends on the graph type, but descriptors are typically not
reference counted, so if you delete an edge with descriptor e then any
copies of e will be invalid as well. In fact, descriptors for other edges
might also become invalid; there is a section in the adjacency_list
documentation about those rules. In that way, descriptors are somewhat
like pointers; there is a spectrum of descriptor types between values that
are the edge and don't point to anything else (such as grid_graph edge
descriptors) and edge descriptors that are index values or pointers (such
as adjacency_list or compressed_sparse_row_graph descriptors).