平面度

check_planarity (g) [, counterexample] ) 检查图是否是平面的,并返回反例或嵌入。
class PlanarEmbedding(incoming_graph_data=None, **attr)[源代码]

表示平面图及其平面嵌入。

平面嵌入由 combinatorial embedding .

邻居排序:

与通常的图形结构相比,嵌入还存储每个顶点的所有相邻点的顺序。相邻的顺序可以是顺时针(CW)或逆时针(CCW)方向。这个顺序在底层的有向图中存储为边缘属性。对于边(u,v),沿顺时针方向将边属性“cw”设置为紧随v之后的u的邻居。

为了使planarembedding有效,它必须满足多个条件。可以用该方法检查这些条件是否满足 check_structure() . 条件是:

  • 边缘必须向两个方向移动(因为边缘属性不同)
  • 每个边必须有一个“cw”和“ccw”属性,该属性对应于正确的平面嵌入。
  • 具有非零度的节点必须具有节点属性“first_nbr”。

只要planarembedding无效,只应调用以下方法:

尽管该图是nx.digraph的一个子类,但它仍然可以用于需要无向图的算法,因为该方法 is_directed() 被重写。这是可能的,因为有效的平面图必须在两个方向都有边。

半边:

在方法上像 add_half_edge_ccw the term "half-edge" is used, which is a term that is used in doubly connected edge lists . 它用来强调边缘只在一个方向上,而在相反方向上存在另一个半边缘。虽然常规边总是在其旁边有两个面(包括外表面),但可以指定每个半边 恰好一 面对。对于定向为u低于v的半边(u,v),则属于(u,v)的面位于该半边的右侧。

实际案例

创建星型图的嵌入(比较 nx.star_graph(3) ):

>>> G = nx.PlanarEmbedding()
>>> G.add_half_edge_cw(0, 1, None)
>>> G.add_half_edge_cw(0, 2, 1)
>>> G.add_half_edge_cw(0, 3, 2)
>>> G.add_half_edge_cw(1, 0, None)
>>> G.add_half_edge_cw(2, 0, None)
>>> G.add_half_edge_cw(3, 0, None)

或者,同样的嵌入也可以按逆时针方向定义。以下结果将产生完全相同的平面嵌入:

>>> G = nx.PlanarEmbedding()
>>> G.add_half_edge_ccw(0, 1, None)
>>> G.add_half_edge_ccw(0, 3, 1)
>>> G.add_half_edge_ccw(0, 2, 3)
>>> G.add_half_edge_ccw(1, 0, None)
>>> G.add_half_edge_ccw(2, 0, None)
>>> G.add_half_edge_ccw(3, 0, None)

创建图形后,可以验证planarembedding对象是否正确:

>>> G.check_structure()
add_half_edge_ccw(start_node, end_node, reference_neighbor)[源代码]

添加从开始节点到结束节点的半边缘。

半边沿逆时针方向添加到现有半边(起始节点、参考相邻节点)旁边。

参数:
  • start_nodenode )--插入边的起始节点。
  • end_nodenode )--插入边缘的结束节点。
  • reference_neighbornode )--参考边的结束节点。
加薪:

nx.NetworkXException --如果引用邻居不存在。

add_half_edge_cw(start_node, end_node, reference_neighbor)[源代码]

添加从开始节点到结束节点的半边缘。

半边将顺时针添加到现有半边旁边(起始节点,参考相邻)。

参数:
  • start_nodenode )--插入边的起始节点。
  • end_nodenode )--插入边缘的结束节点。
  • reference_neighbornode )--参考边的结束节点。
加薪:

nx.NetworkXException --如果引用邻居不存在。

add_half_edge_first(start_node, end_node)[源代码]

添加的半边按顺序插入到第一个位置。

参数:
  • start_nodenode
  • end_nodenode
check_structure()[源代码]

如果此对象有效,则无例外运行。

检查是否满足以下属性:

  • 边缘向两个方向移动(因为边缘属性不同)。
  • 每个边都有一个“cw”和“ccw”属性,对应于正确的平面嵌入。
  • 度数大于0的节点具有节点属性“first_nbr”。

运行此方法可以验证基础图必须是平面的。

加薪:nx.NetworkXException --如果planarembedding无效,将引发此异常并给出简短解释。
connect_components(v, w)[源代码]

在某些位置为(v,w)和(w,v)添加半边。

仅当v和w在不同的组件中时才应调用此方法,否则可能会破坏嵌入。这尤其意味着如果 connect_components(v, w) 被调用它不允许调用 connect_components(w, v) 之后。在第一次调用后,两个方向上的邻居方向都设置正确。

参数:
  • vnode
  • wnode
get_data()[源代码]

将相邻结构转换为可读性更好的结构。

返回:嵌入 --将所有节点映射到按顺时针顺序排序的邻居列表的dict。
返回类型:dict

参见

set_data()

is_directed()[源代码]

有效的planarembedding是无向的。

所有反向边缘都包含在内,即对于每个现有的半边缘(V,W),反向的半边缘(W,V)也包含在内。

neighbors_cw_order(v)[源代码]

发电机按顺时针顺序与V相邻。

参数:vnode
产量:node
next_face_half_edge(v, w)[源代码]

返回面的左下半个边。

参数:
  • vnode
  • wnode
返回:

half-edge

返回类型:

tuple

set_data(data)[源代码]

根据给定的排序邻居列表插入边。

输入格式与get_data()的输出格式相同。

参数:datadict )--将所有节点映射到按顺时针顺序排序的邻居列表的dict。

参见

get_data()

traverse_face(v, w, mark_half_edges=None)[源代码]

返回属于半边(V,W)的面上的节点。

经过的面位于半边缘的右侧(在V低于W的方向)。

或者,可以传递一个集合,将所有遇到的半边添加到该集合中。在调用此方法之前,此集合不能包含属于面的任何半边。

参数:
  • vnode )--半边缘的起始节点。
  • wnode )--半边缘的末端节点。
  • mark_half_edges可选设置 )--将所有遇到的半边添加到的集合。
返回:

face --位于此面上的节点列表。

返回类型:

list