Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to change edges' weight by designated rule?

Tags:

I have a weighted graph:

F=nx.path_graph(10) G=nx.Graph() for (u, v) in F.edges():     G.add_edge(u,v,weight=1) 

Get the nodes list:

[(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9)] 

I want to change each edge's weight by this rule:

Remove one node, such as node 5, clearly, edge (4, 5), and (5, 6) will be delete, and the weight of each edge will turn to:

{# these edges are nearby the deleted edge (4, 5) and (5, 6)  (3,4):'weight'=1.1,  (6,7):'weight'=1.1,   #these edges are nearby the edges above mentioned  (2,3):'weight'=1.2,  (7,8):'weight'=1.2,   #these edges are nearby the edges above mentioned  (1,2):'weight'=1.3,  (8,9):'weight'=1.3,   # this edge is nearby (1,2)  (0,1):'weight'=1.4} 

How to write this algorithm?

path_graph is just an example. I need a program to suit any graph type. Furthermore, the program need to be iterable, it means I can remove one node from the origin graph each time.

like image 637
Johnny Avatar asked Oct 19 '10 04:10

Johnny


People also ask

What is the weight of an edge in a graph?

The weight of an edge is often referred to as the "cost" of the edge. In applications, the weight may be a measure of the length of a route, the capacity of a line, the energy required to move between locations along a route, etc.

Can an edge have a weight of 0?

Notes. In an undirected graph edges with weight 0 can be eliminated and the nodes be merged. A shortest path between them will always have length 0 . If the whole graph only has 0 weights, then the graph could just be merged to one node.


1 Answers

You can access the edge weight as G[u][v]['weight'] or by iterating over the edge data. So you can e.g.

In [1]: import networkx as nx  In [2]: G=nx.DiGraph()  In [3]: G.add_edge(1,2,weight=10)  In [4]: G.add_edge(2,3,weight=20)  In [5]: G[2][3]['weight'] Out[5]: 20  In [6]: G[2][3]['weight']=200  In [7]: G[2][3]['weight'] Out[7]: 200  In [8]: G.edges(data=True) Out[8]: [(1, 2, {'weight': 10}), (2, 3, {'weight': 200})]  In [9]: for u,v,d in G.edges(data=True):    ...:     d['weight']+=7    ...:         ...:       In [10]: G.edges(data=True) Out[10]: [(1, 2, {'weight': 17}), (2, 3, {'weight': 207})] 
like image 169
Aric Avatar answered Oct 28 '22 18:10

Aric