graph.Graph

Module graph

A module containing Graph class. We assume that every graph is simple, i.e., there is no loops or multi edges.

class graph.Graph(graph_dict={})

add_edge(edge)

Add an edge to graph. Assumes that edge is of type set, tuple or list. No loops or multiple edges.

Returns:Returns true if edge is not present, otherwise false.

add_edges(edges)

Adds a list of edges to graph.

Parameters:edges – a list of edges to be added Returns:void

add_vertex(vertex)

If 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.

Returns:True if the vertex is not present in the graph, otherwise false.

biggest_component_diameter()

Returns:the diameter of the biggest component

connected_component()

Computes the number of connected components and the size of each componenent

Returns:a pair: thi first entry is the number of components, the second is a list constaining sizes of components

connected_components()

Computes connected components.

Returns:a list of lists, each containing vertices from the same conn component.

degree_sequence()

Degree sequence is a list of all degrees in non-increasing order.

Returns:a degree sequence of the graph

density()

Density is ratio of number of edges and number of edges that complete graph has with the same number of vertices.

Returns:returns the density of the graph

diameter()

Computes the diameter of the graph.

Returns:The maximum of distances between any pair of nodes or infinity if the graph is not connected

edges()

Returns:a list of tuples representing the edges of the graph

erdos_gallai(degree_seq=None)

Erdos Gallai theorem states that a non-increasing sequence of n numbers d_i is a degree sequence of a simple graph if and only if the sum of sequence is even and the condition $sum_{i=1}^{k}{d_i} leq k(k-1) + sum_{i=k+1}^n min(d_i, k) ext{ for all } k$ This can be implemented in time $O(n)$. However, the current implementation requires O(n^2) time.

Parameters:degree_seq – If it is None, then the degree sequence of the graph is used. Returns:True if the degree sequence satisfies both conditions and False otherwise

find_isolated_vertices()

Returns:a list of vertices of degree 0.

get_neighbors(u)

Parameters:u – vertex in the graph Returns:a list of neighbors of u

global_clustering_coefficient()

Global clustering coefficient is the ratio of number of triangles and number of connected triplets of vertices

Returns:float, clustering coefficient of the graph

in_neighbourhood(u, v)

Parameters:

• u – a vertex of the graph
• v – a vertex of the graph

Returns:

Returns True if v is in the neighborhood of u. It raises KeyError if u is not present in the graph.

is_vertex_present(vertex)

Checks if the vertex is already created. Returns True if it is otherwise False

Parameters:vertex – name of the vertex Returns:true if vertex is in the graph, false otherwise

number_of_edges()

Returns:returns the number of edges

number_of_vertices()

Returns:returns the number of vertices

read_from_file(filename=None)

Reads graph from a file.

Parameters:filename – path to the file Returns:True if the graph is read successfully. If filename is not specified or it does not exist, ValueError and IOError are raised (respectively).

shortest_path(u=None, v=None)

Computes the shortest path between u and v. If both of them are None, then computes the shorthest path between all pair of vertices. If u is not None and v is None, then it computes the shortest path between u and all other vertices. Finally, if both of them are not None, it computes the shorthest path between u and v.

Parameters:

• u – the source vertex
• v – the end vertex

Returns:

the shortest path

spanning_tree()

Computes the spanning tree of the graph using Kruskal algorithm and union - find. Complexity: $O(mlog*(n))$

Returns:a list of tuples representing edges of the tree

update_neighbors(u, new_neighbors)

Updates the list of vertices of a vertex. :param u: Vertex whose neighborhood is updated :param new_neighbors: (list) New neighbors of u :return: None

vertex_degree(vertex)

Returns the degree of the vertex.

Parameters:vertex – vertex for which degree is computed Returns:return the degree if the vertex is present, otherwise raises keyerror

vertices()

Returns:the vertices of a graph

vertices_degree_list()

Returns:returns a list of degrees of vertices