Graph Condensation and MST Analysis in Java

This project reads a weighted graph from stdin, groups “hub nodes” (nodes connected by special edges), builds a condensed undirected graph of hubs using Dijkstra's algorithm, then computes a minimum spanning tree (MST) of that condensed graph using Kruskal’s algorithm.

This is practice for a Choicescript Story Map generator (inspired by Twine and StoryPrint, a theoretical interactive visualization from Disney Research)

Features

Given an input graph (example here):

• Hub detection / clustering: vertices connected by edges of weight -1 are unioned into the same hub (using Union-Find / Partition).
• Condensation: each hub becomes a single vertex in a new (smaller) undirected graph.
• Shortest connections between hubs: for each hub-vertex, a modified Dijkstra is run over positive-weight edges only, storing shortest hub-to-hub distances while avoiding parallel edges (keeps the minimum).
• MST selection: Kruskal is run on the condensed graph to choose the cheapest set of hub-to-hub segments.

Output includes:

• list of hub node names
• counts (hubs, hub-vertices, possible segments)
• total cost and the list of segments in the MST (or Impossible)

Input Format

Example here

The program expects:

1. Two integers:

   • n = number of vertices

   • m = number of edges

2. n vertex lines:

   • vertex id (integer-like token)

   • station name (rest of the line)

3. A line containing $ (consumed by scan.nextLine())

   • m edge lines:

   • v1 v2 weight

376 933
0000 Abbesses
0001 Alexandre Dumas
0002 Alma Marceau
$
59 162 53
60 299 63
60 133 45
138 137 -1
142 144 -1
142 143 -1

Notes:

• Edges with weight == -1 are treated as “hub connections” (used to cluster vertices into hub stations).
• Dijkstra only considers edges with weight > 0.

Run

java main.java.grapher.Metro < test/test1.txt

Project structure

• Graph
  Graph structure (vertices, edges, vertexMap), plus createPartition(), sortEdges(), and kruskal().
• Vertex, Edge
• Union-Find structures: Partition, Cluster, Node
• GraphCondenser
  Runs hub clustering, modified Dijkstra, and creates the condensed graph.

Requirements

• Java 8+ (Java 11+ recommended)

Compile

From the directory containing your main/java/grapher package root:

javac main/java/grapher/*.java

Attribution

This project was originally developed as part of a university DS&A assignment. The core problem specification was provided by the course instructor and based on this Online Judge problem: link

This repository contains my implementation and extensions beyond the original requirements.