sdk/platform-tools/systrace/catapult/telemetry/third_party/altgraph/altgraph_tests/test_graphutil.py

   1 import unittest
   2 from altgraph import GraphUtil
   3 from altgraph import Graph, GraphError
   4
   5 class 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
 139 if __name__ == "__main__": # pragma: no cover
 140     unittest.main()