Statistics
| Branch: | Revision:

## iof-tools / networkxMiCe / networkx-master / networkx / generators / line.py @ 5cef0f13

 1 ```# Copyright (C) 2013-2019 by ``` ```# Aric Hagberg ``` ```# Dan Schult ``` ```# Pieter Swart ``` ```# All rights reserved. ``` ```# BSD license. ``` ```# ``` ```# Authors: James Clough ``` ```# Aric Hagberg ``` ```# Pieter Swart ``` ```# Dan Schult ``` ```# chebee7i ``` ```"""Functions for generating line graphs.""" ``` ```from itertools import combinations ``` ```from collections import defaultdict ``` ```import networkx as nx ``` ```from networkx.utils import arbitrary_element ``` ```from networkx.utils.decorators import * ``` ```__all__ = ['line_graph', 'inverse_line_graph'] ``` ```def line_graph(G, create_using=None): ``` ``` r"""Returns the line graph of the graph or digraph `G`. ``` ``` ``` ``` The line graph of a graph `G` has a node for each edge in `G` and an ``` ``` edge joining those nodes if the two edges in `G` share a common node. For ``` ``` directed graphs, nodes are adjacent exactly when the edges they represent ``` ``` form a directed path of length two. ``` ``` ``` ``` The nodes of the line graph are 2-tuples of nodes in the original graph (or ``` ``` 3-tuples for multigraphs, with the key of the edge as the third element). ``` ``` ``` ``` For information about self-loops and more discussion, see the **Notes** ``` ``` section below. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` A NetworkX Graph, DiGraph, MultiGraph, or MultiDigraph. ``` ``` create_using : NetworkX graph constructor, optional (default=nx.Graph) ``` ``` Graph type to create. If graph instance, then cleared before populated. ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` L : graph ``` ``` The line graph of G. ``` ``` ``` ``` Examples ``` ``` -------- ``` ``` >>> import networkx as nx ``` ``` >>> G = nx.star_graph(3) ``` ``` >>> L = nx.line_graph(G) ``` ``` >>> print(sorted(map(sorted, L.edges()))) # makes a 3-clique, K3 ``` ``` [[(0, 1), (0, 2)], [(0, 1), (0, 3)], [(0, 2), (0, 3)]] ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` Graph, node, and edge data are not propagated to the new graph. For ``` ``` undirected graphs, the nodes in G must be sortable, otherwise the ``` ``` constructed line graph may not be correct. ``` ``` ``` ``` *Self-loops in undirected graphs* ``` ``` ``` ``` For an undirected graph `G` without multiple edges, each edge can be ``` ``` written as a set `\{u, v\}`. Its line graph `L` has the edges of `G` as ``` ``` its nodes. If `x` and `y` are two nodes in `L`, then `\{x, y\}` is an edge ``` ``` in `L` if and only if the intersection of `x` and `y` is nonempty. Thus, ``` ``` the set of all edges is determined by the set of all pairwise intersections ``` ``` of edges in `G`. ``` ``` ``` ``` Trivially, every edge in G would have a nonzero intersection with itself, ``` ``` and so every node in `L` should have a self-loop. This is not so ``` ``` interesting, and the original context of line graphs was with simple ``` ``` graphs, which had no self-loops or multiple edges. The line graph was also ``` ``` meant to be a simple graph and thus, self-loops in `L` are not part of the ``` ``` standard definition of a line graph. In a pairwise intersection matrix, ``` ``` this is analogous to excluding the diagonal entries from the line graph ``` ``` definition. ``` ``` ``` ``` Self-loops and multiple edges in `G` add nodes to `L` in a natural way, and ``` ``` do not require any fundamental changes to the definition. It might be ``` ``` argued that the self-loops we excluded before should now be included. ``` ``` However, the self-loops are still "trivial" in some sense and thus, are ``` ``` usually excluded. ``` ``` ``` ``` *Self-loops in directed graphs* ``` ``` ``` ``` For a directed graph `G` without multiple edges, each edge can be written ``` ``` as a tuple `(u, v)`. Its line graph `L` has the edges of `G` as its ``` ``` nodes. If `x` and `y` are two nodes in `L`, then `(x, y)` is an edge in `L` ``` ``` if and only if the tail of `x` matches the head of `y`, for example, if `x ``` ``` = (a, b)` and `y = (b, c)` for some vertices `a`, `b`, and `c` in `G`. ``` ``` ``` ``` Due to the directed nature of the edges, it is no longer the case that ``` ``` every edge in `G` should have a self-loop in `L`. Now, the only time ``` ``` self-loops arise is if a node in `G` itself has a self-loop. So such ``` ``` self-loops are no longer "trivial" but instead, represent essential ``` ``` features of the topology of `G`. For this reason, the historical ``` ``` development of line digraphs is such that self-loops are included. When the ``` ``` graph `G` has multiple edges, once again only superficial changes are ``` ``` required to the definition. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` * Harary, Frank, and Norman, Robert Z., "Some properties of line digraphs", ``` ``` Rend. Circ. Mat. Palermo, II. Ser. 9 (1960), 161--168. ``` ``` * Hemminger, R. L.; Beineke, L. W. (1978), "Line graphs and line digraphs", ``` ``` in Beineke, L. W.; Wilson, R. J., Selected Topics in Graph Theory, ``` ``` Academic Press Inc., pp. 271--305. ``` ``` ``` ``` """ ``` ``` if G.is_directed(): ``` ``` L = _lg_directed(G, create_using=create_using) ``` ``` else: ``` ``` L = _lg_undirected(G, selfloops=False, create_using=create_using) ``` ``` return L ``` ```def _node_func(G): ``` ``` """Returns a function which returns a sorted node for line graphs. ``` ``` ``` ``` When constructing a line graph for undirected graphs, we must normalize ``` ``` the ordering of nodes as they appear in the edge. ``` ``` ``` ``` """ ``` ``` if G.is_multigraph(): ``` ``` def sorted_node(u, v, key): ``` ``` return (u, v, key) if u <= v else (v, u, key) ``` ``` else: ``` ``` def sorted_node(u, v): ``` ``` return (u, v) if u <= v else (v, u) ``` ``` return sorted_node ``` ```def _edge_func(G): ``` ``` """Returns the edges from G, handling keys for multigraphs as necessary. ``` ``` ``` ``` """ ``` ``` if G.is_multigraph(): ``` ``` def get_edges(nbunch=None): ``` ``` return G.edges(nbunch, keys=True) ``` ``` else: ``` ``` def get_edges(nbunch=None): ``` ``` return G.edges(nbunch) ``` ``` return get_edges ``` ```def _sorted_edge(u, v): ``` ``` """Returns a sorted edge. ``` ``` ``` ``` During the construction of a line graph for undirected graphs, the data ``` ``` structure can be a multigraph even though the line graph will never have ``` ``` multiple edges between its nodes. For this reason, we must make sure not ``` ``` to add any edge more than once. This requires that we build up a list of ``` ``` edges to add and then remove all duplicates. And so, we must normalize ``` ``` the representation of the edges. ``` ``` ``` ``` """ ``` ``` return (u, v) if u <= v else (v, u) ``` ```def _lg_directed(G, create_using=None): ``` ``` """Returns the line graph L of the (multi)digraph G. ``` ``` ``` ``` Edges in G appear as nodes in L, represented as tuples of the form (u,v) ``` ``` or (u,v,key) if G is a multidigraph. A node in L corresponding to the edge ``` ``` (u,v) is connected to every node corresponding to an edge (v,w). ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : digraph ``` ``` A directed graph or directed multigraph. ``` ``` create_using : NetworkX graph constructor, optional ``` ``` Graph type to create. If graph instance, then cleared before populated. ``` ``` Default is to use the same graph class as `G`. ``` ``` ``` ``` """ ``` ``` L = nx.empty_graph(0, create_using, default=G.__class__) ``` ``` # Create a graph specific edge function. ``` ``` get_edges = _edge_func(G) ``` ``` for from_node in get_edges(): ``` ``` # from_node is: (u,v) or (u,v,key) ``` ``` L.add_node(from_node) ``` ``` for to_node in get_edges(from_node): ``` ``` L.add_edge(from_node, to_node) ``` ``` return L ``` ```def _lg_undirected(G, selfloops=False, create_using=None): ``` ``` """Returns the line graph L of the (multi)graph G. ``` ``` ``` ``` Edges in G appear as nodes in L, represented as sorted tuples of the form ``` ``` (u,v), or (u,v,key) if G is a multigraph. A node in L corresponding to ``` ``` the edge {u,v} is connected to every node corresponding to an edge that ``` ``` involves u or v. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` An undirected graph or multigraph. ``` ``` selfloops : bool ``` ``` If `True`, then self-loops are included in the line graph. If `False`, ``` ``` they are excluded. ``` ``` create_using : NetworkX graph constructor, optional (default=nx.Graph) ``` ``` Graph type to create. If graph instance, then cleared before populated. ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` The standard algorithm for line graphs of undirected graphs does not ``` ``` produce self-loops. ``` ``` ``` ``` """ ``` ``` L = nx.empty_graph(0, create_using, default=G.__class__) ``` ``` # Graph specific functions for edges and sorted nodes. ``` ``` get_edges = _edge_func(G) ``` ``` sorted_node = _node_func(G) ``` ``` # Determine if we include self-loops or not. ``` ``` shift = 0 if selfloops else 1 ``` ``` edges = set([]) ``` ``` for u in G: ``` ``` # Label nodes as a sorted tuple of nodes in original graph. ``` ``` nodes = [sorted_node(*x) for x in get_edges(u)] ``` ``` if len(nodes) == 1: ``` ``` # Then the edge will be an isolated node in L. ``` ``` L.add_node(nodes) ``` ``` # Add a clique of `nodes` to graph. To prevent double adding edges, ``` ``` # especially important for multigraphs, we store the edges in ``` ``` # canonical form in a set. ``` ``` for i, a in enumerate(nodes): ``` ``` edges.update([_sorted_edge(a, b) for b in nodes[i + shift:]]) ``` ``` L.add_edges_from(edges) ``` ``` return L ``` ```@not_implemented_for('directed') ``` ```@not_implemented_for('multigraph') ``` ```def inverse_line_graph(G): ``` ``` """ Returns the inverse line graph of graph G. ``` ``` ``` ``` If H is a graph, and G is the line graph of H, such that H = L(G). ``` ``` Then H is the inverse line graph of G. ``` ``` ``` ``` Not all graphs are line graphs and these do not have an inverse line graph. ``` ``` In these cases this generator returns a NetworkXError. ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : graph ``` ``` A NetworkX Graph ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` H : graph ``` ``` The inverse line graph of G. ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXNotImplemented ``` ``` If G is directed or a multigraph ``` ``` ``` ``` NetworkXError ``` ``` If G is not a line graph ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` This is an implementation of the Roussopoulos algorithm. ``` ``` ``` ``` References ``` ``` ---------- ``` ``` * Roussopolous, N, "A max {m, n} algorithm for determining the graph H from ``` ``` its line graph G", Information Processing Letters 2, (1973), 108--112. ``` ``` ``` ``` """ ``` ``` if G.number_of_edges() == 0 or G.number_of_nodes() == 0: ``` ``` msg = "G is not a line graph (has zero vertices or edges)" ``` ``` raise nx.NetworkXError(msg) ``` ``` starting_cell = _select_starting_cell(G) ``` ``` P = _find_partition(G, starting_cell) ``` ``` # count how many times each vertex appears in the partition set ``` ``` P_count = {u: 0 for u in G.nodes()} ``` ``` for p in P: ``` ``` for u in p: ``` ``` P_count[u] += 1 ``` ``` if max(P_count.values()) > 2: ``` ``` msg = "G is not a line graph (vertex found in more " \ ``` ``` "than two partition cells)" ``` ``` raise nx.NetworkXError(msg) ``` ``` W = tuple([(u,) for u in P_count if P_count[u] == 1]) ``` ``` H = nx.Graph() ``` ``` H.add_nodes_from(P) ``` ``` H.add_nodes_from(W) ``` ``` for a, b in combinations(H.nodes(), 2): ``` ``` if len(set(a).intersection(set(b))) > 0: ``` ``` H.add_edge(a, b) ``` ``` return H ``` ```def _triangles(G, e): ``` ``` """ Return list of all triangles containing edge e""" ``` ``` u, v = e ``` ``` if u not in G: ``` ``` raise nx.NetworkXError("Vertex %s not in graph" % u) ``` ``` if v not in G.neighbors(u): ``` ``` raise nx.NetworkXError("Edge (%s, %s) not in graph" % (u, v)) ``` ``` triangle_list = [] ``` ``` for x in G.neighbors(u): ``` ``` if x in G.neighbors(v): ``` ``` triangle_list.append((u, v, x)) ``` ``` return triangle_list ``` ```def _odd_triangle(G, T): ``` ``` """ Test whether T is an odd triangle in G ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` T : 3-tuple of vertices forming triangle in G ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` True is T is an odd triangle ``` ``` False otherwise ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXError ``` ``` T is not a triangle in G ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` An odd triangle is one in which there exists another vertex in G which is ``` ``` adjacent to either exactly one or exactly all three of the vertices in the ``` ``` triangle. ``` ``` ``` ``` """ ``` ``` for u in T: ``` ``` if u not in G.nodes(): ``` ``` raise nx.NetworkXError("Vertex %s not in graph" % u) ``` ``` for e in list(combinations(T, 2)): ``` ``` if e not in G.neighbors(e): ``` ``` raise nx.NetworkXError("Edge (%s, %s) not in graph" % (e, e)) ``` ``` T_neighbors = defaultdict(int) ``` ``` for t in T: ``` ``` for v in G.neighbors(t): ``` ``` if v not in T: ``` ``` T_neighbors[v] += 1 ``` ``` for v in T_neighbors: ``` ``` if T_neighbors[v] in [1, 3]: ``` ``` return True ``` ``` return False ``` ```def _find_partition(G, starting_cell): ``` ``` """ Find a partition of the vertices of G into cells of complete graphs ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` starting_cell : tuple of vertices in G which form a cell ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` List of tuples of vertices of G ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXError ``` ``` If a cell is not a complete subgraph then G is not a line graph ``` ``` """ ``` ``` G_partition = G.copy() ``` ``` P = [starting_cell] # partition set ``` ``` G_partition.remove_edges_from(list(combinations(starting_cell, 2))) ``` ``` # keep list of partitioned nodes which might have an edge in G_partition ``` ``` partitioned_vertices = list(starting_cell) ``` ``` while G_partition.number_of_edges() > 0: ``` ``` # there are still edges left and so more cells to be made ``` ``` u = partitioned_vertices[-1] ``` ``` deg_u = len(G_partition[u]) ``` ``` if deg_u == 0: ``` ``` # if u has no edges left in G_partition then we have found ``` ``` # all of its cells so we do not need to keep looking ``` ``` partitioned_vertices.pop() ``` ``` else: ``` ``` # if u still has edges then we need to find its other cell ``` ``` # this other cell must be a complete subgraph or else G is ``` ``` # not a line graph ``` ``` new_cell = [u] + list(G_partition.neighbors(u)) ``` ``` for u in new_cell: ``` ``` for v in new_cell: ``` ``` if (u != v) and (v not in G.neighbors(u)): ``` ``` msg = "G is not a line graph" \ ``` ``` "(partition cell not a complete subgraph)" ``` ``` raise nx.NetworkXError(msg) ``` ``` P.append(tuple(new_cell)) ``` ``` G_partition.remove_edges_from(list(combinations(new_cell, 2))) ``` ``` partitioned_vertices += new_cell ``` ``` return P ``` ```def _select_starting_cell(G, starting_edge=None): ``` ``` """ Select a cell to initiate _find_partition ``` ``` ``` ``` Parameters ``` ``` ---------- ``` ``` G : NetworkX Graph ``` ``` starting_edge: an edge to build the starting cell from ``` ``` ``` ``` Returns ``` ``` ------- ``` ``` Tuple of vertices in G ``` ``` ``` ``` Raises ``` ``` ------ ``` ``` NetworkXError ``` ``` If it is determined that G is not a line graph ``` ``` ``` ``` Notes ``` ``` ----- ``` ``` If starting edge not specified then pick an arbitrary edge - doesn't ``` ``` matter which. However, this function may call itself requiring a ``` ``` specific starting edge. Note that the r, s notation for counting ``` ``` triangles is the same as in the Roussopoulos paper cited above. ``` ``` """ ``` ``` if starting_edge is None: ``` ``` e = arbitrary_element(list(G.edges())) ``` ``` else: ``` ``` e = starting_edge ``` ``` if e not in G[e]: ``` ``` msg = 'starting_edge (%s, %s) is not in the Graph' ``` ``` raise nx.NetworkXError(msg % e) ``` ``` e_triangles = _triangles(G, e) ``` ``` r = len(e_triangles) ``` ``` if r == 0: ``` ``` # there are no triangles containing e, so the starting cell is just e ``` ``` starting_cell = e ``` ``` elif r == 1: ``` ``` # there is exactly one triangle, T, containing e. If other 2 edges ``` ``` # of T belong only to this triangle then T is starting cell ``` ``` T = e_triangles ``` ``` a, b, c = T ``` ``` # ab was original edge so check the other 2 edges ``` ``` ac_edges = [x for x in _triangles(G, (a, c))] ``` ``` bc_edges = [x for x in _triangles(G, (b, c))] ``` ``` if len(ac_edges) == 1: ``` ``` if len(bc_edges) == 1: ``` ``` starting_cell = T ``` ``` else: ``` ``` return _select_starting_cell(G, starting_edge=(b, c)) ``` ``` else: ``` ``` return _select_starting_cell(G, starting_edge=(a, c)) ``` ``` else: ``` ``` # r >= 2 so we need to count the number of odd triangles, s ``` ``` s = 0 ``` ``` odd_triangles = [] ``` ``` for T in e_triangles: ``` ``` if _odd_triangle(G, T): ``` ``` s += 1 ``` ``` odd_triangles.append(T) ``` ``` if r == 2 and s == 0: ``` ``` # in this case either triangle works, so just use T ``` ``` starting_cell = T ``` ``` elif r - 1 <= s <= r: ``` ``` # check if odd triangles containing e form complete subgraph ``` ``` # there must be exactly s+2 of them ``` ``` # and they must all be connected ``` ``` triangle_nodes = set([]) ``` ``` for T in odd_triangles: ``` ``` for x in T: ``` ``` triangle_nodes.add(x) ``` ``` if len(triangle_nodes) == s + 2: ``` ``` for u in triangle_nodes: ``` ``` for v in triangle_nodes: ``` ``` if u != v and (v not in G.neighbors(u)): ``` ``` msg = "G is not a line graph (odd triangles " \ ``` ``` "do not form complete subgraph)" ``` ``` raise nx.NetworkXError(msg) ``` ``` # otherwise then we can use this as the starting cell ``` ``` starting_cell = tuple(triangle_nodes) ``` ``` else: ``` ``` msg = "G is not a line graph (odd triangles " \ ``` ``` "do not form complete subgraph)" ``` ``` raise nx.NetworkXError(msg) ``` ``` else: ``` ``` msg = "G is not a line graph (incorrect number of " \ ``` ``` "odd triangles around starting edge)" ``` ``` raise nx.NetworkXError(msg) ``` ``` return starting_cell ```