Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
# -*- coding: utf-8 -*- """ GenericGraph Cython functions
AUTHORS:
- Robert L. Miller (2007-02-13): initial version - Robert W. Bradshaw (2007-03-31): fast spring layout algorithms - Nathann Cohen : exhaustive search """
#***************************************************************************** # Copyright (C) 2007 Robert L. Miller <rlmillster@gmail.com> # 2007 Robert W. Bradshaw <robertwb@math.washington.edu> # # This program is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 2 of the License, or # (at your option) any later version. # http://www.gnu.org/licenses/ #*****************************************************************************
from __future__ import absolute_import, print_function
from cysignals.memory cimport check_allocarray, check_calloc, sig_free from cysignals.signals cimport sig_on, sig_off
import cython
include "sage/data_structures/binary_matrix.pxi" from libc.math cimport sqrt, fabs from libc.string cimport memset
from sage.cpython.string cimport char_to_str from sage.libs.gmp.mpz cimport * from sage.misc.prandom import random from sage.ext.memory_allocator cimport MemoryAllocator from sage.graphs.base.static_sparse_graph cimport short_digraph from sage.graphs.base.static_sparse_graph cimport init_short_digraph from sage.graphs.base.static_sparse_graph cimport free_short_digraph from sage.graphs.base.static_sparse_graph cimport out_degree, has_edge
cdef class GenericGraph_pyx(SageObject): pass
def spring_layout_fast_split(G, **options): """ Graphs each component of G separately, placing them adjacent to each other. This is done because on a disconnected graph, the spring layout will push components further and further from each other without bound, resulting in very tight clumps for each component.
.. NOTE::
If the axis are scaled to fit the plot in a square, the horizontal distance may end up being "squished" due to the several adjacent components.
EXAMPLES::
sage: G = graphs.DodecahedralGraph() sage: for i in range(10): G.add_cycle(list(range(100*i, 100*i+3))) sage: from sage.graphs.generic_graph_pyx import spring_layout_fast_split sage: spring_layout_fast_split(G) {0: [0.77..., 0.06...], ... 902: [3.13..., 0.22...]}
AUTHOR:
Robert Bradshaw """
def spring_layout_fast(G, iterations=50, int dim=2, vpos=None, bint rescale=True, bint height=False, by_component = False, **options): """ Spring force model layout
This function primarily acts as a wrapper around run_spring, converting to and from raw c types.
This kind of speed cannot be achieved by naive Cythonification of the function alone, especially if we require a function call (let alone an object creation) every time we want to add a pair of doubles.
INPUT:
- ``by_component`` -- a boolean
EXAMPLES::
sage: G = graphs.DodecahedralGraph() sage: for i in range(10): G.add_cycle(list(range(100*i, 100*i+3))) sage: from sage.graphs.generic_graph_pyx import spring_layout_fast sage: pos = spring_layout_fast(G) sage: pos[0] # abs tol 0.1 [0.00..., 0.03...] sage: pos[902] # abs tol 0.1 [-0.48..., -0.10...] sage: len(pos) == G.order() True
With ``split=True``, each component of G is layed out separately, placing them adjacent to each other. This is done because on a disconnected graph, the spring layout will push components further and further from each other without bound, resulting in very tight clumps for each component.
If the axis are scaled to fit the plot in a square, the horizontal distance may end up being "squished" due to the several adjacent components. ::
sage: G = graphs.DodecahedralGraph() sage: for i in range(10): G.add_cycle(list(range(100*i, 100*i+3))) sage: from sage.graphs.generic_graph_pyx import spring_layout_fast sage: pos = spring_layout_fast(G, by_component = True) sage: pos[0] # abs tol 0.1 [2.21..., -0.00...] sage: pos[902] # abs tol 0.1 [3.07..., 0.86...] sage: len(pos) == G.order() True """
cdef int i, j, x return {}
except MemoryError: sig_free(pos) sig_free(elist) sig_free(cen) raise
# Initialize the starting positions else: for i in range(n): loc = vpos[vlist[i]] for x in range(dim): pos[i*dim + x] = loc[x]
# Lexicographically ordered list of edges
# finish the list with -1, -1 which never gets matched # but does get compared against when looking for the "next" edge
elif dim == 3: else: raise ValueError("'dim' must be equal to 2 or 3")
# recenter
# put the data back into a position dictionary
@cython.cdivision(True) cdef run_spring(int iterations, dimension_t _dim, double* pos, int* edges, int n, int m, bint height): r""" Find a locally optimal layout for this graph, according to the constraints that neighboring nodes want to be a fixed distance from each other, and non-neighboring nodes always repel.
This is not a true physical model of mutually-repulsive particles with springs, rather it is more a model of such things traveling, without any inertia, through an (ever thickening) fluid.
TODO: The inertial model could be incorporated (with F=ma) TODO: Are the hard-coded constants here optimal?
INPUT:
iterations -- number of steps to take _dim -- number of dimensions of freedom. Provide a value of type `D_TWO` for 2 dimensions, or type `D_THREE` for three dimensions. The actual value does not matter: only its type is important. pos -- already initialized initial positions Each vertex is stored as [dim] consecutive doubles. These doubles are then placed consecutively in the array. For example, if dim=3, we would have pos = [x_1, y_1, z_1, x_2, y_2, z_2, ... , x_n, y_n, z_n] edges -- List of edges, sorted lexicographically by the first (smallest) vertex, terminated by -1, -1. The first two entries represent the first edge, and so on. n -- number of vertices in the graph height -- if True, do not update the last coordinate ever
OUTPUT:
Modifies contents of pos.
AUTHOR:
Robert Bradshaw """ cdef int dim cdef int cur_iter, cur_edge cdef int i, j, x
if dimension_t is D_TWO: else:
# k -- the equilibrium distance between two adjacent nodes cdef double square_dist, dist, force, scale cdef double* disp_i cdef double* disp_j cdef double delta[3] cdef double d_tmp cdef double xx,yy,zz
update_dim = dim-1 else:
# zero out the disp vectors
else:
# they repel according to the (capped) inverse square law
# and if they are neighbors, attract according Hooke's law else:
# add this factor into each of the involved points
# now update the positions
else:
@cython.cdivision(True) cdef inline double sqrt_approx(double x,double y,double xx,double yy): r""" Approximation of `\sqrt(x^2+y^2)`.
Assuming that `x > y > 0`, it is a taylor expansion at `x^2`. To see how 'bad' the approximation is::
sage: def dist(x,y): ....: x = abs(x) ....: y = abs(y) ....: return max(x,y) + min(x,y)**2/(2*max(x,y))
sage: polar_plot([1,lambda x:dist(cos(x),sin(x))], (0, 2*pi)) Graphics object consisting of 2 graphics primitives """
def int_to_binary_string(n): """ A quick python int to binary string conversion.
INPUT:
- ``n`` (integer)
EXAMPLES::
sage: sage.graphs.generic_graph_pyx.int_to_binary_string(389) '110000101' sage: Integer(389).binary() '110000101' sage: sage.graphs.generic_graph_pyx.int_to_binary_string(2007) '11111010111' """ cdef mpz_t i cdef char* s
def binary_string_to_graph6(x): r""" Transforms a binary string into its graph6 representation.
This helper function is named `R` in [McK]_.
INPUT:
- ``x`` -- a binary string.
EXAMPLES::
sage: from sage.graphs.generic_graph_pyx import binary_string_to_graph6 sage: binary_string_to_graph6('110111010110110010111000001100000001000000001') 'vUqwK@?G'
REFERENCES:
.. [McK] McKay, Brendan. 'Description of graph6 and sparse6 encodings.' http://cs.anu.edu.au/~bdm/data/formats.txt (2007-02-13) """ # The length of x must be a multiple of 6. We extend it with 0s.
# Split into groups of 6, and convert numbers to decimal, adding 63 cdef int i
def small_integer_to_graph6(n): r""" Encodes a small integer (i.e. a number of vertices) as a graph6 string.
This helper function is named `N` [McK]_.
INPUT:
- ``n`` (integer)
EXAMPLES::
sage: from sage.graphs.generic_graph_pyx import small_integer_to_graph6 sage: small_integer_to_graph6(13) 'L' sage: small_integer_to_graph6(136) '~?AG' """ else: # get 18-bit rep of n
def length_and_string_from_graph6(s): r""" Returns a pair ``(length,graph6_string)`` from a graph6 string of unknown length.
This helper function is the inverse of `N` from [McK]_.
INPUT:
- ``s`` -- a graph6 string describing an binary vector (and encoding its length).
EXAMPLES::
sage: from sage.graphs.generic_graph_pyx import length_and_string_from_graph6 sage: length_and_string_from_graph6('~??~?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?') (63, '?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?') sage: length_and_string_from_graph6('_???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????') (32, '???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????') """ else: # only first byte is N raise RuntimeError("The string seems corrupt: valid characters are \n" + ''.join(chr(i) for i in xrange(63, 127)))
def binary_string_from_graph6(s, n): r""" Decodes a binary string from its graph6 representation
This helper function is the inverse of `R` from [McK]_.
INPUT:
- ``s`` -- a graph6 string
- ``n`` -- the length of the binary string encoded by ``s``.
EXAMPLES::
sage: from sage.graphs.generic_graph_pyx import binary_string_from_graph6 sage: binary_string_from_graph6('?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?', 63) '0000000000000000000000000000001000000000010000000001000010000000000000000000110000000000000000010100000010000000000001000000000010000000000...10000000000000000000000000000000010000000001011011000000100000000001001110000000000000000000000000001000010010000001100000001000000001000000000100000000' sage: binary_string_from_graph6('???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????', 32) '0000000000000000000001000000000000010000100000100000001000000000000000100000000100000...010000000000000100010000001000000000000000000000000000001010000000001011000000000000010010000000000000010000000000100000000001000001000000000000000001000000000000000000000000000000000000'
""" cdef int i
def binary_string_from_dig6(s, n): """ A helper function for the dig6 format.
INPUT:
- ``s`` -- a graph6 string
- ``n`` -- the length of the binary string encoded by ``s``.
EXAMPLES::
sage: from sage.graphs.generic_graph_pyx import binary_string_from_dig6 sage: binary_string_from_dig6('?????_@?CG??B??@OG?C?G???GO??W@a???CO???OACC?OA?P@G??O??????G??C????c?G?CC?_?@???C_??_?C????PO?C_??AA?OOAHCA___?CC?A?CAOGO??????A??G?GR?C?_o`???g???A_C?OG??O?G_IA????_QO@EG???O??C?_?C@?G???@?_??AC?AO?a???O?????A?_Dw?H???__O@AAOAACd?_C??G?G@??GO?_???O@?_O??W??@P???AG??B?????G??GG???A??@?aC_G@A??O??_?A?????O@Z?_@M????GQ@_G@?C?', 63) '0000000000000000000000000000001000000000010000000001000010000000000000000000110000000000000000010100000010000000000001000000000010000000000...10000000000000000000000000000000010000000001011011000000100000000001001110000000000000000000000000001000010010000001100000001000000001000000000100000000' sage: binary_string_from_dig6('???C?@AA?_?A?O?C??S??O?q_?P?CHD??@?C?GC???C??GG?C_??O?COG????I?J??Q??O?_@@??@??????', 32) '0000000000000000000001000000000000010000100000100000001000000000000000100000000100000...010000000000000100010000001000000000000000000000000000001010000000001011000000000000010010000000000000010000000000100000000001000001000000000000000001000000000000000000000000000000000000'
""" cdef int i
# Exhaustive search in graphs
cdef class SubgraphSearch: r""" This class implements methods to exhaustively search for copies of a graph `H` in a larger graph `G`.
It is possible to look for induced subgraphs instead, and to iterate or count the number of their occurrences.
ALGORITHM:
The algorithm is a brute-force search. Let `V(H) = \{h_1,\dots,h_k\}`. It first tries to find in `G` a possible representant of `h_1`, then a representant of `h_2` compatible with `h_1`, then a representant of `h_3` compatible with the first two, etc.
This way, most of the time we need to test far less than `k! \binom{|V(G)|}{k}` subsets, and hope this brute-force technique can sometimes be useful.
.. NOTE::
This algorithm does not take vertex/edge labels into account.
""" def __init__(self, G, H, induced = False): r""" Constructor
This constructor only checks there is no inconsistency in the input : `G` and `H` are both graphs or both digraphs and that `H` has order at least 2.
EXAMPLES::
sage: g = graphs.PetersenGraph() sage: g.subgraph_search(graphs.CycleGraph(5)) Subgraph of (Petersen graph): Graph on 5 vertices
TESTS:
Test proper initialization and deallocation, see :trac:`14067`. We intentionally only create the class without doing any computations with it::
sage: from sage.graphs.generic_graph_pyx import SubgraphSearch sage: SubgraphSearch(Graph(5), Graph(1)) Traceback (most recent call last): ... ValueError: Searched graph should have at least 2 vertices. sage: SubgraphSearch(Graph(5), Graph(2)) <sage.graphs.generic_graph_pyx.SubgraphSearch ...> """
raise ValueError("One graph can not be directed while the other is not.")
def __iter__(self): r""" Returns an iterator over all the labeleld subgraphs of `G` isomorphic to `H`.
EXAMPLES:
Iterating through all the `P_3` of `P_5`::
sage: from sage.graphs.generic_graph_pyx import SubgraphSearch sage: g = graphs.PathGraph(5) sage: h = graphs.PathGraph(3) sage: S = SubgraphSearch(g, h) sage: for p in S: ....: print(p) [0, 1, 2] [1, 2, 3] [2, 1, 0] [2, 3, 4] [3, 2, 1] [4, 3, 2] """
def cardinality(self): r""" Returns the number of labelled subgraphs of `G` isomorphic to `H`.
.. NOTE::
This method counts the subgraphs by enumerating them all ! Hence it probably is not a good idea to count their number before enumerating them :-)
EXAMPLES:
Counting the number of labelled `P_3` in `P_5`::
sage: from sage.graphs.generic_graph_pyx import SubgraphSearch sage: g = graphs.PathGraph(5) sage: h = graphs.PathGraph(3) sage: S = SubgraphSearch(g, h) sage: S.cardinality() 6 """ return 0
cdef int i
def _initialization(self): r""" Initialization of the variables.
Once the memory allocation is done in :meth:`__cinit__`, several variables need to be set to a default value. As this operation needs to be performed before any call to :meth:`__iter__` or to :meth:`cardinality`, it is cleaner to create a dedicated method.
EXAMPLES:
Finding two times the first occurrence through the re-initialization of the instance ::
sage: from sage.graphs.generic_graph_pyx import SubgraphSearch sage: g = graphs.PathGraph(5) sage: h = graphs.PathGraph(3) sage: S = SubgraphSearch(g, h) sage: S.__next__() [0, 1, 2] sage: S._initialization() sage: S.__next__() [0, 1, 2]
TESTS:
Check that :trac:`21828` is fixed::
sage: Poset().is_incomparable_chain_free(1,1) # indirect doctest True """ cdef int i
# 0 is the first vertex we use, so it is at first busy # stack -- list of the vertices which are part of the partial copy of H # in G. # # stack[i] -- the integer corresponding to the vertex of G representing # the i-th vertex of H. # # stack[i] = -1 means that i is not represented # ... yet!
# Number of representants we have already found. Set to 1 as vertex 0 # is already part of the partial copy of H in G.
def __cinit__(self, G, H, induced = False): r""" Cython constructor
This method initializes all the C values.
EXAMPLES::
sage: g = graphs.PetersenGraph() sage: g.subgraph_search(graphs.CycleGraph(5)) Subgraph of (Petersen graph): Graph on 5 vertices """
# Storing the number of vertices
# Storing the list of vertices
# Are the graphs directed (in __init__(), we check # whether both are of the same type)
cdef int i, j, k
# A vertex is said to be busy if it is already part of the partial copy # of H in G.
sizeof(int)) sizeof(int))
# Should we look for induced subgraphs ? else:
# static copies of the two graphs for more efficient operations
# copying the adjacency relations in both G and H
# vertices is equal to range(nh), as an int *variable
# line_h_out[i] represents the adjacency sequence of vertex i # in h relative to vertices 0, 1, ..., i-1
# Similarly in the opposite direction (only useful if the # graphs are directed)
def __next__(self): r""" Returns the next isomorphic subgraph if any, and raises a ``StopIteration`` otherwise.
EXAMPLES::
sage: from sage.graphs.generic_graph_pyx import SubgraphSearch sage: g = graphs.PathGraph(5) sage: h = graphs.PathGraph(3) sage: S = SubgraphSearch(g, h) sage: S.__next__() [0, 1, 2] """ cdef bint is_admissible
# as long as there is a non-void partial copy of H in G # If we are here and found nothing yet, we try the next possible # vertex as a representant of the active i-th vertex of H. # Looking for a vertex that is not busy and compatible with the # partial copy we have of H. else: # Testing whether the vertex we picked is a # correct extension by checking the edges from the # vertices already selected to self.i satisfy the # constraints
# If G and H are digraphs, we also need to ensure # the edges going in the opposite direction # satisfy the constraints
else:
# If we have found a good representant of H's i-th vertex in G
# updating the last vertex of the stack
# We have found our copy !!!
# We are still missing several vertices ... else:
# we begin the search of the next vertex at 0
# If we found no representant for the i-th vertex, it # means that we cannot extend the current copy of H so we # update the status of stack[active] and prepare to change # the previous vertex.
else:
cdef inline bint vectors_equal(int n, int *a, int *b): r""" Tests whether the two given vectors are equal. Two integer vectors `a = (a_1, a_2, \dots, a_n)` and `b = (b_1, b_2, \dots, b_n)` are equal iff `a_i = b_i` for all `i = 1, 2, \dots, n`. See the function ``_test_vectors_equal_inferior()`` for unit tests.
INPUT:
- ``n`` -- positive integer; length of the vectors.
- ``a``, ``b`` -- two vectors of integers.
OUTPUT:
- ``True`` if ``a`` and ``b`` are the same vector; ``False`` otherwise. """
cdef inline bint vectors_inferior(int n, int *a, int *b): r""" Tests whether the second vector of integers is inferior to the first. Let `u = (u_1, u_2, \dots, u_k)` and `v = (v_1, v_2, \dots, v_k)` be two integer vectors of equal length. Then `u` is said to be less than (or inferior to) `v` if `u_i \leq v_i` for all `i = 1, 2, \dots, k`. See the function ``_test_vectors_equal_inferior()`` for unit tests. Given two equal integer vectors `u` and `v`, `u` is inferior to `v` and vice versa. We could also define two vectors `a` and `b` to be equal if `a` is inferior to `b` and `b` is inferior to `a`.
INPUT:
- ``n`` -- positive integer; length of the vectors.
- ``a``, ``b`` -- two vectors of integers.
OUTPUT:
- ``True`` if ``b`` is inferior to (or less than) ``a``; ``False`` otherwise. """
############################## # Further tests. Unit tests for methods, functions, classes defined with cdef. ##############################
def _test_vectors_equal_inferior(): """ Unit testing the function ``vectors_equal()``. No output means that no errors were found in the random tests.
TESTS::
sage: from sage.graphs.generic_graph_pyx import _test_vectors_equal_inferior sage: _test_vectors_equal_inferior() """ cdef int i # equal vectors: u = v # Since u and v are equal vectors, then u is inferior to v and v is # inferior to u. One could also define u and v as being equal if # u is inferior to v and vice versa. except AssertionError: sig_free(u) sig_free(v) raise AssertionError("Vectors u and v should be equal.") # Different vectors: u != v because we have u_j > v_j for some j. Thus, # u_i = v_i for 0 <= i < j and u_j > v_j. For j < k < n - 2, we could have: # (1) u_k = v_k, # (2) u_k < v_k, or # (3) u_k > v_k. # And finally, u_{n-1} < v_{n-1}. cdef int k # u is not inferior to v because at least u_j > v_j # v is not inferior to u because at least v_{n-1} > u_{n-1} except AssertionError: sig_free(u) sig_free(v) raise AssertionError("".join([ "Vectors u and v should not be equal. ", "u should not be inferior to v, and vice versa."])) # Different vectors: u != v because we have u_j < v_j for some j. Thus, # u_i = v_i for 0 <= i < j and u_j < v_j. For j < k < n - 2, we could have: # (1) u_k = v_k, # (2) u_k < v_k, or # (3) u_k > v_k. # And finally, u_{n-1} > v_{n-1}. # u is not inferior to v because at least u_{n-1} > v_{n-1} # v is not inferior to u because at least u_j < v_j except AssertionError: sig_free(u) sig_free(v) raise AssertionError("".join([ "Vectors u and v should not be equal. ", "u should not be inferior to v, and vice versa."])) # different vectors u != v # What's the probability of two random vectors being equal? except AssertionError: sig_free(u) sig_free(v) raise AssertionError("Vectors u and v should not be equal.") # u is inferior to v, but v is not inferior to u except AssertionError: raise AssertionError( "u should be inferior to v, but v is not inferior to u.") finally:
cpdef tuple find_hamiltonian(G, long max_iter=100000, long reset_bound=30000, long backtrack_bound=1000, find_path=False): r""" Randomized backtracking for finding Hamiltonian cycles and paths.
ALGORITHM:
A path ``P`` is maintained during the execution of the algorithm. Initially the path will contain an edge of the graph. Every 10 iterations the path is reversed. Every ``reset_bound`` iterations the path will be cleared and the procedure is restarted. Every ``backtrack_bound`` steps we discard the last five vertices and continue with the procedure. The total number of steps in the algorithm is controlled by ``max_iter``. If a Hamiltonian cycle or Hamiltonian path is found it is returned. If the number of steps reaches ``max_iter`` then a longest path is returned. See OUTPUT for more details.
INPUT:
- ``G`` -- graph
- ``max_iter`` -- maximum number of iterations
- ``reset_bound`` -- number of iterations before restarting the procedure
- ``backtrack_bound`` -- number of iterations to elapse before discarding the last 5 vertices of the path.
- ``find_path`` -- (default: ``False``) if set to ``True``, will search a Hamiltonian path; if ``False``, will search for a Hamiltonian cycle
OUTPUT:
A pair ``(B, P)``, where ``B`` is a Boolean and ``P`` is a list of vertices.
* If ``B`` is ``True`` and ``find_path`` is ``False``, ``P`` represents a Hamiltonian cycle.
* If ``B`` is ``True`` and ``find_path`` is ``True``, ``P`` represents a Hamiltonian path.
* If ``B`` is ``False``, then ``P`` represents the longest path found during the execution of the algorithm.
.. WARNING::
May loop endlessly when run on a graph with vertices of degree 1.
EXAMPLES:
First we try the algorithm in the Dodecahedral graph, which is Hamiltonian, so we are able to find a Hamiltonian cycle and a Hamiltonian path::
sage: from sage.graphs.generic_graph_pyx import find_hamiltonian as fh sage: G=graphs.DodecahedralGraph() sage: fh(G) (True, [12, 11, 10, 9, 13, 14, 15, 5, 4, 3, 2, 6, 7, 8, 1, 0, 19, 18, 17, 16]) sage: fh(G,find_path=True) (True, [10, 0, 19, 3, 4, 5, 15, 16, 17, 18, 11, 12, 13, 9, 8, 1, 2, 6, 7, 14])
Another test, now in the Möbius-Kantor graph which is also Hamiltonian, as in our previous example, we are able to find a Hamiltonian cycle and path::
sage: G=graphs.MoebiusKantorGraph() sage: fh(G) (True, [15, 10, 2, 3, 4, 5, 13, 8, 11, 14, 6, 7, 0, 1, 9, 12]) sage: fh(G,find_path=True) (True, [10, 15, 7, 6, 5, 4, 12, 9, 14, 11, 3, 2, 1, 0, 8, 13])
Now, we try the algorithm on a non Hamiltonian graph, the Petersen graph. This graph is known to be hypohamiltonian, so a Hamiltonian path can be found::
sage: G=graphs.PetersenGraph() sage: fh(G) (False, [9, 4, 0, 1, 6, 8, 5, 7, 2, 3]) sage: fh(G,find_path=True) (True, [7, 2, 1, 0, 5, 8, 6, 9, 4, 3])
We now show the algorithm working on another known hypohamiltonian graph, the generalized Petersen graph with parameters 11 and 2::
sage: G=graphs.GeneralizedPetersenGraph(11,2) sage: fh(G) (False, [7, 8, 9, 10, 0, 1, 2, 3, 14, 12, 21, 19, 17, 6, 5, 4, 15, 13, 11, 20, 18, 16]) sage: fh(G,find_path=True) (True, [2, 1, 12, 21, 10, 0, 11, 13, 15, 17, 19, 8, 7, 6, 5, 4, 3, 14, 16, 18, 20, 9])
Finally, an example on a graph which does not have a Hamiltonian path::
sage: G=graphs.HyperStarGraph(5,2) sage: fh(G,find_path=False) (False, ['00110', '10100', '01100', '11000', '01010', '10010', '00011', '10001', '00101']) sage: fh(G,find_path=True) (False, ['01001', '10001', '00101', '10100', '00110', '10010', '01010', '11000', '01100'])
TESTS:
:trac:`10206` -- Hamiltonian cycle in small (di)graphs::
sage: for n in range(3): ....: for G in graphs(n): ....: print('order {} and size {}: {}'.format(G.order(),G.size(),fh(G, find_path=False))) order 0 and size 0: (False, []) order 1 and size 0: (False, [0]) order 2 and size 0: (False, [0]) order 2 and size 1: (False, [0, 1]) sage: for n in range(3): ....: for G in digraphs(n): ....: print('order {} and size {}: {}'.format(G.order(),G.size(),fh(G, find_path=False))) order 0 and size 0: (False, []) order 1 and size 0: (False, [0]) order 2 and size 0: (False, [0]) order 2 and size 1: (False, [0, 1]) order 2 and size 2: (False, [0, 1])
:trac:`10206` -- Hamiltonian path in small (di)graphs::
sage: for n in range(3): ....: for G in graphs(n): ....: print('order {} and size {}: {}'.format(G.order(),G.size(),fh(G, find_path=True))) order 0 and size 0: (False, []) order 1 and size 0: (False, [0]) order 2 and size 0: (False, [0]) order 2 and size 1: (True, [0, 1]) sage: for n in range(3): ....: for G in digraphs(n): ....: print('order {} and size {}: {}'.format(G.order(),G.size(),fh(G, find_path=True))) order 0 and size 0: (False, []) order 1 and size 0: (False, [0]) order 2 and size 0: (False, [0]) order 2 and size 1: (True, [0, 1]) order 2 and size 2: (True, [0, 1])
:trac:`10206` -- disconnected graphs::
sage: G = graphs.CompleteGraph(4) + Graph(1) sage: fh(G, find_path=False) (False, [0, 1, 2, 3]) sage: fh(G, find_path=True) (False, [0, 1, 2, 3])
"""
# Easy cases
# To clean the output when find_path is None or a number
# We have an hamiltonian path since n >= 2, but we have an hamiltonian # cycle only if n >= 3
cdef list best_path, p # The (Di)Graph has no hamiltonian path or cycle. We search for the # longest path in its connected components. backtrack_bound=backtrack_bound, find_path=True)
# Misc variables used below cdef int i, j cdef int n_available
#Initialize the path.
#Initialize the membership array
# static copy of the graph for more efficient operations cdef short_digraph sd
# A list to store the available vertices at each step
#We now work towards picking a random edge # First we pick a random vertex u of (out-)degree at least one u = randint(0, n-1) # Then we pick at random a neighbor of u # This will be the first edge in the path
#Initialize all the variables necessary to start iterating
#Initialize a path to contain the longest path
#Initialize a temporary path for flipping
cdef bint flag
#Reverse the path
#Time to reset the procedure
# First we pick a random vertex u of (out-)degree at least one u = randint(0, n-1) # Then we pick at random a neighbor of u # This will be the first edge in the path
else:
# # # # Output test # #
# Test adjacencies #Graph is simple, so both arcs are present good = False break raise RuntimeError('vertices %d and %d are consecutive in the cycle but are not adjacent' % (u, v)) raise RuntimeError('vertices %d and %d are not adjacent' % (path[0], path[n-1]))
def transitive_reduction_acyclic(G): r""" Returns the transitive reduction of an acyclic digraph
INPUT:
- ``G`` -- an acyclic digraph.
EXAMPLES::
sage: from sage.graphs.generic_graph_pyx import transitive_reduction_acyclic sage: G = posets.BooleanLattice(4).hasse_diagram() sage: G == transitive_reduction_acyclic(G.transitive_closure()) True """ cdef int u, v, i
cdef list linear_extension
cdef binary_matrix_t closure
# Build the transitive closure of G # # A point is reachable from u if it is one of its neighbours, or if it is # reachable from one of its neighbours.
# Build the transitive reduction of G # # An edge uv belongs to the transitive reduction of G if no outneighbor of u # can reach v (except v itself, of course).
|