Changeset 3f0880

Timestamp:

10/04/10 11:40:53 (3 years ago)

Author:

Tiago de Paula Peixoto <tiago@…>

Children:

3507df

Parents:

487b47

git-author:

Tiago de Paula Peixoto <tiago@…> (10/03/10 23:47:29)

git-committer:

Tiago de Paula Peixoto <tiago@…> (10/04/10 11:40:53)

Message:

Add lattice and geometric network generation

Location:

src

Files:

• graph/generation/Makefile.am (modified) (2 diffs)
• graph/generation/graph_generation.cc (modified) (2 diffs)
• graph/generation/graph_geometric.cc (added)
• graph/generation/graph_geometric.hh (added)
• graph/generation/graph_lattice.cc (added)
• graph/generation/graph_lattice.hh (added)
• graph_tool/generation/__init__.py (modified) (4 diffs)

src/graph/generation/Makefile.am

@@ -23 +23 @@
     graph_union_vprop.cc \
     graph_union_eprop.cc \
-    graph_triangulation.cc
+    graph_triangulation.cc \
+    graph_lattice.cc \
+    graph_geometric.cc
+
 
 libgraph_tool_generation_la_include_HEADERS = \
@@ -31 +34 @@
     graph_union.hh \
     graph_triangulation.hh \
+    graph_lattice.hh \
+    graph_geometric.hh \
     sampler.hh

src/graph/generation/graph_generation.cc

@@ -98 +98 @@
 void triangulation(GraphInterface& gi, python::object points, boost::any pos,
                    string type, bool periodic);
+void lattice(GraphInterface& gi, python::object oshape, bool periodic);
+void geometric(GraphInterface& gi, python::object opoints, double r,
+               python::object orange, bool periodic, boost::any pos);
 
 using namespace boost::python;
@@ -111 +114 @@
     def("edge_property_union", &edge_property_union);
     def("triangulation", &triangulation);
+    def("lattice", &lattice);
+    def("geometric", &geometric);
 }

src/graph_tool/generation/__init__.py

@@ -35 +35 @@
    graph_union
    triangulation
+   lattice
+   geometric_graph
 
 Contents
@@ -48 +50 @@
 
 __all__ = ["random_graph", "random_rewire", "predecessor_tree", "line_graph",
-           "graph_union", "triangulation"]
+           "graph_union", "triangulation", "lattice", "geometric_graph"]
 
 
@@ -643 +645 @@
     >>> from numpy.random import seed, random
     >>> seed(42)
-    >>> points = random((500,2))*4
+    >>> points = random((500, 2)) * 4
     >>> g, pos = gt.triangulation(points)
     >>> weight = g.new_edge_property("double") # Edge weights corresponding to
@@ -694 +696 @@
                                            _prop("v", g, pos), type, periodic)
     return g, pos
+
+
+def lattice(shape, periodic=False):
+    r"""
+    Generate a N-dimensional square lattice.
+
+    Parameters
+    ----------
+    shape : list or :class:`~numpy.ndarray`
+        List of sizes in each dimension.
+    periodic : bool (optional, default: False)
+        If ``True``, periodic boundary conditions will be used.
+
+    Returns
+    -------
+    lattice_graph : :class:`~graph_tool.Graph`
+        The generated graph.
+
+    See Also
+    --------
+    triangulation: 2D or 3D triangulation
+    random_graph: random graph generation
+
+    Examples
+    --------
+    >>> g = gt.lattice([10,10])
+    >>> gt.graph_draw(g, size=(8,8), output="lattice.png")
+    <...>
+    >>> g = gt.lattice([10,20], periodic=True)
+    >>> gt.graph_draw(g, size=(8,8), output="lattice_periodic.png")
+    <...>
+    >>> g = gt.lattice([10,10,10])
+    >>> gt.graph_draw(g, size=(8,8), output="lattice_3d.png")
+    <...>
+
+    .. image:: lattice.png
+    .. image:: lattice_periodic.png
+    .. image:: lattice_3d.png
+
+    *Left:* 10x10 2D lattice. *Middle:* 10x20 2D periodic lattice (torus).
+    *Right:* 10x10x10 3D lattice.
+
+    References
+    ----------
+    .. [lattice] http://en.wikipedia.org/wiki/Square_lattice
+
+    """
+
+    g = Graph(directed=False)
+    libgraph_tool_generation.lattice(g._Graph__graph, shape, periodic)
+    return g
+
+
+def geometric_graph(points, radius, ranges=None):
+    r"""
+    Generate a geometric network form a set of N-dimensional points.
+
+    Parameters
+    ----------
+    points : list or :class:`~numpy.ndarray`
+        List of points. This must be a two-dimensional array, where the rows are
+        coordinates in a N-dimensional space.
+    radius : float
+        Pairs of points with an euclidean distance lower than this parameters
+        will be connected.
+    ranges : list or :class:`~numpy.ndarray` (optional, default: None)
+        If provided, periodic boundary conditions will be assumed, and the
+        values of this parameter it will be used as the ranges in all
+        dimensions. It must be a two-dimensional array, where each row will
+        cointain the lower and upper bound of each dimension.
+
+    Returns
+    -------
+    geometric_graph : :class:`~graph_tool.Graph`
+        The generated graph.
+    pos : :class:`~graph_tool.PropertyMap`
+        A vertex property map with the position of each vertex.
+
+    Notes
+    -----
+    A geometric graph [geometric-graph]_ is generated by connecting points
+    embedded in a N-dimensional euclidean space which are at a distance equal to
+    or smaller than a given radius.
+
+    See Also
+    --------
+    triangulation: 2D or 3D triangulation
+    random_graph: random graph generation
+    lattice : N-dimensional square lattice
+
+    Examples
+    --------
+    >>> from numpy.random import seed, random
+    >>> seed(42)
+    >>> points = random((500, 2)) * 4
+    >>> g, pos = gt.geometric_graph(points, 0.3)
+    >>> gt.graph_draw(g, pos=pos, pin=True, size=(8,8), output="geometric.png")
+    <...>
+    >>> g, pos = gt.geometric_graph(points, 0.3, [(0,4), (0,4)])
+    >>> gt.graph_draw(g, size=(8,8), output="geometric_periodic.png")
+    <...>
+
+    .. image:: geometric.png
+    .. image:: geometric_periodic.png
+
+    *Left:* Geometric network with random points. *Right:* Same network, but
+     with periodic boundary conditions.
+
+    References
+    ----------
+    .. [geometric-graph] Jesper Dall and Michael Christensen, "Random geometric
+       graphs", Phys. Rev. E 66, 016121 (2002), DOI: 10.1103/PhysRevE.66.016121
+
+    """
+
+    g = Graph(directed=False)
+    pos = g.new_vertex_property("vector<double>")
+    if type(points) != numpy.ndarray:
+        points = numpy.array(points)
+    if len(points.shape) < 2:
+        raise ValueError("points list must be a two-dimensional array!")
+    if ranges is not None:
+        periodic = True
+        if type(ranges) != numpy.ndarray:
+            ranges = numpy.array(ranges, dtype="float")
+        else:
+            ranges = array(ranges, dtype="float")
+    else:
+        periodic = False
+        ranges = ()
+
+    libgraph_tool_generation.geometric(g._Graph__graph, points, float(radius),
+                                       ranges, periodic,
+                                       _prop("v", g, pos))
+    return g, pos