package Ġworld . greg s . game . playground . spatial . graph Ċ Ċ import Ġorg . j gr ap ht . alg . connectivity . K os ar aj u Strong Connectivity Inspector Ċ import Ġorg . j gr ap ht . alg . short est path . Di jk stra Short est Path Ċ import Ġorg . j gr ap ht . graph . Default Direct ed Graph Ċ import Ġorg . j gr ap ht . graph . Default Edge Ċ Ċ class ĠJ Graph T Ġ{ ĊĊĠĠĠ Ġcompanion Ġobject Ġ{ ĊĊĠĠĠĠĠĠĠ Ġ@ Jvm Static ĊĠĠĠĠĠĠĠ Ġfun Ġmain ( args : ĠArray < String >) Ġ{ ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġconstructs Ġa Ġdirected Ġgraph Ġwith Ġthe Ġspecified Ġvertices Ġand Ġedges ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdirected Graph Ġ= ĠDefault Direct ed Graph < String , ĠDefault Edge >( Default Edge :: class . java ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" a ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" b ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" c ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" d ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" e ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" f ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" g ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" h ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Vertex (" i ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" a ", Ġ" b ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" b ", Ġ" d ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" d ", Ġ" c ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" c ", Ġ" a ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" e ", Ġ" d ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" e ", Ġ" f ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" f ", Ġ" g ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" g ", Ġ" e ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" h ", Ġ" e ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġdirected Graph . add Edge (" i ", Ġ" h ") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġcomputes Ġall Ġthe Ġstrongly Ġconnected Ġcomponents Ġof Ġthe Ġdirected Ġgraph ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġsc Alg Ġ= ĠK os ar aj u Strong Connectivity Inspector ( directed Graph ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġstrongly Connected Sub graphs Ġ= Ġsc Alg . strong ly Connected Components ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġprints Ġthe Ġstrongly Ġconnected Ġcomponents ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" Strong ly Ġconnected Ġcomponents :") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġfor Ġ( i Ġin Ġstrongly Connected Sub graphs . indices ) Ġ{ ĊĠĠĠĠĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( strong ly Connected Sub graphs [ i ]) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ} ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln () ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠPrints Ġthe Ġshortest Ġpath Ġfrom Ġvertex Ġi Ġto Ġvertex Ġc . ĠThis Ġcertainly ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġexists Ġfor Ġour Ġparticular Ġdirected Ġgraph . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" Short est Ġpath Ġfrom Ġi Ġto Ġc :") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġdi jk stra Alg Ġ= ĠD ijk stra Short est Path ( directed Graph ) ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġi Paths Ġ= Ġdi jk stra Alg . get Paths (" i ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( i Paths . getPath (" c "). toString () Ġ+ Ġ"\ n ") ĊĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠPrints Ġthe Ġshortest Ġpath Ġfrom Ġvertex Ġc Ġto Ġvertex Ġi . ĠThis Ġpath Ġdoes ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// ĠNOT Ġexist Ġfor Ġour Ġparticular Ġdirected Ġgraph . ĠHence Ġthe Ġpath Ġis ĊĠĠĠĠĠĠĠĠĠĠĠ Ġ// Ġempty Ġand Ġthe Ġvariable Ġ" path "; Ġmust Ġbe Ġnull . ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln (" Short est Ġpath Ġfrom Ġc Ġto Ġi :") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġval Ġc Paths Ġ= Ġdi jk stra Alg . get Paths (" c ") ĊĠĠĠĠĠĠĠĠĠĠĠ Ġprintln ( c Paths . getPath (" i ")) ĊĊĠĠĠĠĠĠĠ Ġ} ĊĠĠĠ Ġ} Ċ }