def ER_Generateor(N=1000, M=3000):
G = nx.gnm_random_graph(N, M)
#component of the network
if nx.is_connected(G) == False:
# Get the Greatest Component of Networks #####
components = sorted(nx.connected_components(G), key = len, reverse=True)
print "Component Number of the Generated Network:", len(components)
for i in range(1, len(components)):
for node in components[i]:
G.remove_node(node)
#end for
print nx.is_connected(G)
#endif
return G
#************************************************************************
python类is_connected()的实例源码
def SF_Generateor(N=1000, m=3):
G = nx.barabasi_albert_graph(N, m)
#component of the network
if nx.is_connected(G) == False:
# Get the Greatest Component of Networks #####
components = sorted(nx.connected_components(G), key = len, reverse=True)
print "Component Number of the Generated Network:", len(components)
for i in range(1, len(components)):
for node in components[i]:
G.remove_node(node)
#end for
print nx.is_connected(G)
#endif
return G
#************************************************************************
def ER_Generateor(N=1000, M=3000):
G = nx.gnm_random_graph(N, M)
#component of the network
if nx.is_connected(G) == False:
# Get the Greatest Component of Networks #####
components = sorted(nx.connected_components(G), key = len, reverse=True)
print "Component Number of the Generated Network:", len(components)
for i in range(1, len(components)):
for node in components[i]:
G.remove_node(node)
#end for
print nx.is_connected(G)
#endif
return G
#************************************************************************
def SF_Generateor(N=1000, m=3):
G = nx.barabasi_albert_graph(N, m)
#component of the network
if nx.is_connected(G) == False:
# Get the Greatest Component of Networks #####
components = sorted(nx.connected_components(G), key = len, reverse=True)
print "Component Number of the Generated Network:", len(components)
for i in range(1, len(components)):
for node in components[i]:
G.remove_node(node)
#end for
print nx.is_connected(G)
#endif
return G
#************************************************************************
def Euler_Tour(multigraph):
""" Uses Fleury's algorithm to find the Euler Tour of the MultiGraph.
"""
tour = []
temp_graph = nx.MultiGraph()
graph_nodes = nx.nodes(multigraph)
current_node = graph_nodes[0]
tour.append(current_node)
while nx.number_of_edges(multigraph) > 0:
for edge in multigraph.edges(current_node):
temp_graph = copy.deepcopy(multigraph)
temp_graph.remove_edge(edge[0], edge[1], key=None)
if nx.is_connected(temp_graph):
tour.append(edge[1])
current_node = edge[1]
multigraph.remove_edge(edge[0], edge[1], key=None)
break
else:
tour.append(edge[1])
current_node = edge[1]
multigraph.remove_edge(edge[0], edge[1], key=None)
multigraph.remove_nodes_from(nx.isolates(multigraph))
return tour
def random_raiden_network(
token_address,
blockchain_service,
node_addresses,
deposit,
settle_timeout):
""" Creates random channels among the test nodes until we have a connected graph. """
graph = networkx.Graph()
graph.add_nodes_from(node_addresses)
for edge in blockchain_service.addresses_by_token(token_address):
graph.add_edge(edge[0], edge[1])
while not networkx.is_connected(graph):
from_address = random.choice(node_addresses)
to_address = random.choice(node_addresses)
netcontract_address = blockchain_service.new_netting_contract(
token_address,
from_address,
to_address,
settle_timeout,
)
blockchain_service.deposit(
token_address,
netcontract_address,
from_address,
deposit,
)
blockchain_service.deposit(
token_address,
netcontract_address,
to_address,
deposit,
)
graph.add_edge(from_address, to_address)
def run(self):
ip_addresses = ['192.168.1.%s' % x for x in range(1, self._number_clients)]
ports = [x for x in range(1, 2)]
clients = []
progress = 0
for ip_addr in ip_addresses:
print_progress(progress, self._number_clients, suffix="Running simulation")
for port in ports:
progress += 1
client = Client(ip_addr, port, clients[0] if len(clients) > 0 else None,
max_chache_size=self._number_connections_per_client)
clients.append(client)
connection = Connection(client, clients[0])
connection.initiate()
bootstrapper_connections = clients[0].get_connections()
for conn in bootstrapper_connections:
connection = Connection(client, conn.second_client)
connection.initiate()
graph = networkx.nx.Graph()
for client in clients:
logging.error(client.get_ident())
logging.error(client.get_connection_idents())
for node in client.get_connections():
graph.add_edge(node.first_client.get_ident(), node.second_client.get_ident())
networkx.draw(graph, with_labels=False)
plt.savefig("path_graph.pdf")
print("Network is connected: %s" % networkx.is_connected(graph))
print("Average shortest path length: %s" % networkx.average_shortest_path_length(graph))
print("Average bipartite clustering coefficent %s" % networkx.average_clustering(graph))
print("Bipartite clustering coefficent %s" % networkx.clustering(graph))
print("degree_assortativity_coefficient %s" % networkx.degree_assortativity_coefficient(graph))
def Prediction_LinkScores_Ratio(G, Predictor, Proportion, Toleration, Predict_Gap):
print "Prediction_LinkScores_Ratio!"
Rank_List_Set = {}
OK_Value = float(G.number_of_edges())/Proportion
if nx.is_connected(G) == True:
Edge_Set = G.edges(data='True')
Total = 0
Error = 0
Rank_List_Set[0] = [Link_Predictors.Wighted_Link_Prediction(Predictor, G), nx.average_clustering(G), nx.average_shortest_path_length(G) ] ##Running time !!!!!
'''
while 1:
#print i,len(Edge_Set),
Tep_Edge = []
Del = random.randint(0, len(Edge_Set)-1)
Tep_Edge.append(Edge_Set[Del])
#print "random range:", len(Edge_Set)-1
#print Del,
#Prediction with different training set
G.remove_edge(Edge_Set[Del][0], Edge_Set[Del][1])
if nx.is_connected(G) != True:
G.add_edges_from(Tep_Edge)
Error = Error + 1
#print "Error:", Error
else:
#print Edge_Set[Del],
Error = 0
Total = Total + 1
#print "Total:", Total
if Total%Predict_Gap == 0:
V1 = Link_Predictors.Wighted_Link_Prediction(Predictor, G)
V2 = nx.average_clustering(G)
V3 = nx.average_shortest_path_length(G)
#V4 = Performance_Evaluation_AUC(Predictor, G, Probe_Set, Non_existing_links)
Rank_List_Set[Total] = [V1,V2,V3]
Edge_Set = G.edges(data='True')
#end if
if Total > OK_Value or Error == Toleration:
#print "complete with Total, Error:", Total, Error
return Rank_List_Set
#end while
'''
return Rank_List_Set
#end if
#return Rank_List_Set
##==========================================================================================
#Native_Prediction_Experiment(G, 'WSD', Probe_Set, Top_L, 3) #Top_K, Deleted_Ratio
def connectGraphComponents(graph, level=2, highway='path', connectNearest=False):
if nx.is_connected(graph):
return graph
combinations = itertools.permutations(range(nx.number_connected_components(graph)),2)
subgraphs = list(nx.connected_component_subgraphs(graph, copy=True))
rtrees = [getGraphRtree(subgraph,'nodes') for subgraph in subgraphs]
nearestComponents={}
for i, j in combinations:
if i not in nearestComponents:
nearestComponents[i] = []
smallest = i if len(subgraphs[i]) < len(subgraphs[j]) else j
biggest = j if smallest is i else i
candidates = {}
nearestNeighbors = {}
for node1, data in subgraphs[smallest].nodes(data=True):
x, y = data['longitude'], data['latitude']
hits = list(rtrees[biggest].nearest((x, y, x, y), 2, objects="raw"))
for candidate in hits:
data = json.loads(candidate)
candidates[data['id']] = Point(data['geometry']['coordinates'])
source = Point([x,y])
distance, node2 = nearestNode(source, candidates)
nearestNeighbors[distance] = node1, node2
u,v = nearestNeighbors[min(nearestNeighbors.keys())]
if connectNearest:
nearestComponents[i].append((j, min(nearestNeighbors.keys()), (u,v)))
else:
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
if connectNearest:
for i in nearestComponents.keys():
data = nearestComponents[i]
j, distance, (u,v) = sorted(data, key=lambda tup: tup[1])[0]
if not graph.has_edge(u, v):
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
return connectGraphComponents(graph, level, highway, connectNearest=connectNearest)
def connectGraphComponents(graph, level=2, highway='path', connectNearest=False):
if nx.is_connected(graph):
return graph
combinations = itertools.permutations(range(nx.number_connected_components(graph)),2)
subgraphs = list(nx.connected_component_subgraphs(graph, copy=True))
rtrees = [getGraphRtree(subgraph,'nodes') for subgraph in subgraphs]
nearestComponents={}
for i, j in combinations:
if i not in nearestComponents:
nearestComponents[i] = []
smallest = i if len(subgraphs[i]) < len(subgraphs[j]) else j
biggest = j if smallest is i else i
candidates = {}
nearestNeighbors = {}
for node1, data in subgraphs[smallest].nodes(data=True):
x, y = data['longitude'], data['latitude']
hits = list(rtrees[biggest].nearest((x, y, x, y), 2, objects="raw"))
for candidate in hits:
data = json.loads(candidate)
candidates[data['id']] = Point(data['geometry']['coordinates'])
source = Point([x,y])
distance, node2 = nearestNode(source, candidates)
nearestNeighbors[distance] = node1, node2
u,v = nearestNeighbors[min(nearestNeighbors.keys())]
if connectNearest:
nearestComponents[i].append((j, min(nearestNeighbors.keys()), (u,v)))
else:
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
if connectNearest:
for i in nearestComponents.keys():
data = nearestComponents[i]
j, distance, (u,v) = sorted(data, key=lambda tup: tup[1])[0]
if not graph.has_edge(u, v):
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
return connectGraphComponents(graph, level, highway, connectNearest=connectNearest)
def evaluateStaticLinkPrediction(digraph, graph_embedding,
train_ratio=0.8,
n_sample_nodes=None,
sample_ratio_e=None,
no_python=False,
is_undirected=True):
node_num = digraph.number_of_nodes()
# seperate train and test graph
train_digraph, test_digraph = evaluation_util.splitDiGraphToTrainTest(
digraph,
train_ratio=train_ratio,
is_undirected=is_undirected
)
if not nx.is_connected(train_digraph.to_undirected()):
train_digraph = max(
nx.weakly_connected_component_subgraphs(train_digraph),
key=len
)
tdl_nodes = train_digraph.nodes()
nodeListMap = dict(zip(tdl_nodes, range(len(tdl_nodes))))
nx.relabel_nodes(train_digraph, nodeListMap, copy=False)
test_digraph = test_digraph.subgraph(tdl_nodes)
nx.relabel_nodes(test_digraph, nodeListMap, copy=False)
# learning graph embedding
X, _ = graph_embedding.learn_embedding(
graph=train_digraph,
no_python=no_python
)
node_l = None
if n_sample_nodes:
test_digraph, node_l = graph_util.sample_graph(
test_digraph,
n_sample_nodes
)
X = X[node_l]
# evaluation
if sample_ratio_e:
eval_edge_pairs = evaluation_util.getRandomEdgePairs(
node_num,
sample_ratio_e,
is_undirected
)
else:
eval_edge_pairs = None
estimated_adj = graph_embedding.get_reconstructed_adj(X, node_l)
predicted_edge_list = evaluation_util.getEdgeListFromAdjMtx(
estimated_adj,
is_undirected=is_undirected,
edge_pairs=eval_edge_pairs
)
filtered_edge_list = [e for e in predicted_edge_list if not train_digraph.has_edge(e[0], e[1])]
MAP = metrics.computeMAP(filtered_edge_list, test_digraph)
prec_curv, _ = metrics.computePrecisionCurve(
filtered_edge_list,
test_digraph
)
return (MAP, prec_curv)
