#!/usr/bin/env python import random from nose.tools import * import networkx as nx from networkx.testing.utils import * class TestFunction(object): def setUp(self): self.G = nx.Graph({0: [1, 2, 3], 1: [1, 2, 0], 4: []}, name='Test') self.Gdegree = {0: 3, 1: 2, 2: 2, 3: 1, 4: 0} self.Gnodes = list(range(5)) self.Gedges = [(0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2)] self.DG = nx.DiGraph({0: [1, 2, 3], 1: [1, 2, 0], 4: []}) self.DGin_degree = {0: 1, 1: 2, 2: 2, 3: 1, 4: 0} self.DGout_degree = {0: 3, 1: 3, 2: 0, 3: 0, 4: 0} self.DGnodes = list(range(5)) self.DGedges = [(0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2)] def test_nodes(self): assert_nodes_equal(self.G.nodes(), list(nx.nodes(self.G))) assert_nodes_equal(self.DG.nodes(), list(nx.nodes(self.DG))) def test_edges(self): assert_edges_equal(self.G.edges(), list(nx.edges(self.G))) assert_equal(sorted(self.DG.edges()), sorted(nx.edges(self.DG))) assert_edges_equal(self.G.edges(nbunch=[0, 1, 3]), list(nx.edges(self.G, nbunch=[0, 1, 3]))) assert_equal(sorted(self.DG.edges(nbunch=[0, 1, 3])), sorted(nx.edges(self.DG, nbunch=[0, 1, 3]))) def test_degree(self): assert_edges_equal(self.G.degree(), list(nx.degree(self.G))) assert_equal(sorted(self.DG.degree()), sorted(nx.degree(self.DG))) assert_edges_equal(self.G.degree(nbunch=[0, 1]), list(nx.degree(self.G, nbunch=[0, 1]))) assert_equal(sorted(self.DG.degree(nbunch=[0, 1])), sorted(nx.degree(self.DG, nbunch=[0, 1]))) assert_edges_equal(self.G.degree(weight='weight'), list(nx.degree(self.G, weight='weight'))) assert_equal(sorted(self.DG.degree(weight='weight')), sorted(nx.degree(self.DG, weight='weight'))) def test_neighbors(self): assert_equal(self.G.neighbors(1), nx.neighbors(self.G, 1)) assert_equal(self.DG.neighbors(1), nx.neighbors(self.DG, 1)) def test_number_of_nodes(self): assert_equal(self.G.number_of_nodes(), nx.number_of_nodes(self.G)) assert_equal(self.DG.number_of_nodes(), nx.number_of_nodes(self.DG)) def test_number_of_edges(self): assert_equal(self.G.number_of_edges(), nx.number_of_edges(self.G)) assert_equal(self.DG.number_of_edges(), nx.number_of_edges(self.DG)) def test_is_directed(self): assert_equal(self.G.is_directed(), nx.is_directed(self.G)) assert_equal(self.DG.is_directed(), nx.is_directed(self.DG)) def test_add_star(self): G = self.G.copy() nlist = [12, 13, 14, 15] nx.add_star(G, nlist) assert_edges_equal(G.edges(nlist), [(12, 13), (12, 14), (12, 15)]) G = self.G.copy() nx.add_star(G, nlist, weight=2.0) assert_edges_equal(G.edges(nlist, data=True), [(12, 13, {'weight': 2.}), (12, 14, {'weight': 2.}), (12, 15, {'weight': 2.})]) def test_add_path(self): G = self.G.copy() nlist = [12, 13, 14, 15] nx.add_path(G, nlist) assert_edges_equal(G.edges(nlist), [(12, 13), (13, 14), (14, 15)]) G = self.G.copy() nx.add_path(G, nlist, weight=2.0) assert_edges_equal(G.edges(nlist, data=True), [(12, 13, {'weight': 2.}), (13, 14, {'weight': 2.}), (14, 15, {'weight': 2.})]) def test_add_cycle(self): G = self.G.copy() nlist = [12, 13, 14, 15] oklists = [[(12, 13), (12, 15), (13, 14), (14, 15)], [(12, 13), (13, 14), (14, 15), (15, 12)]] nx.add_cycle(G, nlist) assert_true(sorted(G.edges(nlist)) in oklists) G = self.G.copy() oklists = [[(12, 13, {'weight': 1.}), (12, 15, {'weight': 1.}), (13, 14, {'weight': 1.}), (14, 15, {'weight': 1.})], [(12, 13, {'weight': 1.}), (13, 14, {'weight': 1.}), (14, 15, {'weight': 1.}), (15, 12, {'weight': 1.})]] nx.add_cycle(G, nlist, weight=1.0) assert_true(sorted(G.edges(nlist, data=True)) in oklists) def test_subgraph(self): assert_equal(self.G.subgraph([0, 1, 2, 4]).adj, nx.subgraph(self.G, [0, 1, 2, 4]).adj) assert_equal(self.DG.subgraph([0, 1, 2, 4]).adj, nx.subgraph(self.DG, [0, 1, 2, 4]).adj) assert_equal(self.G.subgraph([0, 1, 2, 4]).adj, nx.induced_subgraph(self.G, [0, 1, 2, 4]).adj) assert_equal(self.DG.subgraph([0, 1, 2, 4]).adj, nx.induced_subgraph(self.DG, [0, 1, 2, 4]).adj) # subgraph-subgraph chain is allowed in function interface H = nx.induced_subgraph(self.G.subgraph([0, 1, 2, 4]), [0, 1, 4]) assert_is_not(H._graph, self.G) assert_equal(H.adj, self.G.subgraph([0, 1, 4]).adj) def test_edge_subgraph(self): assert_equal(self.G.edge_subgraph([(1, 2), (0, 3)]).adj, nx.edge_subgraph(self.G, [(1, 2), (0, 3)]).adj) assert_equal(self.DG.edge_subgraph([(1, 2), (0, 3)]).adj, nx.edge_subgraph(self.DG, [(1, 2), (0, 3)]).adj) def test_restricted_view(self): H = nx.restricted_view(self.G, [0, 2, 5], [(1, 2), (3, 4)]) assert_equal(set(H.nodes), {1, 3, 4}) assert_equal(set(H.edges), {(1, 1)}) def test_create_empty_copy(self): G = nx.create_empty_copy(self.G, with_data=False) assert_nodes_equal(G, list(self.G)) assert_equal(G.graph, {}) assert_equal(G._node, {}.fromkeys(self.G.nodes(), {})) assert_equal(G._adj, {}.fromkeys(self.G.nodes(), {})) G = nx.create_empty_copy(self.G) assert_nodes_equal(G, list(self.G)) assert_equal(G.graph, self.G.graph) assert_equal(G._node, self.G._node) assert_equal(G._adj, {}.fromkeys(self.G.nodes(), {})) def test_degree_histogram(self): assert_equal(nx.degree_histogram(self.G), [1, 1, 1, 1, 1]) def test_density(self): assert_equal(nx.density(self.G), 0.5) assert_equal(nx.density(self.DG), 0.3) G = nx.Graph() G.add_node(1) assert_equal(nx.density(G), 0.0) def test_density_selfloop(self): G = nx.Graph() G.add_edge(1, 1) assert_equal(nx.density(G), 0.0) G.add_edge(1, 2) assert_equal(nx.density(G), 2.0) def test_freeze(self): G = nx.freeze(self.G) assert_equal(G.frozen, True) assert_raises(nx.NetworkXError, G.add_node, 1) assert_raises(nx.NetworkXError, G.add_nodes_from, [1]) assert_raises(nx.NetworkXError, G.remove_node, 1) assert_raises(nx.NetworkXError, G.remove_nodes_from, [1]) assert_raises(nx.NetworkXError, G.add_edge, 1, 2) assert_raises(nx.NetworkXError, G.add_edges_from, [(1, 2)]) assert_raises(nx.NetworkXError, G.remove_edge, 1, 2) assert_raises(nx.NetworkXError, G.remove_edges_from, [(1, 2)]) assert_raises(nx.NetworkXError, G.clear) def test_is_frozen(self): assert_equal(nx.is_frozen(self.G), False) G = nx.freeze(self.G) assert_equal(G.frozen, nx.is_frozen(self.G)) assert_equal(G.frozen, True) def test_info(self): G = nx.path_graph(5) G.name = "path_graph(5)" info = nx.info(G) expected_graph_info = '\n'.join(['Name: path_graph(5)', 'Type: Graph', 'Number of nodes: 5', 'Number of edges: 4', 'Average degree: 1.6000']) assert_equal(info, expected_graph_info) info = nx.info(G, n=1) expected_node_info = '\n'.join( ['Node 1 has the following properties:', 'Degree: 2', 'Neighbors: 0 2']) assert_equal(info, expected_node_info) def test_info_digraph(self): G = nx.DiGraph(name='path_graph(5)') nx.add_path(G, [0, 1, 2, 3, 4]) info = nx.info(G) expected_graph_info = '\n'.join(['Name: path_graph(5)', 'Type: DiGraph', 'Number of nodes: 5', 'Number of edges: 4', 'Average in degree: 0.8000', 'Average out degree: 0.8000']) assert_equal(info, expected_graph_info) info = nx.info(G, n=1) expected_node_info = '\n'.join( ['Node 1 has the following properties:', 'Degree: 2', 'Neighbors: 2']) assert_equal(info, expected_node_info) assert_raises(nx.NetworkXError, nx.info, G, n=-1) def test_neighbors(self): graph = nx.complete_graph(100) pop = random.sample(list(graph), 1) nbors = list(nx.neighbors(graph, pop[0])) # should be all the other vertices in the graph assert_equal(len(nbors), len(graph) - 1) graph = nx.path_graph(100) node = random.sample(list(graph), 1)[0] nbors = list(nx.neighbors(graph, node)) # should be all the other vertices in the graph if node != 0 and node != 99: assert_equal(len(nbors), 2) else: assert_equal(len(nbors), 1) # create a star graph with 99 outer nodes graph = nx.star_graph(99) nbors = list(nx.neighbors(graph, 0)) assert_equal(len(nbors), 99) def test_non_neighbors(self): graph = nx.complete_graph(100) pop = random.sample(list(graph), 1) nbors = list(nx.non_neighbors(graph, pop[0])) # should be all the other vertices in the graph assert_equal(len(nbors), 0) graph = nx.path_graph(100) node = random.sample(list(graph), 1)[0] nbors = list(nx.non_neighbors(graph, node)) # should be all the other vertices in the graph if node != 0 and node != 99: assert_equal(len(nbors), 97) else: assert_equal(len(nbors), 98) # create a star graph with 99 outer nodes graph = nx.star_graph(99) nbors = list(nx.non_neighbors(graph, 0)) assert_equal(len(nbors), 0) # disconnected graph graph = nx.Graph() graph.add_nodes_from(range(10)) nbors = list(nx.non_neighbors(graph, 0)) assert_equal(len(nbors), 9) def test_non_edges(self): # All possible edges exist graph = nx.complete_graph(5) nedges = list(nx.non_edges(graph)) assert_equal(len(nedges), 0) graph = nx.path_graph(4) expected = [(0, 2), (0, 3), (1, 3)] nedges = list(nx.non_edges(graph)) for (u, v) in expected: assert_true((u, v) in nedges or (v, u) in nedges) graph = nx.star_graph(4) expected = [(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] nedges = list(nx.non_edges(graph)) for (u, v) in expected: assert_true((u, v) in nedges or (v, u) in nedges) # Directed graphs graph = nx.DiGraph() graph.add_edges_from([(0, 2), (2, 0), (2, 1)]) expected = [(0, 1), (1, 0), (1, 2)] nedges = list(nx.non_edges(graph)) for e in expected: assert_true(e in nedges) def test_is_weighted(self): G = nx.Graph() assert_false(nx.is_weighted(G)) G = nx.path_graph(4) assert_false(nx.is_weighted(G)) assert_false(nx.is_weighted(G, (2, 3))) G.add_node(4) G.add_edge(3, 4, weight=4) assert_false(nx.is_weighted(G)) assert_true(nx.is_weighted(G, (3, 4))) G = nx.DiGraph() G.add_weighted_edges_from([('0', '3', 3), ('0', '1', -5), ('1', '0', -5), ('0', '2', 2), ('1', '2', 4), ('2', '3', 1)]) assert_true(nx.is_weighted(G)) assert_true(nx.is_weighted(G, ('1', '0'))) G = G.to_undirected() assert_true(nx.is_weighted(G)) assert_true(nx.is_weighted(G, ('1', '0'))) assert_raises(nx.NetworkXError, nx.is_weighted, G, (1, 2)) def test_is_negatively_weighted(self): G = nx.Graph() assert_false(nx.is_negatively_weighted(G)) G.add_node(1) G.add_nodes_from([2, 3, 4, 5]) assert_false(nx.is_negatively_weighted(G)) G.add_edge(1, 2, weight=4) assert_false(nx.is_negatively_weighted(G, (1, 2))) G.add_edges_from([(1, 3), (2, 4), (2, 6)]) G[1][3]['color'] = 'blue' assert_false(nx.is_negatively_weighted(G)) assert_false(nx.is_negatively_weighted(G, (1, 3))) G[2][4]['weight'] = -2 assert_true(nx.is_negatively_weighted(G, (2, 4))) assert_true(nx.is_negatively_weighted(G)) G = nx.DiGraph() G.add_weighted_edges_from([('0', '3', 3), ('0', '1', -5), ('1', '0', -2), ('0', '2', 2), ('1', '2', -3), ('2', '3', 1)]) assert_true(nx.is_negatively_weighted(G)) assert_false(nx.is_negatively_weighted(G, ('0', '3'))) assert_true(nx.is_negatively_weighted(G, ('1', '0'))) assert_raises(nx.NetworkXError, nx.is_negatively_weighted, G, (1, 4)) class TestCommonNeighbors(): def setUp(self): self.func = nx.common_neighbors def test_func(G, u, v, expected): result = sorted(self.func(G, u, v)) assert_equal(result, expected) self.test = test_func def test_K5(self): G = nx.complete_graph(5) self.test(G, 0, 1, [2, 3, 4]) def test_P3(self): G = nx.path_graph(3) self.test(G, 0, 2, [1]) def test_S4(self): G = nx.star_graph(4) self.test(G, 1, 2, [0]) @raises(nx.NetworkXNotImplemented) def test_digraph(self): G = nx.DiGraph() G.add_edges_from([(0, 1), (1, 2)]) self.func(G, 0, 2) def test_nonexistent_nodes(self): G = nx.complete_graph(5) assert_raises(nx.NetworkXError, nx.common_neighbors, G, 5, 4) assert_raises(nx.NetworkXError, nx.common_neighbors, G, 4, 5) assert_raises(nx.NetworkXError, nx.common_neighbors, G, 5, 6) def test_custom1(self): """Case of no common neighbors.""" G = nx.Graph() G.add_nodes_from([0, 1]) self.test(G, 0, 1, []) def test_custom2(self): """Case of equal nodes.""" G = nx.complete_graph(4) self.test(G, 0, 0, [1, 2, 3]) def test_set_node_attributes(): graphs = [nx.Graph(), nx.DiGraph(), nx.MultiGraph(), nx.MultiDiGraph()] for G in graphs: # Test single value G = nx.path_graph(3, create_using=G) vals = 100 attr = 'hello' nx.set_node_attributes(G, vals, attr) assert_equal(G.nodes[0][attr], vals) assert_equal(G.nodes[1][attr], vals) assert_equal(G.nodes[2][attr], vals) # Test dictionary G = nx.path_graph(3, create_using=G) vals = dict(zip(sorted(G.nodes()), range(len(G)))) attr = 'hi' nx.set_node_attributes(G, vals, attr) assert_equal(G.nodes[0][attr], 0) assert_equal(G.nodes[1][attr], 1) assert_equal(G.nodes[2][attr], 2) # Test dictionary of dictionaries G = nx.path_graph(3, create_using=G) d = {'hi': 0, 'hello': 200} vals = dict.fromkeys(G.nodes(), d) vals.pop(0) nx.set_node_attributes(G, vals) assert_equal(G.nodes[0], {}) assert_equal(G.nodes[1]["hi"], 0) assert_equal(G.nodes[2]["hello"], 200) def test_set_edge_attributes(): graphs = [nx.Graph(), nx.DiGraph()] for G in graphs: # Test single value G = nx.path_graph(3, create_using=G) attr = 'hello' vals = 3 nx.set_edge_attributes(G, vals, attr) assert_equal(G[0][1][attr], vals) assert_equal(G[1][2][attr], vals) # Test multiple values G = nx.path_graph(3, create_using=G) attr = 'hi' edges = [(0, 1), (1, 2)] vals = dict(zip(edges, range(len(edges)))) nx.set_edge_attributes(G, vals, attr) assert_equal(G[0][1][attr], 0) assert_equal(G[1][2][attr], 1) # Test dictionary of dictionaries G = nx.path_graph(3, create_using=G) d = {'hi': 0, 'hello': 200} edges = [(0, 1)] vals = dict.fromkeys(edges, d) nx.set_edge_attributes(G, vals) assert_equal(G[0][1]['hi'], 0) assert_equal(G[0][1]['hello'], 200) assert_equal(G[1][2], {}) def test_set_edge_attributes_multi(): graphs = [nx.MultiGraph(), nx.MultiDiGraph()] for G in graphs: # Test single value G = nx.path_graph(3, create_using=G) attr = 'hello' vals = 3 nx.set_edge_attributes(G, vals, attr) assert_equal(G[0][1][0][attr], vals) assert_equal(G[1][2][0][attr], vals) # Test multiple values G = nx.path_graph(3, create_using=G) attr = 'hi' edges = [(0, 1, 0), (1, 2, 0)] vals = dict(zip(edges, range(len(edges)))) nx.set_edge_attributes(G, vals, attr) assert_equal(G[0][1][0][attr], 0) assert_equal(G[1][2][0][attr], 1) # Test dictionary of dictionaries G = nx.path_graph(3, create_using=G) d = {'hi': 0, 'hello': 200} edges = [(0, 1, 0)] vals = dict.fromkeys(edges, d) nx.set_edge_attributes(G, vals) assert_equal(G[0][1][0]['hi'], 0) assert_equal(G[0][1][0]['hello'], 200) assert_equal(G[1][2][0], {}) def test_get_node_attributes(): graphs = [nx.Graph(), nx.DiGraph(), nx.MultiGraph(), nx.MultiDiGraph()] for G in graphs: G = nx.path_graph(3, create_using=G) attr = 'hello' vals = 100 nx.set_node_attributes(G, vals, attr) attrs = nx.get_node_attributes(G, attr) assert_equal(attrs[0], vals) assert_equal(attrs[1], vals) assert_equal(attrs[2], vals) def test_get_edge_attributes(): graphs = [nx.Graph(), nx.DiGraph(), nx.MultiGraph(), nx.MultiDiGraph()] for G in graphs: G = nx.path_graph(3, create_using=G) attr = 'hello' vals = 100 nx.set_edge_attributes(G, vals, attr) attrs = nx.get_edge_attributes(G, attr) assert_equal(len(attrs), 2) if G.is_multigraph(): keys = [(0, 1, 0), (1, 2, 0)] for u, v, k in keys: try: assert_equal(attrs[(u, v, k)], 100) except KeyError: assert_equal(attrs[(v, u, k)], 100) else: keys = [(0, 1), (1, 2)] for u, v in keys: try: assert_equal(attrs[(u, v)], 100) except KeyError: assert_equal(attrs[(v, u)], 100) def test_is_empty(): graphs = [nx.Graph(), nx.DiGraph(), nx.MultiGraph(), nx.MultiDiGraph()] for G in graphs: assert_true(nx.is_empty(G)) G.add_nodes_from(range(5)) assert_true(nx.is_empty(G)) G.add_edges_from([(1, 2), (3, 4)]) assert_false(nx.is_empty(G)) def test_selfloops(): graphs = [nx.Graph(), nx.DiGraph(), nx.MultiGraph(), nx.MultiDiGraph()] for graph in graphs: G = nx.complete_graph(3, create_using=graph) G.add_edge(0, 0) assert_nodes_equal(nx.nodes_with_selfloops(G), [0]) assert_edges_equal(nx.selfloop_edges(G), [(0, 0)]) assert_edges_equal(nx.selfloop_edges(G, data=True), [(0, 0, {})]) assert_equal(nx.number_of_selfloops(G), 1) # test selfloop attr G.add_edge(1, 1, weight=2) assert_edges_equal(nx.selfloop_edges(G, data=True), [(0, 0, {}), (1, 1, {'weight': 2})]) assert_edges_equal(nx.selfloop_edges(G, data='weight'), [(0, 0, None), (1, 1, 2)])