Cographs#
A cograph is a \(P_4\)-free graph, that is a graph without induced path of order 4. Any cograph may be constructed, starting from the single vertex graph, by a sequence of join and disjoint union operations. See the Wikipedia article Cograph for more details on this graph class, and OEIS sequence A000084 to know the number of cographs of order \(n \geq 1\).
This module implements the folowing methods concerning cographs:
Return an iterator over the cographs of order \(n\). |
Methods#
- class sage.graphs.cographs.CoTree(name='root')[source]#
Bases:
object
Generic cotree node.
This data structure is used for the generation of cographs in
cographs()
.- add_child(node)[source]#
Add cotree
node
in the list of children ofself
.INPUT:
node
– a CoTree
EXAMPLES:
sage: from sage.graphs.cographs import CoTree sage: T = CoTree('J') sage: T.add_child(CoTree(1)) sage: T [ J ( 1 ) ]
>>> from sage.all import * >>> from sage.graphs.cographs import CoTree >>> T = CoTree('J') >>> T.add_child(CoTree(Integer(1))) >>> T [ J ( 1 ) ]
- copy_tree(T)[source]#
Make \(T\) a copy of
self
.INPUT:
T
– a CoTree
EXAMPLES:
sage: from sage.graphs.cographs import CoTree sage: T = CoTree('J') sage: T.add_child(CoTree(1)) sage: T.add_child(CoTree(2)) sage: T [ J ( 1 ) ( 2 ) ] sage: B = CoTree('U') sage: T.copy_tree(B) sage: B [ U ( 1 ) ( 2 ) ]
>>> from sage.all import * >>> from sage.graphs.cographs import CoTree >>> T = CoTree('J') >>> T.add_child(CoTree(Integer(1))) >>> T.add_child(CoTree(Integer(2))) >>> T [ J ( 1 ) ( 2 ) ] >>> B = CoTree('U') >>> T.copy_tree(B) >>> B [ U ( 1 ) ( 2 ) ]
- reset_info()[source]#
Reset parameter
info
from all nodes ofself
.EXAMPLES:
sage: from sage.graphs.cographs import CoTree sage: T = CoTree(1) sage: B = CoTree(2) sage: T.add_child(B) sage: C = CoTree(3) sage: B.add_child(C) sage: C.info = 'info' sage: T.reset_info() sage: C.info is None True
>>> from sage.all import * >>> from sage.graphs.cographs import CoTree >>> T = CoTree(Integer(1)) >>> B = CoTree(Integer(2)) >>> T.add_child(B) >>> C = CoTree(Integer(3)) >>> B.add_child(C) >>> C.info = 'info' >>> T.reset_info() >>> C.info is None True
- sage.graphs.cographs.change_label(tree, status, counter)[source]#
Set the names of the nodes of
tree
.This is a helper method to method
cographs()
.The input
tree
is such that each node has as label its number of children. This method changes the label of each node so that a parallel node is labeled ‘U’, a series node is labeled ‘J’ and a leaf node gets a unique number.INPUT:
tree
– the tree to relabelstatus
– boolean; used to to detect series (True
) and parallel (False
) internal nodescounter
– list; the first integer of the list is used to assign a unique number to the leaves of the tree
EXAMPLES:
sage: next(graphs.cographs(4, as_graph=True)).vertices() # indirect doctest [0, 1, 2, 3]
>>> from sage.all import * >>> next(graphs.cographs(Integer(4), as_graph=True)).vertices() # indirect doctest [0, 1, 2, 3]
- sage.graphs.cographs.cographs(n, as_graph=True, immutable=False)[source]#
Return an iterator over the cographs of order \(n\).
A cograph is a \(P_4\)-free graph, that is a graph without induced path of order 4. Any cograph may be constructed, starting from the single vertex graph, by a sequence of
sage.graphs.graph.Graph.join()
andsage.graphs.generic_graph.GenericGraph.disjoint_union()
operations. See the Wikipedia article Cograph for more details.This method implements the generator of all cographs of order \(n\) proposed in [JPD2018]. The algorithm generates one by one every cotree with \(n\) nodes, and each cotree is generated by using its previous cotree. The time to construct the first cotree is \(O(n)\) and the time spent between two consecutive outputs is \(O(n)\). Hence, the overall complexity of the algorithm is \(O(n*M_n)\), where \(n\) is the number of nodes and \(M_n\) is the total number of cographs with \(n\) nodes (see OEIS sequence A000084).
INPUT:
n
– an integer larger or equal to 1as_graph
– boolean (default:True
); whether to return graphs or the tree data structure encoding the graphimmutable
– boolean (default:False
); whether to return an immutable or a mutable graph. This parameter is used only whenas_graph is True
.
EXAMPLES:
The output can be either cotrees or graphs:
sage: for t in graphs.cographs(3, as_graph=False): ....: print(t) [ J ( 0 ) ( 1 ) ( 2 ) ] [ J [ U ( 0 ) ( 1 ) ( 2 ) ] ] [ J ( 0 ) [ U ( 1 ) ( 2 ) ] ] [ J [ U ( 0 ) [ J ( 1 ) ( 2 ) ] ] ] sage: for g in graphs.cographs(3, as_graph=True): ....: print(g.edges(labels=False, sort=True)) [(0, 1), (0, 2), (1, 2)] [] [(0, 1), (0, 2)] [(1, 2)]
>>> from sage.all import * >>> for t in graphs.cographs(Integer(3), as_graph=False): ... print(t) [ J ( 0 ) ( 1 ) ( 2 ) ] [ J [ U ( 0 ) ( 1 ) ( 2 ) ] ] [ J ( 0 ) [ U ( 1 ) ( 2 ) ] ] [ J [ U ( 0 ) [ J ( 1 ) ( 2 ) ] ] ] >>> for g in graphs.cographs(Integer(3), as_graph=True): ... print(g.edges(labels=False, sort=True)) [(0, 1), (0, 2), (1, 2)] [] [(0, 1), (0, 2)] [(1, 2)]
Check that we agree with OEIS sequence A000084:
sage: [sum(1 for _ in graphs.cographs(n, as_graph=False)) ....: for n in range(1, 8)] [1, 2, 4, 10, 24, 66, 180]
>>> from sage.all import * >>> [sum(Integer(1) for _ in graphs.cographs(n, as_graph=False)) ... for n in range(Integer(1), Integer(8))] [1, 2, 4, 10, 24, 66, 180]
- sage.graphs.cographs.find_pivot(T)[source]#
Search for a pivot node in \(T\).
This is a helper method to method
cographs()
.A node in \(T\) is a
pivot
if it is not a leaf, it does not induce a maximum partition and it is the first such node in the inverse postorder traversal.INPUT:
T
– aCoTree
EXAMPLES:
sage: next(graphs.cographs(3, as_graph=True)).vertices() # indirect doctest [0, 1, 2]
>>> from sage.all import * >>> next(graphs.cographs(Integer(3), as_graph=True)).vertices() # indirect doctest [0, 1, 2]
- sage.graphs.cographs.next_tree(T)[source]#
Check if there is another tree after \(T\).
This is a helper method to method
cographs()
.This methods returns
True
if there is a tree after \(T\), and if so it modifies the input tree \(T\) that becomes the next tree.INPUT:
T
– aCoTree
EXAMPLES:
sage: next(graphs.cographs(3, as_graph=True)).vertices() # indirect doctest [0, 1, 2]
>>> from sage.all import * >>> next(graphs.cographs(Integer(3), as_graph=True)).vertices() # indirect doctest [0, 1, 2]
- sage.graphs.cographs.rebuild_node(u, P)[source]#
Replace the subtree rooted at \(u\) by a subtree induced by partition \(P\).
This is a helper method to method
cographs()
.INPUT:
u
– aCoTree
P
– a partition encoding the new structure of the children of \(u\)
EXAMPLES:
sage: next(graphs.cographs(3, as_graph=True)).vertices() # indirect doctest [0, 1, 2]
>>> from sage.all import * >>> next(graphs.cographs(Integer(3), as_graph=True)).vertices() # indirect doctest [0, 1, 2]
- sage.graphs.cographs.tree_to_graph(tree, immutable=False)[source]#
Return the cograph represented by
tree
.This is a helper method to method
cographs()
.EXAMPLES:
sage: for t in graphs.cographs(3, as_graph=True): # indirect doctest ....: print(t.edges(labels=False, sort=True)) [(0, 1), (0, 2), (1, 2)] [] [(0, 1), (0, 2)] [(1, 2)]
>>> from sage.all import * >>> for t in graphs.cographs(Integer(3), as_graph=True): # indirect doctest ... print(t.edges(labels=False, sort=True)) [(0, 1), (0, 2), (1, 2)] [] [(0, 1), (0, 2)] [(1, 2)]