A D E F G H I L M N P R S T U W

A

AdjListElmnt - class AdjListElmnt.

This class implements an element of an adjacency linked-list in the adjacency lists representation of a graph.

AdjListElmnt(int, double) - Constructor for class AdjListElmnt

The class constructor.

AdjListsGraph - class AdjListsGraph.

This is a graph implementation that uses adjacency lists to store edges.

AdjListsGraph(int, boolean) - Constructor for class AdjListsGraph

The class constructor.

AirCanada - class AirCanada.

This class implements a method for determining a set of JetsGo routes that Air Canada should add to their flight network

AirCanada() - Constructor for class AirCanada

addEdge(int, int, double) - Method in class AdjListsGraph

addEdge(int, int, double) - Method in class Graph

This method adds an edge to the graph without checking whether the edge already exists.

addEdge(Edge) - Method in class Graph

This is an alternative method prototype for unsafe edge addition, when the edge is given as an object.

addEdge(int, int, double) - Method in class ListOfEdgesGraph

addEdgeSafe(int, int, double) - Method in class AdjListsGraph

addEdgeSafe(int, int, double) - Method in class Graph

This method adds an edge to the graph as follows: first check whether the edge already exists in the graph; if it does not exist, then add the edge and return true; if it does exist, then do nothing and return false.

addEdgeSafe(Edge) - Method in class Graph

This is an alternative method prototype for safe edge addition, when the edge is given as an object.

addEdgeSafe(int, int, double) - Method in class ListOfEdgesGraph

D

DynamicHeap - class DynamicHeap.

Generic heap that also supports FIFO access, backed by a dynamic array; stores items of type Object with priorities of type Comparable, and correctly handles multiple items with the same priority.

DynamicHeap() - Constructor for class DynamicHeap

Initializes this heap to be empty.

decreasePriority(Object, Comparable) - Method in class DynamicHeap

Decreases the priority of the given item to the given priority value if the new priority is less than the old, does nothing otherwise.

decreasePriority(Object, Comparable) - Method in interface PriorityQueue

Decreases the priority of the given item to the given priority value if the new priority is less than the old, does nothing otherwise.

deleteMinPriority() - Method in class DynamicHeap

Removes the first item with smallest priority from this queue, and returns this item.

deleteMinPriority() - Method in interface PriorityQueue

Removes the first item with smallest priority value from this queue, and returns this item.

dequeueFIFO() - Method in class DynamicHeap

Removes the item that was inserted first into this queue, and returns this item.

dequeueFIFO() - Method in interface FIFOQueue

Removes the item that was inserted first into this queue, and returns this item.

directed - Variable in class Graph

True if the edges are directed.

E

Edge - interface Edge.

This interface specifies methods that can be used to get the source node, the target node, and the weight of a graph edge.

Element - class Element.

This class is used for implementing and manipulating a tree representation of a generic set, which allows for efficient union and find-set operations.

Element(Object) - Constructor for class Element

This is the constructor method for Element class.

F

FIFOQueue - interface FIFOQueue.

Generic FIFO queue.

FindRoutes(int, Collection, double) - Static method in class AirCanada

This method takes as a parameter an *undirected* graph represented by the number of its nodes and a collection of edges.

findSet() - Method in class Element

This method returns a reference to the Set instance of the set that contains this Element.

G

Graph - class Graph.

This abstract class defines a set of variables and implements some methods that are common in every implementation of a graph object.

Graph(int, boolean) - Constructor for class Graph

The class constructor.

getAdjListOfNode(int) - Method in class AdjListsGraph

This method returns the adjacency linked-list of node i.

getEdges() - Method in class ListOfEdgesGraph

getMinPriority() - Method in class DynamicHeap

Returns the first item with smallest priority value in this queue.

getMinPriority() - Method in interface PriorityQueue

Returns the first item with smallest priority value in this queue.

getNNodes() - Method in class Graph

getParentElmnt() - Method in class Element

This method returns the parent of the Element.

getReprElmnt() - Method in class Set

This method returns the set's representative Element, or null if the set is empty.

getSize() - Method in class DynamicHeap

Returns the current size (number of items) in this queue.

getSize() - Method in interface FIFOQueue

Returns the current size (number of items) in this queue.

getValue() - Method in class Element

This method returns the value of the Element.

H

headFIFO() - Method in class DynamicHeap

Returns the item that was inserted first into this queue.

headFIFO() - Method in interface FIFOQueue

Returns the item that was inserted first into this queue.

I

insert(Object, Comparable) - Method in class DynamicHeap

Adds the given item with the given priority to this queue.

insert(Object, Comparable) - Method in interface PriorityQueue

Adds the given item with the given priority value to this queue.

isDirected() - Method in class Graph

isEmpty() - Method in class DynamicHeap

isEmpty() - Method in interface PriorityQueue

Returns true if the queue is empty and false otherwise.

L

ListOfEdgesGraph - class ListOfEdgesGraph.

This is a graph implementation that uses a linked-list of edges representation.

ListOfEdgesGraph(int, boolean) - Constructor for class ListOfEdgesGraph

The class constructor.

M

Misc - class Misc.

This class contains miscellaneous general purpose functions.

Misc() - Constructor for class Misc

main(String[]) - Static method in class RouteTest

This is a sample main function for testing the implementation of the Air Canada find routes algorithm.

max(int, int) - Static method in class Misc

min(int, int) - Static method in class Misc

N

nNodes - Variable in class Graph

The number of nodes of the graph.

P

PlainEdge - class PlainEdge.

This class implements the Edge interface.

PlainEdge(int, int, double) - Constructor for class PlainEdge

The class constructor.

PriorityQueue - interface PriorityQueue.

Generic min-priority queue (smaller priority value = higher priority).

R

RouteTest - class RouteTest.

This class is used for testing the implementation of the AirCanada find routes implementation.

RouteTest() - Constructor for class RouteTest

removeAllEdges() - Method in class AdjListsGraph

removeAllEdges() - Method in class Graph

This method removes all edges in the graph.

removeAllEdges() - Method in class ListOfEdgesGraph

removeEdge(int, int) - Method in class AdjListsGraph

removeEdge(int, int) - Method in class Graph

This method removes an edge as follows: if the graph contains an edge from source to target node, then this edge is removed and the weight of the edge is returned.

removeEdge(int, int) - Method in class ListOfEdgesGraph

S

Set - class Set.

This class is used for implementing and manipulating a tree representation of a generic set, which allows for efficient union and find-set operations.

Set(Element) - Constructor for class Set

This is the class constructor.

setParentElmnt(Element) - Method in class Element

This method sets the parent of the Element.

source() - Method in interface Edge

source() - Method in class PlainEdge

T

target - Variable in class AdjListElmnt

The target node.

target() - Method in interface Edge

target() - Method in class PlainEdge

toAltGraphRepr(Graph) - Method in class AdjListsGraph

toAltGraphRepr(Graph) - Method in class Graph

This method copies this graph to graph g, if g has the same number of nodes, and both g and this graph are directed, or both are undirected.

toAltGraphRepr(Graph) - Method in class ListOfEdgesGraph

toString() - Method in class AdjListElmnt

toString() - Method in class AdjListsGraph

toString() - Method in class DynamicHeap

Returns a String representation of this heap.

toString() - Method in class Element

Overwrite default toString() method to print Element info.

toString() - Method in class ListOfEdgesGraph

toString() - Method in class PlainEdge

toStringDebug() - Method in class DynamicHeap

Returns a String representation of this queue that tries to include all information, for debugging.

toStringFIFO() - Method in class DynamicHeap

Returns a String representation of this FIFO queue.

U

union(Set, Set) - Static method in class Set

This method performs the union by size of sets s1, s2.

usePathCompression - Static variable in class Element

This parameter specifies whether path compression is applied whenever a find-set operation is performed.

W

weight - Variable in class AdjListElmnt

The weight of the corresponding edge (i.e., the edge from the node whose adjacency list this AdjListElmnt belongs to, to the target node).

weight() - Method in interface Edge

weight() - Method in class PlainEdge

weightOfEdge(int, int) - Method in class AdjListsGraph

weightOfEdge(int, int) - Method in class Graph

This method returns the weight of the edge from the source node to the target node, or +Infinity if no such edge exists.

weightOfEdge(int, int) - Method in class ListOfEdgesGraph

A D E F G H I L M N P R S T U W