Digraph classes
Digraph
- class Digraph(init)
Creates a Digraph object
- Parameters:
init – if integer (V) initialize empty Digraph 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 Digraph
- Return type:
string
Directed Cycle
Detects cycles in Digraphs
- class DirectedCycle(DG)
- Parameters:
DG – Digraph object
- has_cycle()
- Return type:
boolean
- get_cycle()
- Return type:
list of vertices in the cycle
DepthFirstOrder
Performs a depth first search with support for returning visited nodes in pre-order, post-order and reverse post-order.
- class DepthFirstOrder(DG)
- Parameters:
DG – Digraph object
- get_pre()
- Return type:
vertice list in pre-order
- get_post()
- Return type:
vertice list in post-order
- get_reverse_post()
- Return type:
vertice list in reverse post-order
DirectedDFSearch
- class DirectedDFSearch(DG, s)
Does a depth first search of Digraph from s.
- Parameters:
DG – Digraph object
s – Vertex id of the starting point for search
- dfs(DG, v)
Performs the depth first search - called from constructor, should not be called directly
- Parameters:
DG – Digraph object
v – Vertex id of the starting point for search
- has_path_to(v)
Does (DG, 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 (Digraph, s)
- Return type:
number of visited nodes
Regex
An implementation of regular expressions. Constructs a NFA Digraph of the regular expression, then simulates the NFA using repeated depth first searches.
- class Regex(expression)
- Parameters:
expression – regular expression
- match(text)
- Parameters:
text – text string to be matched against the regex
- Return type:
boolean
SymbolDigraph
Support Digraph objects with named edges.
- class SymbolDigraph(filename)
- Parameters:
filename – file to read
- graph()
- Return type:
Digraph object
- node_names()
List of node names corresponding to vertice ids
- Return type:
array of node names
Topological Sort
Performs topological sort. Since this can only work on DAGs this code raises an exception of a cycle is found.