CODEWITHSUNDEEP
pythonnetworkx
Suman Pandey
Suman Pandey

Reputation: 21

Code for finding all negative and positive cycle within weighted graph in python?

I am new in python and I am working on complex network. I want to find all negative and positive cycle within a graph and also find the weight of edges which is participated to make cycles (positive or negative cycle). Can any one help me for this? for example: 

nodes:[1,2,3,4,5] 

edges:[(1,2,w=1),(1,4,w=4),(2,3,w=2),(3,1,w=2),(3,5,w=1),(4,5,w=2),                     
(5,4,w=7),(4,3,w=-6),(5,1,w=3)] 


cycles:[(1-2-3-1,sum=1),(1-4-3-1,sum=0)....etc]

Upvotes: 0

Views: 1336

Answers (1)

Brian Huey
Brian Huey

Reputation: 1630

Create a DiGraph with your nodes, edges and edge attributes:

nodes = [1,2,3,4,5] 
edges = edges = [(1,2,{'w': 1}), (1,4,{'w': 4}), (2,3,{'w':2}), (3,1,{'w': 2}), (3,5,{'w': 1}), (4,5,{'w':2}), (5,4,{'w': 7}), (4,3,{'w': -6}), (5,1,{'w': 3})]
G = nx.DiGraph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)

Find cycles and calculate their weights:

>>> cycles = nx.simple_cycles(G)
>>> weights = nx.get_edge_attributes(dgraph, 'w')
>>> for cycle in cycles:
        cycle.append(cycle[0])
        sumw = sum([weights[(cycle[i-1], cycle[i])] for i in range(1, len(cycle))])
        print cycle, sumw
[1, 4, 5, 1] 9
[1, 4, 3, 5, 1] 2
[1, 4, 3, 1] 0
[1, 2, 3, 5, 1] 7
[1, 2, 3, 1] 5
[3, 5, 4, 3] 2
[4, 5, 4] 9

Upvotes: 1

Related Questions