package to manipulate graphs
Project description
graphpy
This is a package for the manipulation of graphs made for a class of graphs in the Brazilian university 'Universidade Tecnologica Federal do Paraná'
Installation
pip install graphpython
Complete Documentation
Graph
to use this class, the main element is Graph class
. With this class, you will be able to fill the graph with vertex and edges and do all the necessary operations
Graph([directed])
: create a graphdirected
: Defaults to False. tells if the graph is directed or not
Code example
# Create a new graph
from graphpy.graph import Graph
gp = Graph()
# add a new vertex
gp.add_vertex('vertex1')
# to get the create vertex, you can use the [] operator
vertex1 = gp['vertex1']
Vertex operations
The base of all graph is the vertex, to create a new vertex you got to use the follow functions
-
gp.add_vertex(name, [value])
: create a new vertex and insert to the graphname
: Unique identification to the vertex inside the graphvalue
: optional value to the vertex
-
gp.get_vertex(name)
orgp[name]
: return the vertex from the graphname
: Unique identification to the vertex inside the graph
-
gp.get_all_vertex()
: get a list with all vertex from the graph -
gp.adjacents_vertex(vtx)
: get all adjacent vertex from one vertexvtx
: vertex you want to know the adjacent
-
gp.remove_vertex(vertex_to_remove)
: Remove a vertex and all the connections he havevertex_to_remove
: vertex you want to remove
Code example
from graphpy.graph import Graph
gp = Graph()
gp.add_vertex('01')
gp.remove_vertex(gp['01'])
Search in the graph
The main class has a search method and to use, you need to pass a by params an strategy to make the search.
Implement a new search strategy
In the class has two class strategies already implemented:
- BFSstrategy
- DFSstrategy
from graphpy.graph import Graph
from graphpy.BFSstrategy import BFSstrategy
graph = Graph()
graph.search(BFSstrategy(INITIAL_VERTEX))
To extend all the search types you can create a new strategy extending the SearchStrategy class from search_strategy.
from graphpy.search_strategy import SearchStrategy
class DFSstrategy(SearchStrategy):
def __init__(self):
self.__predecessors = {}
self.__firstSee = {}
self.__close = {}
self.__time = 0
def __dfs_visit(self, vertex):
self.__time = self.__time + 1
self.__firstSee[vertex] = self.__time
vertex.set_color(1)
for adjacent in self.get_adjacent_list()[vertex]:
if adjacent.get_color() == 0:
self.__predecessors[adjacent] = vertex
self.__dfs_visit(adjacent)
vertex.set_color(2)
self.__time += 1
self.__close[vertex] = self.__time
def search(self):
# colors:
# white: not visited
# grey: in the queue
# black: nothing more to do
for key in self.get_adjacent_list():
# set color for all vertices to white
key.set_color(0)
self.__predecessors[key] = None
self.__time = 0
for key in self.get_adjacent_list():
if key.get_color() == 0:
self.__dfs_visit(key)
return self.__firstSee, self.__close, self.__predecessors
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distribution
Hashes for graphpython-0.83-py3-none-any.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f505a5d185a41906e47ada57b30a039e8a46909c01c50e25f583334c19e103cd |
|
MD5 | 646a0f2cb48333ee8cafe2abe9e1ec94 |
|
BLAKE2b-256 | 101d61642fe7f6b8daafd53b403a51e467f23249a465457ecbd01c343916cea2 |