Book a Demo!
CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutPoliciesSign UpSign In
sagemath
GitHub Repository: sagemath/sagelib
 Path: blob/master/sage/graphs/planarity/graphK33Search.private.h
4097 views
1
#ifndef GRAPH_K33SEARCH_PRIVATE_H

2
#define GRAPH_K33SEARCH_PRIVATE_H

3


4
/*

5
Planarity-Related Graph Algorithms Project

6
Copyright (c) 1997-2010, John M. Boyer

7
All rights reserved. Includes a reference implementation of the following:

8


9
* John M. Boyer. "Simplified O(n) Algorithms for Planar Graph Embedding,

10
  Kuratowski Subgraph Isolation, and Related Problems". Ph.D. Dissertation,

11
  University of Victoria, 2001.

12


13
* John M. Boyer and Wendy J. Myrvold. "On the Cutting Edge: Simplified O(n)

14
  Planarity by Edge Addition". Journal of Graph Algorithms and Applications,

15
  Vol. 8, No. 3, pp. 241-273, 2004.

16


17
* John M. Boyer. "A New Method for Efficiently Generating Planar Graph

18
  Visibility Representations". In P. Eades and P. Healy, editors,

19
  Proceedings of the 13th International Conference on Graph Drawing 2005,

20
  Lecture Notes Comput. Sci., Volume 3843, pp. 508-511, Springer-Verlag, 2006.

21


22
Redistribution and use in source and binary forms, with or without modification,

23
are permitted provided that the following conditions are met:

24


25
* Redistributions of source code must retain the above copyright notice, this

26
  list of conditions and the following disclaimer.

27


28
* Redistributions in binary form must reproduce the above copyright notice, this

29
  list of conditions and the following disclaimer in the documentation and/or

30
  other materials provided with the distribution.

31


32
* Neither the name of the Planarity-Related Graph Algorithms Project nor the names

33
  of its contributors may be used to endorse or promote products derived from this

34
  software without specific prior written permission.

35


36
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"

37
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

38
IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

39
DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR

40
ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

41
(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

42
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON

43
ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

44
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS

45
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

46
*/

47


48
#include "graph.h"

49


50
#ifdef __cplusplus

51
extern "C" {

52
#endif

53


54
// Additional equipment for each graph node (edge arc or vertex)

55
typedef struct

56
{

57
     int  noStraddle, pathConnector;

58
} K33Search_GraphNode;

59


60
typedef K33Search_GraphNode * K33Search_GraphNodeP;

61


62
// Additional equipment for each vertex

63
typedef struct

64
{

65
        int sortedDFSChildList, backArcList;

66
        int externalConnectionAncestor, mergeBlocker;

67
} K33Search_VertexRec;

68


69
typedef K33Search_VertexRec * K33Search_VertexRecP;

70


71


72
typedef struct

73
{

74
    // Helps distinguish initialize from re-initialize

75
    int initialized;

76


77
    // The graph that this context augments

78
    graphP theGraph;

79


80
    // Additional graph-level equipment

81
    listCollectionP sortedDFSChildLists;

82


83
    // Parallel array for additional graph node level equipment

84
    K33Search_GraphNodeP G;

85


86
    // Parallel array for additional vertex level equipment

87
    K33Search_VertexRecP V;

88


89
    // Overloaded function pointers

90
    graphFunctionTable functions;

91


92
} K33SearchContext;

93


94
#ifdef __cplusplus

95
}

96
#endif

97


98
#endif

99


100


101