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