graphs.directed_and_undirected_weighted_graph¶
Classes¶
Module Contents¶
- class graphs.directed_and_undirected_weighted_graph.DirectedGraph¶
- add_pair(u, v, w=1) None¶
Adds a directed edge u->v with weight w. Add vertices and edges Add the weight is optional Handle repetition
>>> dg = DirectedGraph() >>> dg.add_pair(-1,2) >>> dg.add_pair(1,3,5) >>> dg.add_pair(1,3,5) >>> dg.add_pair(1,3,6) >>> dg.all_nodes() [-1, 2, 1, 3] >>> dg.graph[1] [[5, 3], [6, 3]]
- all_nodes()¶
Returns list of all nodes in the graph. >>> dg = DirectedGraph() >>> dg.all_nodes() [] >>> dg.add_pair(1,1) >>> dg.all_nodes() [1] >>> dg.add_pair(2,3,3) >>> dg.all_nodes() [1, 2, 3]
- bfs(s=-2)¶
Performs breadth first search from s Returns list. >>> dg = DirectedGraph() >>> dg.bfs() [] >>> dg.add_pair(1,1) >>> dg.bfs(1) [1] >>> dg = DirectedGraph() >>> dg.add_pair(0,1) >>> dg.add_pair(0,2) >>> dg.add_pair(1,3) >>> dg.add_pair(1,4) >>> dg.add_pair(1,5) >>> dg.add_pair(2,5) >>> dg.add_pair(5,6) >>> dg.bfs(0) [0, 1, 2, 3, 4, 5, 6] >>> dg.bfs(1) [1, 3, 4, 5, 6] >>> dg.bfs() [0, 1, 2, 3, 4, 5, 6]
- bfs_time(s=-2)¶
- cycle_nodes()¶
- dfs(s=-2, d=-1)¶
Performs depth first search from s to find d. Returns the path s->d as a list. Returns dfs from s if d is not found >>> dg = DirectedGraph() >>> dg.dfs() [] >>> dg.add_pair(1,1) >>> dg.dfs(1,1) [1] >>> dg = DirectedGraph() >>> dg.add_pair(0,1) >>> dg.add_pair(0,2) >>> dg.add_pair(1,3) >>> dg.add_pair(1,4) >>> dg.add_pair(1,5) >>> dg.add_pair(2,5) >>> dg.add_pair(5,6) >>> dg.dfs(0,6) [0, 2, 5, 6] >>> dg.dfs(1,6) [1, 5, 6] >>> dg.dfs() [0, 2, 5, 6, 1, 4, 3] >>> dg.dfs(1,0) [1, 5, 6, 4, 3]
- dfs_time(s=-2, e=-1)¶
- fill_graph_randomly(c=-1) None¶
- has_cycle() bool | None¶
- in_degree(u)¶
- out_degree(u)¶
- remove_pair(u, v) None¶
Removes all edges u->v if it exists. >>> dg = DirectedGraph() >>> dg.remove_pair(1,2) # silently exits >>> dg.add_pair(0,5,2) >>> dg.graph[0] [[2, 5]] >>> dg.remove_pair(5,0) >>> dg.graph[0] [[2, 5]] >>> dg.remove_pair(0,5) >>> dg.graph[0] []
- topological_sort(s=-2)¶
- graph¶
- class graphs.directed_and_undirected_weighted_graph.Graph¶
- add_pair(u, v, w=1) None¶
- all_nodes()¶
- bfs(s=-2)¶
Performs breadth first search from s Returns list. >>> ug = Graph() >>> ug.bfs() [] >>> ug.add_pair(1,1) >>> ug.bfs(1) [1] >>> ug = Graph() >>> ug.add_pair(0,1) >>> ug.add_pair(0,2) >>> ug.add_pair(1,3) >>> ug.add_pair(1,4) >>> ug.add_pair(1,5) >>> ug.add_pair(2,5) >>> ug.add_pair(5,6) >>> ug.bfs(0) [0, 1, 2, 3, 4, 5, 6] >>> ug.bfs(1) [1, 0, 3, 4, 5, 2, 6] >>> ug.bfs() [0, 1, 2, 3, 4, 5, 6]
- bfs_time(s=-2)¶
- cycle_nodes()¶
- degree(u)¶
- dfs(s=-2, d=-1)¶
Performs depth first search from s to find d. Returns the path s->d as a list. Returns dfs from s if d is not found >>> ug = Graph() >>> ug.dfs() [] >>> ug.add_pair(1,1) >>> ug.dfs(1,1) [1] >>> ug = Graph() >>> ug.add_pair(0,1) >>> ug.add_pair(0,2) >>> ug.add_pair(1,3) >>> ug.add_pair(1,4) >>> ug.add_pair(1,5) >>> ug.add_pair(2,5) >>> ug.add_pair(5,6) >>> ug.dfs(0,6) [0, 2, 5, 6] >>> ug.dfs(1,6) [1, 5, 6] >>> ug.dfs() [0, 2, 5, 6, 1, 4, 3] >>> ug.dfs(1,0) [1, 5, 6, 2, 0]
- dfs_time(s=-2, e=-1)¶
- fill_graph_randomly(c=-1) None¶
- has_cycle() bool | None¶
- remove_pair(u, v) None¶
- graph¶