add outerplanar docs, fix typos

thm-mni-ii · May 16, 2019 · 815f178 · 815f178
1 parent bf2f5d1
commit 815f178
Show file tree

Hide file tree

Showing 10 changed files with 68 additions and 39 deletions.
diff --git a/README.md b/README.md
@@ -30,6 +30,7 @@ For some data structures and algorithms we also provide a folklore implementatio
 | Breadth First Search  | O(n+m)         | O(n)                    | [here](docs/n-bit-bfs.md)           |
 | Cut-Vertex            | O(n+m)         | O(n+m)                  | [here](docs/cut-vertex-iterator.md) |
 | Biconnected-Component | O(n+m)         | O(n+m)                  | [here](docs/bcc-iterator.md)        |
+| Outerplanar Detection | O(n log(log n))| O(n)                    | [here](docs/outerplanar.md)         |
 
 ### Data Structures
 * Graph(G = {V, E}): A adjacency list graph representation that occupies O((n + m) log n) bits.

diff --git a/docs/bcc-iterator.md b/docs/bcc-iterator.md
@@ -1,19 +1,14 @@
-Biconnected-Component Iterator
+Biconnected-Component Output
 ===
 A *biconnected component* (BCC) is a subgraph of G=(V,E) that is biconnected: at least 2 vertices must be removed from it to *disconnect* the component. That means that a biconnected graph can never contain a [cut vertex](cut-vertex-iterator.md).
 
-To find the BCCs in a graph, the edges are classified into tree, back and cross/forward edges using a DFS. Another DFS dinds the *edge markings* for all the tree edges of G. It is then possible to supply an edge (u,v) and get all the nodes and edges that belong to the same BCC as the edge.
+To find the BCCs in a graph, the edges are classified into tree, back and cross/forward edges using a DFS. Another DFS finds the *edge markings* for all the tree edges of G. It is then possible to supply a start vertex *u0* and get all the nodes and edges that belong to the same BCC as *u0*.
 
 This space-efficient variant
 - uses the O(n+m)-Bit DFS to identify and mark edges
 - uses a static-space allocation to hold the edge markings
-- is built as an iterator:
-    - *init()*: initializes the iterator (identifies and marks tree edges)
-    - *start(u,v)*: sets the starting edge (u,v)
-    - *more()*: returns true if there are more nodes/edges in the current BCC
-    - *next()*: gets the next node/edge found in the BCC
-        - if a node is found, the returned tuple is (u,INVALID)
-        - if an edge is found, the returned tuple is (u,v)
+- has the following method:
+    - *traverse(u0, onVertex, onEdge)*: traverses the entire BCC of *u0*, calls *onVertex(u)* for each vertex *u* belonging to the BCC and *onEdge(u,v)* for each edge *{u,v}* belonging to the BCC
 
 ## Efficiency
 * Time: O(n+m)
@@ -28,15 +23,20 @@ This space-efficient variant
 int main() {
     Sealib::UndirectedGraph g = Sealib::GraphCreator::windmill(3,4);
 
-    Sealib::BCCIterator b(g);
-    b.init();
-    b.start(1,2);
-    b.forEach([](std::pair<uint64_t,uint64_t> p) {
-        if(p.second==INVALID) {
-            std::cout << "found node: " << p.first << "\n";
-        } else {
-            std::cout << "found edge: " << p.first << "," << p.second << "\n";
-        }
-    });
+    Sealib::BCCOutput b(g);
+    b.traverse(2,
+        [](uint64_t u){
+            printf("found vertex: %lu\n", u); 
+        },
+        [](uint64_t u, uint64_t v) {
+            printf("found edge: %lu,%lu\n", u, v);
+        });
 }
-```
+```
+
+Biconnected-Component Iterator
+===
+An iterative version of the above algorithm.
+- *init(u,v)*: iterate over the BCC belonging to edge *{u,v}*
+- *more()*: returns true if there are more vertices/edges in the BCC
+- *next()* returns a pair holding the next element: either *(u,INVALID)* for vertex *u*, or *(u,v)* for edge *{u,v}*
diff --git a/docs/cut-vertex-iterator.md b/docs/cut-vertex-iterator.md
@@ -3,7 +3,7 @@ Cut-Vertex Iterator
 A *cut vertex* is a vertex of an undirected, connected graph G=(V,E) that will *disconnect* the graph if it is removed. To find the cut vertices in a graph, the edges are classified into tree, back and cross/forward edges using a DFS. Another DFS finds the *edge markings* for all the tree edges of G.
 
 This space-efficient variant
-- uses the O(n+m)-Bit DFS to identify and mark edges
+- uses the [O(n+m)-Bit DFS](./nplusm-bit-dfs.md) to identify and mark edges
 - uses a static-space allocation to hold the edge markings
 - is built as an iterator:
     - *init()*: initializes the iterator (identifies and marks tree edges)

diff --git a/docs/n-bit-bfs.md b/docs/n-bit-bfs.md
@@ -1,13 +1,14 @@
 O(n)-Bit Breadth-First Search
 ===
-The breadth-first search over a graph G=(V,E) will find all *connected components* of G and output the tuple (u,dist) for each node, which is shows the distance of u to the starting node of the current component. Two *user-defined procedures* are available: `preprocess` and `preexplore`.
+The breadth-first search over a graph G=(V,E) will find all *connected components* of G and output the tuple (u,dist) for each vertex, which is shows the distance of u to the starting vertex of the current component. Two *user-defined procedures* are available: `preprocess` and `preexplore`.
 
 This space-efficient variant
-- uses a compact bitset to store the *node colors*
+- uses a compact bitset to store the *vertex colors*
+- uses two [choice dictionaries](./choice-dictionary.md) to manage color swapping
 - is built as an iterator which *streams* the results to the user:
 	- *init()*: initializes the BFS
 	- *more()*: returns true if there is more to do in this connected component
-	- *next()*: gets the next node and distance from the component
+	- *next()*: gets the next vertex and distance from the component
 	- *nextComponent()*: advances to the next component, or returns false if the graph is completely explored
 
 ## Efficiency

diff --git a/docs/n-bit-dfs.md b/docs/n-bit-dfs.md
@@ -1,9 +1,9 @@
 O(n)-Bit Depth-First Search
 ===
-The depth-first search over a graph G=(V,E) will *process* every node and *explore* every edge exactly once. The user can supply four *user-defined procedures*: `preprocess`, `preexplore`, `postexplore` and `postprocess`.
+The depth-first search over a graph G=(V,E) will *process* every vertex and *explore* every edge exactly once. The user can supply four *user-defined procedures*: `preprocess`, `preexplore`, `postexplore` and `postprocess`.
 
 This space-efficient variant
-- uses a compact bitset to store the *node colors*
+- uses a compact bitset to store the *vertex colors*
 - uses a segment stack which only keeps the two top-most segments and the last *trailer*.
     - When both segments are full and a push occurs, the lower segment is discarded.
     - When both segments are empty and a pop occurs, a restoration is started. The restoration is simply a *quiet* run (user procedures are disabled) of the DFS from the beginning. It runs until the current trailer matches with the trailer before the restoration.
@@ -26,9 +26,9 @@ void preexp(uint64_t u, uint64_t v) { printf("preexplore %u,%u\n", u, v); }
 void postexp(uint64_t u, uint64_t v) { printf("postexplore %u,%u\n", u, v); }
 
 int main() {
-    DirectedGraph g = Sealib::GraphCreator::sparseDirected(50);
+    Sealib::DirectedGraph g = Sealib::GraphCreator::sparseDirected(50);
     DFS::nBitDFS(g);  // quiet run
 
-    DFS::nBitDFS(g, preproc, preexp, postexp, postproc);  // supply procedures to do something with the current node or edge
+    DFS::nBitDFS(g, preproc, preexp, postexp, postproc);  // supply procedures to do something with the current vertex or edge
 }
 ```
diff --git a/docs/nloglogn-bit-dfs.md b/docs/nloglogn-bit-dfs.md
@@ -1,12 +1,12 @@
 O(n*log(log(n)))-Bit Depth-First Search
 ===
-The depth-first search over a graph G=(V,E) will *process* every node and *explore* every edge exactly once. The user can supply four *user-defined procedures*: `preprocess`, `preexplore`, `postexplore` and `postprocess`.
+The depth-first search over a graph G=(V,E) will *process* every vertex and *explore* every edge exactly once. The user can supply four *user-defined procedures*: `preprocess`, `preexplore`, `postexplore` and `postprocess`.
 
 This space-efficient variant
 - uses a compact bitset to store the *vertex colors*
 - uses a segment stack which only keeps the two top-most segments and the last *trailer*.
     - When both segments are full and a push occurs, the lower segment is discarded.
-    - When both segments are empty and a pop occurs, a restoration is started. The restoration will recreate exactly one segment by starting at the second-last trailer and continuously pushing the next gray node located in the top segment.
+    - When both segments are empty and a pop occurs, a restoration is started. The restoration will recreate exactly one segment by starting at the second-last trailer and continuously pushing the next gray vertex located in the top segment.
 - speeds up the restoration by not searching through all outgoing edges:
 	- A compact bitset stores edge approximations for *small vertices* in O(n log(log(n))) bits total
 	- The outgoing edges of *big vertices* are stored separately (there are at most n/log(n) big vertices so that they occupy no more than O(n) bits)
@@ -32,6 +32,6 @@ int main() {
     Sealib::DirectedGraph g = Sealib::GraphCreator::imbalanced(500);
     DFS::nloglognBitDFS(g);  // quiet run
 
-    DFS::nloglognBitDFS(g, preproc, preexp, postexp, postproc);  // supply procedures to do something with the current node or edge
+    DFS::nloglognBitDFS(g, preproc, preexp, postexp, postproc);  // supply procedures to do something with the current vertex or edge
 }
 ```
diff --git a/docs/nplusm-bit-dfs.md b/docs/nplusm-bit-dfs.md
@@ -1,12 +1,12 @@
 O(n+m)-Bit Depth-First Search
 ===
-The depth-first search over a graph G=(V,E) will *process* every node and *explore* every edge exactly once. The user can supply four *user-defined procedures*: `preprocess`, `preexplore`, `postexplore` and `postprocess`.
+The depth-first search over a graph G=(V,E) will *process* every vertex and *explore* every edge exactly once. The user can supply four *user-defined procedures*: `preprocess`, `preexplore`, `postexplore` and `postprocess`.
 
 This space-efficient variant *only works with undirected graphs*:
-- A static-space allocation keeps the backwards edge index for each node.
-    - By looking up the index, we know which node is the parent node. 
+- A static-space allocation keeps the backwards edge index for each vertex.
+    - By looking up the index, we know which vertex is the parent vertex. 
     - Another trick helps to find the next edge of the parent: Since each adjacency in an undirected graph also holds *cross indices*, the next edge that the parent will explore is `mate(childNode,backwardsEdge)+1`.
-- A compact bitset is used to store the *node colors*.
+- A compact bitset is used to store the *vertex colors*.
 
 ## Efficiency
 * Time: O(n+m)
@@ -22,14 +22,14 @@ using Sealib::DFS;
 // example procedures:
 void preproc(uint64_t u) { printf("preprocess %u\n", u); }
 void postproc(uint64_t u) { printf("postprocess %u\n", u); }
-// ! Attention: for this DFS variant, the 'explore' calls return the edge INDEX k, not the node v
+// ! Attention: for this DFS variant, the 'explore' calls return the edge INDEX k, not the vertex v
 void preexp(uint64_t u, uint64_t k) { printf("preexplore %u,%u\n", u, k); }
 void postexp(uint64_t u, uint64_t k) { printf("postexplore %u,%u\n", u, k); }
 
 int main() {
     Sealib::UndirectedGraph g = Sealib::GraphCreator::kRegular(100,5);
     DFS::nBitDFS(g);  // quiet run
 
-    DFS::nBitDFS(g, preproc, preexp, postexp, postproc);  // supply procedures to do something with the current node or edge
+    DFS::nBitDFS(g, preproc, preexp, postexp, postproc);  // supply procedures to do something with the current vertex or edge
 }
 ```
diff --git a/docs/outerplanar.md b/docs/outerplanar.md
@@ -0,0 +1,27 @@
+Outerplanarity Detection
+===
+This algorithm detects whether a biconnected input graph is *biconnected outerplanar* or not.
+- The algorithm **requires a biconnected input graph**: to create one, run the [BCC output](./bcc-iterator.md) on an arbitrary graph and feed the resulting BCCs to this algorithm one by one.
+
+This space-efficient outerplanar detection
+- uses a virtual graph consisting of a bit vector and a [ragged dictionary](./ragged-dictionary.md)
+- uses a compact array with [rank-select](./rank-select.md) for path counters
+
+## Efficiency
+- Time: O(n log(log(n)))
+- Space: O(n) bits
+
+## Example
+```cpp
+#include "sealib/iterator/outerplanarchecker.h"
+#include "sealib/graph/graphcreator.h"
+
+int main() {
+    Sealib::UndirectedGraph g = Sealib::GraphCreator::cycle(5000, 8);
+
+    Sealib::OuterplanarChecker c(g);
+    if(c.isOuterplanar()) {
+        // do something with the outerplanar graph
+    }
+}
+```
diff --git a/docs/reverse-dfs.md b/docs/reverse-dfs.md
@@ -20,7 +20,7 @@ This space-efficient reverse DFS
 #include "sealib/graph/graphcreator.h"
 
 int main() {
-    Sealib::DirectedGraph g = Sealib::GraphCreator::createRandomFixed(1024, 16);
+    Sealib::DirectedGraph g = Sealib::GraphCreator::kOutdegree(1024, 16);
 
     Sealib::ReverseDFS d(g);
     d.init();

diff --git a/docs/subgraph-stack.md b/docs/subgraph-stack.md
@@ -47,7 +47,7 @@ Pushes 10 new subgraphs on the stack, with each new subgraph containing 3/4 of t
 
 void main() {
 	std::shared_ptr<Sealib::Graph> bg = ;
-		Sealib::GraphCreator::generateRandomBipartiteBasicGraph(1000, 1000, 0.1, 1);
+		Sealib::GraphCreator::randomBipartite(1000, 1000, 0.1, 1);
 
 	Sealib::SubgraphStack stack(bg);