Create an edge object without an implicit bias towards a side in Python

Question

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?

Answer 1

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]