英文:
Create an edge object without an implicit bias towards a side in Python
问题
Python初学者。
我试图在Python中创建一个包含节点和边对象的网络对象。边由两个节点构成。网络由节点和边的列表构成。
我的问题出在,有时网络无法意识到边与特定节点相连接,这是由于边构造中节点的隐式排序,因此出现了一些节点看起来“孤立”的情况,但实际上不应该是这样的。
我有3个类:
class Node:
def __init__(self, key):
self.key = key
class Edge:
def __init__(self, node1, node2):
self.p1 = node1
self.p2 = node2
class Network:
def __init__(self, nodes=[], edges=[]):
self.nodes = nodes
self.edges = edges
def maximal_subnetwork(self, node):
nodes = {node}
traced = set()
while nodes:
node = nodes.pop()
traced.add(node)
for i in self.adjacent_nodes(node): # 返回相邻节点
if i not in traced:
nodes.add(i)
traced = list(traced)
return Network(nodes=traced, edges=self.return_edges(*traced)) # 返回网络中边的子集
不可避免地,由于我构造类的方式,后者“找到”的最大子网络完全取决于边的起始位置。
我可以尝试更改类,但我希望保持足够通用,以便可以添加诸如有向边和多重边之类的属性。
如何使边对节点不感兴趣,同时不影响添加方向或重复的能力?
英文:
Python noob here.
I am trying to create a network object in Python that contains both node and edge objects. Edges are constructed from two nodes. Networks are constructed from lists of nodes and edges.
My problem arises where the network sometimes doesn't realise that an edge is connected to a specific node due to the implicit ordering of the nodes within the edge construction, thus giving the appearance that some nodes are 'isolated' when they shouldn't be.
I have 3 classes:
class Node:
def __init__(self,key):
self.key = key
class Edge:
def __init__(self, node1, node2):
self.p1 = node1
self.p2 = node2
class Network:
def __init__(self, nodes = [], edges = []):
self.nodes = nodes
self.edges = edges
def maximal_subnetwork(self, node):
nodes = {node}
traced = set()
while nodes:
node = nodes.pop()
traced.add(node)
for i in self.adjacent_nodes(node): # returns adhacent nodes
if i not in traced:
nodes.add(i)
traced = list(traced)
return Network(nodes = traced , edges = self.return_edges(*traced)) # returns the subset of edges in the network
Inevitably, due to how I constructed the classes, the latter 'finds' maximal subnetworks that depend entirely on where the edge originates.
I could try changing the classes, however, I want to keep it general enough that I can add properties such as directed edges and multiedges.
How could I make it such that an edge is indifferent to the nodes, without compromising the ability to add a direction to it or a duplicate?
答案1
得分: 1
不要将[]
用作参数的默认值
在实际回答您的问题之前,我想指出您的Network.__init__
方法存在一个重要问题。
一般建议不要使用可变的默认参数(除非您真的知道在做什么)。有关这个问题,可以参考"Least Astonishment" and the Mutable Default Argument。
以下是问题的示例代码:
class Network:
def __init__(self, nodes = [], edges = []):
self.nodes = nodes
self edges = edges
g = Network()
h = Network()
g.nodes.append('x')
print('Nodes in g: ', g.nodes)
print('Nodes in h: ', h.nodes)
# Nodes in g: ['x']
# Nodes in h: ['x']
相反,您可以这样做:
class Network:
def __init__(self, nodes=None, edges=None):
self.nodes = (nodes if nodes is not None else [])
self.edges = (edges if edges is not None else [])
g = Network()
h = Network()
g.nodes.append('x')
print('Nodes in g: ', g.nodes)
print('Nodes in h: ', h.nodes)
# Nodes in g: ['x']
# Nodes in h: []
一切不可避免,一切都在Network.adjacent_nodes
您说"不可避免",但这似乎完全取决于Network.adjacent_nodes
方法,而您尚未展示该方法。根据该方法的不同,问题可能根本不存在。因此,这里没有不可避免的事情。
可能的数据结构:邻接表
您选择仅使用节点列表g.nodes
和边列表g.edges
来表示网络g
。
这种表示方法有点过于简化,这意味着许多操作将会低效。例如,如何找到给定节点的所有邻居?如果您只有边的列表,那么需要遍历整个网络的所有边以找到一个节点的邻居,如果网络很大,这将非常慢:
class Network:
def adjacent_nodes(self, node): # 如果网络中有很多边,这将非常慢
neighbours = []
for (u,v) in self.edges:
if u == node:
neighbours.append(v)
elif v == node:
neighbours.append(u)
return neighbours
相反,您可以使用邻接表来存储网络。对于每个节点,一次性计算其邻居列表,并将其存储为Network
对象的一部分:
class Network:
def __init__(self, nodes=None, edges=None):
self.nodes = (nodes if nodes is not None else [])
self.edges = (edges if edges is not None else [])
self.adjacency_list = { u: [] for u in self.nodes }
for (u, v) in self.edges:
self.adjacency_list[u].append(v)
self.adjacency_list[v].append(u)
def adjacent_nodes(self, node):
# 如果节点不在self.adjacency_list中,引发某个异常
return self.adjacency_list[node]
英文:
Don't use []
as a default value for an argument
Before actually answering your question, I'd like to point out that there is a big issue with your Network.__init__
method.
In general it is recommended to never use mutable defaults arguments (unless you really know what you're doing). See "Least Astonishment" and the Mutable Default Argument for more on the issue.
Showcasing the issue:
class Network:
def __init__(self, nodes = [], edges = []):
self.nodes = nodes
self.edges = edges
g = Network()
h = Network()
g.nodes.append('x')
print('Nodes in g: ', g.nodes)
print('Nodes in h: ', h.nodes)
# Nodes in g: ['x']
# Nodes in h: ['x']
Instead you can do:
class Network:
def __init__(self, nodes=None, edges=None):
self.nodes = (nodes if nodes is not None else [])
self.edges = (edges if edges is not None else [])
g = Network()
h = Network()
g.nodes.append('x')
print('Nodes in g: ', g.nodes)
print('Nodes in h: ', h.nodes)
# Nodes in g: ['x']
# Nodes in h: []
Nothing inevitable, all is in Network.adjacent_nodes
> Inevitably, due to how I constructed the classes, the latter 'finds' maximal subnetworks that depend entirely on where the edge originates.
You say "inevitably", but this appears to depend entirely on method Network.adjacent_nodes
, which you have not shown. Depending on that method, there might not be an issue at all. So, nothing inevitable here.
Possible data structure: adjacency lists
You have chosen to represent a network g
using only a list of nodes g.nodes
and a list of edges g.edges
.
This representation is a bit minimalistic, and means that many operations will be inefficient. For instance, how do you find all the neighbours to a given node? If all you have is the list of edges, you need to iterate over all the edges of the network to find the neighbours of one node. This is going to be very slow if the network is big:
class Network:
def adjacent_nodes(self, node): # very slow if many edges in network
neighbours = []
for (u,v) in self.edges:
if u == node:
neighbours.append(v)
elif v == node:
neighbours.append(u)
return neighbours
Instead, you could store the network using adjacency lists. For every node, compute once and for all the list of its neighbours and store that as part of your Network
object.
class Network
def __init__(self, nodes=None, edges=None)
self.nodes = (nodes if nodes is not None else [])
self.edges = (edges if edges is not None else [])
self.adjacency_list = { u: [] for u in self.nodes }
for (u, v) in self.edges:
self.adjacency_list[u].append(v)
self.adjacency_list[v].append(u)
def adjacent_nodes(self, node):
# if node not in self.adjacency_list: raise some exception
return self.adjacency_list[node]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论