# Define path_exists() def path_exists(G, node1, node2): """ This function checks whether a path exists between two nodes (node1, node2) in graph G. """ visited_nodes = set()
# Initialize the queue of nodes to visit with the first node: queue queue = [node1]
# Iterate over the nodes in the queue for node in queue:
# Get neighbors of the node neighbors = G.neighbors(node)
# Check to see if the destination node is in the set of neighbors if node2 in neighbors: print('Path exists between nodes {0} and {1}'.format(node1, node2)) return True break
def path_exists(G, node1, node2): """ This function checks whether a path exists between two nodes (node1, node2) in graph G. """ visited_nodes = set() queue = [node1]
for node in queue: neighbors = G.neighbors(node) if node2 in neighbors: print('Path exists between nodes {0} and {1}'.format(node1, node2)) return True else: # Add current node to visited nodes visited_nodes.add(node)
# Add neighbors of current node that have not yet been visited queue.extend([n for n in neighbors if n not in visited_nodes])
def path_exists(G, node1, node2): """ This function checks whether a path exists between two nodes (node1, node2) in graph G. """ visited_nodes = set() queue = [node1]
for node in queue: neighbors = G.neighbors(node) if node2 in neighbors: print('Path exists between nodes {0} and {1}'.format(node1, node2)) return True break
else: visited_nodes.add(node) queue.extend([n for n in neighbors if n not in visited_nodes])
# Check to see if the final element of the queue has been reached if node == queue[-1]: print('Path does not exist between nodes {0} and {1}'.format(node1, node2))
# Place the appropriate return statement return False
# Write a function that identifies all nodes in a triangle relationship with a given node. def nodes_in_triangle(G, n): """ Returns the nodes in a graph `G` that are involved in a triangle relationship with the node `n`. """ triangle_nodes = set([n])
# Iterate over all possible triangle relationship combinations for n1, n2 in combinations(G.neighbors(n),2):
# Check if n1 and n2 have an edge between them if G.has_edge(n1,n2):
# Add n1 to triangle_nodes triangle_nodes.add(n1)
# Add n2 to triangle_nodes triangle_nodes.add(n2)
return triangle_nodes
# Write the assertion statement assert len(nodes_in_triangle(T, 1)) == 35
# Define node_in_open_triangle() def node_in_open_triangle(G, n): """ Checks whether pairs of neighbors of node `n` in graph `G` are in an 'open triangle' relationship with node `n`. """ in_open_triangle = False
# Iterate over all possible triangle relationship combinations for n1, n2 in combinations(G.neighbors(n),2):
# Check if n1 and n2 do NOT have an edge between them if not G.has_edge(n1,n2):
in_open_triangle = True
break
return True
我们可以利用这个函数来查看一个图中，有多少个open triangle:
1 2 3 4 5 6 7 8 9 10 11 12 13
# Compute the number of open triangles in T num_open_triangles = 0
# Iterate over all the nodes in T for n in T.nodes():
# Check if the current node is in an open triangle if node_in_open_triangle(T,n):
# Define maximal_cliques() def maximal_cliques(G, size): """ Finds all maximal cliques in graph `G` that are of size `size`. """ mcs = [] for clique in nx.find_cliques(G): if len(clique) == size: mcs.append(clique) return mcs
# Check that there are 33 maximal cliques of size 3 in the graph T assert len(maximal_cliques(T, 3)) == 33
# 导入包 In [1]: import networkx as nx # 创建图 In [2]: G = nx.erdos_renyi_graph(n=20, p=0.2) # 查看节点 In [3]: G.nodes() Out[3]: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
# 将上面图中的节点8复制给nodes In [4]: nodes = G.neighbors(8) In [5]: nodes Out[5]: [2, 3, 4, 10] In [6]: nodes.append(8)
1 2 3 4 5 6 7 8 9 10
# 将子图添加到G In [7]: G_eight = G.subgraph(nodes)
# 查看G_eight的edges In [8]: G_eight.edges() Out[8]: [(8, 2), (8, 3), (8, 4), (8, 10), (2, 10)] In [9]: G_eight Out[9]: <networkx.classes.graph.Graph at 0x10cae39e8> In [10]: G Out[10]: <networkx.classes.graph.Graph at 0x10cad1f60>
# Define get_nodes_and_nbrs() def get_nodes_and_nbrs(G, nodes_of_interest): """ Returns a subgraph of the graph `G` with only the `nodes_of_interest` and their neighbors. """ nodes_to_draw = []
# Iterate over the nodes of interest for n in nodes_of_interest:
# Append the nodes of interest to nodes_to_draw nodes_to_draw.append(n)
# Iterate over all the neighbors of node n for nbr in G.neighbors(n):
# Append the neighbors of n to nodes_to_draw nodes_to_draw.append(nbr)
return G.subgraph(nodes_to_draw)
测试一下：
1 2 3 4 5 6 7 8
nodes_of_interest = [29, 38, 42]
# Extract the subgraph with the nodes of interest: T_draw T_draw = get_nodes_and_nbrs(T,nodes_of_interest)
# Draw the subgraph to the screen nx.draw(T_draw) plt.show()
