Phani.lav
Phani.lav

Reputation: 153

Random Graph Python networkx Read file and plot graph

I am trying to read a file that has like 10000+ entries and with 3 columns. column 1 and 2 are the nodes and column 3 is the time in seconds. I am initially trying to plot a random graph G=(n,m) with the data and later want assign the data from 3rd column in between the two relative nodes. After that i have to count the number of nodes, edges, bridges in that graph. I am some what lost here. if i should first plot the graph and then do the counting or should i count and then plot the graph. Any suggestion will be helpful.

import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
import scipy as sy
import itertools as it
import time

with open("File.txt") as f:
     data = f.read()
     data = data.split('\n')
node_one = [row[0] for row in data]
node_two = [row[1] for row in data]
def draw_graph(graph): 
    G = nx.Graph()
    #G.add_edges_from([(node_one[0], node_two[1]])
    #G.add_edges_from(node_one, node_two)
    G.number_of_nodes()
    G.number_of_edges() 
    G.neighbors(edge[0], edge[1])
    n = nx.number_connected_components(G)
    bridge_count = 0
    for edge in G.edges():
        if len(set(G.neighbors(edge[0])) & set(G.neighbors(edge[1]))) == 0:         
           G.remove_edge(edge[0], edge[1])          
             if nx.number_connected_components(G) > n:                  
                print edge, 'is a bridge'
                bridge_count += 1
                G.add_edge(edge[0], edge[1])
print number_of_nodes()

print number_edges()

print neighbors()

print bridge_count

The error i am getting here is Traceback (most recent call last): File "edge_bridge.py", line 13, in

node_one = [row[0] for row in data]

IndexError: string index out of range

Upvotes: 2

Views: 1260

Answers (1)

sophiadw
sophiadw

Reputation: 567

G.number_of_nodes()
G.number_of_edges()

can do the counting for you, they can be done separately than plotting the graph out. Edge attributes can be added following the instruction here.

What is your definition of a bridge here, an edge between 2 nodes that don't have common neighbors? For that, you can iterate through each edge and look for common neighbors of the two end nodes. If there is no common neighbor, that is a bridging tie.

If the definition of a bridge is an edge that when removed, yield more unconnected components, as mentioned by @mdml in the comments. You can do the same iteration as mentioned above, adding one more step. When there is no common neighbors, delete the edge from the graph, count the number of connected components, if the number increases, that's a bridge. Then remember to put the edge back to the graph before iterating to the next edge. Something similar as below

G = nx.Graph()
G.add_edges_from([(1,2), (1,3), (2,3), (2,4), (2,5), (5,6), (6,7), (5,7)])
n = nx.number_connected_components(G)
bridge_count = 0
for edge in G.edges():
    if len(set(G.neighbors(edge[0])) & set(G.neighbors(edge[1]))) == 0:
        G.remove_edge(edge[0], edge[1])
        if nx.number_connected_components(G) > n:
            print edge, 'is a bridge'
            bridge_count += 1
        G.add_edge(edge[0], edge[1])
print bridge_count

The output is

(2, 4) is a bridge
(2, 5) is a bridge
2

Upvotes: 2

Related Questions