Statistics
| Branch: | Revision:

iof-tools / networkxMiCe / networkx-master / networkx / algorithms / isomorphism / tests / test_temporalisomorphvf2.py @ 5cef0f13

History | View | Annotate | Download (7.31 KB)

1
"""
2
    Tests for the temporal aspect of the Temporal VF2 isomorphism algorithm.
3
"""
4
from nose.tools import assert_true, assert_false
5
import networkx as nx
6
from networkx.algorithms import isomorphism as iso
7
from datetime import date, datetime, timedelta
8

    
9

    
10
def provide_g1_edgelist():
11
    return [(0, 1), (0, 2), (1, 2), (2, 4), (1, 3), (3, 4), (4, 5)]
12

    
13

    
14
def put_same_time(G, att_name):
15
    for e in G.edges(data=True):
16
        e[2][att_name] = date(2015, 1, 1)
17
    return G
18

    
19

    
20
def put_same_datetime(G, att_name):
21
    for e in G.edges(data=True):
22
        e[2][att_name] = datetime(2015, 1, 1)
23
    return G
24

    
25

    
26
def put_sequence_time(G, att_name):
27
    current_date = date(2015, 1, 1)
28
    for e in G.edges(data=True):
29
        current_date += timedelta(days=1)
30
        e[2][att_name] = current_date
31
    return G
32

    
33

    
34
def put_time_config_0(G, att_name):
35
    G[0][1][att_name] = date(2015, 1, 2)
36
    G[0][2][att_name] = date(2015, 1, 2)
37
    G[1][2][att_name] = date(2015, 1, 3)
38
    G[1][3][att_name] = date(2015, 1, 1)
39
    G[2][4][att_name] = date(2015, 1, 1)
40
    G[3][4][att_name] = date(2015, 1, 3)
41
    G[4][5][att_name] = date(2015, 1, 3)
42
    return G
43

    
44

    
45
def put_time_config_1(G, att_name):
46
    G[0][1][att_name] = date(2015, 1, 2)
47
    G[0][2][att_name] = date(2015, 1, 1)
48
    G[1][2][att_name] = date(2015, 1, 3)
49
    G[1][3][att_name] = date(2015, 1, 1)
50
    G[2][4][att_name] = date(2015, 1, 2)
51
    G[3][4][att_name] = date(2015, 1, 4)
52
    G[4][5][att_name] = date(2015, 1, 3)
53
    return G
54

    
55

    
56
def put_time_config_2(G, att_name):
57
    G[0][1][att_name] = date(2015, 1, 1)
58
    G[0][2][att_name] = date(2015, 1, 1)
59
    G[1][2][att_name] = date(2015, 1, 3)
60
    G[1][3][att_name] = date(2015, 1, 2)
61
    G[2][4][att_name] = date(2015, 1, 2)
62
    G[3][4][att_name] = date(2015, 1, 3)
63
    G[4][5][att_name] = date(2015, 1, 2)
64
    return G
65

    
66

    
67
class TestTimeRespectingGraphMatcher(object):
68
    """
69
        A test class for the undirected temporal graph matcher.
70
    """
71

    
72
    def provide_g1_topology(self):
73
        G1 = nx.Graph()
74
        G1.add_edges_from(provide_g1_edgelist())
75
        return G1
76

    
77
    def provide_g2_path_3edges(self):
78
        G2 = nx.Graph()
79
        G2.add_edges_from([(0, 1), (1, 2), (2, 3)])
80
        return G2
81

    
82
    def test_timdelta_zero_timeRespecting_returnsTrue(self):
83
        G1 = self.provide_g1_topology()
84
        temporal_name = 'date'
85
        G1 = put_same_time(G1, temporal_name)
86
        G2 = self.provide_g2_path_3edges()
87
        d = timedelta()
88
        gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d)
89
        assert_true(gm.subgraph_is_isomorphic())
90

    
91
    def test_timdelta_zero_datetime_timeRespecting_returnsTrue(self):
92
        G1 = self.provide_g1_topology()
93
        temporal_name = 'date'
94
        G1 = put_same_datetime(G1, temporal_name)
95
        G2 = self.provide_g2_path_3edges()
96
        d = timedelta()
97
        gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d)
98
        assert_true(gm.subgraph_is_isomorphic())
99

    
100
    def test_attNameStrange_timdelta_zero_timeRespecting_returnsTrue(self):
101
        G1 = self.provide_g1_topology()
102
        temporal_name = 'strange_name'
103
        G1 = put_same_time(G1, temporal_name)
104
        G2 = self.provide_g2_path_3edges()
105
        d = timedelta()
106
        gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d)
107
        assert_true(gm.subgraph_is_isomorphic())
108

    
109
    def test_notTimeRespecting_returnsFalse(self):
110
        G1 = self.provide_g1_topology()
111
        temporal_name = 'date'
112
        G1 = put_sequence_time(G1, temporal_name)
113
        G2 = self.provide_g2_path_3edges()
114
        d = timedelta()
115
        gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d)
116
        assert_false(gm.subgraph_is_isomorphic())
117

    
118
    def test_timdelta_one_config0_returns_no_embeddings(self):
119
        G1 = self.provide_g1_topology()
120
        temporal_name = 'date'
121
        G1 = put_time_config_0(G1, temporal_name)
122
        G2 = self.provide_g2_path_3edges()
123
        d = timedelta(days=1)
124
        gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d)
125
        count_match = len(list(gm.subgraph_isomorphisms_iter()))
126
        assert_true(count_match == 0)
127

    
128
    def test_timdelta_one_config1_returns_four_embedding(self):
129
        G1 = self.provide_g1_topology()
130
        temporal_name = 'date'
131
        G1 = put_time_config_1(G1, temporal_name)
132
        G2 = self.provide_g2_path_3edges()
133
        d = timedelta(days=1)
134
        gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d)
135
        count_match = len(list(gm.subgraph_isomorphisms_iter()))
136
        assert_true(count_match == 4)
137

    
138
    def test_timdelta_one_config2_returns_ten_embeddings(self):
139
        G1 = self.provide_g1_topology()
140
        temporal_name = 'date'
141
        G1 = put_time_config_2(G1, temporal_name)
142
        G2 = self.provide_g2_path_3edges()
143
        d = timedelta(days=1)
144
        gm = iso.TimeRespectingGraphMatcher(G1, G2, temporal_name, d)
145
        L = list(gm.subgraph_isomorphisms_iter())
146
        count_match = len(list(gm.subgraph_isomorphisms_iter()))
147
        assert_true(count_match == 10)
148

    
149

    
150
class TestDiTimeRespectingGraphMatcher(object):
151
    """
152
        A test class for the directed time-respecting graph matcher.
153
    """
154

    
155
    def provide_g1_topology(self):
156
        G1 = nx.DiGraph()
157
        G1.add_edges_from(provide_g1_edgelist())
158
        return G1
159

    
160
    def provide_g2_path_3edges(self):
161
        G2 = nx.DiGraph()
162
        G2.add_edges_from([(0, 1), (1, 2), (2, 3)])
163
        return G2
164

    
165
    def test_timdelta_zero_same_dates_returns_true(self):
166
        G1 = self.provide_g1_topology()
167
        temporal_name = 'date'
168
        G1 = put_same_time(G1, temporal_name)
169
        G2 = self.provide_g2_path_3edges()
170
        d = timedelta()
171
        gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d)
172
        assert_true(gm.subgraph_is_isomorphic())
173

    
174
    def test_attNameStrange_timdelta_zero_same_dates_returns_true(self):
175
        G1 = self.provide_g1_topology()
176
        temporal_name = 'strange'
177
        G1 = put_same_time(G1, temporal_name)
178
        G2 = self.provide_g2_path_3edges()
179
        d = timedelta()
180
        gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d)
181
        assert_true(gm.subgraph_is_isomorphic())
182

    
183
    def test_timdelta_one_config0_returns_no_embeddings(self):
184
        G1 = self.provide_g1_topology()
185
        temporal_name = 'date'
186
        G1 = put_time_config_0(G1, temporal_name)
187
        G2 = self.provide_g2_path_3edges()
188
        d = timedelta(days=1)
189
        gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d)
190
        count_match = len(list(gm.subgraph_isomorphisms_iter()))
191
        assert_true(count_match == 0)
192

    
193
    def test_timdelta_one_config1_returns_one_embedding(self):
194
        G1 = self.provide_g1_topology()
195
        temporal_name = 'date'
196
        G1 = put_time_config_1(G1, temporal_name)
197
        G2 = self.provide_g2_path_3edges()
198
        d = timedelta(days=1)
199
        gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d)
200
        count_match = len(list(gm.subgraph_isomorphisms_iter()))
201
        assert_true(count_match == 1)
202

    
203
    def test_timdelta_one_config2_returns_two_embeddings(self):
204
        G1 = self.provide_g1_topology()
205
        temporal_name = 'date'
206
        G1 = put_time_config_2(G1, temporal_name)
207
        G2 = self.provide_g2_path_3edges()
208
        d = timedelta(days=1)
209
        gm = iso.TimeRespectingDiGraphMatcher(G1, G2, temporal_name, d)
210
        count_match = len(list(gm.subgraph_isomorphisms_iter()))
211
        assert_true(count_match == 2)