MOAL.data_structures.graphs package¶

Submodules¶

MOAL.data_structures.graphs.adjacency_list module¶

class MOAL.data_structures.graphs.adjacency_list.AbstractGraphList[source]¶

Bases: object

__init__()¶

class MOAL.data_structures.graphs.adjacency_list.AdjacencyList[source]¶

Bases: MOAL.data_structures.graphs.adjacency_list.AbstractGraphList

[Wikipedia] “In graph theory and computer science, an adjacency list representation of a graph is a collection of unordered lists, one for each vertex in the graph. Each list describes the set of neighbors of its vertex. See “Storing a sparse matrix” for an alternative approach.”

__getitem__(node)[source]¶

__setitem__(node, neighbors)[source]¶

__str__()[source]¶

report(vertex)[source]¶

MOAL.data_structures.graphs.adjacency_matrix module¶

class MOAL.data_structures.graphs.adjacency_matrix.AdjacencyMatrix[source]¶

Bases: MOAL.data_structures.graphs.adjacency_matrix.GraphMatrix

[Wikipedia] “In mathematics and computer science, an adjacency matrix is a means of representing which vertices of a graph are adjacent to which other vertices.”

...In other words, it’s another way to represent a graph, very compactly (and thus efficiently), by using a matrix that represents the connections – by mapping the row and column to a specific node (similar technique as a Cayley or multiplication table).

A B C D

A 0 1 1 0 might correspond to: B 1 0 1 1 (row A, col A) = 0, C 1 1 0 0 (row B, col A) = 1, etc... D 1 0 0 0 generally, self referencing nodes are not

represented, but if they are, their value is 2.

class MOAL.data_structures.graphs.adjacency_matrix.GraphMatrix[source]¶

Bases: object

__delitem__(vertex)¶: Deletes a vertex and flips all adjacent connections to off.

__init__()¶: The matrix structure is just a list of lists, where each sublist represents a row. A separate nodes dictionary is used for fast lookups to reference which row/column to look at when doing operations.

e.g. >>> nodes = {‘A’: 0, ‘B’: 1, ... }, >>> matrix = [[0, 1], [1, 0], ...]

__setitem__(new_vertex, connections)¶: Adds a new vertex, and adds any connections that may not exist.

__str__()¶: Visualize the matrix as a table

_add(new_vertex)¶

_add_edge(start, end)¶: Adds an edge

_fill_previous_rows(count)¶: Fill previous rows to ensure the row length is always equal.

_new_row(count)¶

_remove_edge(start, end)¶: Removes an edge

_reorder_dict_indices(vals)¶: Generic reordering function for resetting indices of a given dictionary.

_reorder_edges()¶

_reorder_vertices()¶: Using a dictionary for the label lookup makes setting/getting items very fast, but the downside is that the indices must be re-ordered if any items are deleted. The flip-side then, would be to use a list – but lookups would suffer the same problem – so, the problem is reversed. It could however, be tuned to work either way, depending on access patterns, but that is well beyond the scope here.

_zeros(count)¶

degree(vertex)¶: Another interesting feature of Adjacency matrices is the fact that any row or column summed is automatically the degree of that vertex – magical!

get_column_vals(label)¶: Returns a list of values representing the given labels column values.

get_row_vals(label)¶: Returns the range slice of a given label, representing the row.

has_edge(start, end)¶

MOAL.data_structures.graphs.binary_decision_diagram module¶

MOAL.data_structures.graphs.graph_structured_stack module¶

MOAL.data_structures.graphs.graphs module¶

MOAL.data_structures.graphs.hypergraph module¶

MOAL.data_structures.graphs.incidence_matrix module¶

class MOAL.data_structures.graphs.incidence_matrix.IncidenceMatrix[source]¶

Bases: MOAL.data_structures.graphs.adjacency_matrix.GraphMatrix

Unlike the Adjacency matrix, where rows and columns both represent vertices of a graph, and using row, then column to indicate direction, in the incidence matrix, rows represent vertices, and columns represent edges. The incidence matrix is therefore a matrix representation of the number of edge incidences, not necessarily the connections between vertices (hence the names).

0 1 2 3

A 1 0 1 0 B 0 0 1 0 C 0 1 1 0 D 0 0 1 1

__delitem__(vertex)[source]¶

__init__()[source]¶: Here, we keep track of edges/edge count just like vertices/vertex in the adjacency matrix.

__setitem__(new_vertex, edges)[source]¶: Data comes in as im[‘A’] = [0, 1, 2], where A is the vertex, and [0, 1, 2] are the incident edges.

(A) /| 0 1 2

/ | (B) (C) (D)

__str__()[source]¶

_update_row(row_index, edges)[source]¶

class MOAL.data_structures.graphs.incidence_matrix.OrientedIncidenceMatrix[source]¶: Bases: MOAL.data_structures.graphs.incidence_matrix.IncidenceMatrix