~ubuntu-branches/ubuntu/utopic/python-networkx/utopic

« back to all changes in this revision

Viewing changes to networkx/algorithms/approximation/tests/test_vertex_cover.py

• browse files at revision 10
• compare with another revision
• download diff
• download tarball
• view history from revision 10

Show diffs side-by-side

added

removed

networkx/algorithms/approximation/tests/test_vertex_cover.py

 

1

#!/usr/bin/env python

 

2

from nose.tools import *

 

3

import networkx as nx

 

4

from  networkx.algorithms import approximation as a

 

5

 

 

6

class TestMWVC:

 

7

 

 

8

    def test_min_vertex_cover(self):

 

9

        # create a simple star graph

 

10

        size = 50

 

11

        sg = nx.star_graph(size)

 

12

        cover = a.min_weighted_vertex_cover(sg)

 

13

        assert_equals(2, len(cover))

 

14

        for u, v in sg.edges_iter():

 

15

            ok_((u in cover or v in cover), "Node node covered!")

 

16

 

 

17

        wg = nx.Graph()

 

18

        wg.add_node(0, weight=10)

 

19

        wg.add_node(1, weight=1)

 

20

        wg.add_node(2, weight=1)

 

21

        wg.add_node(3, weight=1)

 

22

        wg.add_node(4, weight=1)

 

23

 

 

24

        wg.add_edge(0, 1)

 

25

        wg.add_edge(0, 2)

 

26

        wg.add_edge(0, 3)

 

27

        wg.add_edge(0, 4)

 

28

 

 

29

        wg.add_edge(1,2)

 

30

        wg.add_edge(2,3)

 

31

        wg.add_edge(3,4)

 

32

        wg.add_edge(4,1)

 

33

 

 

34

        cover = a.min_weighted_vertex_cover(wg, weight="weight")

 

35

        csum = sum(wg.node[node]["weight"] for node in cover)

 

36

        assert_equals(4, csum)

 

37

 

 

38

        for u, v in wg.edges_iter():

 

39

            ok_((u in cover or v in cover), "Node node covered!")

• Older »

Loggerhead is a web-based interface for Breezy
Version: 2.0.1