Skip to main content

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 graph
    • directed: 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 graph

    • name: Unique identification to the vertex inside the graph
    • value: optional value to the vertex
  • gp.get_vertex(name) or gp[name]: return the vertex from the graph

    • name: 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 vertex

    • vtx: vertex you want to know the adjacent
  • gp.remove_vertex(vertex_to_remove): Remove a vertex and all the connections he have

    • vertex_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


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

graphpython-0.83.tar.gz (6.4 kB view details)

Uploaded Source

Built Distribution

graphpython-0.83-py3-none-any.whl (8.3 kB view details)

Uploaded Python 3

File details

Details for the file graphpython-0.83.tar.gz.

File metadata

  • Download URL: graphpython-0.83.tar.gz
  • Upload date:
  • Size: 6.4 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/1.11.0 pkginfo/1.4.2 requests/2.19.1 setuptools/40.2.0 requests-toolbelt/0.8.0 tqdm/4.25.0 CPython/3.6.5

File hashes

Hashes for graphpython-0.83.tar.gz
Algorithm Hash digest
SHA256 617ad3c4602d9d5f0cb13f9db245975d823b8751292a2a17d6c99bb9927dda8b
MD5 71cc166bdc92ca763c06e95e7f9e6263
BLAKE2b-256 0fcf39aa3211db3362334df12c44a57c40a8f5b8fc40a55a8d379c3c56c18d32

See more details on using hashes here.

File details

Details for the file graphpython-0.83-py3-none-any.whl.

File metadata

  • Download URL: graphpython-0.83-py3-none-any.whl
  • Upload date:
  • Size: 8.3 kB
  • Tags: Python 3
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/1.11.0 pkginfo/1.4.2 requests/2.19.1 setuptools/40.2.0 requests-toolbelt/0.8.0 tqdm/4.25.0 CPython/3.6.5

File hashes

Hashes for graphpython-0.83-py3-none-any.whl
Algorithm Hash digest
SHA256 f505a5d185a41906e47ada57b30a039e8a46909c01c50e25f583334c19e103cd
MD5 646a0f2cb48333ee8cafe2abe9e1ec94
BLAKE2b-256 101d61642fe7f6b8daafd53b403a51e467f23249a465457ecbd01c343916cea2

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page