Repository: CharJon/GeCO (language: python)

Issue:
Add Lavrov graphs
[This comment](https://math.stackexchange.com/a/2811761/1039279) describes an interesting graph type. Add a generator for this class of graphs. I do not know if they have a name yet, so let's call them after the author of the comment (Lavrov).


Discussion / hints:

Fix patch:
diff --git a/geco/graphs/__init__.py b/geco/graphs/__init__.py
index 8bea5ee..e9aad98 100644
--- a/geco/graphs/__init__.py
+++ b/geco/graphs/__init__.py
@@ -1,3 +1,4 @@
 import geco.graphs.chimera as chimera
 import geco.graphs.pegasus as pegasus
 import geco.graphs.utilities as utilities
+import geco.graphs.lavrov_graph as lavrov_graphs
\ No newline at end of file
diff --git a/geco/graphs/lavrov_graph.py b/geco/graphs/lavrov_graph.py
new file mode 100644
index 0000000..b80882c
--- /dev/null
+++ b/geco/graphs/lavrov_graph.py
@@ -0,0 +1,34 @@
+import networkx as nx
+
+
+def lavrov_graph(
+        k
+):
+    """
+    Generate Lavrov graph as described in [1] using networkx.
+
+    Parameters
+    ----------
+    k: int
+       Number k for Lavrov graph, number of nodes is 2 * k
+
+    Returns
+    -------
+    graph: nx.Graph
+        The generated Lavrov graph
+
+    References
+    ----------
+    ..[1] https://math.stackexchange.com/questions/2811736/an-upper-bound-on-the-number-of-chordless-cycles-in-an-undirected-graph/2811761#2811761
+    """
+
+    g = nx.Graph()
+    g.add_nodes_from([0,2 * k - 1])
+
+    for i in range(0, k):
+        g.add_edge(i, (i + 1) % k)
+        g.add_edge(i + k, (i + 1) % k + k)
+        g.add_edge(i, (i + 1) % k + k)
+        g.add_edge(i + k, (i + 1) % k)
+
+    return g


Test patch:
diff --git a/geco/graphs/tests/test_lavrov_graph.py b/geco/graphs/tests/test_lavrov_graph.py
new file mode 100644
index 0000000..efdcbdb
--- /dev/null
+++ b/geco/graphs/tests/test_lavrov_graph.py
@@ -0,0 +1,20 @@
+from geco.graphs.lavrov_graph import lavrov_graph
+
+import pytest
+
+
+def test_lavrov_graph_properties():
+    k = 200
+    g = lavrov_graph(k)
+    assert g.number_of_nodes() == k * 2
+    assert g.number_of_edges() == k * 4
+
+def test_lavrov_graph_edges():
+    g = lavrov_graph(5)
+    edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0),    # inner cycle
+             (5, 6), (6, 7), (7, 8), (8, 9), (9, 5),    # outer cycle
+             (5, 1), (6, 2), (7, 3), (8, 4), (9, 0),    # forward cross
+             (5, 4), (9, 3), (8, 2), (7, 1), (6, 0)]    # backward cross
+
+    for a,b in edges:
+        assert g.has_edge(a, b)