cusack.hcg.games.pebble.algorithms.islands

Class IslandUtils

java.lang.Object

cusack.hcg.games.pebble.algorithms.islands.IslandUtils

public class IslandUtils
extends java.lang.Object

Constructor Summary

Constructors

Constructor and Description
IslandUtils()

Method Summary

Modifier and Type	Method and Description
static boolean	containsEmpire(java.util.Collection<Island> islands) Determines if any island in the collection contains an empire.
static Path	findPathBFS(Vertex source, Vertex sink, java.util.Set<Vertex> includes)
static java.util.List<Path>	getDoublePebblePaths(Island i, Vertex u, Vertex v) Tests to see if using only the vertices in Island i, we can move two pebbles simultaneously to Vertex v.
static java.util.HashSet<Island>	getIslands(PebbleInstance pi)
static PebbleAlgorithmStates	isSolvableDiamTwoRec(PebbleInstance pi, java.util.Set<Vertex> L) Recursive function that determines if this graph is solvable.
static int	pebbleAlongPath(PebbleInstance pi, Path path) Added by CAC 1/09
static int	pebbleAlongPaths(PebbleInstance pi, java.util.Collection<Path> paths) Pebble along multiple paths.
static int	pebbleFromIsland(PebbleInstance pi, Island island, Vertex v) Moves a pebble from the island to the vertex, if possible.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

IslandUtils

public IslandUtils()

Method Detail

getIslands

public static java.util.HashSet<Island> getIslands(PebbleInstance pi)

isSolvableDiamTwoRec

public static PebbleAlgorithmStates isSolvableDiamTwoRec(PebbleInstance pi,
                                                         java.util.Set<Vertex> L)

Recursive function that determines if this graph is solvable. Almost identical to the algorithm written by Charles Cusack and Airat Bekmetjev.

Returns:

true, if is solvable diam two rec

pebbleAlongPaths

public static int pebbleAlongPaths(PebbleInstance pi,
                                   java.util.Collection<Path> paths)

Pebble along multiple paths.

Parameters:

paths - the collection of paths

Returns:

the int

pebbleAlongPath

public static int pebbleAlongPath(PebbleInstance pi,
                                  Path path)

Added by CAC 1/09

Parameters:

path -

Returns:

pebbleFromIsland

public static int pebbleFromIsland(PebbleInstance pi,
                                   Island island,
                                   Vertex v)

Moves a pebble from the island to the vertex, if possible.

Parameters:

island - the island I'm pebbling from

v - the vertex I want to pebble to

Returns:

the number of moves made

findPathBFS

public static Path findPathBFS(Vertex source,
                               Vertex sink,
                               java.util.Set<Vertex> includes)

containsEmpire

public static boolean containsEmpire(java.util.Collection<Island> islands)

Determines if any island in the collection contains an empire.

Parameters:

islands - the islands

Returns:

true, if the graph contains an empire

getDoublePebblePaths

public static java.util.List<Path> getDoublePebblePaths(Island i,
                                                        Vertex u,
                                                        Vertex v)

Tests to see if using only the vertices in Island i, we can move two pebbles simultaneously to Vertex v. Vertex u and v must be adjacent (or in) the Island i. This is done by finding the two vertex disjoint (VD) paths in the set of vertices covered by the island and verts u and v.

Parameters:

i - the island

u - the vertex we are attempting to move a pebble to

v - the vertex we are attempting to move a pebble to

Returns:

null if there are no VD paths, otherwise it returns a list of paths.

See Also:

graph.UnweightedFlow#getVertexDisjointPaths(Set, Set, Set, int)