An Intro to Python 3/

...

/

Puzzles 45 to 47

Puzzles 45 to 47

Learn about graph traversal, lexicographical sorting, and chaining of set operations in Python.

We'll cover the following...

Puzzle 45

What is the output of the following code?

Note: Enter the output you guessed. Then, press the Run button, and your new Elo will be calculated. Don’t forget to save your Elo rating.

Python 3.5
############################
## id 274
## Puzzle Elo 1729
## Correctly solved 44 %
#############################
def has_path(graph, v_start, v_end, path_len=0):
  '''Graph has path from v_start to v_end'''
    
  # Traverse each vertex only once
  if path_len >= len(graph):
    return False
  # Direct path from v_start to v_end?
  if graph[v_start][v_end]:
    return True 
    
  # Indirect path via neighbor v_nbor?
  for v_nbor, edge in enumerate(graph[v_start]):
    if edge: # between v_start and v_nbor
      if has_path(graph, v_nbor, v_end,
        path_len + 1): 
          return True
  return False
# The graph represented as adjancy matrix
G = [[1, 1, 0, 0, 0],
      [0, 1, 0, 0, 0],
      [0, 0, 1, 0, 0],
      [0, 1, 1, 1, 0],
      [1, 0, 0, 1, 1]]
print(has_path(graph=G, v_start=3, v_end=0))
Did you find this helpful?

Graph traversal

What is a graph?

You already know data structures like lists, sets, and dictionaries. These data structures are denoted as complex data structures. But this is not because they’re difficult to understand but because they build upon other data structures.

A graph is just another complex data structure for relational data.

Relational data consists of edges and vertices. Each vertex stands in one or more relations with other vertices. An example of relational data is the Facebook social graph. Facebook represents users as vertices and friendship relations as edges. Two users are connected via an edge in the graph if they are (Facebook) friends.

Social graph

How to maintain a graph data structure in the code

The puzzle uses an adjacency matrix as graph data structure G. Each row i in the matrix stores the out-neighbors of vertex i. And each column j stores the in-neighbors of vertex j. Thus, there is an edge from vertex i to vertex j: if G[i][j]==1.

How to determine whether there is a path between two vertices

Function ...