Table of Contents

Class: graph ../bkchem/oasa/oasa/graph/graph.py

provides a minimalistic graph implementation suitable for analysis of chemical problems, even if some care was taken to make the graph work with nonsimple graphs, there are cases where it won't!

Base Classes   
object
Methods   
__init__
__str__
add_edge
add_vertex
clean_distance_from_vertices
connect_a_graph
contains_cycle
copy
create_edge
create_graph
create_vertex
deep_copy
defines_connected_subgraph_e
defines_connected_subgraph_v
delete_vertex
disconnect
disconnect_edge
edge_subgraph_to_vertex_subgraph
find_path_between
get_all_cycles
get_all_cycles_e
get_all_cycles_e_old
get_almost_all_cycles_e
get_connected_components
get_degrees
get_diameter
get_disconnected_subgraphs
get_edge_between
get_induced_subgraph_from_vertices
get_neighbors
get_neighbors_indexes
get_new_induced_subgraph
get_pieces_after_edge_removal
get_size_of_pieces_after_edge_removal
get_smallest_independent_cycles
get_smallest_independent_cycles_dangerous_and_cached
get_smallest_independent_cycles_e
insert_a_graph
is_connected
is_cycle
is_edge_a_bridge
is_edge_a_bridge_fast_and_dangerous
is_euler
is_tree
mark_vertices_with_distance_from
reconnect_temporarily_disconnected_edge
reconnect_temporarily_disconnected_edges
remove_vertex
sort_vertices_in_path
temporarily_disconnect_edge
temporarily_strip_bridge_edges
vertex_subgraph_to_edge_subgraph
  __init__ 
__init__ ( self,  vertices=[] )

  __str__ 
__str__ ( self )

  add_edge 
add_edge (
        self,
        v1,
        v2,
        e=None,
        )

adds an edge to a graph connecting vertices v1 and v2, if e argument is not given creates a new one. returns None if operation fails or the edge instance if successful

  add_vertex 
add_vertex ( self,  v=None )

adds a vertex to a graph, if v argument is not given creates a new one. returns None if vertex is already present or the vertex instance if successful

  clean_distance_from_vertices 
clean_distance_from_vertices ( self )

  connect_a_graph 
connect_a_graph (
        self,
        gr,
        v1,
        v2,
        e=None,
        )

gr is a graph, v1 is vertex in self, v2 is vertex in gr, bond is what to use for connection

  contains_cycle 
contains_cycle ( self )

this assumes that the graph is connected

  copy 
copy ( self )

provides a really shallow copy, the vertex and edge objects will remain the same, only the graph itself is different

  create_edge 
create_edge ( self )

  create_graph 
create_graph ( self )

  create_vertex 
create_vertex ( self )

  deep_copy 
deep_copy ( self )

provides a deep copy of the graph. The result is an isomorphic graph, all the used objects are different

  defines_connected_subgraph_e 
defines_connected_subgraph_e ( self,  edges )

  defines_connected_subgraph_v 
defines_connected_subgraph_v ( self,  vertices )

  delete_vertex 
delete_vertex ( self,  v )

  disconnect 
disconnect (
        self,
        v1,
        v2,
        )

disconnects vertices v1 and v2, on success returns the edge

  disconnect_edge 
disconnect_edge ( self,  e )

  edge_subgraph_to_vertex_subgraph 
edge_subgraph_to_vertex_subgraph ( self,  cycle )

  find_path_between 
find_path_between (
        self,
        start,
        end,
        dont_go_through=[],
        )

finds path between two vertices, if dont_go_through is given (as a list of vertices and edges), only paths not containing these vertices will be given (or None is returned if such a path does not exist

  get_all_cycles 
get_all_cycles ( self )

returns all cycles found in the graph as sets of vertices, use get_all_cycles_e to get the edge variant, which is better for building new graphs as the mapping edges => vertices is unambiguous, while edges=>vertices=>edges might include some more edges

  get_all_cycles_e 
get_all_cycles_e ( self )

returns all cycles found in the graph as sets of edges; this version of the algorithm strips all non-cyclic (bridge) edges and then searches for cycles in the rest

  get_all_cycles_e_old 
get_all_cycles_e_old ( self )

returns all cycles found in the graph as sets of edges

  get_almost_all_cycles_e 
get_almost_all_cycles_e ( self )

returns almost all cycles found in the graph as sets of edges this version is not perfect as it sometimes forgets a few rings

  get_connected_components 
get_connected_components ( self )

returns the connected components of graph in a form o list of lists of vertices

  get_degrees 
get_degrees ( self )

returns a generator of degrees, this is useful because for many properties the whole list is not important

  get_diameter 
get_diameter ( self )

  get_disconnected_subgraphs 
get_disconnected_subgraphs ( self )

returns the subgraphs of self, it is dangerous as it reuses the original vertices and edges, therefore it should be used only when the old self is no longer needed.

  get_edge_between 
get_edge_between (
        self,
        v1,
        v2,
        )

takes two vertices

  get_induced_subgraph_from_vertices 
get_induced_subgraph_from_vertices ( self,  vs )

it creates a new graph, however uses the old vertices and edges!

  get_neighbors 
get_neighbors ( self,  v )

Info - available also trough the vertex.get_neighbors()

  get_neighbors_indexes 
get_neighbors_indexes ( self,  v )

  get_new_induced_subgraph 
get_new_induced_subgraph (
        self,
        vertices,
        edges,
        )

returns a induced subgraph that is newly created and can be therefore freely changed without worry about the original.

  get_pieces_after_edge_removal 
get_pieces_after_edge_removal ( self,  e )

  get_size_of_pieces_after_edge_removal 
get_size_of_pieces_after_edge_removal ( self,  e )

  get_smallest_independent_cycles 
get_smallest_independent_cycles ( self )

returns a set of smallest possible independent cycles, other cycles in graph are guaranteed to be combinations of them

  get_smallest_independent_cycles_dangerous_and_cached 
get_smallest_independent_cycles_dangerous_and_cached ( self )

  get_smallest_independent_cycles_e 
get_smallest_independent_cycles_e ( self )

returns a set of smallest possible independent cycles as list of Sets of edges, other cycles in graph are guaranteed to be combinations of them. Gasteiger J. (Editor), Engel T. (Editor), Chemoinformatics : A Textbook, John Wiley & Sons 2001, ISBN 3527306811, 174.

  insert_a_graph 
insert_a_graph ( self,  gr )

inserts all edges and vertices to the graph

  is_connected 
is_connected ( self )

  is_cycle 
is_cycle ( self )

  is_edge_a_bridge 
is_edge_a_bridge ( self,  e )

tells whether an edge is bridge

  is_edge_a_bridge_fast_and_dangerous 
is_edge_a_bridge_fast_and_dangerous ( self,  e )

should be used only in case of repetitive questions for the same edge in cases where no edges are added to the graph between the questions (if brigde==1 the value is stored and returned, which is safe only in case no edges are added)

  is_euler 
is_euler ( self )

  is_tree 
is_tree ( self )

  mark_vertices_with_distance_from 
mark_vertices_with_distance_from ( self,  v )

returns the maximum d

  reconnect_temporarily_disconnected_edge 
reconnect_temporarily_disconnected_edge ( self,  e )

  reconnect_temporarily_disconnected_edges 
reconnect_temporarily_disconnected_edges ( self )

  remove_vertex 
remove_vertex ( self,  v )

  sort_vertices_in_path 
sort_vertices_in_path (
        self,
        path,
        start_from=None,
        )

returns None if there is no path

  temporarily_disconnect_edge 
temporarily_disconnect_edge ( self,  e )

  temporarily_strip_bridge_edges 
temporarily_strip_bridge_edges ( self )

strip all edges that ar ea bridge, thus leaving only the cycles connected

  vertex_subgraph_to_edge_subgraph 
vertex_subgraph_to_edge_subgraph ( self,  cycle )


Table of Contents

This document was automatically generated on Tue Dec 12 13:46:44 2006 by HappyDoc version 2.1