21 #ifndef TULIP_PLANARITYIMPL_H 22 #define TULIP_PLANARITYIMPL_H 28 #include <tulip/Edge.h> 29 #include <tulip/MutableContainer.h> 30 #include <tulip/BmdList.h> 31 #include <tulip/tulipconf.h> 32 #include <tulip/Node.h> 36 enum { NOT_VISITED, VISITED, TERMINAL, VISITED_IN_RBC };
37 static const node NULL_NODE = node();
38 static const edge NULL_EDGE = edge();
40 class TLP_SCOPE PlanarityTestImpl {
43 PlanarityTestImpl(Graph *sg);
44 bool isPlanar(
bool embedsg =
false);
45 static bool isPlanarEmbedding(
const Graph *sG);
46 std::list<edge> getObstructions();
49 bool compute(Graph *);
52 edge edgeReversal(edge e);
53 void makeBidirected(Graph *sG);
54 void swapNode(node &n1, node &n2);
55 void findTerminalNodes(Graph *sG, node n, std::list<node> &listOfComponents,
56 std::map<node, std::list<node>> &terminalNodes);
57 bool findObstruction(Graph *sG, node n, std::list<node> &terminalNodes);
58 void setInfoForNewCNode(Graph *sG, node n, node newCNode, std::list<node> &terminalNodes);
59 node findActiveCNode(node, node, std::list<node> &);
60 void preProcessing(Graph *);
61 tlp::BmdLink<node> *searchRBC(
int, tlp::BmdLink<node> *, node, std::list<node> &);
62 bool isT0Edge(Graph *, edge);
63 bool isBackEdge(Graph *, edge);
65 void sortNodesIncreasingOrder(Graph *, MutableContainer<int> &, std::vector<node> &);
66 node activeCNodeOf(
bool, node);
67 void addOldCNodeRBCToNewRBC(node, node, node, node, node, BmdList<node> &);
68 void updateLabelB(node);
69 void calcNewRBCFromTerminalNode(node, node, node, node, BmdList<node> &);
70 node lastPNode(node, node);
71 node lcaBetween(node, node,
const MutableContainer<node> &);
72 node lcaBetweenTermNodes(node, node);
73 void calculateNewRBC(Graph *, node, node, std::list<node> &);
74 node findNodeWithLabelBGreaterThanDfsN(
bool, Graph *, node, node);
75 void setPossibleK33Obstruction(node, node, node, node);
76 bool testCNodeCounter(Graph *, node, node, node, node, node &, node &);
77 bool testObstructionFromTerminalNode(Graph *, node, node, node);
80 bool listEdgesUpwardT0(node n1, node n2);
81 void extractBoundaryCycle(Graph *sG, node cNode, std::list<edge> &listEdges);
83 void obstrEdgesTerminal(Graph *G, node w, node t, node u);
84 void addPartOfBc(Graph *sG, node cNode, node n1, node n2, node n3);
85 void sortByLabelB(node &n1, node &n2, node &n3);
86 void obstrEdgesPNode(Graph *sG, node p, node u);
87 void calcInfo3Terminals(node &t1, node &t2, node &t3,
int &countMin,
int &countF, node &cNode,
89 void obstructionEdgesT0(Graph *sG, node w, node t1, node t2, node t3, node v);
90 void obstructionEdgesCountMin1(Graph *sG, node n, node cNode, node t1, node t2, node t3);
91 void obstructionEdgesCountMin23(Graph *sG, node n, node cNode, node t1, node t2, node t3, node q,
94 void obstructionEdgesK5(Graph *sG, node w, node cNode, node t1, node t2, node t3);
95 void obstructionEdgesPossibleObstrConfirmed(Graph *sG, node w, node t, node v);
96 void obstructionEdgesCNodeCounter(Graph *sG, node cNode, node w, node jl, node jr, node t1,
100 void embedRoot(Graph *sG,
int n);
101 void calculatePartialEmbedding(Graph *sG, node w, node newCNode, std::list<edge> &listBackEdges,
102 std::list<node> &terminalNodes);
103 void markPathInT(node t, node w, std::map<node, node> &backEdgeRepresentant,
104 std::list<node> &traversedNodes);
105 std::map<node, std::list<edge>> groupBackEdgesByRepr(Graph *sG, std::list<edge> &listBackEdges,
106 std::map<node, node> &backEdgeRepresentant,
107 std::list<node> &traversedNodes,
108 std::list<node> &listRepresentants);
109 std::list<node> embedUpwardT(
bool embBackEdgesOutW, node t1, node t2, Graph *sG, node w,
110 std::map<node, std::list<edge>> &bEdgesRepres,
111 std::list<node> &traversedNodes, BmdList<edge> &embList);
112 void addOldCNodeToEmbedding(
bool embBackEdgesOutW, Graph *sG, node w, node oldCNode, node u,
113 std::map<node, std::list<edge>> &bEdgesRepres,
114 std::list<node> &traversedNodes, std::list<node> &toEmbedLater,
115 BmdList<edge> &embList);
116 void embedBackEdges(
bool embBackEdgesOutW, Graph *sG, node repr, std::list<node> &traversedNodes,
117 std::list<edge> &listBackEdges, BmdList<edge> &embList);
118 int sortBackEdgesByDfs(Graph *sG, node w, node repr, std::list<edge> &listBackEdges,
119 std::vector<edge> &backEdge);
125 bool embed, biconnected;
126 node lastNodeInQLinha;
127 std::map<edge, edge> bidirectedEdges;
128 std::map<edge, edge> reversalEdge;
131 node cNodeOfPossibleK33Obstruction;
138 std::map<node, std::list<node>> childrenInT0;
145 std::map<node, std::list<edge>> listBackEdges;
149 std::map<node, BmdList<node>> RBC;
154 std::map<node, BmdList<edge>> embedList;
157 std::map<tlp::BmdLink<node> *, node> activeCNode;
161 BmdList<edge> listBackEdgesOutW;
165 std::list<node> obstructionNodes;
168 std::list<edge> obstructionEdges;
173 MutableContainer<tlp::BmdLink<node> *> ptrItem;
176 MutableContainer<int> dfsPosNum;
179 MutableContainer<node> nodeWithDfsPos;
183 MutableContainer<edge> T0EdgeIn;
187 MutableContainer<node> parent;
188 MutableContainer<node> p0;
193 MutableContainer<int> largestNeighbor;
199 MutableContainer<int> labelB;
205 MutableContainer<node> nodeLabelB;
209 MutableContainer<node> lastVisited;
214 MutableContainer<node> neighborWTerminal;
219 MutableContainer<int> state;
223 MutableContainer<int> counter;
227 MutableContainer<bool> hasBackEdge;
228 unsigned int numberOfNodesInG;
234 std::list<tlp::edge> posDFS(
tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos);