How to easily create Graphs in Python
Tags: programming, datastructures
Published: 2023-06-29 14:36:48

Graphs are fundamental data structures used to represent relationships between objects. They consist of a collection of vertices (also known as nodes) and edges (also known as arcs) that connect these vertices. Graphs are widely used in various fields, including computer science, mathematics, and social network analysis, to model and analyze complex relationships and networks.

A graph can be defined as a tuple G = (V, E), where V represents the set of vertices and E represents the set of edges. The set of vertices, V, can be finite or infinite. Each vertex in V is uniquely identified and can be associated with additional information known as vertex properties. 

The set of edges, E, represents the connections between vertices. Each edge in E is an unordered pair of vertices (u, v), where u and v belong to V. Edges can be directed (having a specific direction from one vertex to another) or undirected (without any specific direction). In the case of directed edges, the pair (u, v) represents an edge originating from vertex u and ending at vertex v.

For example, let's consider a graph G = (V, E) with the following sets:

V = {1, 2, 3, 4, 5}

E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5)}

In this example, V represents the set of vertices, and E represents the set of edges.

The set V contains five vertices: {1, 2, 3, 4, 5}.

The set E contains six edges, where each edge is represented by an unordered pair of vertices. The edges are:
{(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5)}.

This graph can be visually represented as:

```
      1
     / \
    2---3
   / \ / \
  4---5
```

Here is an implementation of a basic graph in Python:

```
from collections import defaultdict

class Graph:
    """Basic implementation of a graph."""

    def __init__(self, edges, directed=False):
        """Initialize the basic structures of the graph."""
        self.adj = defaultdict(set) # defaultdict: key not found won't raise an error, it will create a new one
        self.directed = directed
        self.add_edges(edges)

    def get_vertices(self):
        """Return the list of vertices in the graph."""
        return list(self.adj.keys())

    def get_edges(self):
        """Return the list of edges in the graph."""
        return [(k, v) for k in self.adj.keys() for v in self.adj[k]]

    def add_edges(self, edges):
        """Add edges to the graph."""
        for u, v in edges:
            self.add_arc(u, v)

    def add_arc(self, u, v):
        """Add a connection (arc) between nodes 'u' and 'v'."""
        self.adj[u].add(v)
        # If the graph is undirected, we need to add arcs in both directions.
        if not self.directed:
            self.adj[v].add(u)

    def has_edge(self, u, v):
        """Does an edge exist between vertices 'u' and 'v'?"""
        return u in self.adj and v in self.adj[u]

    def __len__(self):
        return len(self.adj)

    def __str__(self):
        return '{}({})'.format(self.__class__.__name__, dict(self.adj))

    def __getitem__(self, v):
        return self.adj[v]
```

Here's an example to create the graph described earlier:
```
edges = [ (1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5) ]

g = Graph(edges, directed=False)
```

This implementation provides basic functionalities for a graph, including initializing the graph with a set of edges, adding edges and arcs, checking if an edge exists between two vertices, and retrieving the vertices and edges of the graph. It can handle both directed and undirected graphs.

Feel free to use this implementation as a starting point for working with graphs in your projects or applications. Remember to create an instance of the Graph class and pass the appropriate edges to initialize the graph.