Welcome to GraphState and Graphine documentation!¶
GraphState and Graphine are graph manipulation libraries. The key feature of these libraries is usage of generalization of graph representation offered by B. G. Nickel et al. In this approach graph is represented in some unique ‘canonical’ form that depends only on its combinatorial type. The uniqueness of graph representation gives an efficient way for isomorphism finding, searching for subgraphs and other graph manipulation tasks. Though offered libraries were originally designed for Feynman graphs, they might be useful for more general graph problems.
Properties and its configuration¶
To define edge and node properties behaviour (name, (de)serialization process, directed or undirected (for edge properties only))
PropertiesConfig
and PropertyKey
is used. PropertyKey
defines single type of properties and PropertiesConfig
defines all properties that are contained in graph. Additionally PropertiesConfig
serves as factory object to create edges, nodes
and GraphState
objects.
-
class
graph_state.
PropertiesConfig
(property_order, property_directionality, property_externalizer, property_target)¶ Base factory class to produce
GraphState
,Edge
orNode
objects. Creation of all new instances must be done using this class. Don’t use constructors of these classes directly.-
static
create
(*property_keys)¶ Parameters: property_keys – property keys define properties behaviour. See graph_state_property.PropertyKey
.Returns: properties config created for given keys
-
graph_state_from_str
(string)¶ Returns: GraphState
object for given serialized string corresponding to properties config.
-
new_edge
(nodes, external_node=-1, edge_id=None, **kwargs)¶ Parameters: Returns: new edge represented as
Edge
object
-
classmethod
new_graph_state
(edges)¶ Returns: GraphState
object from given edges and properties config held by these edges.
-
static
-
class
graph_state.
PropertyKey
(name, is_directed=False, is_edge_property=True, externalizer=None)¶ Class defines behaviour of properties that can be assigned to lines or nodes of graph. Any property must have a name that can be used as pseudofield of
Node
orEdge
to access value, for example edge property with name “weight” can be accessed using following code:>>> edge.weight
To emulate directed graphs property can be directed. In this case value of this property MUST have defined
__cmp__()
method:>>> PropertyKey("arrow", is_directed=True, is_edge_property=True, externalizer=ArrowExternalizer())
To create node property
is_edge_property()
parameter must be specified as False>>> node_property = PropertyKey("color", is_edge_property=False, externalizer=ColorExternalizer())
-
class
graph_state.
PropertyExternalizer
¶ Base externalizer (serializer/deserializer) superclass. Any properties externalizer should override this class.
For example to externalize numeric values following implementation can be used:
class IntegerExternalizer(PropertyExternalizer): def serialize(self, obj): return str(obj) def deserialize(self, string): return eval(string)
-
deserialize
(string)¶ Returns: object deserialized from string
-
serialize
(obj)¶ Returns: string serialization of given object
-
Edges and nodes¶
Graph edges and nodes represented using following classes: Edge
and Node
.
Note that you must not use constructor to create instances of this classes. All instances must be produced
using factory methods of PropertiesConfig
instance. Edges and nodes are immutable objects and to ‘change’ them
copy()
method can be used.
-
class
graph_state.
Edge
(nodes, external_node=-1, edge_id=None, **kwargs)¶ Representation of an edge of a graph. Edge could have directed or undirected properties defined by
PropertiesConfig
.-
co_node
(node)¶ Returns: node that complements node given by parameter
-
copy
(node_map=None, **kwargs)¶ Creates a copy of the object with possible change of nodes and possible change of properties.
Parameters: - node_map – dictionary mapping old nodes to new ones. Identity map is assumed for the missed keys.
- **kwargs –
properties that must be replaced for edge copy
Returns: new
Edge
constructed by given rules.
-
is_external
()¶ Returns: if edge is external (has external node)
-
nodes
¶ Returns: nodes of edge
-
-
class
graph_state.
Node
(index, properties)¶ Representation of graph node. Any node has unique integer index to identify node in graph.
Usually to simplify dealing with
Node
implicit conversion to integer is used. It means that node with given index equals to index:>>> assert node.index == node True
This means that for simple cases when nodes don’t have any properties
Node
can be considered as integer number.-
copy
(new_node_index=None, **kwargs)¶ Parameters: - new_node_index (int) – if not None then new index of node will be assigned
- **kwargs –
properties of node to change
-
index
¶ Returns: unique index of Node
-
graph_state.GraphState
¶
graph_state.GraphState
represents graph state (or structure). It can be used to determine isomorphisms of graph, to low-level access
to edges, graph (de)serialization. In other cases it’s useful to use Graph
objects because it provides additional possibilities.
-
class
graph_state.
GraphState
(edges, node_maps=None)¶ Don’t use constructor to create instances directly. Use
PropertiesConfig.graph_state_from_str()
orPropertiesConfig.new_graph_state()
.To access of isomorphisms group of graph call
graph_state.obj.sortings
. It returns all possible isomorphic graphs represented as list of edges.>>> GraphState.from_str("e11|e|", config).sortings [(((0,), ), ((0, 1), ), ((0, 1), ), ((1,), )), (((0,), ), ((0, 1), ), ((0, 1), ), ((1,), ))]
Nodes and edges of graph can be obtained by corresponding properties access:
GraphState.edges
(or iterating over object) andGraphState.nodes
:>>> gs = GraphState.from_str("e11|e|", config) >>> gs.edges (((0,), ), ((0, 1), ), ((0, 1), ), ((1,), )) >>> [e for e in gs] [((0,), ), ((0, 1), ), ((0, 1), ), ((1,), )] >>> gs.nodes [-1, 0, 1]
graph state can be serialized to Nickel string using
str()
function:>>> str(gs) "e11|e|"
-
edges
¶ Returns ordered with Nickel order edges which represents corresponding GraphState.
-
static
from_str
(string, properties_config=None)¶ Creates
graph_state.GraphState
object from Nickel serialized string. SeePropertiesConfig.graph_state_from_str()
.
-
nodes
¶ Returns all internal unique nodes in Nickel order.
-
operations_lib
module¶
operations_lib
provides operations on low-level data structures (list of edges or graph_state.GraphState
).
Usually all operations are produced only using graphine.Graph
objects, but if there is no way to escape low-level data structures or
in case of decreasing of Graph
performance, these functions can be used.
Module provides some useful operations on graphs such obtaining nodes of graph or connected components.
All of functions in module marked with @_graph_state_to_edges_implicit_conversion()
can take list of edges or GraphState
object as parameter as well.
-
graph_state.operations_lib.
edges_for_node
(some_obj, *other_params, **other_kwargs)¶ Returns: only edges that contain node
-
graph_state.operations_lib.
get_bound_vertices
(some_obj, *other_params, **other_kwargs)¶ Returns: non-external nodes of external edges
-
graph_state.operations_lib.
get_connected_components
(edges, additional_vertices=set([]), singular_vertices=set([]))¶ Returns: get lists of connected undirected graph nodes
Parameters:
-
graph_state.operations_lib.
get_external_node
(some_obj, *other_params, **other_kwargs)¶ Method does not check that all edges have same external node and returns
external_node()
field of first occurred edge.Returns: external node for edges
-
graph_state.operations_lib.
get_vertices
(some_obj, *other_params, **other_kwargs)¶ Returns: all nodes including external
-
graph_state.operations_lib.
is_1_irreducible
(some_obj, *other_params, **other_kwargs)¶ Checks that graph is 1-irreducible
-
graph_state.operations_lib.
is_edge_property_fully_none
(some_obj, *other_params, **other_kwargs)¶ Checks that property with given name is None for all edges
-
graph_state.operations_lib.
is_graph_connected
(some_obj, *other_params, **other_kwargs)¶ Checks that graph is connected. See
get_connected_components()
-
graph_state.operations_lib.
is_vertex_irreducible
(some_obj, *other_params, **other_kwargs)¶ Checks that graph is vertex irreducible
-
graph_state.operations_lib.
split_edges_for_node
(some_obj, *other_params, **other_kwargs)¶ Returns: only edges that contain node
Graphine overview¶
graphine.Graph
class is main representation for graph. Full access to graph structure and operations on graph can be
done using this class (use graph_state.GraphState
only for graph serialization/deserializaion tasks).
Several frequently used methods of this class (for ex.: Graph.edges()
, Graph.loops_count
) are cacheable
in hard reference map hidden in Graph
backend.
-
class
graphine.
Graph
(obj, renumbering=True)¶ Graph
object can be created from both list of edges andGraphState
object as a first parameter. Additionally one can useGraph.from_str()
for creation fromGraphState
serialized string and givenPropertiesConfig
.In case of list of edges passed in constructor this list will be processed to list of edges that are relevant to minimal Nickel notation. If you don’t need that then specify
renumbering
parameter asFalse
.-
batch_shrink_to_point
(sub_graphs, with_aux_info=False)¶ Method shrinks given collection of
sub_graphs
(can be edges or graphs) to point and returns shrunk graph. Ifwith_aux_info
specified asTrue
then method returns pair where the first element is shrunk graph but the second are indices of vertices created while shrink operation.
-
change
(edges_to_remove=None, edges_to_add=None, renumbering=True)¶ Returns graph with deleted edges
edges_to_remove
and addededges_to_add
.
-
contains
(other_graph)¶ Returns if graph has given graph as subset of edges.
-
create_vertex_index
()¶ Creates and returns index of vertex that are not occurred among vertex indices of given graph.
-
delete_vertex
(vertex, transform_edges_to_external=False)¶ Deletes vertex from graph and makes all of edges containing specified vertex external.
-
edges
(*params, **kwargs)¶ Returns edges of graph for corresponding
vertex
andvertex2
if specified.>>> Graph.from_str("e11|e|", config).edges(0) [(0, -1), (0, 1), (0, 1)]
>>> Graph.from_str("e11|e|", config).edges(0, 1) [(0, 1), (0, 1)]
-
edges_indices
¶ Returns indices of edges. See
Edge
,Edge.edge_id
.
-
external_edges
¶ Returns external edges of graph. See
external_edges_count
,internal_edges
.
-
external_edges_count
¶ Returns count of external edges. See
external_edges
,external_edges
.
-
external_vertex
¶ Returns external vertex of graph.
-
static
from_str
(string, properties_config=None)¶ Parameters: - string (str.) – GraphState serialized string
- properties_config (
PropertiesConfig
) – valid properties configuration do deserialize string
Returns: constructed
Graph
object
-
get_bound_vertices
(*params, **kwargs)¶ Returns vertices of graph that are bound to external vertex.
-
internal_edges
¶ Returns internal edges of graph. See
external_edges()
,internal_edges_count()
.
-
internal_edges_count
¶ Returns internal edges of graph. See
internal_edges()
.
-
loops_count
¶ Returns count of loops in diagram (graph).
-
shrink_to_point
(edges, with_aux_info=False)¶ Method shrinks given
edges
to point and returns shrunk graph. Ifwith_aux_info
specified asTrue
then method returns pair where the first element is shrunk graph but the second are indices of vertices created while shrink operation.
-
to_graph_state
(*params, **kwargs)¶ Returns
GraphState
of given graph.
-
to_tadpole
()¶ Creates graph copy and removes all external edges from its.
-
vertices
¶ Returns vertices of graph (includes external vertex). See
get_bound_vertices()
.
-
x_relevant_sub_graphs
(filters=[], result_representator=None, cut_edges_to_external=True, exact=True)¶ Parameters: - filters – condition to decide if subgraph is relevant.
filters
is list of filter. Seegraphine.filters
overview. - result_representator – defines representation of returned result. Can be one of:
graphine.Representator.asGraph
(without vertices renumbering and Nickel canonicalization),
graphine.Representator.asMinimalGraph
(graph that has minimal Nickel notation),graphine.Representator.asList
(edges list)Parameters: - cut_edges_to_external – representate edges of vertex included in subgraph that are not included in subgraph as external edges for subgraph
- exact – yield self graph as relevant subgraph
Returns: iterator of relevant subgraph for given condition (filters)
- filters – condition to decide if subgraph is relevant.
-
graphine.filters
module¶
Module provides tools to create relevance filters for graphs that can be used for searching of relevant subgraphs:
>>> graph.x_relevant_sub_graphs(filters=my_filters)
Any filter must be a function with 2 parameters. First is subgraph edges list, second is super graph. Function is responsible
to decide if graph is relevant and returns boolean decision value (True
if subgraph is relevant). Filter function must have
graphine.filters.graph_filter
decorator. To create composite filter +
operator can be used:
>>> composite_filters = connected + vertex_irreducible
Additionally package contains set of predefined filters: for subgraph connectivity, 1-irreducibility etc.:
graph_state.filters.connected
graph_state.filters.one_irreducible
graph_state.filters.vertex_irreducible
graph_state.filters.no_tadpoles
(no tadpoles in co-subgraph)
-
graphine.filters.
graph_filter
(qualifier)¶ Marker decorator for filters.
-
graphine.filters.
has_n_borders
(n)¶ Filter graphs only with
n
count of borders (border vertices)