Converting edge weight to edge length (e.g., for shortest paths)

[Conrad Lee]

In most situations, I'd interpret an edge with a high weight as having a strong connection---e.g., nodes that communicate frequently or between which a high rate of flow exists.

However, in some situations, the sematincs of "weight" are reversed. For exaple, in dijkstra's shortest paths implementations in NetworkX, weights are interpreted as lengths.  Thus, if an edge has a high weight, it means that the two nodes that it connects are distant, which rather suggests a weak connection.

Is there a function that converts the first meaning of weight to the second meaning?  Something like the following is what I have in mind:

def weights_to_lengths(G, weight_key):
    total_weight = float(G.size(weight=weight_key))
    for i, j, attr_dict in G.edges_iter(data=True):
        length = total_weight / attr_dict[weight_key]
        G.edge[i][j]["length"] = length
        if not G.is_directed():
            G.edge[j][i]["length"] = length

[Dan Schult]

The method you show is pretty close to the way I would choose to do it.
Some comments though:
You don't have to worry about setting both sides of an edge because the
edge data dict is actually shared by the two pointers G[u][v] and G[v]
[u]
point to the same dict for undirected. G.succ[u][v] and G.pred[v][u]
point
to the same dict for directed.

The choice of total_weight/weight is not the only choice.
You could use 1/weight. Its just a different scaling, but it allows
a single pass

G.add_edges_from( (u,v,{length_key: (1/dd[weight_key])}) for (u,v,dd)
in G.edges_iter(data=True) )

Dan

> --
> You received this message because you are subscribed to the Google
> Groups "networkx-discuss" group.
> To post to this group, send email to networkx-
> dis...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discuss
> +unsub...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/
> group/networkx-discuss?hl=en.

[Conrad Lee]

Thanks for the feedback, I agree with your points.  The main question though might be:

• Does such a function already exist in networkx?
• If not, should we add it?
• If we should add it, where should it go?

Conrad

On Thu, Apr 5, 2012 at 2:14 PM, Dan Schult <dsc...@colgate.edu> wrote:

The method you show is pretty close to the way I would choose to do it.
Some comments though:
You don't have to worry about setting both sides of an edge because the
edge data dict is actually shared by the two pointers G[u][v] and G[v][u]
point to the same dict for undirected.  G.succ[u][v] and G.pred[v][u] point
to the same dict for directed.

The choice of total_weight/weight is not the only choice.
You could use 1/weight.  Its just a different scaling, but it allows a single pass

G.add_edges_from( (u,v,{length_key: (1/dd[weight_key])}) for (u,v,dd) in G.edges_iter(data=True) )

Dan

On Apr 5, 2012, at 8:47 AM, Conrad Lee wrote:

In most situations, I'd interpret an edge with a high weight as having a strong connection---e.g., nodes that communicate frequently or between which a high rate of flow exists.

However, in some situations, the sematincs of "weight" are reversed. For exaple, in dijkstra's shortest paths implementations in NetworkX, weights are interpreted as lengths.  Thus, if an edge has a high weight, it means that the two nodes that it connects are distant, which rather suggests a weak connection.

Is there a function that converts the first meaning of weight to the second meaning?  Something like the following is what I have in mind:

def weights_to_lengths(G, weight_key):
   total_weight = float(G.size(weight=weight_key))
   for i, j, attr_dict in G.edges_iter(data=True):
       length = total_weight / attr_dict[weight_key]
       G.edge[i][j]["length"] = length
       if not G.is_directed():
           G.edge[j][i]["length"] = length

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To post to this group, send email to networkx-discuss@googlegroups.com.
To unsubscribe from this group, send email to networkx-discuss+unsubscribe@googlegroups.com.

For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

To post to this group, send email to networkx-discuss@googlegroups.com.
To unsubscribe from this group, send email to networkx-discuss+unsubscribe@googlegroups.com.

[Dan Schult]

Ahh.... I see now.

No such function exists in networkx at the moment.
We don't have many routines for transforming edge attributes.

I don't think we should add specific transformations (unless they are common and easy to agree upon what formula to use). But it could be good to make creating your own transformations easier. For example,

G.create_edge_attribute('length', ( (u,v,1/value) for (u,v,value) in G.edges(data='coupling') ))

Suggestions?
Dan

> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.

> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
>
> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.

> For more options, visit this group at http://groups.google.com/group/networkx-discuss?hl=en.
>
>
>
> --
> You received this message because you are subscribed to the Google Groups "networkx-discuss" group.

> To post to this group, send email to networkx...@googlegroups.com.
> To unsubscribe from this group, send email to networkx-discu...@googlegroups.com.