Skip to content

README1.md

Latest commit

 

History

History
172 lines (145 loc) · 4.33 KB

README1.md

File metadata and controls

172 lines (145 loc) · 4.33 KB

Combinatorial Algorithms (Spring 2025)

Assignment 1

Authors (in arbitrary order):

  • Zirui Fang
  • Hao Guo

Date: April 2025
Course: Combinatorial Algorithms
Instructor: Prof. Pablo Ezequiel Terlisky

📘 Overview

This repository contains our solutions for Assignment 1 of the Combinatorial Algorithms (104291) course, Spring 2025.
The assignment consists of two main programming exercises implemented in Python:

  1. Exercise 1: Detecting Induced Paw Subgraphs in an undirected graph.
  2. Exercise 2: Computing the Trotter–Johnson rank of a valid topological permutation under given precedence constraints.

All source files are structured, documented, and can be executed in a Unix-based environment using Python 3.

🧩 Exercise 1 — Induced Paw Detection

Description

A paw graph is a 4-vertex graph consisting of a triangle plus one additional vertex connected to exactly one vertex of the triangle.

This program reads an undirected graph from standard input and outputs all sets of 4 vertices that form an induced paw subgraph, listed in lexicographic order.
If no paw exists, it reports accordingly.

Input Format

n m v1 w1 v2 w2 ... vm wm

  • n: number of vertices
  • m: number of edges
  • vi wi: edges between vertices (0-indexed)

Output

  • A list of vertex sets (each set as a list) forming induced paws, in lexicographic order.
  • If none found, prints: It found no paws in the graph.

Example 1 (from assignment)

Input 7 10 1 2 1 3 2 3 3 4 2 4 0 1 0 4 6 4 5 3 2 6 Output [0,1,2,3] [0,2,3,4] [0,2,4,6] [1,2,3,5] [1,2,3,6] [1,2,4,6] [2,3,4,5]

Example 2 (no paws)

Input 6 12 0 1 0 3 1 3 2 1 2 4 4 1 5 3 5 4 3 4 0 2 0 5 2 5 Output It found no paws in the graph.

How It Works

  1. Builds an adjacency list of the graph.
  2. Iterates over all 4-combinations of vertices (without using itertools).
  3. For each combination:
    • Counts total edges between these 4 vertices.
    • Checks if they form a triangle + one pendant vertex.
  4. Prints results in lexicographic order (generated by nested loops, not sort()).

🔁 Exercise 2 — Topological Sorting & Trotter–Johnson Rank

Description

Given a set of precedence constraints ( a \prec b ) between numbers (1 \dots n),
the program finds a permutation satisfying all constraints (if possible)
and computes its Trotter–Johnson rank.

If no permutation satisfies the constraints (graph contains a cycle),
the program prints a message indicating impossibility.

Input Format

n m a1 b1 a2 b2 ... am bm

  • n: number of elements
  • m: number of constraints
  • ai bi: means "a must come before b"

Output

  • The valid topological order (if exists).
  • Its Trotter–Johnson rank.
  • Otherwise: Impossible to satisfy the conditions

Example 1 (from assignment)

Input 10 8 2 3 4 5 1 2 1 4 2 4 7 8 4 7 3 6 Output (example) Topological Sort: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] Trotter–Johnson Rank: 244529

Example 2 (impossible case)

Input 5 5 1 2 2 3 5 3 3 4 4 1 Output Impossible to satisfy the conditions

How It Works

  1. Builds a directed graph from the constraints using adjacency lists.
  2. Performs Depth-First Search (DFS) topological sorting with cycle detection.
  3. If acyclic:
    • Computes Trotter–Johnson rank recursively based on position of the largest element.
  4. Outputs the result.

🧠 Algorithmic Highlights

Concept Algorithm Used Complexity
Induced Paw Detection Brute-force enumeration of 4-subsets + structural checks (O(n^4))
Topological Sort DFS with cycle detection (O(n+m))
Rank Calculation Recursive Trotter–Johnson algorithm (O(n^2))

Both programs are efficient enough to handle all test cases (including 10-vertex graphs) within the required time limit (< 1 minute).

⚙️ Usage Instructions

1. Run Exercise

python3 induced_paw_detection.py
You will be prompted: Enter True, if you want to see the examples from assignment and ours.
Enter False, if you want to test your own graph.
python3 constrained_permutation_ranking.py
Similar interactive input format: Enter True, if you want to see the examples from the assignment and ours.
Enter False, if you want to test your own cases.