libpysal.graph.Graph¶

class libpysal.graph.Graph(adjacency, transformation='O')[source]¶

Graph class encoding spatial weights matrices

The Graph is currently experimental and its API is incomplete and unstable.

__init__(adjacency, transformation='O')[source]¶

Weights base class based on adjacency list

It is recommenced to use one of the from_* or build_* constructors rather than invoking __init__ directly.

Each observation needs to be present in the focal, at least as a self-loop with a weight 0.

Parameters:

adjacencypandas.Series

A MultiIndexed pandas.Series with "focal" and "neigbor" levels encoding adjacency, and values encoding weights. By convention, isolates are encoded as self-loops with a weight 0.

transformationpython:str, default “O”

weights transformation used to produce the table.

O – Original
B – Binary
R – Row-standardization (global sum \(=n\))
D – Double-standardization (global sum \(=1\))
V – Variance stabilizing

Methods

`__init__`(adjacency[, transformation])	Weights base class based on adjacency list
`asymmetry`([intrinsic])	Asymmetry check.
`build_block_contiguity`(regimes)	Generate Graph from block contiguity (regime neighbors)
`build_contiguity`(geometry[, rook, ...])	Generate Graph from geometry based on contiguity
`build_distance_band`(data, threshold[, ...])	Generate Graph from geometry based on a distance band
`build_fuzzy_contiguity`(geometry[, ...])	Generate Graph from fuzzy contiguity
`build_kernel`(data[, kernel, k, bandwidth, ...])	Generate Graph from geometry data based on a kernel function
`build_knn`(data, k[, metric, p, coincident])	Generate Graph from geometry data based on k-nearest neighbors search
`build_triangulation`(data[, method, ...])	Generate Graph from geometry based on triangulation
`copy`([deep])	Make a copy of this Graph's adjacency table and transformation
`difference`(right)	Provide the set difference between the graph on the left and the graph on the right.
`equals`(right)	Check that two graphs are identical.
`explore`(gdf[, focal, nodes, color, ...])	Plot graph as an interactive Folium Map
`from_W`(w)	Create an experimental Graph from libpysal.weights.W object
`from_adjacency`(adjacency[, focal_col, ...])	Create a Graph from a pandas DataFrame formatted as an adjacency list
`from_arrays`(focal_ids, neighbor_ids, weight)	Generate Graph from arrays of indices and weights of the same length
`from_dicts`(neighbors[, weights])	Generate Graph from dictionaries of neighbors and weights
`from_sparse`(sparse[, ids])	Convert a `scipy.sparse` array to a PySAL `Graph` object.
`from_weights_dict`(weights_dict)	Generate Graph from a dict of dicts
`higher_order`([k, shortest_path, diagonal, ...])	Contiguity weights object of order \(k\).
`intersection`(right)	Returns a binary Graph, that includes only those neighbor pairs that exist in both left and right.
`intersects`(right)	Returns True if left and right share at least one link, irrespective of weights value.
`isomorphic`(right)	Check that two graphs are isomorphic.
`issubgraph`(right)	Return True if every link in the left Graph also occurs in the right Graph.
`lag`(y)	Spatial lag operator
`plot`(gdf[, focal, nodes, color, edge_kws, ...])	Plot edges and nodes of the Graph
`symmetric_difference`(right)	Filter out links that are in both left and right Graph objects.
`to_W`()	Convert Graph to a libpysal.weights.W object
`to_networkx`()	Convert Graph to a `networkx` graph.
`to_parquet`(path, **kwargs)	Save Graph to a Apache Parquet
`transform`(transformation)	Transformation of weights
`union`(right)	Provide the union of two Graph objects, collecing all links that are in either graph.

Attributes

`adjacency`	Return a copy of the adjacency list
`cardinalities`	Number of neighbors for each observation
`component_labels`	Get component labels per observation
`isolates`	Index of observations with no neighbors
`n`	Number of observations.
`n_components`	Get a number of connected components
`n_edges`	Number of observations.
`n_nodes`	Number of observations.
`neighbors`	Get neighbors dictionary
`nonzero`	Number of nonzero weights.
`pct_nonzero`	Percentage of nonzero weights.
`sparse`	Return a scipy.sparse array (COO)
`unique_ids`	Unique IDs used in the Graph
`weights`	Get weights dictionary

property adjacency¶

Return a copy of the adjacency list

Returns:

pandas.Series: Underlying adjacency list

asymmetry(intrinsic=True)[source]¶

Asymmetry check.

Parameters:

intrinsicbool, optional

Default is True. Intrinsic symmetry is defined as:

\[w_{i,j} == w_{j,i}\]

If intrinsic is False symmetry is defined as:

\[i \in N_j \ \& \ j \in N_i\]

where \(N_j\) is the set of neighbors for \(j\), e.g., True requires equality of the weight to consider two links equal, False requires only a presence of a link with a non-zero weight.

Returns:

pandas.Series: A Series of (i,j) pairs of asymmetries sorted ascending by the focal observation (index value), where i is the focal and j is the neighbor. An empty Series is returned if no asymmetries are found.

classmethod build_block_contiguity(regimes)[source]¶

Generate Graph from block contiguity (regime neighbors)

Block contiguity structures are relevant when defining neighbor relations based on membership in a regime. For example, all counties belonging to the same state could be defined as neighbors, in an analysis of all counties in the US.

Parameters:

regimeslist-like: list-like of regimes. If pandas.Series, its index is used to encode Graph. Otherwise a default RangeIndex is used.

Returns:

Graph: libpysal.graph.Graph encoding block contiguity

classmethod build_contiguity(geometry, rook=True, by_perimeter=False, strict=False)[source]¶

Generate Graph from geometry based on contiguity

Contiguity builder assumes that all geometries are forming a coverage, i.e. a non-overlapping mesh and neighbouring geometries share only points or segments of their exterior boundaries. In practice, build_contiguity is capable of creating a Graph of partially overlapping geometries when strict=False, by_perimeter=False, but that would not strictly follow the definition of queen or rook contiguity.

Parameters:

geometrynumpy:array_like of shapely.Geometry objects: Could be geopandas.GeoSeries or geopandas.GeoDataFrame, in which case the resulting Graph is indexed by the original index. If an array of shapely.Geometry objects is passed, Graph will assume a RangeIndex.
rookbool, optional: Contiguity method. If True, two geometries are considered neighbours if they share at least one edge. If False, two geometries are considered neighbours if they share at least one vertex. By default True
by_perimeterbool, optional: If True, weight represents the length of the shared boundary between adjacent units, by default False. For row-standardized version of perimeter weights, use Graph.build_contiguity(gdf, by_perimeter=True).transform("r").
strictbool, optional: Use the strict topological method. If False, the contiguity is determined based on shared coordinates or coordinate sequences representing edges. This assumes geometry coverage that is topologically correct. This method is faster but can miss some relations. If True, the contiguity is determined based on geometric relations that do not require precise topology. This method is slower but will result in correct contiguity even if the topology of geometries is not optimal. By default False.

Returns:

Graph: libpysal.graph.Graph encoding contiguity weights

classmethod build_distance_band(data, threshold, binary=True, alpha=-1.0, kernel=None, bandwidth=None)[source]¶

Generate Graph from geometry based on a distance band

Parameters:

datanumpy.ndarray, geopandas.GeoSeries, geopandas.GeoDataFrame: geometries containing locations to compute the delaunay triangulation. If a geopandas object with Point geometry is provided, the .geometry attribute is used. If a numpy.ndarray with shapely geometry is used, then the coordinates are extracted and used. If a numpy.ndarray of a shape (2,n) is used, it is assumed to contain x, y coordinates.
thresholdpython:float: distance band
binarybool, optional: If True \(w_{ij}=1\) if \(d_{i,j}<=threshold\), otherwise \(w_{i,j}=0\). If False \(wij=dij^{alpha}\), by default True.
alphapython:float, optional: distance decay parameter for weight (default -1.0) if alpha is positive the weights will not decline with distance. Ignored if binary=True or kernel is not None.
kernelpython:str, optional: kernel function to use in order to weight the output graph. See Graph.build_kernel() for details. Ignored if binary=True.
bandwidthpython:float (default: python:None): distance to use in the kernel computation. Should be on the same scale as the input coordinates. Ignored if binary=True or kernel=None.

Returns:

Graph: libpysal.graph.Graph encoding distance band weights

classmethod build_fuzzy_contiguity(geometry, tolerance=None, buffer=None, predicate='intersects')[source]¶

Generate Graph from fuzzy contiguity

Fuzzy contiguity relaxes the notion of contiguity neighbors for the case of geometry collections that violate the condition of planar enforcement. It handles three types of conditions present in such collections that would result in missing links when using the regular contiguity methods.

The first are edges for nearby polygons that should be shared, but are digitized separately for the individual polygons and the resulting edges do not coincide, but instead the edges intersect. This case can also be covered by build_contiguty with the strict=False parameter.

The second case is similar to the first, only the resultant edges do not intersect but are “close”. The optional buffering of geometry then closes the gaps between the polygons and a resulting intersection is encoded as a link.

The final case arises when one polygon is “inside” a second polygon but is not encoded to represent a hole in the containing polygon.

It is also possible to create a contiguity based on a custom spatial predicate.

Parameters:

geomsnumpy:array_like of shapely.Geometry objects: Could be geopandas.GeoSeries or geopandas.GeoDataFrame, in which case the resulting Graph is indexed by the original index. If an array of shapely.Geometry objects is passed, Graph will assume a RangeIndex.
tolerancepython:float, optional: The percentage of the length of the minimum side of the bounding rectangle for the geoms to use in determining the buffering distance. Either tolerance or buffer may be specified but not both. By default None.
bufferpython:float, optional: Exact buffering distance in the units of geoms.crs. Either tolerance or buffer may be specified but not both. By default None.
predicatepython:str, optional: The predicate to use for determination of neighbors. Default is ‘intersects’. If None is passed, neighbours are determined based on the intersection of bounding boxes. See the documentation of geopandas.GeoSeries.sindex.query for allowed predicates.

Returns:

Graph: libpysal.graph.Graph encoding fuzzy contiguity

classmethod build_kernel(data, kernel='gaussian', k=None, bandwidth=None, metric='euclidean', p=2, coincident='raise')[source]¶

Generate Graph from geometry data based on a kernel function

Parameters:

datanumpy.ndarray, geopandas.GeoSeries, geopandas.GeoDataFrame

geometries over which to compute a kernel. If a geopandas object with Point geoemtry is provided, the .geometry attribute is used. If a numpy.ndarray with shapely geoemtry is used, then the coordinates are extracted and used. If a numpy.ndarray of a shape (2,n) is used, it is assumed to contain x, y coordinates. If metric=”precomputed”, data is assumed to contain a precomputed distance metric.

kernelpython:str or python:callable() (default: ‘gaussian’)

kernel function to apply over the distance matrix computed by metric. The following kernels are supported:

"triangular":
"parabolic":
"gaussian":
"bisquare":
"cosine":
'boxcar'/discrete: all distances less than bandwidth are 1, and all other distances are 0
"identity"/None : do nothing, weight similarity based on raw distance
callable : a user-defined function that takes the distance vector and the bandwidth and returns the kernel: kernel(distances, bandwidth)

kpython:int (default: python:None)

number of nearest neighbors used to truncate the kernel. This is assumed to be constant across samples. If None, no truncation is conduted.

bandwidthpython:float (default: python:None)

distance to use in the kernel computation. Should be on the same scale as the input coordinates.

metricpython:str or python:callable() (default: ‘euclidean’)

distance function to apply over the input coordinates. Supported options depend on whether or not scikit-learn is installed. If so, then any distance function supported by scikit-learn is supported here. Otherwise, only euclidean, minkowski, and manhattan/cityblock distances are admitted.

ppython:int (default: 2)

parameter for minkowski metric, ignored if metric != “minkowski”.

coincident: str, optional (default “raise”)

Method for handling coincident points when k is not None. Options are 'raise' (raising an exception when coincident points are present), 'jitter' (randomly displace coincident points to produce uniqueness), & 'clique' (induce fully-connected sub cliques for coincident points).

Returns:

Graph: libpysal.graph.Graph encoding kernel weights

classmethod build_knn(data, k, metric='euclidean', p=2, coincident='raise')[source]¶

Generate Graph from geometry data based on k-nearest neighbors search

Parameters:

datanumpy.ndarray, geopandas.GeoSeries, geopandas.GeoDataFrame: geometries over which to compute a kernel. If a geopandas object with Point geoemtry is provided, the .geometry attribute is used. If a numpy.ndarray with shapely geoemtry is used, then the coordinates are extracted and used. If a numpy.ndarray of a shape (2,n) is used, it is assumed to contain x, y coordinates.
kpython:int: number of nearest neighbors.
metricpython:str or python:callable() (default: ‘euclidean’): distance function to apply over the input coordinates. Supported options depend on whether or not scikit-learn is installed. If so, then any distance function supported by scikit-learn is supported here. Otherwise, only euclidean, minkowski, and manhattan/cityblock distances are admitted.
ppython:int (default: 2): parameter for minkowski metric, ignored if metric != “minkowski”.
coincident: str, optional (default “raise”): Method for handling coincident points. Options include 'raise' (raising an exception when coincident points are present), 'jitter' (randomly displace coincident points to produce uniqueness), & 'clique' (induce fully-connected sub cliques for coincident points).

Returns:

Graph: libpysal.graph.Graph encoding KNN weights

classmethod build_triangulation(data, method='delaunay', bandwidth=inf, kernel='boxcar', clip='extent', rook=True, coincident='raise')[source]¶

Generate Graph from geometry based on triangulation

Parameters:

datanumpy.ndarray, geopandas.GeoSeries, geopandas.GeoDataFrame

geometries containing locations to compute the delaunay triangulation. If a geopandas object with Point geoemtry is provided, the .geometry attribute is used. If a numpy.ndarray with shapely geoemtry is used, then the coordinates are extracted and used. If a numpy.ndarray of a shape (2,n) is used, it is assumed to contain x, y coordinates.

methodpython:str, (default “delaunay”)

method of extracting the weights from triangulation. Supports:

"delaunay"
"gabriel"
"relative_neighborhood"
"voronoi"

bandwidthpython:float, optional

distance to use in the kernel computation. Should be on the same scale as the input coordinates, by default numpy.inf

kernelpython:str, optional

kernel function to use in order to weight the output graph. See Graph.build_kernel() for details. By default “boxcar”

clippython:str (default: ‘bbox’)

Clipping method when method="voronoi". Ignored otherwise. Default is 'extent'. Options are as follows.

'none'/None: No clip is applied. Voronoi cells may be arbitrarily larger that the source map. Note that this may lead to cells that are many orders of magnitude larger in extent than the original map. Not recommended.
'bbox'/'extent'/'bounding box': Clip the voronoi cells to the bounding box of the input points.
'chull/'convex hull': Clip the voronoi cells to the convex hull of the input points.
'ashape'/'ahull': Clip the voronoi cells to the tightest hull that contains all points (e.g. the smallest alphashape, using libpysal.cg.alpha_shape_auto()).
shapely.Polygon: Clip to an arbitrary Polygon.

rookbool, optional

Contiguity method when method="voronoi". Ignored otherwise. If True, two geometries are considered neighbours if they share at least one edge. If False, two geometries are considered neighbours if they share at least one vertex. By default True

coincident: str, optional (default “raise”)

Method for handling coincident points. Options include 'raise' (raising an exception when coincident points are present), 'jitter' (randomly displace coincident points to produce uniqueness), & 'clique' (induce fully-connected sub cliques for coincident points).

Returns:

Graph: libpysal.graph.Graph encoding triangulation weights

property cardinalities¶

Number of neighbors for each observation

Returns:

pandas.Series: Series with a number of neighbors per each observation

property component_labels¶

Get component labels per observation

Returns:

numpy.array: Array of component labels

copy(deep=True)[source]¶

Make a copy of this Graph’s adjacency table and transformation

Parameters:

deepbool, optional: Make a deep copy of the adjacency table, by default True

Returns:

Graph: libpysal.graph.Graph as a copy of the original

explore(gdf, focal=None, nodes=True, color='black', edge_kws=None, node_kws=None, focal_kws=None, m=None, **kwargs)[source]¶

Plot graph as an interactive Folium Map

Parameters:

gdfgeopandas.GeoDataFrame: geodataframe used to instantiate to Graph
focalpython:list, optional: subset of focal observations to plot in the map, by default None. If none, all relationships are plotted
nodesbool, optional: whether to display observations as nodes in the map, by default True
colorpython:str, optional: color applied to nodes and edges, by default “black”
edge_kwspython:dict, optional: additional keyword arguments passed to geopandas explore function when plotting edges, by default None
node_kwspython:dict, optional: additional keyword arguments passed to geopandas explore function when plotting nodes, by default None
focal_kwspython:dict, optional: additional keyword arguments passed to geopandas explore function when plotting focal observations, by default None. Only applicable when passing a subset of nodes with the focal argument
mFolilum.Map, optional: folium map objecto to plot on top of, by default None
**kwargspython:dict, optional: additional keyword arguments are passed directly to geopandas.explore, when m=None by default None

Returns:

folium.Map: folium map

classmethod from_W(w)[source]¶

Create an experimental Graph from libpysal.weights.W object

Parameters:

wlibpysal.weights.W

Returns:

Graph: libpysal.graph.Graph from W

classmethod from_adjacency(adjacency, focal_col='focal', neighbor_col='neighbor', weight_col='weight')[source]¶

Create a Graph from a pandas DataFrame formatted as an adjacency list

Parameters:

adjacencypandas.DataFrame: a dataframe formatted as an ajacency list. Should have columns “focal”, “neighbor”, and “weight”, or columns that can be mapped to these (e.g. origin, destination, cost)
focalpython:str, optional: name of column holding focal/origin index, by default ‘focal’
neighborpython:str, optional: name of column holding neighbor/destination index, by default ‘neighbor’
weightpython:str, optional: name of column holding weight values, by default ‘weight’

Returns:

Graph: libpysal.graph.Graph

classmethod from_arrays(focal_ids, neighbor_ids, weight)[source]¶

Generate Graph from arrays of indices and weights of the same length

The arrays needs to be sorted in a way ensuring that focal_ids.unique() is equal to the index of original observations from which the Graph is being built

Parameters:

focal_indexnumpy:array_like: focal indices
neighbor_indexnumpy:array_like: neighbor indices
weightnumpy:array_like: weights

Returns:

Graph: libpysal.graph.Graph based on arrays

classmethod from_dicts(neighbors, weights=None)[source]¶

Generate Graph from dictionaries of neighbors and weights

Parameters:

neighborspython:dict: dictionary of neighbors with the {focal: [neighbor1, neighbor2]} structure
weightspython:dict, optional: dictionary of neighbors with the {focal: [weight1, weight2]} structure. If None, assumes binary weights.

Returns:

Graph: libpysal.graph.Graph based on dictionaries

classmethod from_sparse(sparse, ids=None)[source]¶

Convert a scipy.sparse array to a PySAL Graph object.

Parameters:

sparsescipy.sparse array: sparse representation of a graph
idslist-like, default python:None: list-like of ids for geometries that is mappable to positions from sparse. If None, the positions are used as labels.

Returns:

Graph: libpysal.graph.Graph based on sparse

classmethod from_weights_dict(weights_dict)[source]¶

Generate Graph from a dict of dicts

Parameters:

weights_dictdictionary of dictionaries: weights dictionary with the {focal: {neighbor: weight}} structure.

Returns:

Graph: libpysal.graph.Graph based on weights dictionary of dictionaries

higher_order(k=2, shortest_path=True, diagonal=False, lower_order=False)[source]¶

Contiguity weights object of order \(k\).

Proper higher order neighbors are returned such that \(i\) and \(j\) are \(k\)-order neighbors if the shortest path from \(i-j\) is of length \(k\).

Parameters:

kpython:int, optional: Order of contiguity. By default 2.
shortest_pathbool, optional: If True, \(i,j\) and \(k\)-order neighbors if the shortest path for \(i,j\) is \(k\). If False, \(i,j\) are k-order neighbors if there is a path from \(i,j\) of length \(k\). By default True.
diagonalbool, optional: If True, keep \(k\)-order (\(i,j\)) joins when \(i==j\). If False, remove \(k\)-order (\(i,j\)) joins when \(i==j\). By default False.
lower_orderbool, optional: If True, include lower order contiguities. If False return only weights of order \(k\). By default False.

Returns:

Graph: higher order weights

property isolates¶

Index of observations with no neighbors

Isolates are encoded as a self-loop with the weight == 0 in the adjacency table.

Returns:

pandas.Index: Index with a subset of observations that do not have any neighbor

lag(y)[source]¶

Spatial lag operator

If weights are row standardized, returns the mean of each observation’s neighbors; if not, returns the weighted sum of each observation’s neighbors.

Parameters:

ynumpy:array_like: array-like (N,) shape where N is equal to number of observations in self.

Returns:

numpy.ndarray: array of numeric values for the spatial lag

property n¶: Number of observations.

property n_components¶

Get a number of connected components

Returns:

python:int: number of components

property n_edges¶: Number of observations.

property n_nodes¶: Number of observations.

property neighbors¶

Get neighbors dictionary

Returns:

python:dict: dict of tuples representing neighbors

Notes

It is recommended to work directly with Graph.adjacency() rather than using the Graph.neighbors().

property nonzero¶: Number of nonzero weights.

property pct_nonzero¶: Percentage of nonzero weights.

plot(gdf, focal=None, nodes=True, color='k', edge_kws=None, node_kws=None, focal_kws=None, ax=None, figsize=None, limit_extent=False)[source]¶

Plot edges and nodes of the Graph

Creates a maptlotlib plot based on the topology stored in the Graph and spatial location defined in gdf.

Parameters:

gdfgeopandas.GeoDataFrame: Geometries indexed using the same index as Graph. Geometry types other than points are converted to centroids encoding start and end point of Graph edges.
focalhashable | numpy:array_like[hashable] | python:None, optional: ID or an array-like of IDs of focal geometries whose weights shall be plotted. If None, all weights from all focal geometries are plotted. By default None
nodesbool, optional: Plot nodes as points, by default True
colorpython:str, optional: The color of all objects, by default “k”
edge_kwspython:dict, optional: Keyword arguments dictionary to send to LineCollection, which provides fine-grained control over the aesthetics of the edges in the plot. By default None
node_kwspython:dict, optional: Keyword arguments dictionary to send to ax.scatter, which provides fine-grained control over the aesthetics of the nodes in the plot. By default None
focal_kwspython:dict, optional: Keyword arguments dictionary to send to ax.scatter, which provides fine-grained control over the aesthetics of the focal nodes in the plot on top of generic node_kws. Values of node_kws are updated from focal_kws. Ignored if focal=None. By default None
axmatplotlib.axes.Axes, optional: Axis on which to plot the weights. If None, a new figure and axis are created. By default None
figsizepython:tuple, optional: figsize used to create a new axis. By default None
limit_extentbool, optional: limit the extent of the axis to the extent of the plotted graph, by default False

Returns:

matplotlib.axes.Axes: Axis with the resulting plot

Notes

If you’d like to overlay the actual geometries from the geopandas.GeoDataFrame, create an axis by plotting the GeoDataFrame and plot the Graph on top.

ax = gdf.plot() gdf_graph.plot(gdf, ax=ax)

property sparse¶

Return a scipy.sparse array (COO)

Returns:

scipy.sparse.COO: sparse representation of the adjacency

to_W()[source]¶

Convert Graph to a libpysal.weights.W object

Returns:

libpysal.weights.W: representation of graph as a weights.W object

to_networkx()[source]¶

Convert Graph to a networkx graph.

If Graph is symmetric, returns nx.Graph, otherwise returns a nx.DiGraph.

Returns:

networkx.Graph | networkx.DiGraph: Representation of libpysal Graph as networkx graph

to_parquet(path, **kwargs)[source]¶

Save Graph to a Apache Parquet

Graph is serialized to the Apache Parquet using the underlying adjacency object stored as a Parquet table and custom metadata containing transformation.

Requires pyarrow package.

Parameters:

pathpython:str | pyarrow.NativeFile: path or any stream supported by pyarrow
**kwargs: additional keyword arguments passed to pyarrow.parquet.write_table