rename GraphCreator methods

thm-mni-ii · Feb 5, 2019 · 6d547bb · 6d547bb
1 parent 2d146e6
commit 6d547bb
Show file tree

Hide file tree

Showing 22 changed files with 107 additions and 106 deletions.
diff --git a/README.md b/README.md
@@ -79,7 +79,7 @@ bool reachable(DirectedGraph *g, uint a, uint b) {
 }
 
 int main(void) {
-    DirectedGraph g = GraphCreator::createRandomKRegularGraph(100, 30);
+    DirectedGraph g = GraphCreator::kOutdegree(100, 30);
     return reachable(&g, 10, 25);
 }
 ```

diff --git a/docs/bcc-iterator.md b/docs/bcc-iterator.md
@@ -21,7 +21,7 @@ This space-efficient variant
 
 ## Example
 ```cpp
-UndirectedGraph g=GraphCreator::createWindmill(3,4);
+UndirectedGraph g=GraphCreator::windmill(3,4);
 
 BCCIterator b(&g);
 b.init();

diff --git a/docs/cut-vertex-iterator.md b/docs/cut-vertex-iterator.md
@@ -17,7 +17,7 @@ This space-efficient variant
 
 ## Example
 ```cpp
-UndirectedGraph g=GraphCreator::createWindmill(3,4);
+UndirectedGraph g=GraphCreator::windmill(3,4);
 
 CutVertexIterator c(&g);
 c.init();

diff --git a/docs/n-bit-dfs.md b/docs/n-bit-dfs.md
@@ -14,7 +14,7 @@ This space-efficient variant
 
 ## Example
 ```cpp
-DirectedGraph g=GraphCreator::createRandomGenerated(50);
+DirectedGraph g=GraphCreator::sparseDirected(50);
 
 DFS::nBitDFS(&g);  // quiet run
 

diff --git a/docs/nloglogn-bit-dfs.md b/docs/nloglogn-bit-dfs.md
@@ -17,7 +17,7 @@ This space-efficient variant
 
 ## Example
 ```cpp
-DirectedGraph g=GraphCreator::createRandomImbalanced(500);
+DirectedGraph g=GraphCreator::imbalanced(500);
 
 DFS::nloglognBitDFS(&g);  // quiet run
 

diff --git a/docs/nplusm-bit-dfs.md b/docs/nplusm-bit-dfs.md
@@ -14,7 +14,7 @@ This space-efficient variant *only works with undirected graphs*:
 
 ## Example
 ```cpp
-UndirectedGraph g=GraphCreator::createRandomKRegularUndirectedGraph(100,5)
+UndirectedGraph g=GraphCreator::kRegular(100,5)
 
 DFS::nplusmBitDFS(&g);  // quiet run
 

diff --git a/include/sealib/graph/graphcreator.h b/include/sealib/graph/graphcreator.h
@@ -15,59 +15,60 @@ class GraphCreator {
  public:
     /**
      * Create a graph from an adjacency matrix.
-     * @param adjMatrix NxN adjacency matrix of the graph: M[i,j] = number of edges from i to j
+     * @param adjMatrix NxN adjacency matrix of the graph: M[i,j] = number of
+     * edges from i to j
      * @param order Order of the graph (number of nodes)
      * @return the generated graph
      * @author Johannes Meintrup
      */
-    static UndirectedGraph createGraphFromAdjacencyMatrix(uint32_t **adjMatrix,
-                                                          uint32_t order);
+    static UndirectedGraph createFromAdjacencyMatrix(uint32_t **adjMatrix,
+                                                     uint32_t order);
 
-    static UndirectedGraph *createGraphPointerFromAdjacencyMatrix(
+    static UndirectedGraph *createPointerFromAdjacencyMatrix(
         uint32_t **adjMatrix, uint32_t order);
 
     static std::shared_ptr<UndirectedGraph>
-    createSharedGraphFromAdjacencyMatrix(uint32_t **adjMatrix, uint32_t order);
+    createSharedPointerFromAdjacencyMatrix(uint32_t **adjMatrix,
+                                           uint32_t order);
 
     /**
-     * Create a random k-regular graph, i.e., a graph with a fixed number
-     * of neighbours per node.
+     * Create a random directed graph with a fixed number of outneighbours per
+     * node.
      * @param order number of nodes the graph should contain
-     * @param k the degree of each node; the edges will go to any
-     * random node
+     * @param k the degree of each node; the edges will go to any random node
      * @return the resulting graph G (n = order, m = k*order)
      * @author Simon Heuser
      */
-    static DirectedGraph createRandomKRegularGraph(uint32_t order, uint32_t k);
+    static DirectedGraph kOutdegree(uint32_t order, uint32_t k);
 
     /**
-     * Create a random k-regular undirected graph.
-     * (Takes very long for larger graphs!)
+     * Create a random k-regular graph.
+     * Complexity: O(n*k) time
      * @param order number of nodes to generate
-     * @param k outgoing edges per node
-     * @return the resulting undirected graph
+     * @param k the degree of each node
+     * @return the resulting undirected graph G (n = order, m = k*order)
      * @author Simon Heuser
      */
-    static UndirectedGraph createRandomKRegularUndirectedGraph(
-        uint32_t order, uint32_t outdegreePerNode);
+    static UndirectedGraph kRegular(uint32_t order, uint32_t k);
 
     /**
-     * Create a completely random graph with a given number of nodes. Each node
-     * will have outgoing edges to at most n other nodes.
+     * Create a random sparseDirected graph with a given number of nodes. Each
+     * node
+     * will have outgoing edges to at most log(n) other nodes.
      * @param order the number of nodes the graph should contain
-     * @return the resulting graph: n = order, m = O(n^2)
+     * @return the resulting graph: n = order, m = O(n*log(n))
      * @author Simon Heuser
      */
-    static DirectedGraph createRandomGenerated(uint32_t order);
+    static DirectedGraph sparseDirected(uint32_t order);
 
     /**
-     * Generate a random undirected graph. Each node will have at least 5
-     * connections to other nodes.
+     * Generate a random undirected graph. Each node will be adjacent to O(log
+     * n) nodes.
      * @param order number of nodes
-     * @return the resulting undirected graph: n = order, m = O(n)
+     * @return the resulting undirected graph: n = order, m = O(n*log(n))
      * @author Simon Heuser
      */
-    static UndirectedGraph createRandomGeneratedUndirected(uint32_t order);
+    static UndirectedGraph sparseUndirected(uint32_t order);
 
     /**
      * Create a random "imbalanced" graph, which contains a handful of very
@@ -76,11 +77,12 @@ class GraphCreator {
      * @return the resulting graph: some nodes have a very large degree (they
      * are "big")
      */
-    static DirectedGraph createRandomImbalanced(uint32_t order);
+    static DirectedGraph imbalanced(uint32_t order);
 
     /**
      *  Generate a Gilbert graph G(n,p) in standard representation with n nodes
-     *  and an occurence of every possible edge with a probability of p (0 < p < 1)
+     *  and an occurence of every possible edge with a probability of p (0 < p <
+     *1)
      *  Complexity: O(n^2)
      *	@param n order of the graph
      *	@param p probability of an edge
@@ -93,16 +95,18 @@ class GraphCreator {
     static uint *fastGraphGeneration(uint n, uint mPern);
 
     /**
-     * Create a random bipartite graph with the vertex sets V1 and V2 and the probability p for each possible edge to occur.
+     * Create a random bipartite graph with the vertex sets V1 and V2 and the
+     * probability p for each possible edge to occur.
      * @param order1 Number of vertices in V1
      * @param order2 Number of vertices in V2
      * @param p Edge probability
      * @param seed Seed for the random number generator
      * @author Johannes Meintrup
      */
-    static std::unique_ptr<UndirectedGraph>
-    generateRandomBipartiteUndirectedGraph(uint32_t order1, uint32_t order2,
-                                           double p, uint32_t seed);
+    static std::unique_ptr<UndirectedGraph> randomBipartite(uint32_t order1,
+                                                            uint32_t order2,
+                                                            double p,
+                                                            uint32_t seed);
 
     /**
      * Create an undirected windmill graph (m complete graphs of order n joined
@@ -112,7 +116,7 @@ class GraphCreator {
      * @return the generated windmill graph W_n^m
      * @author Simon Heuser
      */
-    static UndirectedGraph createWindmill(uint32_t order, uint32_t count);
+    static UndirectedGraph windmill(uint32_t order, uint32_t count);
 };
 }  // namespace Sealib
 #endif  // SEALIB_GRAPH_GRAPHCREATOR_H_
diff --git a/src-view/main.cpp b/src-view/main.cpp
@@ -20,7 +20,7 @@ void tikz_example() {
     adj_mtrx[3] = new unsigned int[order]{1, 0, 1, 0};
 
     Sealib::UndirectedGraph bg =
-        Sealib::GraphCreator::createGraphFromAdjacencyMatrix(adj_mtrx, order);
+        Sealib::GraphCreator::createFromAdjacencyMatrix(adj_mtrx, order);
     std::shared_ptr<SealibVisual::TikzGraph> vg =
         SealibVisual::TikzGenerator::generateTikzElement(&bg);
 

diff --git a/src-view/test_visual.h b/src-view/test_visual.h
@@ -23,14 +23,14 @@ class VisualTest {
     static void testDFS() {
         uint n = 50;
         Sealib::DirectedGraph g =
-            Sealib::GraphCreator::createRandomKRegularGraph(n, 1);
+            Sealib::GraphCreator::kOutdegree(n, 1);
         Sealib::CompactArray c(n, 3);
         VisualDFS d(&g, &c, "out-dfs.tex", "beamer");
         d.run();
     }
 
     static void testCutVertex() {
-        Sealib::UndirectedGraph g = Sealib::GraphCreator::createWindmill(3, 4);
+        Sealib::UndirectedGraph g = Sealib::GraphCreator::windmill(3, 4);
         std::shared_ptr<VisualEdgeMarker> e(
             new VisualEdgeMarker(&g, "out-cutvertex.tex", "beamer"));
         e->init();
@@ -41,7 +41,7 @@ class VisualTest {
 
     static void testBCC() {
         Sealib::UndirectedGraph g =
-            Sealib::GraphCreator::createRandomKRegularUndirectedGraph(20, 2);
+            Sealib::GraphCreator::kRegular(20, 2);
         std::shared_ptr<VisualEdgeMarker> e(
             new VisualEdgeMarker(&g, "out-bcc.tex", "beamer", true));
         e->init();

diff --git a/src/graph/graphcreator.cpp b/src/graph/graphcreator.cpp
@@ -13,7 +13,7 @@ using Sealib::UndirectedGraph;
 using Sealib::CompactGraph;
 using Sealib::GraphCreator;
 
-UndirectedGraph *Sealib::GraphCreator::createGraphPointerFromAdjacencyMatrix(
+UndirectedGraph *Sealib::GraphCreator::createPointerFromAdjacencyMatrix(
     uint **adjMatrix, uint order) {
     std::vector<ExtendedNode> nodes(order);
 
@@ -60,23 +60,20 @@ UndirectedGraph *Sealib::GraphCreator::createGraphPointerFromAdjacencyMatrix(
     return new UndirectedGraph(nodes);
 }
 
-UndirectedGraph GraphCreator::createGraphFromAdjacencyMatrix(uint **adjMatrix,
-                                                             uint order) {
-    return *createGraphPointerFromAdjacencyMatrix(adjMatrix, order);
+UndirectedGraph GraphCreator::createFromAdjacencyMatrix(uint **adjMatrix,
+                                                        uint order) {
+    return *createPointerFromAdjacencyMatrix(adjMatrix, order);
 }
 
 std::shared_ptr<UndirectedGraph>
-GraphCreator::createSharedGraphFromAdjacencyMatrix(uint **adjMatrix,
-                                                   uint order) {
+GraphCreator::createSharedPointerFromAdjacencyMatrix(uint **adjMatrix,
+                                                     uint order) {
     return std::shared_ptr<UndirectedGraph>(
-        createGraphPointerFromAdjacencyMatrix(adjMatrix, order));
+        createPointerFromAdjacencyMatrix(adjMatrix, order));
 }
 
-std::unique_ptr<Sealib::UndirectedGraph>
-Sealib::GraphCreator::generateRandomBipartiteUndirectedGraph(uint order1,
-                                                             uint order2,
-                                                             double p,
-                                                             uint seed) {
+std::unique_ptr<Sealib::UndirectedGraph> Sealib::GraphCreator::randomBipartite(
+    uint order1, uint order2, double p, uint seed) {
     std::unique_ptr<Sealib::UndirectedGraph> graph(
         new Sealib::UndirectedGraph(order1 + order2));
 
@@ -104,7 +101,7 @@ Sealib::GraphCreator::generateRandomBipartiteUndirectedGraph(uint order1,
 
 static std::random_device rng;
 
-Sealib::DirectedGraph GraphCreator::createRandomImbalanced(uint order) {
+Sealib::DirectedGraph GraphCreator::imbalanced(uint order) {
     std::vector<SimpleNode> n(order);
     std::uniform_int_distribution<uint> rnd(0, order - 1);
     std::uniform_int_distribution<uint> dist1(order * order, 2 * order * order);
@@ -129,8 +126,8 @@ Sealib::DirectedGraph GraphCreator::createRandomImbalanced(uint order) {
     return DirectedGraph(n);
 }
 
-Sealib::DirectedGraph Sealib::GraphCreator::createRandomKRegularGraph(
-    uint order, uint degreePerNode) {
+Sealib::DirectedGraph Sealib::GraphCreator::kOutdegree(uint order,
+                                                       uint degreePerNode) {
     std::uniform_int_distribution<uint> rnd(0, order - 1);
     std::vector<SimpleNode> n(order);
     for (uint a = 0; a < order; a++) {
@@ -143,26 +140,28 @@ Sealib::DirectedGraph Sealib::GraphCreator::createRandomKRegularGraph(
     return DirectedGraph(n);
 }
 
-Sealib::DirectedGraph Sealib::GraphCreator::createRandomGenerated(uint order) {
+Sealib::DirectedGraph Sealib::GraphCreator::sparseDirected(uint order) {
     std::vector<SimpleNode> n(order);
-    std::uniform_int_distribution<uint> rnd(0, order - 1);
+    std::uniform_int_distribution<uint> nR(0, order - 1);
+    std::uniform_int_distribution<uint> degR(0, log2(order));
     for (uint a = 0; a < order; a++) {
-        uint deg = rnd(rng);
+        uint deg = degR(rng);
         std::vector<uint> ad(deg);
         for (uint b = 0; b < deg; b++) {
-            ad[b] = rnd(rng);
+            ad[b] = nR(rng);
         }
         n[a] = SimpleNode(ad);
     }
     return DirectedGraph(n);
 }
 
-UndirectedGraph GraphCreator::createRandomGeneratedUndirected(uint order) {
+UndirectedGraph GraphCreator::sparseUndirected(uint order) {
     UndirectedGraph g(order);
-    std::uniform_int_distribution<uint> rnd(0, order - 1);
+    std::uniform_int_distribution<uint> nR(0, order - 1);
+    std::uniform_int_distribution<uint> degR(0, log2(order));
     for (uint a = 0; a < order; a++) {
-        for (uint c = 0; c < 5; c++) {
-            uint b = rnd(rng);
+        for (uint c = 0; c < degR(rng); c++) {
+            uint b = nR(rng);
             ExtendedNode &n1 = g.getNode(a), &n2 = g.getNode(b);
             uint i1 = g.deg(a), i2 = g.deg(b);
             n1.addAdjacency({b, i2});
@@ -172,8 +171,7 @@ UndirectedGraph GraphCreator::createRandomGeneratedUndirected(uint order) {
     return g;
 }
 
-UndirectedGraph GraphCreator::createRandomKRegularUndirectedGraph(
-    uint order, uint degreePerNode) {
+UndirectedGraph GraphCreator::kRegular(uint order, uint degreePerNode) {
     UndirectedGraph g(order);
     std::uniform_int_distribution<uint> dist(0, order - 1);
     std::unordered_set<uint> todo;
@@ -206,7 +204,7 @@ UndirectedGraph GraphCreator::createRandomKRegularUndirectedGraph(
     return g;
 }
 
-UndirectedGraph GraphCreator::createWindmill(uint order, uint count) {
+UndirectedGraph GraphCreator::windmill(uint order, uint count) {
     order--;
     uint n = order * count + 1;
     UndirectedGraph g(n);

diff --git a/src/legacy.cpp b/src/legacy.cpp
@@ -9,7 +9,7 @@
 namespace Sealib {
 
 void *Sealib_Graph_new(uint32_t **m, uint32_t order) {
-    return GraphCreator::createGraphPointerFromAdjacencyMatrix(m, order);
+    return GraphCreator::createPointerFromAdjacencyMatrix(m, order);
 }
 void Sealib_Graph_delete(void *self) {
     delete static_cast<Graph const *>(self);

diff --git a/src/marker/cutvertexiterator.cpp b/src/marker/cutvertexiterator.cpp
@@ -20,7 +20,8 @@ void CutVertexIterator::findCCs() {
         if (color.get(a) == DFS_WHITE) {
             cc.insert(a);
             DFS::visit_nplusm(a, g, &color, &parent, DFS_NOP_PROCESS,
-                           DFS_NOP_EXPLORE, DFS_NOP_EXPLORE, DFS_NOP_PROCESS);
+                              DFS_NOP_EXPLORE, DFS_NOP_EXPLORE,
+                              DFS_NOP_PROCESS);
         }
     }
 }