Statistics
| Branch: | Revision:

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

 1 ```""" ``` ``` Tests for VF2 isomorphism algorithm. ``` ```""" ``` ```import os ``` ```import struct ``` ```import random ``` ```from nose.tools import assert_true, assert_equal ``` ```from nose import SkipTest ``` ```import networkx as nx ``` ```from networkx.algorithms import isomorphism as iso ``` ```class TestWikipediaExample(object): ``` ``` # Source: https://en.wikipedia.org/wiki/Graph_isomorphism ``` ``` # Nodes 'a', 'b', 'c' and 'd' form a column. ``` ``` # Nodes 'g', 'h', 'i' and 'j' form a column. ``` ``` g1edges = [['a', 'g'], ['a', 'h'], ['a', 'i'], ``` ``` ['b', 'g'], ['b', 'h'], ['b', 'j'], ``` ``` ['c', 'g'], ['c', 'i'], ['c', 'j'], ``` ``` ['d', 'h'], ['d', 'i'], ['d', 'j']] ``` ``` # Nodes 1,2,3,4 form the clockwise corners of a large square. ``` ``` # Nodes 5,6,7,8 form the clockwise corners of a small square ``` ``` g2edges = [[1, 2], [2, 3], [3, 4], [4, 1], ``` ``` [5, 6], [6, 7], [7, 8], [8, 5], ``` ``` [1, 5], [2, 6], [3, 7], [4, 8]] ``` ``` def test_graph(self): ``` ``` g1 = nx.Graph() ``` ``` g2 = nx.Graph() ``` ``` g1.add_edges_from(self.g1edges) ``` ``` g2.add_edges_from(self.g2edges) ``` ``` gm = iso.GraphMatcher(g1, g2) ``` ``` assert_true(gm.is_isomorphic()) ``` ``` #Just testing some cases ``` ``` assert_true(gm.subgraph_is_monomorphic()) ``` ``` mapping = sorted(gm.mapping.items()) ``` ```# this mapping is only one of the possibilies ``` ```# so this test needs to be reconsidered ``` ```# isomap = [('a', 1), ('b', 6), ('c', 3), ('d', 8), ``` ```# ('g', 2), ('h', 5), ('i', 4), ('j', 7)] ``` ```# assert_equal(mapping, isomap) ``` ``` def test_subgraph(self): ``` ``` g1 = nx.Graph() ``` ``` g2 = nx.Graph() ``` ``` g1.add_edges_from(self.g1edges) ``` ``` g2.add_edges_from(self.g2edges) ``` ``` g3 = g2.subgraph([1, 2, 3, 4]) ``` ``` gm = iso.GraphMatcher(g1, g3) ``` ``` assert_true(gm.subgraph_is_isomorphic()) ``` ``` def test_subgraph_mono(self): ``` ``` g1 = nx.Graph() ``` ``` g2 = nx.Graph() ``` ``` g1.add_edges_from(self.g1edges) ``` ``` g2.add_edges_from([[1, 2], [2, 3], [3, 4]]) ``` ``` gm = iso.GraphMatcher(g1, g2) ``` ``` assert_true(gm.subgraph_is_monomorphic()) ``` ```class TestVF2GraphDB(object): ``` ``` # http://amalfi.dis.unina.it/graph/db/ ``` ``` @staticmethod ``` ``` def create_graph(filename): ``` ``` """Creates a Graph instance from the filename.""" ``` ``` # The file is assumed to be in the format from the VF2 graph database. ``` ``` # Each file is composed of 16-bit numbers (unsigned short int). ``` ``` # So we will want to read 2 bytes at a time. ``` ``` # We can read the number as follows: ``` ``` # number = struct.unpack('