Exam 3 Review

The following are some problems that you can do as practice for the exam. They are representative of some of the questions that might be on the exam. However, the following are not comprehensive, in that they do not cover all of the material emphasized on this exam. We have also provided a more comprehensive list of study topics.

Note that the wording on these problems is a bit looser than is typical, leaving some details open for interpretation.

• You want to search a huge graph, but it is too time-consuming to exhaustively search the entire graph. Instead, you will search a representative random sample via a random walk. You are given a graph, a maximum number of nodes to search, and a specific target node to search for. Write a modified version of DFS/BFS that picks the next node to explore randomly from the “to-do list”. In addition, it visits at most the given maximum number of nodes.

  The following is a solution outline.
  
  import random
  
  Start with a copy of either DFS or BFS.  The 200-version of DFS looped
  over  graph[nodes]  while the 130-version of DFS added  graph[nodes]
  to the end of the "todo list" and BFS added  graph[nodes]  to the front
  of the "todo list".  In each of these, what we want to do instead is
  loop over  graph[nodes]  and probabilistically do the same action as
  before.
  
  ...
  for neighber in graph[nodes]:
     if random.random <= probability:
        ...
  ...
      

• For our graph-traversal functions, we need sample input graphs. Generating large ones by hand is too tedious, so instead we need functions to generate graphs of specific desired types. Write a function that is given a number of nodes and a probability. It returns a directed graph with that number of nodes. Each possible directed edge has the given probability of existing in the constructed graph.

  import random
  
  def randomGraph(numberNodes,probability):
      """Creates a subset of a complete directed graph, choosing each edge with the given probability."""
  
      graph = {}
  
      for source in range(numberNodes):
          graph[source] = []
          for target in range(numberNodes):
              if source != target and random.random() <= probability:
                  graph[source].append(target)
  
      return graph
      

• Describe how you would modify DFS or BFS to count how many nodes are reachable from the given source node.

  Approach 1:
  
  Add a counter to the DFS/BFS function.  Initialize it with one, as
  you are initially visiting the source.  Every time you visit a node,
  increment the counter.  At the end, return the counter.
  (For the recursive 200-version of DFS, the counter would need to be global.)
  
  Approach 2:
  
  When returning, simply return the number of visited nodes, i.e.,
  len(visited).
      

• Write a function that takes a graph in our dictionary representation. It should determine and return whether or not the graph is undirected.

  def isUndirected(graph):
      """Returns whether the given graph is undirected."""
  
      # For each edge source-to-target, verify that there is an edge target-to-source.
      for source in graph:
          for target in graph[source]:
              if source not in graph[target]:
                  return False
      return True
      

• With Dijkstra's algorithm, we used graphs with edge “weights”, where the weights represented distances or times between nodes. As an alternative, let's now assume that you are given a graph with weights on the nodes, instead of the edges. (Note: The networkx library allows node attributes, just like it allows edge attributes.) A path length in such a graph is defined as the sum of node weights in the path, including those on the source and target nodes. Modify Dijkstra's algorithm to work with these graphs.

  The following is a solution outline.
  
  When adding the source to the PQ, it has distance equal to the
  source node weight, instead of zero.
  
  When adding a neighbor to the PQ, it has distance equal to the source
  distance plus the neighbor node weight, instead of the source distance
  plus the source-to-neighbor edge weight.
  
  In these computations, you need the Python syntax to access a networkx
  graph node weight.  Assuming the node is called n, we use the following:
      graph.node[n]['weight']