Python 实现简单的超图

本文主要是介绍Python 实现简单的超图，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

1. 超图

在数学中，超图（Hypergraph）是一种广义上的图，是有限集合中最一般的离散结构，在信息科学、生命科学等领域有着广泛的应用。
图 由 边（edge） 和 顶点（vertex 或 node） 组成。
超图 由 超边（hyperedge） 和 顶点（vertex） 组成。

类型	元素
图	顶点 + 边
超图	顶点 + 超边

普通图，一条边只能连接两个顶点，而超图的一条边可以连接任意数量的顶点。
记超图为 $G$，顶点集合为 $\mathcal{V}$，超边集合为 $\mathcal{E}$，则有
$$G=(\mathcal{V},\mathcal{E})$$
如果是加权超图，则：
$$G=(\mathcal{V},\mathcal{E},W)$$
其中 $W$ 表示权重。

对于顶点集合 $\mathcal{V}$ 中的任意顶点 $v$，可以表示为 $v\in \mathcal{V}$；
对于超边集合 $\mathcal{E}$ 中的任意超边 $e$，可以表示为 $e\in \mathcal{E}$，且 $e\subset V$。

2. 代码

首先定义顶点类：

class Vertex:def __init__(self, name: str = None, weight: float = None):self.name = nameself.weight = weight

接着定义超边类：

from typing import List
import Vertexclass Edge:def __init__(self, name: str = None, weight: float = None, vertices: List[Vertex] = None):self.name = nameself.weight = weightself.vertices = vertices

最后由定义可得超图类：

from typing import List
import numpy as npimport Edge
import Vertexclass Hypergraph(object):def __init__(self, vertices: List[Vertex] = None, edges: List[Edge] = None):self.vertices = verticesself.edges = edgesif vertices is None or edges is None:self.num_vertices = 0self.num_edges = 0self.incident_matrix = Noneself.vertices_degree = Noneself.edges_degree = Noneself.vertex_degree_diagonal_matrix = Noneself.edge_degree_diagonal_matrix = Noneelse:self.num_vertices = len(vertices)self.num_edges = len(edges)self.incident_matrix = self.calculate_incident_matrix()self.vertices_degree = self.calculate_vertex_degree()self.edges_degree = self.calculate_edge_degree()self.vertex_degree_diagonal_matrix = self.calculate_diagonal_matrix_of_vertex_degree()self.edge_degree_diagonal_matrix = self.calculate_diagonal_matrix_of_edge_degree()def init_hypergraph_from_files(self, dataset_dir: str):self.vertices, self.edges = hypergraph_construction(dataset_dir)self.num_vertices = len(self.vertices)self.num_edges = len(self.edges)self.incident_matrix = self.calculate_incident_matrix()self.vertices_degree = self.calculate_vertex_degree()self.edges_degree = self.calculate_edge_degree()self.vertex_degree_diagonal_matrix = self.calculate_diagonal_matrix_of_vertex_degree()self.edge_degree_diagonal_matrix = self.calculate_diagonal_matrix_of_edge_degree()def calculate_incident_matrix(self):"""Calculate the incident matrix of the hypergraph.:return: The incident matrix of the hypergraph."""incident_matrix = np.zeros(shape=(self.num_vertices, self.num_edges), dtype=int)for i in range(self.num_vertices):vertex = self.vertices[i]for j in range(self.num_edges):edge = self.edges[j]if vertex in edge.vertices:incident_matrix[i, j] = 1return incident_matrixdef calculate_vertex_degree(self):"""Calculate the degree of vertices in the hypergraph.:return: The degree of vertices in the hypergraph."""edge_weights = np.zeros(shape=(self.num_edges,), dtype=np.float64)for i in range(self.num_edges):edge = self.edges[i]edge_weights[i] = edge.weightedge_weights = edge_weights.reshape(-1, 1)vertex_degree_array = np.dot(self.incident_matrix, edge_weights)return vertex_degree_array.reshape(vertex_degree_array.size, )def calculate_edge_degree(self):"""Calculate the degree of edges in the hypergraph.:return: The degree of edges in the hypergraph."""edges_degree = self.incident_matrix.sum(axis=0)return edges_degreedef calculate_diagonal_matrix_of_vertex_degree(self):"""Create a diagonal matrix with the degrees of vertex as the diagonal elements.:return: The diagonal matrix."""return np.diag(self.vertices_degree)def calculate_diagonal_matrix_of_edge_degree(self):"""Create a diagonal matrix with the degrees of edge as the diagonal elements.:return: The diagonal matrix."""return np.diag(self.edges_degree)

3. 参考

1. 集智百科

这篇关于Python 实现简单的超图的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---