3
\$\begingroup\$

I wanted to represent graphs in Python, and wrote the following class. I don't care about values associated with nodes or the weights of the connections between them, simply the connections between nodes.

Is this a good enough implementation? Or is there a significantly better way?

class Graph:
    def __init__(self, nodes):
        self.array_representation = [[] for _ in range(nodes)]

    def directly_connected(self, node_1, node_2):
        # Predicate, checks if the two nodes are connected by one edge
        return node_2 in self.array_representation[node_1]

    def connect(self, node_1, node_2):
        # Draws an edge between the node at node_1 and the node at node_2
        self.array_representation[node_1].append(node_2)
        self.array_representation[node_2].append(node_1)
\$\endgroup\$
1
\$\begingroup\$

If your graph becomes big (or rather if a node has many connections), node_2 in self.array_representation[node_1] might take a long time, because in is O(n) for lists. Therefore I would use a set for the connections of a node. You don't even needed to change a lot:

class Graph:

    def __init__(self, nodes):
        self.connections = [set() for _ in range(nodes)]

    def directly_connected(self, node_1, node_2):
        """Predicate, checks if the two nodes are connected by one edge"""
        return node_2 in self.connections[node_1]

    def connect(self, node_1, node_2):
        """Draws an edge between the node at node_1 and the node at node_2"""
        self.connections[node_1].add(node_2)
        self.connections[node_2].add(node_1)

And while I was at it, I promoted your comments to proper docstrings. Now you can do help(Graph.connect) in an interactive session.

I also changed the name of the internal representation to self.connections.

\$\endgroup\$
  • \$\begingroup\$ Okay thank you, to be honest I didn't even know python had docstrings xD Using a set makes a lot of sense too \$\endgroup\$ – theonlygusti Dec 8 '16 at 23:44
1
\$\begingroup\$

The business logic of graphs is mathematical in nature. As implemented the Graph class does not directly reflect the underlying mathematics. Poor mapping between code and graph mathematics is not uncommon even for graph implementations in well regraded text books and online tutorials.

Mathematics

A graph G is defined as a set of nodes or vertices V = {v1, v2...vn} and a bag of edges E = {e1, e2, ...em}. The only relation between edges and vertices is that for each edge e between vertices u and v both u and v must be members of V.

Dependencies

Mathematically, a set of vertices V is independent of the set of edges E. Two different graphs G1 and G2 can be defined across the same set of vertices based solely on the difference between two sets of edges E1 and E2.

 G1 = V, E1
 G2 = V, E2 

Nodes are necessarily properties of Edges. Edges are not properties of nodes. Edges are [ properties | fields | objects ] of a graph. The dependencies are:

 Graph <- Edges
 Graph <- Nodes
 Edge  <- Node, Node

An Minimal Implementation

This code does not attempt to be particularly Pythonic. It attempts to reflect the underlying mathematics in an object based manner.

from collections import Counter

class Graph:
    E = Counter()
    V = set()

    def add_node(self, node):
        self.V.add(node)

    def remove_node(self, node):
        self.V.remove(node)

    def add_edge(self, node_1, node_2):
        if self.exists_node(node_1) and self.exists_node(node_2):
            edge = str(node_1) + '_' + str(node_2)
            self.E[edge]+=1

    def remove_edge(self, node_1, node_2):
        edge = str(node_1) + '_' + str(node_2)
        if self.E[edge] > 0:
            self.E[edge]-=1
        else:
            self.E[edge] = 0

    def exists_edge(self, node_1, node_2):
        edge_1 = str(node_1) + '_' + str(node_2)
        return self.E[edge_1] > 0  

    def exists_node(self, node):
        return node in self.V

The Graph class maintains the nodes as a set in order to provide set semantics. It uses collection.Counter to maintain a bag of edges as recommended by the Python documentation. The implementation of undirectional edges is left as an exercise.

\$\endgroup\$
  • 1
    \$\begingroup\$ Using a frozenset as the keys to the bag of edges instead of building the string might be an easy way to implement the unidirectional edges and be maybe faster. \$\endgroup\$ – Graipher Dec 9 '16 at 7:38
  • \$\begingroup\$ @graipher I don't disagree. I'd probably be inclined to model an undirected graph with pairs of edges because I don't know how too model a directed graph using frozenset in a straightforward way. I have a bias toward fewer data structures and would rather have two sets of functions that operate on one data structure than two data structures. But that's just opinion. \$\endgroup\$ – ben rudgers Dec 9 '16 at 13:57
1
\$\begingroup\$

Building on Ben Rudgers answer above, I would change some small things. Storing the edge as string seems odd, so I changed it to a namedtuple. Naming the internal variables to something more readable. Raising an error on adding an edge with unknown nodes, instead of ignoring it.

I also added the directly_connected() and connected() methods the OP is asking for.

from collections import namedtuple

Edge = namedtuple('Edge', ['node_1', 'node_2'])


class Graph:
    edges = set()
    nodes = set()

    def add_node(self, node):
        self.nodes.add(node)

    def remove_node(self, node):
        self.nodes.remove(node)

    def add_edge(self, node_1, node_2):
        if self.exists_node(node_1) and self.exists_node(node_2):
            self.edges.add(Edge(node_1, node_2))
        else:
            msg = 'Either {} or {} are not registered nodes!'
            msg = msg.format(node_1, node_2)
            raise KeyError(msg)

    def remove_edge(self, node_1, node_2):
        self.edges.remove(Edge(node_1, node_2))

    def exists_edge(self, node_1, node_2):
        return Edge(node_1, node_2) in self.edges

    def exists_node(self, node):
        return node in self.nodes

    def directly_connected(self, node_1, node_2):
        return self.exists_edge(node_1, node_2,)

    def connected(self, node_1, node_2):
        if self.directly_connected(node_1, node_2):
            return True

        for edge in self.edges:
            if edge.node_1 == node_1:
                return self.connected(edge.node_2, node_2)

        return False

g = Graph()
g.add_node('A')
g.add_node('B')
g.add_node('C')
g.add_edge('A', 'B')
g.add_edge('B', 'C')

print("A -> C Directly connected: ", g.directly_connected('A', 'C'))
print("A -> C Connected: ", g.connected('A', 'C'))

Returns

A -> C Directly connected:  False
A -> C Connected:  True
\$\endgroup\$
  • \$\begingroup\$ There are all kinds of ways to implement E. The important goal, for me, is to abstract over the implementation details by working at a higher level. This allows the implementation to be changed if profiling or coding standards indicate such a change is warranted. In regard to adding an edge that does not exist, I felt that crashing the program was inconsistent mathematical abstractions. It also seemed a bit extreme given that the most likely way of handling would boil down ignoring it and proceeding with input. If I were to do something about it, I'd probably write to a log. \$\endgroup\$ – ben rudgers Dec 12 '16 at 17:28
  • 1
    \$\begingroup\$ @benrudgers I'm not saying your answer is bad. I actually really like it, and was building on it for my own exploration. About unexpected events: there are a lot of design choices you can make for unexpected. Raise error, warn, log and continue, or in the case of an edge between unknown nodes: add the new nodes to the node set. What "the best solution" is depends on the use case. For user input one might want to give direct feedback (so an error might be appropriate), for processing a large database for some analysis softer feedback like a log might be more appropriate. \$\endgroup\$ – Peter Smit Dec 13 '16 at 10:17
  • \$\begingroup\$ I took your comments in the spirit you intended and was just explaining my reasoning. If the program were in Erlang, I'd be all for crashing it with an error because anything else would be kind of 'unErlangic'. I considered adding nodes when an edge is added that references a non-existent node. I didn't because it does not fit with the underlying mathematical dependency of edges upon nodes. For a particular implementation, that seems to be something that happens at a higher level of business logic than the mathematics. \$\endgroup\$ – ben rudgers Dec 13 '16 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.