提取图中的进出度

Question

我试图得到一个图中顶点的进出度的值。我已经实现了一个图形类，但我需要一个函数，给我的程度值。我试图这样做，没有networkX方法。以下是我到目前为止所做的尝试:

from collections import defaultdict
class Graph:
def __init__(self):
self._graph = defaultdict(set)
self._weight = dict()
def node_count(self):
return len(self._graph)
def neighbours(self, n):
return iter(self._graph[n])
def add_node(self, n):
self._graph[n] = set()
def remove_node(self, n):
for n1 in self.neighbours(n):
if n1 != n:
self._graph[n1].remove(n)
del self._weight[self._edge(n, n1)]
del self._graph[n]
def _edge(self, n1, n2):
return (n1, n2) if n1 <= n2 else (n2, n1)
def edge_count(self):
return len(self._weight)
def add_edge(self, n1, n2, w=0.0):
self._graph[n1].add(n2)
#self._graph[n2].add(n1)
self._weight[self._edge(n1, n2)] = w
def remove_edge(self, n1, n2):
self._graph[n1].remove(n2)
if n1 != n2:
self._graph[n2].remove(n1)
del self._weight[self._edge(n1, n2)]
def get_connections(self):
total = 0
for w in self._weight.values():
total += w
return total

我该如何写一个函数来返回这个图中一个顶点的入度和出度?

def out(self, vertex):
return ??
def _in(self, vertex):
return ??

Answer 1

你的图形目前没有方向，所以没有进出度。

调整你的功能。

def add_edge(self, n1, n2, w=0.0):
self._graph[n1].add(n2)
# self._graph[n2].add(n1)
self._weight[(n1, n2)] = w

如果你想让它无定向或进行改编，你可以使用len(neighbours(node))

在当前的结构中，你可以通过检查所有节点来获得度数，但它是O(n)