Exercise

Open In Colab

Exercise#

Exercise 01#

  1. Create a network of landmasses and bridges of Binghamton, NY.

  2. Find an Euler path that crosses all the bridges of Binghamton, NY exactly once.

Binghamton Map

# If you are using colab, uncomment the following line
# !sudo apt install libcairo2-dev pkg-config python3-dev
# !pip install pycairo cairocffi
# !pip install igraph

Define the edges

# This is a placeholder for your code for the exercise
edges = ...

Define the adjacnecy matrix (without for loops!)

A = ...

Visualize the graph

import igraph
import matplotlib.pyplot as plt
import numpy as np

def visualize_graph(A, **params):
  A = np.array(A)
  src, trg = np.where(A)
  g = igraph.Graph(directed=False)
  g.add_vertices(A.shape[0])
  for s, t in zip(src, trg):
    for _ in range(A[s, t]):
      g.add_edge(s, t)
  return igraph.plot(g, **params)

visualize_graph(A)

---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
Cell In[4], line 15
     12       g.add_edge(s, t)
     13   return igraph.plot(g, **params)
---> 15 visualize_graph(A)

Cell In[4], line 7, in visualize_graph(A, **params)
      5 def visualize_graph(A, **params):
      6   A = np.array(A)
----> 7   src, trg = np.where(A)
      8   g = igraph.Graph(directed=False)
      9   g.add_vertices(A.shape[0])

ValueError: not enough values to unpack (expected 2, got 1)

Check if the graph has an Euler path

Exercise 02#

Let’s create a network from pre-existing data and check if it has an Euler path.

  1. Select a network of your choice from Netzschleuder. For convenience, choose a network of nodes less than 5000.

  2. Download the csv version of the data by clicking something like “3KiB” under csv column.

  3. Unzip the file and find “edges.csv”, open it with a text editor to familiarize yourself with the format.

  4. Load the data using pandas.

  5. Get the source and target nodes from the data to create an edge list.

  6. Construct the adjacency matrix from the edge list.

  7. Draw the graph using igraph.

  8. Check if the graph has an Euler path.

Load the data by

import pandas as pd
df = pd.read_csv('edges.csv') # load the data
display(df)

Then, get the srce and target nodes to compose an edge list

src = ...
trg = ...
edges = ...

Create the adjacency matrix from the edge list

Get the degree of each node

deg = ...

Visualize the graph

visualize_graph(A)

Check if the graph has an Euler path

Contents