Coding Python Graphs

Computer Science Level pending

As we all know, graphs are an easy way to represent relationships among people, objects, concepts, etc. While there are many ways to create a graph, a random graph is one that is generated from adding randomly edges to a list of nodes. The list of nodes for this problem is generated as follows:

nodes = []
for i in range(n):
     nodes.append(newNode(i)) 

# newNode takes one parameter, the number of the node

Now, suppose we use a helper method addEdge that takes two integers, representing nodes of a graph, and adds a directed edge from the first node to the second, so addEdge(8,2) adds a directed edge from Node 8 to Node 2. The following will produce graphs of different types. Your job is to determine the type of graph that results out of each of the four situations below.

for i in range(len(nodes)):
     x = random.choice(nodes)
     y = random.choice(nodes)
     addEdge(x,y)

for i in range(len(nodes)):
    x = random.choice(nodes)
    y = random.choice(nodes)
    addEdge(x,y)
    addEdge(y,x)

for i in range(len(nodes)):
    w = random.choice(nodes)
    x = random.choice(nodes)
    y = random.choice(nodes)
    z = random.choice(nodes)
    addEdge(w,x)
    addEdge(x,y)
    addEdge(y,z)
    addEdge(z,w)

 for x in nodes:
    for y in nodes:
        addEdge(x,y)
        addEdge(y,x)

Your graph options are:

  1. tree
  2. graph (undirected graph)
  3. line graph
  4. digraph (directed graph)
  5. complete graph or clique
  6. bar graph
  7. bipartite graph
  8. loop or connected chain of nodes (a graph that consists of a single large loop or connected chain of nodes

Enter the numbers corresponding to the graphs of each of the four graphs. Ie: If the first graph is a bar graph, second is a digraph, third is a line graph, and fourth is a clique, then enter "6435".

×

Problem Loading...

Note Loading...

Set Loading...