1"""Gathers together a collection of helper functions and classes that the library needs, 2but end users won't care about.""" 3 4import copy 5 6from ..classes import UndirectedGraph, DirectedGraph 7 8 9# Graph Conversions 10 11def make_subgraph(graph, vertices, edges): 12 """Converts a subgraph given by a list of vertices and edges into a graph object.""" 13 # Copy the entire graph 14 local_graph = copy.deepcopy(graph) 15 16 # Remove all the edges that aren't in the list 17 edges_to_delete = [x for x in local_graph.get_all_edge_ids() if x not in edges] 18 for e in edges_to_delete: 19 local_graph.delete_edge_by_id(e) 20 21 # Remove all the vertices that aren't in the list 22 nodes_to_delete = [x for x in local_graph.get_all_node_ids() if x not in vertices] 23 for n in nodes_to_delete: 24 local_graph.delete_node(n) 25 26 return local_graph 27 28 29def convert_graph_directed_to_undirected(dg): 30 """Converts a directed graph into an undirected graph. Directed edges are made undirected.""" 31 32 udg = UndirectedGraph() 33 34 # Copy the graph 35 # --Copy nodes 36 # --Copy edges 37 udg.nodes = copy.deepcopy(dg.nodes) 38 udg.edges = copy.deepcopy(dg.edges) 39 udg.next_node_id = dg.next_node_id 40 udg.next_edge_id = dg.next_edge_id 41 42 # Convert the directed edges into undirected edges 43 for edge_id in udg.get_all_edge_ids(): 44 edge = udg.get_edge(edge_id) 45 target_node_id = edge['vertices'][1] 46 target_node = udg.get_node(target_node_id) 47 target_node['edges'].append(edge_id) 48 49 return udg 50 51 52def remove_duplicate_edges_directed(dg): 53 """Removes duplicate edges from a directed graph.""" 54 # With directed edges, we can just hash the to and from node id tuples and if 55 # a node happens to conflict with one that already exists, we delete it 56 57 # --For aesthetic, we sort the edge ids so that lower edge ids are kept 58 lookup = {} 59 edges = sorted(dg.get_all_edge_ids()) 60 for edge_id in edges: 61 e = dg.get_edge(edge_id) 62 tpl = e['vertices'] 63 if tpl in lookup: 64 dg.delete_edge_by_id(edge_id) 65 else: 66 lookup[tpl] = edge_id 67 68 69def remove_duplicate_edges_undirected(udg): 70 """Removes duplicate edges from an undirected graph.""" 71 # With undirected edges, we need to hash both combinations of the to-from node ids, since a-b and b-a are equivalent 72 # --For aesthetic, we sort the edge ids so that lower edges ids are kept 73 lookup = {} 74 edges = sorted(udg.get_all_edge_ids()) 75 for edge_id in edges: 76 e = udg.get_edge(edge_id) 77 tpl_a = e['vertices'] 78 tpl_b = (tpl_a[1], tpl_a[0]) 79 if tpl_a in lookup or tpl_b in lookup: 80 udg.delete_edge_by_id(edge_id) 81 else: 82 lookup[tpl_a] = edge_id 83 lookup[tpl_b] = edge_id 84 85 86def get_vertices_from_edge_list(graph, edge_list): 87 """Transforms a list of edges into a list of the nodes those edges connect. 88 Returns a list of nodes, or an empty list if given an empty list. 89 """ 90 node_set = set() 91 for edge_id in edge_list: 92 edge = graph.get_edge(edge_id) 93 a, b = edge['vertices'] 94 node_set.add(a) 95 node_set.add(b) 96 97 return list(node_set) 98 99 100def get_subgraph_from_edge_list(graph, edge_list): 101 """Transforms a list of edges into a subgraph.""" 102 node_list = get_vertices_from_edge_list(graph, edge_list) 103 subgraph = make_subgraph(graph, node_list, edge_list) 104 105 return subgraph 106 107 108def merge_graphs(main_graph, addition_graph): 109 """Merges an ''addition_graph'' into the ''main_graph''. 110 Returns a tuple of dictionaries, mapping old node ids and edge ids to new ids. 111 """ 112 113 node_mapping = {} 114 edge_mapping = {} 115 116 for node in addition_graph.get_all_node_objects(): 117 node_id = node['id'] 118 new_id = main_graph.new_node() 119 node_mapping[node_id] = new_id 120 121 for edge in addition_graph.get_all_edge_objects(): 122 edge_id = edge['id'] 123 old_vertex_a_id, old_vertex_b_id = edge['vertices'] 124 new_vertex_a_id = node_mapping[old_vertex_a_id] 125 new_vertex_b_id = node_mapping[old_vertex_b_id] 126 new_edge_id = main_graph.new_edge(new_vertex_a_id, new_vertex_b_id) 127 edge_mapping[edge_id] = new_edge_id 128 129 return node_mapping, edge_mapping 130 131 132def create_graph_from_adjacency_matrix(adjacency_matrix): 133 """Generates a graph from an adjacency matrix specification. 134 Returns a tuple containing the graph and a list-mapping of node ids to matrix column indices. 135 136 The graph will be an UndirectedGraph if the provided adjacency matrix is symmetric. 137 The graph will be a DirectedGraph if the provided adjacency matrix is not symmetric. 138 Ref: http://mathworld.wolfram.com/AdjacencyMatrix.html""" 139 if is_adjacency_matrix_symmetric(adjacency_matrix): 140 graph = UndirectedGraph() 141 else: 142 graph = DirectedGraph() 143 144 node_column_mapping = [] 145 146 num_columns = len(adjacency_matrix) 147 for _ in range(num_columns): 148 node_id = graph.new_node() 149 node_column_mapping.append(node_id) 150 151 for j in range(num_columns): 152 for i in range(num_columns): 153 if adjacency_matrix[j][i]: 154 jnode_id = node_column_mapping[j] 155 inode_id = node_column_mapping[i] 156 # Because of our adjacency matrix encoding, [j][i] in our code corresponds to [i][j] in a traditional matrix interpretation 157 # Thus, we need to put an edge from node i to node j if [j][i] in our code is non-zero 158 graph.new_edge(inode_id, jnode_id) 159 160 return (graph, node_column_mapping) 161 162 163def is_adjacency_matrix_symmetric(adjacency_matrix): 164 """Determines if an adjacency matrix is symmetric. 165 Ref: http://mathworld.wolfram.com/SymmetricMatrix.html""" 166 # Verify that the matrix is square 167 num_columns = len(adjacency_matrix) 168 for column in adjacency_matrix: 169 # In a square matrix, every row should be the same length as the number of columns 170 if len(column) != num_columns: 171 return False 172 173 # Loop through the bottom half of the matrix and compare it to the top half 174 # --We do the bottom half because of how we construct adjacency matrices 175 max_i = 0 176 for j in range(num_columns): 177 for i in range(max_i): 178 # If i == j, we can skip ahead so we don't compare with ourself 179 if i == j: 180 continue 181 # Compare the value in the bottom half with the mirrored value in the top half 182 # If they aren't the same, the matrix isn't symmetric 183 if adjacency_matrix[j][i] != adjacency_matrix[i][j]: 184 return False 185 max_i += 1 186 187 # If we reach this far without returning false, then we know that everything matched, 188 # which makes this a symmetric matrix 189 return True 190 191