1import unittest
2from altgraph import GraphUtil
3from altgraph import Graph, GraphError
4
5class TestGraphUtil (unittest.TestCase):
6
7    def test_generate_random(self):
8        g =  GraphUtil.generate_random_graph(10, 50)
9        self.assertEqual(g.number_of_nodes(), 10)
10        self.assertEqual(g.number_of_edges(), 50)
11
12        seen = set()
13
14        for e in g.edge_list():
15            h, t = g.edge_by_id(e)
16            self.assertFalse(h == t)
17            self.assertTrue((h, t) not in seen)
18            seen.add((h, t))
19
20        g =  GraphUtil.generate_random_graph(5, 30, multi_edges=True)
21        self.assertEqual(g.number_of_nodes(), 5)
22        self.assertEqual(g.number_of_edges(), 30)
23
24        seen = set()
25
26        for e in g.edge_list():
27            h, t = g.edge_by_id(e)
28            self.assertFalse(h == t)
29            if (h, t) in seen:
30                break
31            seen.add((h, t))
32
33        else:
34            self.fail("no duplicates?")
35
36        g =  GraphUtil.generate_random_graph(5, 21, self_loops=True)
37        self.assertEqual(g.number_of_nodes(), 5)
38        self.assertEqual(g.number_of_edges(), 21)
39
40        seen = set()
41
42        for e in g.edge_list():
43            h, t = g.edge_by_id(e)
44            self.assertFalse((h, t) in seen)
45            if h == t:
46                break
47            seen.add((h, t))
48
49        else:
50            self.fail("no self loops?")
51
52        self.assertRaises(GraphError, GraphUtil.generate_random_graph, 5, 21)
53        g = GraphUtil.generate_random_graph(5, 21, True)
54        self.assertRaises(GraphError, GraphUtil.generate_random_graph, 5, 26, True)
55
56    def test_generate_scale_free(self):
57        graph = GraphUtil.generate_scale_free_graph(50, 10)
58        self.assertEqual(graph.number_of_nodes(), 500)
59
60        counts = {}
61        for node in graph:
62            degree = graph.inc_degree(node)
63            try:
64                counts[degree] += 1
65            except KeyError:
66                counts[degree] = 1
67
68        total_counts = sum(counts.values())
69        P = {}
70        for degree, count in counts.items():
71            P[degree] = count * 1.0 / total_counts
72
73        # XXX: use algoritm <http://stackoverflow.com/questions/3433486/how-to-do-exponential-and-logarithmic-curve-fitting-in-python-i-found-only-polyn>
74        # to check if P[degree] ~ degree ** G (for some G)
75
76        #print sorted(P.items())
77
78        #print sorted([(count, degree) for degree, count in counts.items()])
79
80        #self.fail("missing tests for GraphUtil.generate_scale_free_graph")
81
82    def test_filter_stack(self):
83        g = Graph.Graph()
84        g.add_node("1", "N.1")
85        g.add_node("1.1", "N.1.1")
86        g.add_node("1.1.1", "N.1.1.1")
87        g.add_node("1.1.2", "N.1.1.2")
88        g.add_node("1.1.3", "N.1.1.3")
89        g.add_node("1.1.1.1", "N.1.1.1.1")
90        g.add_node("1.1.1.2", "N.1.1.1.2")
91        g.add_node("1.1.2.1", "N.1.1.2.1")
92        g.add_node("1.1.2.2", "N.1.1.2.2")
93        g.add_node("1.1.2.3", "N.1.1.2.3")
94        g.add_node("2", "N.2")
95
96        g.add_edge("1", "1.1")
97        g.add_edge("1.1", "1.1.1")
98        g.add_edge("1.1", "1.1.2")
99        g.add_edge("1.1", "1.1.3")
100        g.add_edge("1.1.1", "1.1.1.1")
101        g.add_edge("1.1.1", "1.1.1.2")
102        g.add_edge("1.1.2", "1.1.2.1")
103        g.add_edge("1.1.2", "1.1.2.2")
104        g.add_edge("1.1.2", "1.1.2.3")
105
106        v, r, o =  GraphUtil.filter_stack(g, "1", [
107            lambda n: n != "N.1.1.1", lambda n: n != "N.1.1.2.3" ])
108
109        self.assertEqual(v,
110            set(["1", "1.1", "1.1.1", "1.1.2", "1.1.3",
111                "1.1.1.1", "1.1.1.2", "1.1.2.1", "1.1.2.2",
112                "1.1.2.3"]))
113        self.assertEqual(r, set([
114                "1.1.1", "1.1.2.3"]))
115
116        o.sort()
117        self.assertEqual(o,
118            [
119                ("1.1", "1.1.1.1"),
120                ("1.1", "1.1.1.2")
121            ])
122
123        v, r, o =  GraphUtil.filter_stack(g, "1", [
124            lambda n: n != "N.1.1.1", lambda n: n != "N.1.1.1.2" ])
125
126        self.assertEqual(v,
127            set(["1", "1.1", "1.1.1", "1.1.2", "1.1.3",
128                "1.1.1.1", "1.1.1.2", "1.1.2.1", "1.1.2.2",
129                "1.1.2.3"]))
130        self.assertEqual(r, set([
131                "1.1.1", "1.1.1.2"]))
132
133        self.assertEqual(o,
134            [
135                ("1.1", "1.1.1.1"),
136            ])
137
138
139if __name__ == "__main__": # pragma: no cover
140    unittest.main()
141