Compose two graphs as binary relations

Relational composition of two graph.

Usage

compose(g1, g2, byname = "auto")

Arguments

g1

The first input graph.

g2

The second input graph.

byname

A logical scalar, or the character scalar auto. Whether to perform the operation based on symbolic vertex names. If it is auto, that means TRUE if both graphs are named and FALSE otherwise. A warning is generated if auto and one graph, but not both graphs are named.

Value

A new graph object.

Details

compose() creates the relational composition of two graphs. The new graph will contain an (a,b) edge only if there is a vertex c, such that edge (a,c) is included in the first graph and (c,b) is included in the second graph. The corresponding operator is %c%.

The function gives an error if one of the input graphs is directed and the other is undirected.

If the byname argument is TRUE (or auto and the graphs are all named), then the operation is performed based on symbolic vertex names. Otherwise numeric vertex ids are used.

compose() keeps the attributes of both graphs. All graph, vertex and edge attributes are copied to the result. If an attribute is present in multiple graphs and would result a name clash, then this attribute is renamed by adding suffixes: _1, _2, etc.

The name vertex attribute is treated specially if the operation is performed based on symbolic vertex names. In this case name must be present in both graphs, and it is not renamed in the result graph.

Note that an edge in the result graph corresponds to two edges in the input, one in the first graph, one in the second. This mapping is not injective and several edges in the result might correspond to the same edge in the first (and/or the second) graph. The edge attributes in the result graph are updated accordingly.

Also note that the function may generate multigraphs, if there are more than one way to find edges (a,b) in g1 and (b,c) in g2 for an edge (a,c) in the result. See simplify() if you want to get rid of the multiple edges.

The function may create loop edges, if edges (a,b) and (b,a) are present in g1 and g2, respectively, then (a,a) is included in the result. See simplify() if you want to get rid of the self-loops.

See also

Other functions for manipulating graph structure: +.igraph(), add_edges(), add_vertices(), complementer(), connect(), contract(), delete_edges(), delete_vertices(), difference(), difference.igraph(), disjoint_union(), edge(), igraph-minus, intersection(), intersection.igraph(), path(), permute(), rep.igraph(), reverse_edges(), simplify(), union(), union.igraph(), vertex()

Author

Gabor Csardi csardi.gabor@gmail.com

Examples

g1 <- make_ring(10)
g2 <- make_star(10, mode = "undirected")
gc <- compose(g1, g2)
print_all(gc)
#> IGRAPH ea6d82a U--- 10 36 -- 
#> + attr: name_1 (g/c), name_2 (g/c), mutual (g/l), circular (g/l), mode
#> | (g/c), center (g/n)
#> + edges:
#>  1 --  1  1  1  1  2  3  3  4  4  5  5  6  6  7  7  8  8  9  9 10
#>  2 --  1  2  2  3  4  5  6  7  8  9 10 10
#>  3 --  1  1  2 10
#>  4 --  1  1  2 10
#>  5 --  1  1  2 10
#>  6 --  1  1  2 10
#>  7 --  1  1  2 10
#>  8 --  1  1  2 10
#>  9 --  1  1  2 10
#> 10 --  1  2  2  3  4  5  6  7  8  9 10 10
print_all(simplify(gc))
#> IGRAPH ef5bb54 U--- 10 24 -- 
#> + attr: name_1 (g/c), name_2 (g/c), mutual (g/l), circular (g/l), mode
#> | (g/c), center (g/n)
#> + edges:
#>  1 --  2  3  4  5  6  7  8  9 10    2 --  1  3  4  5  6  7  8  9 10
#>  3 --  1  2 10                      4 --  1  2 10                  
#>  5 --  1  2 10                      6 --  1  2 10                  
#>  7 --  1  2 10                      8 --  1  2 10                  
#>  9 --  1  2 10                     10 --  1  2  3  4  5  6  7  8  9