Fun code and problems

A graph is called simple if it is unweighted, undirected and without parallel edges of self-loops.
My python class for working with such graphs can be found here: download.

I will be adding different methods to this class gradually. If you have implemented additional method and would like to contribute to the development of this class or you have found a bug in the existing implementation please leave a comment to this post.

Note that to insure correct behavior, node names should be strings. If you want to store any other information in the nodes you can keep the dictionary with mapping (node name: data) or convert your node data to string (if applicable). Each graph has its ID.

This class implements the Bron-Kerbosch algorithm (Version 2) for finding all cliques in the graph. Note that, when the graph is sparse and does not contain exponential number of cliques, this method can process graphs of a decent size.

If you have any questions/comments regarding using this graph, leave a comment to this post.

Bellow is the description of this class (generated using pydoc):

class graph(__builtin__.object)
| A class for representing and manipulation undirected, unweighted simple graphs without self-loops
|
| Methods defined here:
|
| BFS(self, source)
| Implements Breadth-first search from node ’source’ in graph ’self’.
| Returns dictionary D {node: distance from source}
| distance=-1 if ‘node’ is unreachable from ’source’
|
| __init__(self, userID=None)
| Constructor
|
| add_edge(self, nd1, nd2)
| Adds edge (nd1,nd2) to the graph.
|
| add_node(self, node)
| Adds node to the graph.
|
| all_pairs_dist(self)
| Returns dictionary of all-pairs shortest paths in ’self’
| The dictionary has format {t=(nd1,nd2): distance},
| where t is a tuple.
|
| are_adjacent(self, nd1, nd2)
| Checks if nd1 and nd2 are connected
|
| create_circulant_graph(self, n, j)
| Creates a circulant graph with n nodes and m edges.
| Nodes are numbered from 1 to n.
| The chords are defined by parameters j.
| That is node i is connected to (i-j) mod n and (i+j) mod n.
| Note that not always the exact match in terms of edges is possible!
| Check the output graph for the number of edges!
|
| create_complete_graph(self, n)
| creates complete graph on n nodes
|
| create_cycle_graph(self, n)
| Creates graph-cycle on n nodes.
| Nodes are numbered from 1 to n.
|
| create_empty_graph(self, n)
| creates graph with n nodes but without edges
|
| create_path_graph(self, n)
| Create path-graph on n nodes
|
| degree(self, node)
| Returns the degree of a node
|
| dist(self, nd1, nd2)
| Returns shortest-path distance between nd1 and nd2
|
| find_all_cliques(self)
| Implements Bron-Kerbosch algorithm, Version 2
|
| get_edge_set(self)
| Returns set of edges in the graph.
|
| get_node_clust_coef(self, node)
| Returns the clustering coefficient of the node
|
| get_node_eccentricities_both(self, node)
| This function is for performance purposes.
| This is function returns standard and averaged eccentricities of the node.
| Note that both eccentricities of the node are within its connected component
|
| get_node_eccentricity(self, node)
| Returns the eccentricity of the node.
| Note that this function returns the eccentricity of a node within its
| connected component
|
| get_node_eccentricity_avg(self, node)
| Returns the averaged eccentricity of the node. That is, “avg”, not “max” distance
| Note that this function returns the eccentricity of a node within its
| connected component
|
| get_node_neighbors(self, nd)
| Returns set of node neighbors
|
| number_of_edges(self)
| Returns number of edges in the graph.
|
| number_of_nodes(self)
| Returns number of nodes in the graph.
|
| readFromEdgeList(self, path)
| Read graph from the file where it is represented as an edge list.
| The lines of the file should be formated as:
| node1[space]node2[newline]
| Duplicate edges and self loops are ignored.
|
| saveAsEdgeList(self, path)
| Saves graph as edge list
|
| ———————————————————————-

This is a collection of mathematical and computer science problems which I think might be fun and interesting.  The collection is for entertainment or educational purposes. Anyone can post new problems here, however I reserve the right to remove any post for any reason. Please do not post solutions to the probems unless it is asked explicitly by me. Also, sometimes I will post code and my thought on particular problems.

Authorship: To the best of my knowledge I will post the references to the websites/literature from where the problems have been taken. I am not responsible for the problems posted by other people here.

This problem is know as 2 eggs problem and is said to be asked by Google on thier interviews (I do not know if it is true or not). Below is a simple version of the problem taken from here

Simple problem:

You are given 2 identical eggs.
1) You have access to a 100-storey building.
2) Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.
3) You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking.

Question: How many drops you need to make? You are allowed to break 2 eggs in the process 

Below is somewhat more general version of the problem similar to what I’ve seen in Algorithm Design, by Kleinberg and Tardos, Addison-Wesley, 2006.

More general problem:

You are given k>1 identical eggs.
1) You have access to a n-storey building. (k<n)
2) Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from n th floor.
3) You need to figure out the highest floor of a n-storey building an egg can be dropped without breaking. You are allowed to break k eggs in the process.

Question:  Find a sublinear time algorithm to figure out the highest floor and prove algorithms complexity.

This logical puzzle is called Einstein’s Puzzle because it is said to have been invented by Albert Einstein. There are  rumors that Einstein claimed that only 2% of people can solve it mentally i.e. without using pen and paper, computer or any other medium.  If you are allowed to use pen and paper the problem is very easy and is not interesting.

The problem:

1. The British lives in the red house.
2. The Swedish keeps dogs as pets.
3. The Danish drinks tea.
4. The green house is on the left of the white house.
5. The green homeowner drinks coffee.
6. The person who smokes Pall Mall rears birds.
7. The owner of the yellow house smokes Dunhill.
8. The man living in the center house drinks milk.
9. The Norwegian lives in the first house.
10. The man who smokes Blend lives next to the one who keeps cats.
11. The man who keeps the horse lives next to the man who smokes Dunhill.
12. The owner who smokes Bluemaster drinks beer.
13. The German smokes prince.
14. The Norwegian lives next to the blue house.
15. The man who smokes Blend has a neighbor who drinks water.

Question: Who owns the fish?