[Lemon-user] Question about modifying edgeMap values

[Alpár Jüttner]

Hi,


> [...]
> 
> Later, I'd like to modify the entries of the edgeMap weight.
> Specifically, I have a complete bipartite graph with partitions A =
> {0,...,N-1} and B = {N,N+1,...N+K-1}, and I want to do something like
> the following:
> 
> 
> for(i = 0; i < N; i++) {
>   for(k = 0; k < K; k++) {
>     if(w[i][k] == 0)
>       //here, change the value of edgeMap corresponding to the edge
> between nodes i and k+N to zero
>   }
> }
> 
> 
> How can I do this?

The point is that ListGraph uses a incidence list representation of the
graph, thus it is able to list the edges incident to a certain node (or
all edges) very fast, but it cannot look up an edge between two nodes
directly.

For the purpose, you can use findEdge() or *ArcLookUp, but be aware that
they are slow (O(d) and O(log d) time, respectively).

In most of the cases you had better organizing your code in a way that
avoid edge look up. For example instead of your code above you can
simply write this:

for(ListGraph::EdgeIt e(g);e!=INVALID;++e)
  weight[e] = 0;

Of course, the end-nodes of and edge can be retrieved efficiently, thus
you can also do things like this:

for(ListGraph::EdgeIt e(g);e!=INVALID;++e)
  weight[e] = pot[g.u(e)] + pot[g.v(e)];

Here pot is a  ListGraph::NodeMap<int>.


>  I would like to do this by referencing the edges by their endpoints,
> although I'm assuming this is impossible since this isn't a unique
> identifier (I thought I saw somewhere in the documentation that it's
> possible to define multiple edges between nodes). Should/can I use the
> labels I defined for the edges in the .lgf file to refer to the edges?

If you really want, then of course, you can.
For this you must read the labels into an EdgeMap.

In order to be able to look up an Edge by its label fast (O(logn) time),
you will want to use a CrossRefMap
( http://lemon.cs.elte.hu/pub/doc/1.2.1/a00093.html ) on the top of the
EdgeMap storing the labels.

I hope this helped.

Regards,
Alpár