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 or Node 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:
  • nodes (tuple) – pair of nodes defines edge
  • external_node (int or Node) – external node index
  • edge_id (int) – unique edge id, if not given then assigned automatically
  • **kwargs –

    properties of edge and properties config
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.
new_node(node_index, **kwargs)

creates new node with this config with specified node_index and specified node properties in **kwargs.

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 or Edge 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() or PropertiesConfig.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) and GraphState.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. See PropertiesConfig.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:
  • additional_vertices (set) – any additional nodes which will be included to result
  • singular_vertices (set) – nodes that not produce connection between nodes. All edges containing these nodes will be ignored
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 and GraphState object as a first parameter. Additionally one can use Graph.from_str() for creation from GraphState serialized string and given PropertiesConfig.

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 as False.

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. If with_aux_info specified as True 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 added edges_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 and vertex2 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. If with_aux_info specified as True 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. See graphine.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)

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.:

  1. graph_state.filters.connected
  2. graph_state.filters.one_irreducible
  3. graph_state.filters.vertex_irreducible
  4. 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)

Indices and tables