## File: product.py

package info (click to toggle)
python-networkx 1.7~rc1-3
• links: PTS, VCS
• area: main
• in suites: wheezy
• size: 4,128 kB
• sloc: python: 44,557; makefile: 135
 file content (330 lines) | stat: -rw-r--r-- 10,841 bytes parent folder | download
 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330 """ Graph products. """ # Copyright (C) 2011 by # Aric Hagberg # Dan Schult # Pieter Swart # All rights reserved. # BSD license. import networkx as nx from itertools import product __author__ = """\n""".join(['Aric Hagberg (hagberg@lanl.gov)', 'Pieter Swart (swart@lanl.gov)', 'Dan Schult(dschult@colgate.edu)' 'Ben Edwards(bedwards@cs.unm.edu)']) __all__ = ['tensor_product','cartesian_product', 'lexicographic_product', 'strong_product'] def _dict_product(d1,d2): return dict((k,(d1.get(k),d2.get(k))) for k in set(d1)|set(d2)) # Generators for producting graph products def _node_product(G,H): for u,v in product(G, H): yield ((u,v), _dict_product(G.node[u], H.node[v])) def _directed_edges_cross_edges(G,H): if not G.is_multigraph() and not H.is_multigraph(): for u,v,c in G.edges_iter(data=True): for x,y,d in H.edges_iter(data=True): yield (u,x),(v,y),_dict_product(c,d) if not G.is_multigraph() and H.is_multigraph(): for u,v,c in G.edges_iter(data=True): for x,y,k,d in H.edges_iter(data=True,keys=True): yield (u,x),(v,y),k,_dict_product(c,d) if G.is_multigraph() and not H.is_multigraph(): for u,v,k,c in G.edges_iter(data=True,keys=True): for x,y,d in H.edges_iter(data=True): yield (u,x),(v,y),k,_dict_product(c,d) if G.is_multigraph() and H.is_multigraph(): for u,v,j,c in G.edges_iter(data=True,keys=True): for x,y,k,d in H.edges_iter(data=True,keys=True): yield (u,x),(v,y),(j,k),_dict_product(c,d) def _undirected_edges_cross_edges(G,H): if not G.is_multigraph() and not H.is_multigraph(): for u,v,c in G.edges_iter(data=True): for x,y,d in H.edges_iter(data=True): yield (v,x),(u,y),_dict_product(c,d) if not G.is_multigraph() and H.is_multigraph(): for u,v,c in G.edges_iter(data=True): for x,y,k,d in H.edges_iter(data=True,keys=True): yield (v,x),(u,y),k,_dict_product(c,d) if G.is_multigraph() and not H.is_multigraph(): for u,v,k,c in G.edges_iter(data=True,keys=True): for x,y,d in H.edges_iter(data=True): yield (v,x),(u,y),k,_dict_product(c,d) if G.is_multigraph() and H.is_multigraph(): for u,v,j,c in G.edges_iter(data=True,keys=True): for x,y,k,d in H.edges_iter(data=True,keys=True): yield (v,x),(u,y),(j,k),_dict_product(c,d) def _edges_cross_nodes(G,H): if G.is_multigraph(): for u,v,k,d in G.edges_iter(data=True,keys=True): for x in H: yield (u,x),(v,x),k,d else: for u,v,d in G.edges_iter(data=True): for x in H: if H.is_multigraph(): yield (u,x),(v,x),None,d else: yield (u,x),(v,x),d def _nodes_cross_edges(G,H): if H.is_multigraph(): for x in G: for u,v,k,d in H.edges_iter(data=True,keys=True): yield (x,u),(x,v),k,d else: for x in G: for u,v,d in H.edges_iter(data=True): if G.is_multigraph(): yield (x,u),(x,v),None,d else: yield (x,u),(x,v),d def _edges_cross_nodes_and_nodes(G,H): if G.is_multigraph(): for u,v,k,d in G.edges_iter(data=True,keys=True): for x in H: for y in H: yield (u,x),(v,y),k,d else: for u,v,d in G.edges_iter(data=True): for x in H: for y in H: if H.is_multigraph(): yield (u,x),(v,y),None,d else: yield (u,x),(v,y),d def _init_product_graph(G,H): if not G.is_directed() == H.is_directed(): raise nx.NetworkXError("G and H must be both directed or", "both undirected") if G.is_multigraph() or H.is_multigraph(): GH = nx.MultiGraph() else: GH = nx.Graph() if G.is_directed(): GH = GH.to_directed() return GH def tensor_product(G,H): r"""Return the tensor product of G and H. The tensor product P of the graphs G and H has a node set that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$. P has an edge ((u,v),(x,y)) if and only if (u,v) is an edge in G and (x,y) is an edge in H. Sometimes referred to as the categorical product. Parameters ---------- G, H: graphs Networkx graphs. Returns ------- P: NetworkX graph The tensor product of G and H. P will be a multi-graph if either G or H is a multi-graph. Will be a directed if G and H are directed, and undirected if G and H are undirected. Raises ------ NetworkXError If G and H are not both directed or both undirected. Notes ----- Node attributes in P are two-tuple of the G and H node attributes. Missing attributes are assigned None. For example >>> G = nx.Graph() >>> H = nx.Graph() >>> G.add_node(0,a1=True) >>> H.add_node('a',a2='Spam') >>> P = nx.tensor_product(G,H) >>> P.nodes(data=True) [((0, 'a'), {'a1': (True, None), 'a2': (None, 'Spam')})] Edge attributes and edge keys (for multigraphs) are also copied to the new product graph """ GH = _init_product_graph(G,H) GH.add_nodes_from(_node_product(G,H)) GH.add_edges_from(_directed_edges_cross_edges(G,H)) if not GH.is_directed(): GH.add_edges_from(_undirected_edges_cross_edges(G,H)) GH.name = "Tensor product("+G.name+","+H.name+")" return GH def cartesian_product(G,H): """Return the Cartesian product of G and H. The tensor product P of the graphs G and H has a node set that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$. P has an edge ((u,v),(x,y)) if and only if (u,v) is an edge in G and x==y or and (x,y) is an edge in H and u==v. and (x,y) is an edge in H. Parameters ---------- G, H: graphs Networkx graphs. Returns ------- P: NetworkX graph The Cartesian product of G and H. P will be a multi-graph if either G or H is a multi-graph. Will be a directed if G and H are directed, and undirected if G and H are undirected. Raises ------ NetworkXError If G and H are not both directed or both undirected. Notes ----- Node attributes in P are two-tuple of the G and H node attributes. Missing attributes are assigned None. For example >>> G = nx.Graph() >>> H = nx.Graph() >>> G.add_node(0,a1=True) >>> H.add_node('a',a2='Spam') >>> P = nx.tensor_product(G,H) >>> P.nodes(data=True) [((0, 'a'), {'a1': (True, None), 'a2': (None, 'Spam')})] Edge attributes and edge keys (for multigraphs) are also copied to the new product graph """ if not G.is_directed() == H.is_directed(): raise nx.NetworkXError("G and H must be both directed or", "both undirected") GH = _init_product_graph(G,H) GH.add_nodes_from(_node_product(G,H)) GH.add_edges_from(_edges_cross_nodes(G,H)) GH.add_edges_from(_nodes_cross_edges(G,H)) GH.name = "Cartesian product("+G.name+","+H.name+")" return GH def lexicographic_product(G,H): """Return the lexicographic product of G and H. The lexicographical product P of the graphs G and H has a node set that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$. P has an edge ((u,v),(x,y)) if and only if (u,v) is an edge in G or u==v and (x,y) is an edge in H. Parameters ---------- G, H: graphs Networkx graphs. Returns ------- P: NetworkX graph The Cartesian product of G and H. P will be a multi-graph if either G or H is a multi-graph. Will be a directed if G and H are directed, and undirected if G and H are undirected. Raises ------ NetworkXError If G and H are not both directed or both undirected. Notes ----- Node attributes in P are two-tuple of the G and H node attributes. Missing attributes are assigned None. For example >>> G = nx.Graph() >>> H = nx.Graph() >>> G.add_node(0,a1=True) >>> H.add_node('a',a2='Spam') >>> P = nx.tensor_product(G,H) >>> P.nodes(data=True) [((0, 'a'), {'a1': (True, None), 'a2': (None, 'Spam')})] Edge attributes and edge keys (for multigraphs) are also copied to the new product graph """ GH = _init_product_graph(G,H) GH.add_nodes_from(_node_product(G,H)) # Edges in G regardless of H designation GH.add_edges_from(_edges_cross_nodes_and_nodes(G,H)) # For each x in G, only if there is an edge in H GH.add_edges_from(_nodes_cross_edges(G,H)) GH.name = "Lexographic product("+G.name+","+H.name+")" return GH def strong_product(G,H): """Return the strong product of G and H. The strong product P of the graphs G and H has a node set that is the Cartesian product of the node sets, $V(P)=V(G) \times V(H)$. P has an edge ((u,v),(x,y)) if and only if u==v and (x,y) is an edge in H, or x==y and (u,v) is an edge in G, or (u,v) is an edge in G and (x,y) is an edge in H. Parameters ---------- G, H: graphs Networkx graphs. Returns ------- P: NetworkX graph The Cartesian product of G and H. P will be a multi-graph if either G or H is a multi-graph. Will be a directed if G and H are directed, and undirected if G and H are undirected. Raises ------ NetworkXError If G and H are not both directed or both undirected. Notes ----- Node attributes in P are two-tuple of the G and H node attributes. Missing attributes are assigned None. For example >>> G = nx.Graph() >>> H = nx.Graph() >>> G.add_node(0,a1=True) >>> H.add_node('a',a2='Spam') >>> P = nx.tensor_product(G,H) >>> P.nodes(data=True) [((0, 'a'), {'a1': (True, None), 'a2': (None, 'Spam')})] Edge attributes and edge keys (for multigraphs) are also copied to the new product graph """ GH = _init_product_graph(G,H) GH.add_nodes_from(_node_product(G,H)) GH.add_edges_from(_nodes_cross_edges(G,H)) GH.add_edges_from(_edges_cross_nodes(G,H)) GH.add_edges_from(_directed_edges_cross_edges(G,H)) if not GH.is_directed(): GH.add_edges_from(_undirected_edges_cross_edges(G,H)) GH.name = "Strong product("+G.name+","+H.name+")" return GH