snowdrop.src.info package¶
Submodules¶
snowdrop.src.info.graph module¶
Python class that demonstrates the essential facts and functionalities of graphs. This class represents a directed graph using adjacency list representation It finds biconnected components in a given undirected graph with complexity : O(V + E)
- Original version of the code can be found at:
https://www.python-course.eu/graphs_python.php https://tutorialspoint.dev/data-structure/graph-data-structure/biconnected-components
Modified by A.Goumilevski
- class snowdrop.src.info.graph.Graph(graph_dict={}, m=None, weights=None)[source]¶
Bases:
object
Graph class.
- BCCUtil(u, parent, low, disc, st)[source]¶
A recursive function that finds and prints strongly connected components using DFS traversal
u –> The vertex to be visited next disc[] –> Stores discovery times of visited vertices low[] – >> earliest visited vertex (the vertex with minimum
discovery time) that can be reached from subtree rooted with current vertex
st – >> To store visited edges
- add_edge(edge, w=None)[source]¶
Add an edge.
It is assumed that edge is of type set, tuple or list; between two vertices can be multiple edges!
- add_vertex(vertex)[source]¶
Add graph vertex.
If the vertex is not in self.__graph_dict, a key “vertex” with an empty list as a value is added to the dictionary. Otherwise nothing has to be done.
- connected(t)[source]¶
Return connected vertices of a minimum spanning tree.
- Args:
- tlist
List of vertices.
- Returns:
Connected vertices of a minimum spanning tree.
- static erdoes_gallai(dsequence)[source]¶
Check if the condition of the Erdoes-Gallai inequality is fullfilled.
- find(parent, i)[source]¶
Find a set of an element i.
This algorithm uses path compression technique.
- Args:
- parentlist
Parent list.
- iint
Element.
- Returns:
Set of an element i.
- find_all_paths(start_vertex, end_vertex, path=[])[source]¶
Find all paths from start_vertex to end_vertex in graph.
- find_distance(start_vertex, end_vertex)[source]¶
Find number of edges from start_vertex to end_vertex.
- find_path(start_vertex, end_vertex, path=[])[source]¶
Find a path from start_vertex to end_vertex in graph.
- find_shortest_path(start_vertex, end_vertex, path=[])[source]¶
Find shortest path from start_vertex to end_vertex.
- getMinimumSpanningTree()[source]¶
Kruskal’s algorithm to find Minimum Spanning Tree (MST)of a given connected, undirected and weighted graph.
Time Complexity: O(ElogE) or O(ElogV). Here E is the number of edges and V is the number of vertices. Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost O(V2), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV).
https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
- Args:
self: Graph object.
- Returns:
None.
- get_connected_vertices(start_vertex, vertices_encountered=None, gdict=None)[source]¶
Determine if graph is connected.
- isCyclic()[source]¶
Check whether a given graph contains a cycle or not.
- Returns:
- bool
True if graph is cyclic and False otherwise.
- is_connected(vertices_encountered=None, start_vertex=None)[source]¶
Determine if graph is connected.
- static is_degree_sequence(sequence)[source]¶
Find degree sequence.
Method returns True, if the “sequence” is a degree sequence, i.e. a non-increasing sequence. Otherwise returns False.
- union(parent, rank, x, y)[source]¶
Return union of two sets of x and y.
This algoritm sorts uses union by rank.
- Args:
- parentlist
Parent list of vertices.
- ranklist
Rank of tree.
- xlist
Graph vertices.
- ylist
Graph vertices.
- Returns:
None.
snowdrop.src.info.graphs module¶
Created on Sat Apr 18 13:01:21 2020
@author: A.Goumilevski
- snowdrop.src.info.graphs.createClusters(model, img_file_name='Minimum_Spanning_Tree.png')[source]¶
Create graph of components of model equations endogenous variables.
- Parameters:
- param model:
The Model object.
- type model:
Instance of class Model.
- snowdrop.src.info.graphs.createGraph(model, img_file_name='Equations_Graph.png')[source]¶
Create a graph of endogenous variables of a model.
- Parameters:
- param model:
The Model object.
- type model:
Instance of class Model.
snowdrop.src.info.test module¶
Created on Sun Apr 19 16:16:04 2020
@author: Alexei