Table of contents
- Session 1 - Introduction
- Session 2 - ADT - Graph Traversal - Complexity
- Session 3 - Graph Traversal - Complexity
- Session 4 - Minimum Spanning Tree
- Session 5 - Binary Trees - Huffman - Binary Search Trees
- Session 6 - Maximum flows - Ford-Fulkerson -Edmonds and Karp
- Session 7 - Graph Coloring
- Session 8 - Introduction to NP-complete problems
- Session 9 - Complex Networks
Documents for students
- Slides: Introduction to graphs
- Code: naïve Graph class using edge adjacency lists
basic_graph_adjlist.py - Code: naïve Graph class using adjacency matrix
basic_graph_matrix.py - Notebook: plotting a graph with matplotlib
- Notebook: Introduction to NetworkX
- Notebook: Plotting Karate Network using NetworkX
- Gephi: The Open Graph Viz Platform
- Video tutorial: Introduction to Network Analysis and Visualization
- Slides: Abstract Data Types: Stack, Queues, and Dictionaries
- Slides: Graph Traversal Algorithms, DFS
- Notebook: A simple python implementation of DFS using Recursion 02-a-DFS-recursive.ipynb
- Code: copy lib directory and its content lib
- Data: example graph:
soc-karate.mtx - Slides: DFS Algorithm with a stack
Implement BFS using a queue in Python
Code the BFS (breadth-first-search) algorithm in Python using
- The Graph class provided by NetworkX
- The Queue class seen in class
Upload your work as a unique file, either a .py or a notebook .ipynb
- Slides: Algorithmic Complexity
- Slides: Breadth-First-Search (BFS)
- Slides: Dijkstra's Algorithm
- Slides: Prim's and Kruskal algorithms
- Slides: Minimum Spanning Tree: examples
Implement a Minimum Spanning Tree Algorithm
Implement one of
- Prim's algorithm
- Boruvka's algorithm
- Kruskal's algorithm
and apply it to a small graph of your choice.
You code will:
- build the graph
- compute a minimum spanning tree
- display the result: the edges belonging to the spanning tree in red, the other in grey
- Slides: Maximum Flows
- Slides: Graph Coloring
- Slides: Intro. NP-complete
- Slides: Complex Networks