Python - Data Structures - Graphs

Graphs Data Structures in Python

A graph consists of a set of edges and nodes that can or cannot be linked to one another. Networks such as social networks and the Internet are represented as graphs.

Graphs are a versatile and widely used data structure in computer science, representing entities (nodes or vertices) and their relationships (edges). This chapter provides a comprehensive introduction to graphs in Python, including their structure, representations, and common operations.

What is a Graph?

A graph G is defined as a pair G = (V, E), where:

• V: A set of vertices (nodes).
• E: A set of edges, which are pairs of vertices that represent connections between them.

Types of Graphs

Directed vs. Undirected:

• Directed: Edges have a direction, e.g., (A→B).
• Undirected: Edges are bidirectional, e.g., (A−B).

Weighted vs. Unweighted:

• Weighted: Edges have associated weights, e.g., (A→B,weight=5).
• Unweighted: All edges have equal weight.

Cyclic vs. Acyclic:

• Cyclic: Contains one or more cycles.
• Acyclic: Does not contain cycles.

Graph Representation in Python

Adjacency List

An adjacency list represents a graph as a dictionary where each key is a vertex, and the value is a list of its neighbors.

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

This representation is efficient for sparse graphs, where the number of edges is much smaller than V².

Adjacency Matrix

An adjacency matrix is a 2D array where the element at position (i,j) indicates whether an edge exists between the vertex i and j.

# Adjacency Matrix for the graph above
# Vertices: A, B, C, D, E, F
matrix = [
    [0, 1, 1, 0, 0, 0],  # A
    [1, 0, 0, 1, 1, 0],  # B
    [1, 0, 0, 0, 0, 1],  # C
    [0, 1, 0, 0, 0, 0],  # D
    [0, 1, 0, 0, 0, 1],  # E
    [0, 0, 1, 0, 1, 0]   # F
]

This is efficient for dense graphs, where the number of edges approaches V².

Edge List

An edge list is a simple list of all edges, represented as pairs or tuples of vertices.

edges = [
    ('A', 'B'), ('A', 'C'), ('B', 'D'),
    ('B', 'E'), ('C', 'F'), ('E', 'F')
]

Edge lists are space-efficient and easy to construct for dynamic graphs.

Implementing Graphs in Python

Using a Dictionary

The most common implementation uses a dictionary for the adjacency list.

class Graph:
    def __init__(self):
        self.graph = {}

    def add_vertex(self, vertex):
        if vertex not in self.graph:
            self.graph[vertex] = []

    def add_edge(self, vertex1, vertex2):
        if vertex1 in self.graph and vertex2 in self.graph:
            self.graph[vertex1].append(vertex2)
            self.graph[vertex2].append(vertex1)  # Undirected graph

    def display(self):
        for vertex, edges in self.graph.items():
            print(f"{vertex} -> {', '.join(edges)}")

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

Display Graph Vertices

To display the graph vertices we simply find the keys of the graph dictionary. We use the keys() method.

class graph:
   def __init__(self,gdict=None):
      if gdict is None:
         gdict = []
      self.gdict = gdict
# Get the keys of the dictionary
   def getVertices(self):
      return list(self.gdict.keys())
# Create the dictionary with graph elements
graph_elements = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
g = graph(graph_elements)
print(g.getVertices())

Display Graph Edges

Finding the graph edges is a little trickier than the vertices as we have to find each of the pairs of vertices which have an edge in between them.

class graph:
   def __init__(self,gdict=None):
      if gdict is None:
         gdict = {}
      self.gdict = gdict

   def edges(self):
      return self.findedges()
# Find the distinct list of edges
   def findedges(self):
      edgename = []
      for vrtx in self.gdict:
         for nxtvrtx in self.gdict[vrtx]:
            if {nxtvrtx, vrtx} not in edgename:
               edgename.append({vrtx, nxtvrtx})
      return edgename
# Create the dictionary with graph elements
graph_elements = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
g = graph(graph_elements)
print(g.edges())

Use Cases of Graph

There are the following use cases of the Graph:

• Social Networks: Graphs, in which nodes stand in for people and edges for connections or interactions between them, are used to depict and examine social systems.
• Maps and navigation: Graphs are used by GPS and routing algorithms to determine the shortest path between two sites by representing networks of roads or pathways.
• Resource Allocation Networks: Graphs are used to describe resource flow in situations involving networks, with an emphasis on aspects such as maximum throughput.
• Connected Systems: Graphs depict intricately interconnected systems that facilitate study and optimization, ranging from the web's network of pages linked together by hyperlinks to software programs' dependencies.