How to Read Line From Txt as Matrix in Python
Last week I wrote how to represent graph structure as adjacency listing. This week time has come to describe how we tin can represent graphs in a a matrix representation.
Our requirements (the same as previous calendar week):
- small amount of code (we desire to code information technology fast on algorithmic contest)
- ability to alter our construction dynamically (nosotros want to add some edges or vertices after graph initialization)
- graph is undirected (for each two vertices there tin can be at virtually one border and edges don't have directions)
Graph as matrix in Python
Graph represented as a matrix is a structure which is usually represented by a \(2\)-dimensional assortment (tabular array) indexed with vertices. Value in cell described by row-vertex and column-vertex corresponds to an border. So for graph from this picture show:
nosotros can represent it by an assortment like this:
| # jail cell | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 1 | one | 1 |
| B | 1 | 0 | 0 | 0 |
| C | ane | 0 | 0 | one |
| D | ane | 0 | ane | 0 |
For example \(cell[A][B] = one\), because at that place is an edge between \(A\) and \(B\), \(cell[B][D] = 0\), because there is no edge betwixt \(B\) and \(D\).
In C++ we tin can easily stand for such structure using \(2\)-dimensional arrays (std::vector is better than regular array):
std :: vector < std :: vector < int >> graph ; Of course then we accept to initialize every cell in our array:
// graph initializing for ( int i = 0 ; i < number_of_vertices ; i ++ ) { graph . push_back ( vector < int > ()); // adding an empty rows } for ( int j = 0 ; j < number_of_vertices ; j ++ ) { for ( int i = 0 ; i < graph . size (); i ++ ) { graph [ i ]. push_back ( i * j ); // add columns to rows } } // adding an edge example (nosotros need to add both ends): graph [ 2 ][ 3 ] = one ; graph [ iii ][ ii ] = i ; In Python a list is an equivalent of an array. The about obvious implementation of a structure could look like this:
class ListGraph ( object ): def __init__ ( self , number_of_vertices ): self . matrix = [[ 0 ] * number_of_vertices for _ in range ( number_of_vertices )] def add_edge ( self , v1 , v2 ): self . matrix [ v1 ][ v2 ] = 1 cocky . matrix [ v2 ][ v1 ] = ane It seems in Python nosotros can initialize this structure in much shorter way (actually in one line - look at __init__). For this implementation nosotros need \(O(|V| ^ two)\) memory, where \(|V|\) is number of vertices. Of course every bit graph is undirected we can skip one-half of this array, because we duplicate edge data, just I'm not going to cover it in this postal service, because for Python I've a better solution. And then, think about this question:
Is there a way to omit information about not existing edges?
And now think about dict.
Using dict for matrix graph implementation
Ok, so we want to store our graph-matrix in a dict. As information technology'south a key-value store, we want to know what data to shop in keys and what value should they have. Every bit nosotros still want to be able to write something like this: graph[i][j] to access an edge it becomes articulate that values are edges and equally keys we should accept pairs of vertices. And then allow's utilize tuple of vertices as keys!
graph = {} # yep, that'south it - we don't need to initialize whole structure # add edge graph [( 2 , 3 )] = 1 # or anything what is not None graph [( 3 , two )] = 1 graph [( iii , 2 )] # it'due south i graph [( 0 , 1 )] # it'south None, so there is no edge between 0, ane That'south information technology! When at that place is an edge between two vertices we will accept a not None value otherwise None. For sparse graphs we can relieve a lot of memory here, because we volition actually use \(|E| * 2\) where \(|E|\) is number of edges. Of course, we are unable to tell easily how many vertices our graph has (we have to check all keys). If nosotros demand this kind of data we can create a more sophisticated implementation:
class DictGraph ( dict ): def __init__ ( cocky , vertices ): self . vertices = vertices # vertices is a list or set def add_edge ( cocky , v1 , v2 ): if v1 in cocky . vertices and v2 in self . vertices : self [( v1 , v2 )] = ane cocky [( v2 , v1 )] = 1 Class DictGraph derives from dict, and so we still can use it equally dictionary, but we have too a list of vertices. Now it'south easy to check if vertex is in our graph - it's enough that we check if it'due south in vertices list.
Comparision of dict and list graph implementations
Adding a vertex
Let'due south meet how to add a vertex in both dict and list implementations mentioned above.
Adding a vertex in listing implementation
grade ListGraph ( object ): # ... def add_vertex ( self ): self . number_of_vertices += 1 for vertices in self . matrix : vertices . append ( 0 ) self . matrix . suspend ([ 0 ] * self . number_of_vertices ) To add a vertex \(v\) we demand to add to our matrix new cavalcade and new row. So nosotros take to iterate over all vertices lists and append \(v\) there (you can remember nigh it as adding a new column). Next nosotros have to create an array of vertices for \(5\) (adding a new row). Time complexity is \(O(|5|)\). We also need about \(2 * |V|\) space.
Calculation a vertex in dict implementation
class DictGraph ( dict ): # ... def add_vertex ( self , 5 ): self . vertices . append ( five ) Hither we take to append a vertex \(v\) to vertices listing (if we use i, it's not necessary). Equally it doesn't take any edges with other vertices it doesn't require whatever activity. Necessary time: \(O(1)\) (worst case is \(O(|V|)\), space is \(O(ane)\).
Removing an border
In both implementation it's like shooting fish in a barrel:
Removing an edge in list implementation
class ListGraph ( object ): # ... def remove_edge ( cocky , v1 , v2 ): self . matrix [ v1 ][ v2 ] = 0 self . matrix [ v2 ][ v1 ] = 0 Just put \(0\) in both ends of border. Time \(O(ane)\). We don't save any space.
Removing an edge in dict implementation
class DictGraph ( dict ): # ... def remove_edge ( self , v1 , v2 ): del cocky [( v1 , v2 )] del self [( v2 , v1 )] Here we can actually delete both ends of edge from dictionary. Time \(O(i)\), saving a piddling of space.
Removing a vertex
Removing a vertex is more complicated, especially in list implementation.
Removing a vertex in listing implementation
class ListGraph ( object ): # ... def remove_vertex ( self , v ): for vertices in self . matrix : vertices . remove ( vertices [ v ]) cocky . matrix . remove ( self . matrix [ v ]) cocky . number_of_vertices -= 1 To remove vertex \(five\) nosotros take to remove its column and row in a table. So we have iterate over all vertices lists, remove vertex \(five\) from them (removing a column), finally remove whole list corresponding to this vertex (removing row). Time complexity is \(O(|Five|)\).
Removing a vertex in dict implementation
course DictGraph ( dict ): # ... def remove_vertex ( self , 5 ): keys = list ( self . keys ()) for v1 , v2 in keys : if v1 == v or v2 == v and self . get (( v1 , v2 )): del self [( v1 , v2 )] self . vertices . remove ( v ) To remove vertex \(v\) from dictionary graph we demand to remove all its edges, and so nosotros have to to cheque all keys (tuple of two vertices) and if whatsoever of them has \(5\) remove it - it is removing an edge. After that we demand to remove \(5\) from vertices listing if we use it. Fourth dimension complexity is \(O(|E|)\), because we iterate over all edges, not vertices. Really for dense graphs it is worse than in listing implementation.
Summing up
Information technology seems that except removing a vertex in dense graphs, dict implementation of graph-matrix is much meliorate than list implementation. It saves much more space, because information technology doesn't need to save information most non-existing edges. Also for me information technology's much more than readable, considering it allows usage of any kind of names for vertices - you can name them using numbers, letters, whatever you want (as long equally you don't add the same vertex twice, amend to check it before adding?). Dictionaries in Python are really powerful - they are implemented as hash tables that's mode it has actually adept time complexities for dictionary operations.
You can find code of both implementations and some tests as examples of usage here: gist. Hopefully y'all enjoyed reading about this approach for implementing graph structure. Let me know your thoughts or remarks in comments!
Source: https://vevurka.github.io/dsp17/python/cs/graph_in_python_matrix/
0 Response to "How to Read Line From Txt as Matrix in Python"
Post a Comment