21 #ifndef TULIP_PLANARITYIMPL_H 22 #define TULIP_PLANARITYIMPL_H 27 #include <unordered_map> 29 #include <tulip/Edge.h> 30 #include <tulip/MutableContainer.h> 31 #include <tulip/BmdList.h> 32 #include <tulip/tulipconf.h> 33 #include <tulip/Node.h> 37 enum { NOT_VISITED, VISITED, TERMINAL, VISITED_IN_RBC };
38 #define NULL_NODE node() 39 #define NULL_EDGE edge() 41 class TLP_SCOPE PlanarityTestImpl {
44 PlanarityTestImpl(Graph *sg);
45 bool isPlanar(
bool embedsg =
false);
46 static bool isPlanarEmbedding(
const Graph *sG);
47 std::list<edge> getObstructions();
50 bool compute(Graph *);
53 edge edgeReversal(edge e);
54 void makeBidirected(Graph *sG);
55 void swapNode(node &n1, node &n2);
56 void findTerminalNodes(Graph *sG, node n, std::list<node> &listOfComponents,
57 std::map<node, std::list<node>> &terminalNodes);
58 bool findObstruction(Graph *sG, node n, std::list<node> &terminalNodes);
59 void setInfoForNewCNode(Graph *sG, node n, node newCNode, std::list<node> &terminalNodes);
60 node findActiveCNode(node, node, std::list<node> &);
61 void preProcessing(Graph *);
62 tlp::BmdLink<node> *searchRBC(
int, tlp::BmdLink<node> *, node, std::list<node> &);
63 bool isT0Edge(Graph *, edge);
64 bool isBackEdge(Graph *, edge);
66 void sortNodesIncreasingOrder(Graph *, MutableContainer<int> &, std::vector<node> &);
67 node activeCNodeOf(
bool, node);
68 void addOldCNodeRBCToNewRBC(node, node, node, node, node, BmdList<node> &);
69 void updateLabelB(node);
70 void calcNewRBCFromTerminalNode(node, node, node, node, BmdList<node> &);
71 node lastPNode(node, node);
72 node lcaBetween(node, node,
const MutableContainer<node> &);
73 node lcaBetweenTermNodes(node, node);
74 void calculateNewRBC(Graph *, node, node, std::list<node> &);
75 node findNodeWithLabelBGreaterThanDfsN(
bool, Graph *, node, node);
76 void setPossibleK33Obstruction(node, node, node, node);
77 bool testCNodeCounter(Graph *, node, node, node, node, node &, node &);
78 bool testObstructionFromTerminalNode(Graph *, node, node, node);
81 bool listEdgesUpwardT0(node n1, node n2);
82 void extractBoundaryCycle(Graph *sG, node cNode, std::list<edge> &listEdges);
84 void obstrEdgesTerminal(Graph *G, node w, node t, node u);
85 void addPartOfBc(Graph *sG, node cNode, node n1, node n2, node n3);
86 void sortByLabelB(node &n1, node &n2, node &n3);
87 void obstrEdgesPNode(Graph *sG, node p, node u);
88 void calcInfo3Terminals(node &t1, node &t2, node &t3,
int &countMin,
int &countF, node &cNode,
90 void obstructionEdgesT0(Graph *sG, node w, node t1, node t2, node t3, node v);
91 void obstructionEdgesCountMin1(Graph *sG, node n, node cNode, node t1, node t2, node t3);
92 void obstructionEdgesCountMin23(Graph *sG, node n, node cNode, node t1, node t2, node t3, node q,
95 void obstructionEdgesK5(Graph *sG, node w, node cNode, node t1, node t2, node t3);
96 void obstructionEdgesPossibleObstrConfirmed(Graph *sG, node w, node t, node v);
97 void obstructionEdgesCNodeCounter(Graph *sG, node cNode, node w, node jl, node jr, node t1,
101 void embedRoot(Graph *sG,
int n);
102 void calculatePartialEmbedding(Graph *sG, node w, node newCNode, std::list<edge> &listBackEdges,
103 std::list<node> &terminalNodes);
104 void markPathInT(node t, node w, std::map<node, node> &backEdgeRepresentant,
105 std::list<node> &traversedNodes);
106 std::map<node, std::list<edge>> groupBackEdgesByRepr(Graph *sG, std::list<edge> &listBackEdges,
107 std::map<node, node> &backEdgeRepresentant,
108 std::list<node> &traversedNodes,
109 std::list<node> &listRepresentants);
110 std::list<node> embedUpwardT(
bool embBackEdgesOutW, node t1, node t2, Graph *sG, node w,
111 std::map<node, std::list<edge>> &bEdgesRepres,
112 std::list<node> &traversedNodes, BmdList<edge> &embList);
113 void addOldCNodeToEmbedding(
bool embBackEdgesOutW, Graph *sG, node w, node oldCNode, node u,
114 std::map<node, std::list<edge>> &bEdgesRepres,
115 std::list<node> &traversedNodes, std::list<node> &toEmbedLater,
116 BmdList<edge> &embList);
117 void embedBackEdges(
bool embBackEdgesOutW, Graph *sG, node repr, std::list<node> &traversedNodes,
118 std::list<edge> &listBackEdges, BmdList<edge> &embList);
119 int sortBackEdgesByDfs(Graph *sG, node w, node repr, std::list<edge> &listBackEdges,
120 std::vector<edge> &backEdge);
126 bool embed, biconnected;
127 node lastNodeInQLinha;
128 std::unordered_map<edge, edge> bidirectedEdges;
129 std::unordered_map<edge, edge> reversalEdge;
132 node cNodeOfPossibleK33Obstruction;
139 std::unordered_map<node, std::list<node>> childrenInT0;
146 std::map<node, std::list<edge>> listBackEdges;
150 std::map<node, BmdList<node>> RBC;
155 std::unordered_map<node, BmdList<edge>> embedList;
158 std::unordered_map<tlp::BmdLink<node> *, node> activeCNode;
162 BmdList<edge> listBackEdgesOutW;
166 std::list<node> obstructionNodes;
169 std::list<edge> obstructionEdges;
174 MutableContainer<tlp::BmdLink<node> *> ptrItem;
177 MutableContainer<int> dfsPosNum;
180 MutableContainer<node> nodeWithDfsPos;
184 MutableContainer<edge> T0EdgeIn;
188 MutableContainer<node> parent;
189 MutableContainer<node> p0;
194 MutableContainer<int> largestNeighbor;
200 MutableContainer<int> labelB;
206 MutableContainer<node> nodeLabelB;
210 MutableContainer<node> lastVisited;
215 MutableContainer<node> neighborWTerminal;
220 MutableContainer<int> state;
224 MutableContainer<int> counter;
228 MutableContainer<bool> hasBackEdge;
229 unsigned int numberOfNodesInG;
235 std::list<tlp::edge> posDFS(
tlp::Graph *sG, tlp::MutableContainer<int> &dfsPos);