NetworkX-based graphs

NetworkX-based in-memory graph objects.

This module implements data structures wrapping the networkx.DiGraph class.

class regraph.backends.networkx.graphs.NXGraph(incoming_graph_data=None, **attr)

Wrapper for NetworkX directed graphs.

Methods

add_edge(self, s, t[, attrs])	Add an edge to a graph.
add_node(self, node_id[, attrs])	Abstract method for adding a node.
adj_dict_factory	alias of builtins.dict
copy(graph)	Copy the input graph object.
edges(self[, data])	Return the list of edges.
find_matching(self, pattern[, nodes, …])	Find matching of a pattern in a graph.
get_edge(self, s, t)	Get edge attributes.
get_node(self, n)	Get node attributes.
get_relabeled_graph(self, mapping)	Return a graph with node labeling specified in the mapping.
node_dict_factory	alias of builtins.dict
nodes(self[, data])	Return the list of nodes.
predecessors(self, node_id)	Return the set of predecessors.
remove_edge(self, s, t)	Remove edge from the graph.
remove_node(self, node_id)	Remove node.
subgraph(self, nodes)	Get a subgraph induced by the collection of nodes.
successors(self, node_id)	Return the set of successors.
update_edge_attrs(self, s, t, attrs[, normalize])	Update attributes of a node.
update_node_attrs(self, node_id, attrs[, …])	Update attributes of a node.

add_edge(self, s, t, attrs=None, **attr)

Add an edge to a graph.

Parameters

graphnetworkx.(Di)Graph

shashable, source node id.

thashable, target node id.

attrsdict

Edge attributes.

add_node(self, node_id, attrs=None)

Abstract method for adding a node.

Parameters

node_idhashable

Prefix that is prepended to the new unique name.

attrsdict, optional

Node attributes.

adj_dict_factory

alias of builtins.dict

classmethod copy(graph)

Copy the input graph object.

edges(self, data=False)

Return the list of edges.

find_matching(self, pattern, nodes=None, graph_typing=None, pattern_typing=None)

Find matching of a pattern in a graph.

This function takes as an input a graph and a pattern, optionally, it also takes a collection of nodes specifying the subgraph of the original graph, where the matching should be searched in, then it searches for a matching of the pattern inside of the graph (or induced subragh), which corresponds to solving subgraph matching problem. The matching is defined by a map from the nodes of the pattern to the nodes of the graph such that:

• edges are preserved, i.e. if there is an edge between nodes n1 and n2 in the pattern, there is an edge between the nodes of the graph that correspond to the image of n1 and n2, moreover, the attribute dictionary of the edge between n1 and n2 is the subdictiotary of the edge it corresponds to in the graph;

• the attribute dictionary of a pattern node is a subdictionary of its image in the graph;

Uses networkx.isomorphism.(Di)GraphMatcher class, which implements subgraph matching algorithm.

In addition, two parameters graph_typing and pattern_typing can be specified. They restrict the space of admisible solutions by checking if an isomorphic subgraph found in the input graph respects the provided pattern typings according to the specified graph typings.

Parameters

graphnx.(Di)Graph

patternnx.(Di)Graph

Pattern graph to search for

nodesiterable, optional

Subset of nodes to search for matching

graph_typingdict of dict, optional

Dictionary defining typing of graph nodes

pattern_typingdict of dict, optional

Dictionary definiting typing of pattern nodes

Returns

instanceslist of dict’s

List of instances of matching found in the graph, every instance is represented with a dictionary where keys are nodes of the pattern, and values are corresponding nodes of the graph.

get_edge(self, s, t)

Get edge attributes.

Parameters

graphnetworkx.(Di)Graph

shashable, source node id.

thashable, target node id.

get_node(self, n)

Get node attributes.

Parameters

nhashable

Node id.

get_relabeled_graph(self, mapping)

Return a graph with node labeling specified in the mapping.

Parameters

graphnetworkx.(Di)Graph

mapping: dict

A dictionary with keys being old node ids and their values being new id’s of the respective nodes.

Returns

gnetworkx.(Di)Graph

New graph object isomorphic to the graph with the relabled nodes.

Raises

ReGraphError

If new id’s do not define a set of distinct node id’s.

See also

regraph.primitives.relabel_nodes

node_dict_factory

alias of builtins.dict

nodes(self, data=False)

Return the list of nodes.

predecessors(self, node_id)

Return the set of predecessors.

remove_edge(self, s, t)

Remove edge from the graph.

Parameters

graphnetworkx.(Di)Graph

shashable, source node id.

thashable, target node id.

remove_node(self, node_id)

Remove node.

Parameters

graphnetworkx.(Di)Graph

node_idhashable, node to remove.

subgraph(self, nodes)

Get a subgraph induced by the collection of nodes.

successors(self, node_id)

Return the set of successors.

update_edge_attrs(self, s, t, attrs, normalize=True)

Update attributes of a node.

Parameters

shashable, source node of the edge to update.

thashable, target node of the edge to update.

attrsdict

New attributes to assign to the node

update_node_attrs(self, node_id, attrs, normalize=True)

Update attributes of a node.

Parameters

node_idhashable, node to update.

attrsdict

New attributes to assign to the node