NetworkX的dicts of dicts以及解决Seven Bridges of Königsberg问题 |
您所在的位置：网站首页 › 邻里重叠度 › NetworkX的dicts of dicts以及解决Seven Bridges of Königsberg问题 |
NetworkX的dicts of dicts以及解决Seven Bridges of Königsberg问题
|
提供4种基本图类别：
Graph ：无向图，支持自环，不支持节点间多条边； DiGraph ：有向图，支持自环，不支持节点间多条边； MultiGraph ：无向图，支持节点间多条边； MultiDiGraph ：有向图，支持节点间多条边； 所有图类都允许将任何可散列对象作为节点。可散列对象包括字符串、元组、整数等。任意边属性（如权重和标签）可以与边关联。 图形内部数据结构基于邻接列表表示，并使用Python字典数据结构实现。图邻接结构被实现为Python字典；外部字典由节点键入值，这些值本身是由相邻节点键入与该边缘相关联的边缘属性的字典。这种“dict of dicts”结构允许快速添加、删除和查找大型图中的节点和邻居。底层数据结构由类定义中的方法（编程接口“API”）直接访问。另一方面，所有函数都只通过这些API方法而不是直接作用于数据结构来操纵类似图形的对象。这种设计允许用实现相同方法的替代数据结构替换基于“dicts of dicts”的数据结构。 基本使用在指定图形时，必须做出的下一个选择是使用什么类型的节点和边。如果您只关心网络的拓扑结构，那么使用整数或字符串作为节点是有意义的，您不必担心边缘数据。如果已经有一个数据结构来描述节点，那么只要该结构是可散列的，就可以简单地将其用作节点。如果它不可哈希，则可以使用唯一标识符来表示节点，并将数据分配为节点属性。 边通常具有与其关联的数据。任意数据可以作为边属性与边关联。如果数据是数字，并且意图表示加权图，则对属性使用“weight”关键字。一些图形算法，例如Dijkstra的最短路径算法，默认情况下使用该属性名称来获取每条边的权重。添加边时，可以使用关键字/值对将属性指定给边。可以使用任何关键字来命名属性，然后可以使用该属性关键字查询边缘数据。一旦你决定了如何对节点和边进行编码，以及你是否有一个带有或不带有多边的无向/有向图，就可以建立你的网络了。 解决Seven Bridges of Königsberg柯尼斯堡（今俄罗斯加里宁格勒）的市区横跨普雷格尔河两岸，河中心有两个小岛，小岛与河的两岸有七座桥连接。在所有桥都只能走一遍的前提下，如何才能把这个地方所有的桥都走遍？（注：其实相当于一笔画红包的一笔画问题）
抽象出数学模型：
使用图绘制： import networkx as nx import matplotlib.pyplot as plt import pylab G = nx.DiGraph() G.add_edge("A", "B", label="a") G.add_edge("B", "A", label="b") G.add_edge("A", "C", label="c") G.add_edge("C", "A", label="d") G.add_edge("A", "D", label="e") G.add_edge("B", "D", label="f") G.add_edge("C", "D", label="g") positions = {"A": (0, 0), "B": (1, -2), "C": (1, 2), "D": (2, 0)} edge_labels = nx.get_edge_attributes(G, "label") nx.draw_networkx_nodes(G, pos=positions, node_size=500) nx.draw_networkx_labels(G, pos=positions, font_color="w") nx.draw_networkx_edges( G, pos=positions, edgelist=[("A", "D"), ("B", "D"), ("C", "D")], arrowstyle="-" ) nx.draw_networkx_edges( G, pos=positions, edgelist=[("A", "B"), ("B", "A"), ("C", "A"), ("A", "C")], arrowstyle="-", connectionstyle="arc3,rad=0.2", ) nx.draw_networkx_edge_labels(G, pos=positions, edge_labels=edge_labels, label_pos=0.2) pylab.show()
证明能不能？其实很简单，一次走7桥，需要A B C D字母的序列长度是8.每个地区经过的桥数可以确定经过该地区的次数。A5个桥，则经过A 3次，同理3 + 2 + 2 + 2 = 9.不等于8.说明不可以一次走完。 He described his logic as follows: If we cross bridge a, we walk from A to B, In this case, our travel route is denoted as AB.If we cross first a and then f, our route will be ABD.So, sequential use of n bridges is denoted with n+1 capital letters.Since we need to cross each of 7 bridges, our route should consist of a sequence of A, B, C and D of length 8.He also stated the fact that number of appearances of each land mass in the route depend on the number of bridges it has. A has 5 bridges. All these 5 bridges should appear in our Euler Path exactly once. Then, A should appear in our route for 3 times.B has 3 bridges. It should appear in the route for 2 times.C has 3 bridges. It should appear in the route for 2 times.D has 3 bridges. It should appear in the route for 2 times.Then, the total length of the route should be 3 + 2 + 2 + 2 = 9.It is obvious that we cannot satisfy both of these conditions at the same time. Therefore, Euler concluded that there is no solution to Seven Bridges of Königsberg problem (I.e. Königsberg does not have an Euler Path). 定理： Euler generalized the method he applied for Königsberg problem as follows: A graph has an Euler Path if and only if the number of vertices with odd degree（） is either zero or two. If there are two vertices with odd degree, then they are the starting and ending vertices.If there are no vertices with odd degree, any vertex can be starting or ending vertex and the graph has also an Euler Circuit.注释： odd degree :与其相连的边数目为奇数的顶点NetworkX实现不允许具有孤立节点的图具有欧拉路径和/或欧拉电路。因此，欧拉路径或欧拉回路不仅必须访问图的所有边，还必须访问图中的所有顶点。A directed graph must be strongly connected and every vertex of it must have equal in degree and out degree.semi_eulerian ：它可能有一个具有不同起点和终点的欧拉路径。如上所述，如果且仅当：there are exactly two vertices of odd degree, andall of its vertices belong to a single connected component.For a directed graph to has an Eulerian Path, it must have at most one vertex has out_degree - in_degree = 1,at most one vertex has in_degree - out_degree = 1,every other vertex has equal in_degree and out_degree, andall of its vertices belong to a single connected component of the underlying undirected graph (I.e. Should be weakly connected).code： import networkx as nx nx.is_eulerian(G) nx.has_eulerian_path(G) nx.is_semieulerian(G) nx.eulerize(G) nx.eulerian_path(G) nx.eulerian_circuit(G)NetworkX implements several methods using the Euler’s algorithm. These are: is_eulerian : Whether the graph has an Eulerian circuiteulerian_circuit : Sequence of edges of an Eulerian circuit in the graph.eulerize : Transforms a graph into an Eulerian graphis_semieulerian : Whether the graph has an Eulerian path but not an Eulerian circuit.has_eulerian_path: Whether the graph has an Eulerian path.eulerian_path : Sequence of edges of in Eulerian path in the graph.参考： NetworkX Reference NetworkX — NetworkX documentation Euler’s Algorithm — NetworkX Notebooks |
【本文地址】