2
\$\begingroup\$

As far as I understood this problem, it is a subset of vertices of Graph G, such that every edge has at least one endpoint in the subset. This problem is considered to be NP Complete. However I think a polynomial time greedy solution exists for this problem. I have tested this greedy solution on 12 common instances and it seems to produce the right results.

Either I have misunderstood the problem, or my solution is not polynomial time. Please visit the link below for 12 instances explained with diagram and the code executes all the 12 instances in the same order. Nodes in diagram marked with green are the vertices that should be in the subset.

Problems With Diagrams

'''
Vertex Cover Problem - Greedy approach for finding optimal solution
'''

# case 1
case_1 = {'a': ['b', 'c'], 'b': ['a', 'c', 'd', 'e'], 'c': ['a', 'b', 'd'], 
        'd': ['c', 'b', 'e'], 'e': ['b', 'd']}

# case 2
case_2 = {'a': ['f'], 'b': ['f'], 'c': ['f'], 
        'd': ['f'], 'e': ['f'], 'f': ['a', 'b', 'c', 'd', 'e', 'g'], 'g': ['f']}

# case 3
case_3 = {'a': ['f'], 'b': ['f', 'c'], 'c': ['f', 'd', 'b'], 
        'd': ['f', 'c'], 'e': ['f'], 'f': ['a', 'b', 'c', 'd', 'e', 'g'], 'g': ['f']}

# case 4
case_4 = {'a': ['f'], 'b': ['f', 'c'], 'c': ['f', 'd', 'b'], 
        'd': ['f'], 'e': ['f'], 'f': ['a', 'b', 'c', 'd', 'e', 'g'], 'g': ['f']}

# case 5
case_5 = {'a': ['b', 'd'], 'b': ['a', 'c', 'd', 'e'], 'c': ['b', 'f', 'e'], 
        'd': ['a', 'b', 'e'], 'e': ['b', 'c', 'f'], 'f': ['c', 'e']}

# case 6
case_6 = {'a': ['d', 'b'], 'b': ['a', 'e', 'f', 'c'], 'c': ['b', 'd'], 
        'd': ['a', 'c', 'f', 'e'], 'e': ['b', 'd', 'f'], 'f': ['b', 'd', 'e']}

# case 7
case_7 = {'a': ['b','c'], 'b': ['a','c','d','e','f'], 'c': ['b','a'], 
        'd': ['b'], 'e': ['b'], 'f': ['b']}

# case 8
case_8 = {'a': ['b','c'], 'b': ['a','c','d'], 'c': ['b','a', 'e'], 
        'd': ['b','f','e'], 'e': ['d','c'], 'f': ['d']}

# case 9
case_9 = {'a': ['b', 'f'], 'b': ['a', 'c'], 'c': ['b', 'd'], 
        'd': ['c', 'a'], 'e': ['d', 'f'], 'f': ['e', 'a']}

# case 10
case_10 = {'a': ['b'], 'b': ['c'], 'c': ['d'], 
        'd': ['e'], 'e': ['f'], 'f': ['a']}

# case 11
case_11 = {'a': ['b', 'c', 'd', 'e', 'f'], 'b': ['c', 'a', 'd', 'e', 'f'], 'c': ['d', 'a', 'b', 'e', 'f'], 
        'd': ['e', 'a', 'b', 'c', 'f'], 'e': ['f', 'a', 'b', 'c', 'd'], 'f': ['a', 'b', 'c', 'd', 'e']}

# case 12
case_12 = {'a': ['b', 'c'], 'b': ['d', 'a'], 'c': ['a', 'e'], 
        'd': ['b', 'f', 'g'], 'e': ['h', 'i', 'j'], 'f': ['k', 'l', 'm', 'd'], 
        'g': ['n', 'o', 'p', 'd'], 'h': ['e'], 'i': ['e'], 'j': ['q', 'e'], 'k': ['f'], 'l': ['f'], 'm': ['f'],
        'n': ['g'], 'o': ['g'], 'p': ['g'], 'q': ['j']}

cases = [case_1, case_2, case_3, case_4, case_5, case_6, case_7, case_8, case_9, case_10, case_11, case_12]

class Node(object):
    def __init__(self, name):
        self.name = name
        self.adj_list = []
        self.degree = -1

class Edge(object):
    def __init__(self, node1, node2, weight=0):
        self.node1 = node1
        self.node2 = node2
        self.weight = weight

    def __str__(self):
        return 'Node 1: %s, Node 2: %s' % (self.node1.name, self.node2.name)

    def __repr__(self):
        return '**Node 1: %s, Node 2: %s**' % (self.node1.name, self.node2.name)

def name_of_highest_degree(nodes):
    h = -1
    k = None
    for key in nodes:
        if nodes[key].degree > h:
            h = nodes[key].degree
            k = nodes[key]

    return k

# create Edges and Nodes
def vertex_cover(edges, number):
    total_edges = 0
    nodes = {}
    cover = []

    for a in edges:
        n = Node(a)
        nodes[a] = n

    for n in edges:
        node = nodes[n]
        for e in edges[n]:
            edge = Edge(node, nodes[e])
            node.adj_list.append(edge)
            node.degree += 1
            total_edges += 1

    # Actual algorithm
    while total_edges > 0:
        pick_n = name_of_highest_degree(nodes)
        cover.append(pick_n)
        for key in nodes:
            curr_node = nodes[key]
            j = 0
            while True:
                if len(curr_node.adj_list) <= 0:
                    break

                if j >= len(curr_node.adj_list):
                    break

                edge = curr_node.adj_list[j]
                if edge.node2.name == pick_n.name:
                    curr_node.degree -= 1
                    del curr_node.adj_list[j]
                    total_edges -= 1
                    continue

                if edge.node1.name == pick_n.name:
                    del curr_node.adj_list[j]
                    total_edges -= 1
                    continue

                j += 1

        del nodes[pick_n.name]


    print('Case %d: ' % number, end='')
    for c in cover:
        print(c.name, end=' ')
    print()

for i in range(len(cases)):
    vertex_cover(cases[i], i + 1)

Any review is highly appreciated.

\$\endgroup\$

closed as off-topic by Mast, Graipher, Dannnno, Raystafarian, Ludisposed Jan 8 at 12:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Lacks concrete context: Code Review requires concrete code from a project, with sufficient context for reviewers to understand how that code is used. Pseudocode, stub code, hypothetical code, obfuscated code, and generic best practices are outside the scope of this site." – Mast, Graipher, Dannnno, Raystafarian, Ludisposed
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 3
    \$\begingroup\$ "Please visit the link" Please include the gist of the problem statement in the question itself. Questions should stand on their own for multiple reasons (links can rot, for example). \$\endgroup\$ – Mast Jan 6 at 16:28
2
\$\begingroup\$

The true Vertex Cover Problem is to find the minimum size vertex cover i.e. the smallest set fulfilling the requirements. So I suppose with the minimum requirement it is an NP problem.

For example, your greedy approach for

case_13 = {'a': ['b'], 'b': ['c', 'a'], 'c': ['b', 'd', 'f'], 
    'd': ['e', 'c'], 'e': ['d'], 'f': ['g', 'c'], 'g': ['f']}

yields c a d f, but the minimum cover is b d f.

Other comments:

You can delete nodes.degree; just use len(nodes.adj_list). Have a degree() method on Nodes to calculate it.

You can delete total_edges as well; you can exit the loop when pick_n.degree() == 0.

The inner while loop in your code is then only there to clean up adj_list. Since that is filtering a list, the pythonic way to do it is with a list comprehension:

 curr_node.adj_list = [
     edge for edge in curr_node.adj_list
     if edge.node2.name != pick_n.name
         and edge.node1.name != pick_n.name]

name_of_highest_degree() is misnamed, since it returns the node, not the name of the node.

name_of_highest_degree() can be written as a one-liner using python's max with key= parameter.

\$\endgroup\$
  • \$\begingroup\$ thank you for reviewing and suggesting case 13, code changes. This was really helpful. It cleared my doubts. \$\endgroup\$ – Hemanshu Jan 5 at 8:37

Not the answer you're looking for? Browse other questions tagged or ask your own question.