Data Structures and Algorithms

Week 07

Prof. Dr.-Ing. Olav Hinz

2025-05-21

Agenda | Learning Goals

Lecture

• 10:00 - 10:15: Introducing graphs (Theory)
• 10:15 - 10:45: Implementing graphs ins python
• 11:00 - 11:05: Introducing the project CAMPLA (BYOD exams)
• 11:05 - 11:30: Introducing the board game 1835 (The hackathon)

Practice

• 11:45 - 12:30: Access to the moodle exam course using CAMPLA
• 12:30 - 14:00: Hackathon: Game Development

Graphs

Slide Set Introduction to graphs Slide Set Drawing graphs in python

Introduction to Graphs

• Content:
  • Definition of a graph: Nodes (vertices) and edges.
  • Types of graphs: Directed vs. Undirected, Weighted vs. Unweighted.
  • Brief mention of applications such as social networks, routing algorithms, and recommendation systems.

Graph Representation in Python

• Content:
  • Common ways to represent graphs: adjacency matrix, adjacency list.
  • Introduction to libraries like NetworkX for graph handling.

Adjacency List Representation

• Content:
  • Explanation of adjacency lists.
  • Example Code: Using a dictionary of lists

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

Adjacency Matrix Representation

• Content:
  • Explanation of adjacency matrices.
  • Example Code: Using a 2D list

    import numpy as np

    nodes = ['A', 'B', 'C', 'D']
    adj_matrix = np.array([
        [0, 1, 1, 0],
        [1, 0, 0, 1],
        [1, 0, 0, 1],
        [0, 1, 1, 0]
    ])
    print(adj_matrix)

Creating Graphs with NetworkX

• Content:
  • Introduction to NetworkX library.
  • Basic graph creation and visualization.
  • Example Code:

    import networkx as nx
    import matplotlib.pyplot as plt

    G = nx.Graph()
    G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')])
    
    nx.draw(G, with_labels=True)
    plt.show()

Graph Traversal Techniques

• Content:
  • Explanation of traversal techniques: Breadth-First Search (BFS) and Depth-First Search (DFS).
  • Example Code (BFS):

    from collections import deque

    def bfs(graph, start):
        visited = set()
        queue = deque([start])
        
        while queue:
            vertex = queue.popleft()
            if vertex not in visited:
                print(vertex)
                visited.add(vertex)
                queue.extend(set(graph[vertex]) - visited)

    bfs(graph, 'A')

Application of Graphs: Shortest Path

• Content:
  • Use case: Finding the shortest path using Dijkstra’s algorithm.
  • Example Code:

    import networkx as nx

    G = nx.Graph()
    G.add_weighted_edges_from([('A', 'B', 1), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 3)])
    
    path = nx.shortest_path(G, source='A', target='D', weight='weight')
    print("Shortest path from A to D:", path)

Advanced Applications

• Content:
  • Discuss advanced graph applications:
    • PageRank algorithm.
    • Graph-based machine learning.
    • Social network analysis.
  • Point to resources for further learning.

Example: Railroad Board Games (18xx)

Introducing the Board Games 18xx

• Strategy and Economic Simulation in the World of Railways
• Developed in the late 1980s
• Long term game: 8 - 10 hours per games
• Strategies for
  • Building a network
  • Mechanic of stock markets
  • Trading assets (engines, shares)
  • Decision making (“being a director”)
• Original: 1830, many adaptions 1835, 1844

Overview of 1830: Railways & Robber Barons

• Content:
  • Introduction: Released in 1986, designed by Francis Tresham, part of the 18XX series.
  • Objective: Simulate the development of railroads, focusing on stock market manipulation, route building, and company management.
  • Key Features:
    • Stock Market System: Players buy and sell shares to gain control of railway corporations.
    • Track Building: Expand railway networks strategically across the map.
    • Economic Focus: Emphasizes financial strategy over chance.

Overview of 1835

• Content:
  • Introduction: A subsequent entry in the 18XX series, designed by Michael Meier-Bachl, featuring the German rail system.
  • Objective: Similar economic and strategic focus with unique regional elements.
  • Key Features:
    • Historical Context: Set in 19th-century Germany, offering historical railway companies and regional intricacies.
    • Debt Management and Loans: Adds complexity through mechanisms of loans and debt management, reflecting economic pressures of the era.
    • Advanced Game Mechanics: Variants and expansions introduce new dynamics for seasoned players.

The hackathon

Creating a digital version of a board game

• “easy”: Implementing the rules of the game developing classes and methods
• “nice to look at”: Drawing the railroad network using Matplotlib and / or Qt
• “challenging”: Modelling the railroad network using graphs (NetworkX)