在Python中创建一个不带隐式偏向一侧的边缘对象

huangapple go评论62阅读模式
英文:

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]

huangapple
  • 本文由 发表于 2023年2月26日 20:51:33
  • 转载请务必保留本文链接:https://go.coder-hub.com/75572102.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定