Graph Product¶
Implementation of graph products
Introduction¶
>>> gptest_file = pkg_resources.resource_filename(__name__,"lib/examples/topologies/gptest.graphml")
>>> G_out = graph_product("gptest_file")
Implementation¶
Disable plotting of examples in doctests: >>> plot = lambda x,y: None
Note: add_nodes_from will update the property of a node if it already exists TODO: add example of this
G graph is the undirected base graph
>>> G = nx.Graph()
H graph is the “pop design” graph
Each node u in the graph G has a attribute “H” which specifies the H graph to use
>>> G.add_nodes_from([ ('a', dict(H='style_a')), ('b', dict(H='style_b')), ('c', dict(H='style_c'))])
The ‘H’ attribute of a node in G refers to the key in the ‘H_graphs’ dictionary:
>>> H_graphs = {}
>>> H_graphs['style_a'] = nx.trivial_graph()
>>> plot(H_graphs['style_a'], "style_a")
>>> H_graphs['style_b'] = nx.cycle_graph(2)
>>> plot(H_graphs['style_b'], "style_b")
>>> H_graphs['style_c'] = nx.cycle_graph(3)
>>> plot(H_graphs['style_c'], "style_c")
>>> H_graphs['style_d'] = nx.Graph( [(0,1), (1,2)])
>>> H_graphs['style_d'].add_nodes_from( [(0, dict(root=True))])
>>> plot(H_graphs['style_d'], "style_d")
Edges in the graph G specify edges between pops, and have an operator which specifies the interconnection method (covered below).
Valid operators are cartesian, rooted, strong, or tensor.
>>> G.add_edges_from([('a','b', dict(operator = 'cartesian')), ('a','c', dict(operator = 'rooted')), ('b','c', dict(operator = 'tensor'))])
Nodes in output graph are the tuple (u,v) for u in G for v in G[u][‘H’]
>>> sorted(node_list(G, H_graphs))
[('a', 0), ('b', 0), ('b', 1), ('c', 0), ('c', 1), ('c', 2)]
Examples¶
Using smaller case study for the following examples:
>>> G.clear()
>>> G.add_nodes_from([ ('a', dict(H='style_d')), ('b', dict(H='style_d'))])
>>> G.add_edge( 'a', 'b')
>>> plot(G, "G")
Intra-PoP links¶
Intra PoP links are from the relevant H graph:
>>> sorted(intra_pop_links(G, H_graphs))
[(('a', 0), ('a', 1)), (('a', 1), ('a', 2)), (('b', 0), ('b', 1)), (('b', 1), ('b', 2))]
>>> plot(nx.Graph(intra_pop_links(G, H_graphs)), "intra_pop_links")
Inter-PoP links¶
Cartesian Product¶
>>> G['a']['b']['operator'] = 'cartesian'
>>> inter_pop_links(G, H_graphs)
[(('a', 0), ('b', 0)), (('a', 1), ('b', 1)), (('a', 2), ('b', 2))]
>>> plot(nx.Graph(inter_pop_links(G, H_graphs)), "cartesian")
Rooted Product¶
>>> G['a']['b']['operator'] = 'rooted'
>>> inter_pop_links(G, H_graphs)
[(('a', 0), ('b', 0))]
>>> plot(nx.Graph(inter_pop_links(G, H_graphs)), "rooted")
Lexical Product¶
>>> G['a']['b']['operator'] = 'lexical'
>>> inter_pop_links(G, H_graphs)
[(('a', 0), ('b', 0)), (('a', 0), ('b', 1)), (('a', 0), ('b', 2)), (('a', 1), ('b', 0)), (('a', 1), ('b', 1)), (('a', 1), ('b', 2)), (('a', 2), ('b', 0)), (('a', 2), ('b', 1)), (('a', 2), ('b', 2))]
>>> plot(nx.Graph(inter_pop_links(G, H_graphs)), "lexical")
Tensor Product¶
>>> G['a']['b']['operator'] = 'tensor'
>>> inter_pop_links(G, H_graphs)
[(('a', 0), ('b', 1)), (('a', 1), ('b', 0)), (('a', 1), ('b', 2)), (('a', 2), ('b', 1))]
>>> plot(nx.Graph(inter_pop_links(G, H_graphs)), "tensor")
Strong Product¶
>>> G['a']['b']['operator'] = 'strong'
>>> inter_pop_links(G, H_graphs)
[(('a', 0), ('b', 0)), (('a', 1), ('b', 1)), (('a', 2), ('b', 2)), (('a', 0), ('b', 1)), (('a', 1), ('b', 0)), (('a', 1), ('b', 2)), (('a', 2), ('b', 1))]
>>> plot(nx.Graph(inter_pop_links(G, H_graphs)), "strong")
Combined¶
Intra and Inter pop links can be combined:
>>> G['a']['b']['operator'] = 'cartesian'
>>> edge_list = intra_pop_links(G, H_graphs) + inter_pop_links(G, H_graphs)
>>> plot(nx.Graph(edge_list), "combined")
Attributes¶
The above code generates the list of nodes and the list of edges in the new graph. They do not contain attributes. The node and edge attributes are copied from the relevant G and H graphs using the rules defined in the following sections.
Node Attributes¶
Nodes in AutoNetkit can have attributes. A number of attributes carry special meaning, such as pop and asn, but the user is free to add their own attributes. These attributes are preserved from the G and H graphs.
For attributes that exist in both the H graph and the G graph, the attribute in the H graph is used. This is the idea of inheritance - the H graph is more specific.
Attributes associated with the graph products, such as H and root are not propagated to the output graph, as they are used in the generation process, but are not relevant to AutoNetkit. If the user wishes for a specific attribute to be in the output graph, they should add that to the relevant node.
Example¶
Add some extra attributes to the G graph defined above:
>>> G.add_nodes_from([ ('a', dict(color='red')), ('b', dict(color='blue'))])
>>> G.nodes(data=True)
[('a', {'color': 'red', 'H': 'style_d'}), ('b', {'color': 'blue', 'H': 'style_d'})]
>>> propagate_node_attributes(G, H_graphs, node_list(G, H_graphs))
[(('a', 0), {'x_pos': 0, 'color': 'red', 'pop': 'a', 'label': 'a0', 'y_pos': 0}), (('a', 1), {'x_pos': 100, 'color': 'red', 'pop': 'a', 'label': 'a1', 'y_pos': 0}), (('a', 2), {'x_pos': 0, 'color': 'red', 'pop': 'a', 'label': 'a2', 'y_pos': 100}), (('b', 0), {'x_pos': 0, 'color': 'blue', 'pop': 'b', 'label': 'b0', 'y_pos': 3}), (('b', 1), {'x_pos': 100, 'color': 'blue', 'pop': 'b', 'label': 'b1', 'y_pos': 3}), (('b', 2), {'x_pos': 0, 'color': 'blue', 'pop': 'b', 'label': 'b2', 'y_pos': 103})]
>>> G.add_nodes_from([ ('a', dict(color='red', H='style_e')), ('b', dict(color='blue', H='style_e'))])
>>> G.nodes(data=True)
[('a', {'color': 'red', 'H': 'style_e'}), ('b', {'color': 'blue', 'H': 'style_e'})]
Define a new H graph with some attributes. This shows the color attribute from the H graph over-writing that of the G graph. It can be seen that node (‘a’, 1) and (‘b’, 1) both have the color green from the H graph.
>>> H_graphs['style_e'] = H_graphs['style_d'].copy()
>>> H_graphs['style_e'].add_nodes_from( [(1, dict(color='green'))])
>>> H_graphs['style_e'].nodes(data=True)
[(0, {'root': True}), (1, {'color': 'green'}), (2, {})]
>>> propagate_node_attributes(G, H_graphs, node_list(G, H_graphs))
[(('a', 0), {'x_pos': 0, 'color': 'red', 'pop': 'a', 'label': 'a0', 'y_pos': 0}), (('a', 1), {'x_pos': 100, 'color': 'green', 'pop': 'a', 'label': 'a1', 'y_pos': 0}), (('a', 2), {'x_pos': 0, 'color': 'red', 'pop': 'a', 'label': 'a2', 'y_pos': 100}), (('b', 0), {'x_pos': 0, 'color': 'blue', 'pop': 'b', 'label': 'b0', 'y_pos': 3}), (('b', 1), {'x_pos': 100, 'color': 'green', 'pop': 'b', 'label': 'b1', 'y_pos': 3}), (('b', 2), {'x_pos': 0, 'color': 'blue', 'pop': 'b', 'label': 'b2', 'y_pos': 103})]
Edge Attributes¶
Edge attributes are simpler. Inter-Pop links obtain their data from the G graph. Intra-Pop links obtain their data from their H graph.
Example¶
For clarity, use the cartesian operator:
>>> G['a']['b']['operator'] = 'cartesian'
Add a new attribute to the edge in the G graph:
>>> G.add_edges_from( [('a', 'b', dict(speed=10))])
>>> G.edges(data=True)
[('a', 'b', {'operator': 'cartesian', 'speed': 10})]
>>> edge_list = intra_pop_links(G, H_graphs) + inter_pop_links(G, H_graphs)
>>> H_graphs['style_f'] = H_graphs['style_d'].copy()
>>> H_graphs['style_f'].add_edges_from([ (0, 1, dict(speed=100)), (1, 2, dict(speed=150))])
>>> H_graphs['style_f'].edges(data=True)
[(0, 1, {'speed': 100}), (1, 2, {'speed': 150})]
And use the new H style:
>>> G.add_nodes_from([ ('a', dict(H='style_f')), ('b', dict(H='style_f'))])
>>> propagate_edge_attributes(G, H_graphs, edge_list)
[(('a', 0), ('a', 1), {'speed': 100}), (('a', 1), ('a', 2), {'speed': 150}), (('b', 0), ('b', 1), {'speed': 100}), (('b', 1), ('b', 2), {'speed': 150}), (('a', 0), ('b', 0), {'speed': 10}), (('a', 1), ('b', 1), {'speed': 10}), (('a', 2), ('b', 2), {'speed': 10})]
>>> plot(nx.Graph(propagate_edge_attributes(G, H_graphs, edge_list)), "edge_attributes")
