graph_intersection

graph_tool.generation.graph_intersection(g1, g2, eweight1=None, eweight2=None, vmap='identity', props=[], mt='set', internal_props=False, in_place=False, **kwargs)

Return a graph containing the intersection of the edges of graphs g1 and g2.

Parameters:

g1Graph

Graph to be subtracted from.

g2Graph

Graph to be compared to.

eweight1EdgePropertyMap (optional, default: None)

If provided, this will determine the weights of the edges of graph g1. If not provided, each edge will be assumed to have unity weight.

eweight2EdgePropertyMap (optional, default: None)

If provided, this will determine the weights of the edges of graph g2. If not provided, each edge will be assumed to have unity weight.

vmapVertexPropertyMap, "identity", or None (optional, default: None)

Vertex property map owned by g2 which maps each of its vertices to vertex indices belonging to g1, in which case they are considered to be identical. Negative values mean no mapping exists, and thus both vertices in g1 and g2 will be present in the intersection graph. If this argument is not provided (i.e. vmap is None), both vertex sets will be added to the intersection. If vmap is g2.vertex_index, and the vertex indexes are identical in both graphs, the intersection will correspond only to the edge sets. A special value of vmap == "identity" is a shortcut for vmap = g2.vertex_index.

propslist of tuples of PropertyMap (optional, default: [])

Property maps to be included in the intersection. Each element of th list must be a pair of PropertyMap objects. The first element must be a property of g1, and the second of g2. If either value is None, an new map will be created, and set to appropriately empty values.

mtstr (otional, default: "set")

Merge rule for property values. Should be one of "set", "sum", "diff", "idx_inc", "append", "concat". See graph_merge() for further documentation.

internal_propsbool (optional, default: False)

If True all internal property maps of g1 and g2 will be included in the intersection.

in_placebool (optional, default: False)

If True, the intersection is obtained in-place by subtracting edges from g1, which is then modified. If False, a new graph is created, and both graphs remain unmodified.

**kwargsdict (optional, default: {})

Remaining keyword parameters will be forwarded to graph_merge().

Returns:

ugGraph

The intersection graph.

wEdgePropertyMap

The edge weights of the intersection graph. This is only returned if eweight1 is not None.

propslist of PropertyMap objects

List of properties in the merged graph. This is only returned if props is not empty. Internal property maps are not included in this list.

See also

graph_merge

Merge the edge sets between two graphs.

graph_union

Union of the edge sets between two graphs.

graph_difference

Difference of the edge sets between two graphs.

graph_sym_difference

Symmetrcic difference of the edge sets between two graphs.

Notes

This algorithm is a wrapper around graph_merge(), and shares with it the same algorithmic complexity.

Parallel implementation.

If enabled during compilation, this algorithm will run in parallel using OpenMP. See the parallel algorithms section for information about how to control several aspects of parallelization.

Examples

>>> g = gt.collection.ns["lesmis"]
>>> u1 = gt.GraphView(g, efilt=np.random.random(g.num_edges()) < .5)
>>> u2 = gt.GraphView(g, efilt=np.random.random(g.num_edges()) < .5)
>>> u = gt.graph_intersection(u1, u2)
>>> gt.graph_draw(u1, pos=g.vp._pos, output="gsub1_int.pdf")
<...>
>>> gt.graph_draw(u2, pos=g.vp._pos, output="gsub2_int.pdf")
<...>
>>> gt.graph_draw(u, pos=g.vp._pos, output="gint.pdf")
<...>