Graph

class Graph(init)

Creates a Graph object

Parameters:

init – if integer (V) initialize empty Graph with V vertices. If string (filename) load and populate from file.

add_edge(v, w)

Connects vertices v and w, both must be smaller than V

Parameters:

• v – vertice id

• w – vertice id

adj(v)

Return a list of vertices adjacent to v

Parameters:

v – vertice id

Return type:

array of vertice ids

to_string()

Create a string representation of the Graph

Return type:

string

BFSearch

class BFSearch(G, s)

Does a breadth first search of G from s.

Parameters:

• G – Graph object

• s – Vertex id of the starting point for search

bfs(G, s)

Performs the breadth first search - called from constructor, should not be called directly

Parameters:

• G – Graph object created by Graph or SymbolGraph

• s – Vertex id of the starting point for search

has_path_to(v)

Does (G,s) have a path to vertex v?

Parameters:

v – Vertex id

Return type:

Boolean

path_to(v)

Make one path to v from s

Parameters:

v – Vertex id

Return type:

array of vertex ids connecting v to s

count()

Number of visited nodes when exploring (G, s)

Return type:

number of visited nodes

DFSearch

class DFSearch(G, s)

Does a depth first search of G from s.

Parameters:

• G – Graph object

• s – Vertex id of the starting point for search

dfs(G, v)

Performs the depth first search - called from constructor, should not be called directly

Parameters:

• G – Graph object created by Graph or SymbolGraph

• v – Vertex id of the starting point for search

has_path_to(v)

Does (G,s) have a path to vertex v?

Parameters:

v – Vertex id

Return type:

Boolean

path_to(v)

Make one path to v from s

Parameters:

v – Vertex id

Return type:

array of vertex ids connecting v to s

count()

Number of visited nodes when exploring (G, s)

Return type:

number of visited nodes