Previous topic

graph — Graph Based Data Representaton

Next topic

graph.node — Network Node Object

This Page

`graph.network` — Network File Representation¶

The graph.network module a graph based representation of image overlaps

New in version 0.1.0.

class autocnet.graph.network.CandidateGraph(*args, basepath=None, node_id_map=None, overlaps=False, **kwargs)[source]¶

A NetworkX derived directed graph to store candidate overlap images.

node_counter¶

The number of nodes in the graph.

Type: int

node_name_map¶

The mapping of image labels (i.e. file base names) to their corresponding node indices

Type: dict

clusters¶

of clusters with key as the cluster id and value as a list of node indices

Type: dict

cn¶

A control network object instantiated by calling generate_cnet.

Type: object

----------

add_edge(u, v, **attr)[source]¶

Adds an edge with the given src and dst nodes to the graph

Parameters

u (str) – The filename of the source image for the edge
v (Node) – The filename of the destination image for the edge

add_node(n=None, **attr)[source]¶

Adds an image node to the graph.

Parameters

image_name (str) – The file name of the node
adjacency (str list) – List of files names of adjacent images that correspond to names in CandidateGraph.graph[“node_name_map”]
basepath (str) – The base path to the node image file

apply(function, on='edge', out=None, args=(), **kwargs)[source]¶

Applys a function to every node or edge, returns collected return values. If applying a functions to nodes, then all ignored nodes will be skipped.

TODO: Merge with apply_func_to_edges?

Parameters

function (callable) – Function to apply to graph. Should accept (id, data).
on (string) – Whether to use nodes or edges. default is ‘edge’.
out (var) – Optionally put the output in a variable rather than returning it
args (iterable) – Some iterable of positional arguments for function.
kwargs (dict) – keyword args to pass into function.

apply_func_to_edges(function, nodes=[], *args, **kwargs)[source]¶

Iterates over edges using an optional mask and and applies the given function. If func is not an attribute of Edge, raises AttributeError

Parameters

function (obj) – function to be called on every edge
graph_mask_keys (list) – of keys in graph_masks

clean_singles()[source]¶: Take the controlnetwork dataframe and return only those points with at least two measures. This is automatically called before writing as functions such as subpixel matching can result in orphaned measures.

compute_cliques(node_id=None)[source]¶

Computes all maximum complete subgraphs for the given graph. If a node_id is given, method will return only the complete subgraphs that contain that node

Parameters: node_id (int) – Integer value for a given node
Returns: A list of lists of node ids that make up maximum complete subgraphs of the given graph
Return type: list

compute_clusters(func=<function mcl>, *args, **kwargs)[source]¶

Apply some graph clustering algorithm to compute a subset of the global graph.

Parameters

func (object) – The clustering function to be applied. Defaults to Markov Clustering Algorithm
args (list) – of arguments to be passed through to the func
kwargs (dict) – of keyword arguments to be passed through to the func

compute_fully_connected_components()[source]¶

For a given graph, compute all of the fully connected subgraphs with 3+ components.

Returns: fc – of lists of node identifiers
Return type: list

Examples

>>> G = CandidateGraph()
>>> G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('A', 'E'), ('A', 'F'), ('E', 'F') ])
>>> fc = G.compute_fully_connected_components()
>>> len(fc) #A, B, C, E, A  - D is omitted because it is a singular terminal node
5
>>> sorted(map(sorted,fc['A']))  # Sort inner and outer lists
[['A', 'B', 'C'], ['A', 'E', 'F']]

compute_fundamental_matrices(*args, **kwargs)[source]¶: Compute fundmental matrices for all edges using identical parameters

See also

autocnet.matcher.cpu_outlier_detector.compute_fundamental_matrix

compute_homographies(*args, **kwargs)[source]¶: Compute homographies for all edges using identical parameters

See also

autocnet.graph.edge.Edge.compute_homography, autocnet.matcher.cpu_outlier_detector.compute_homography

compute_intersection(source, clean_keys=[])[source]¶

Computes the intercetion of all images in a graph based around a given source node

Parameters

source (object or int) – Either a networkx Node object or an integer
clean_keys (list) – Strings used to apply masks to omit correspondences

Returns

intersect_gdf – A geopandas dataframe of intersections for all images that overlap with the source node. Also includes the common overlap for all images in the source node.

Return type

dataframe

compute_overlaps(*args, **kwargs)[source]¶: Computes overlap MBRs for all edges

compute_triangular_cycles()[source]¶

Find all cycles of length 3. This is similar: to cycle_basis (networkX), but returns all cycles. As opposed to all basis cycles.

Returns: cycles – A list of cycles in the form [(a,b,c), (c,d,e)], where letters indicate node identifiers
Return type: list

Examples

>>> g = CandidateGraph()
>>> g.add_edges_from([(0,1), (0,2), (1,2), (0,3), (1,3), (2,3)])
>>> sorted(g.compute_triangular_cycles())
[(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]

compute_unique_fully_connected_components(size=2)[source]¶

Compute a list of all cliques with size greater than size.

Parameters: size (int) – Only cliques larger than size are returned. Default 2.
Returns: of lists of node ids
Return type: list

Examples

>>> G = CandidateGraph()
>>> G.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('A', 'E'), ('A', 'F'), ('E', 'F') ])
>>> res = G.compute_unique_fully_connected_components()
>>> sorted(map(sorted,res))
[['A', 'B', 'C'], ['A', 'E', 'F']]

compute_weight(clean_keys, **kwargs)[source]¶

Computes a voronoi weight for each edge in a given graph. Can function as is, but is slightly optimized for complete subgraphs. ———- kwargs : dict

keyword arguments that get passed to compute_voronoi

clean_keyslist: Strings used to apply masks to omit correspondences

connected_subgraphs()[source]¶

Finds and returns a list of each connected subgraph of nodes. Each subgraph is a set.

Returns: A list of connected sub-graphs of nodes, with the largest sub-graph first. Each subgraph is a set.
Return type: list

create_edge_subgraph(edges)[source]¶

Create a subgraph using a list of edges. This is pulled directly from the networkx dev branch.

Parameters: edges (list) – A list of edges in the form [(a,b), (c,d)] to retain in the subgraph
Returns: H – A networkx subgraph object
Return type: object

create_node_subgraph(nodes)[source]¶

Given a list of nodes, create a sub-graph and copy both the node and edge attributes to the subgraph. Changes to node/edge attributes are propagated back to the parent graph, while changes to the graph structure, i.e., the topology, are not.

Parameters: nodes (iterable) – An iterable (list, set, ndarray) of nodes to subset the graph
Returns: H – A networkX graph object
Return type: object

decompose_and_match(*args, **kwargs)[source]¶: For all edges in the graph, apply coupled decomposition followed by feature matching.

See also

autocnet.graph.edge.Edge.decompose_and_match

edge_factory¶: alias of autocnet.graph.edge.Edge

estimate_mbrs(*args, **kwargs)[source]¶: For each edge, estimate the overlap and compute a minimum bounding rectangle (mbr) in pixel space.

See also

autocnet.graoh.edge.Edge.compute_mbr

extract_features(band=1, *args, **kwargs)[source]¶: Extracts features from each image in the graph and uses the result to assign the node attributes for ‘handle’, ‘image’, ‘keypoints’, and ‘descriptors’.

extract_features_with_downsampling(downsample_amount=None, *args, **kwargs)[source]¶

Extract interest points from a downsampled array. The array is downsampled by the downsample_amount keyword using the Lanconz downsample amount. If the downsample keyword is not supplied, compute a downsampling constant as the total array size divided by the network maxsize attribute.

Parameters: downsample_amount (int) – The amount of downsampling to apply to the image

extract_features_with_tiling(*args, **kwargs)[source]¶

property files¶: Return a list of all full file PATHs in the CandidateGraph

filter_edges(func, *args, **kwargs)[source]¶

Filters graph and returns a sub-graph from matches. Mimics python’s filter() function

Parameters: func (function which returns bool used to filter out edges) –
Returns: A networkX graph object
Return type: Object

filter_nodes(func, *args, **kwargs)[source]¶

Filters graph and returns a sub-graph from matches. Mimics python’s filter() function

Parameters: func (function which returns bool used to filter out nodes) –
Returns: A networkX graph object
Return type: Object

classmethod from_adjacency(input_adjacency, node_id_map=None, basepath=None, **kwargs)[source]¶

Instantiate the class using an adjacency dict or file. The input must contain relative or absolute paths to image files.

Parameters: input_adjacency (dict or str) – An adjacency dictionary or the name of a file containing an adjacency dictionary.
Returns: A Network graph object
Return type: object

Examples

>>> from autocnet.examples import get_path
>>> inputfile = get_path('adjacency.json')
>>> candidate_graph = CandidateGraph.from_adjacency(inputfile)
>>> sorted(candidate_graph.nodes())
[0, 1, 2, 3, 4, 5]

classmethod from_filelist(filelist, basepath=None)[source]¶

Instantiate the class using a filelist as a python list. An adjacency structure is calculated using the lat/lon information in the input images. Currently only images with this information are supported.

Parameters: filelist (list) – A list containing the files (with full paths) to construct an adjacency graph from
Returns: A Network graph object
Return type: object

generate_control_network(clean_keys=[], mask=None)[source]¶

Generates a fresh control network from edge matches.

Parameters

clean_keys (list) – A list of clean keys, same that would be used to filter edges
mask –

get_name(node_index)[source]¶

Get the image name for the given node.

Parameters: node_index (int) – The index of the node.
Returns: The name of the image attached to the given node.
Return type: str

is_complete()[source]¶: Checks if the graph is a complete graph

island_nodes()[source]¶

Finds single nodes that are completely disconnected from the rest of the graph

Returns: A list of disconnected nodes, nodes of degree zero, island nodes, etc.
Return type: list

load_features(in_path, nodes=[], nfeatures=None, **kwargs)[source]¶

Load features (keypoints and descriptors) for the specified nodes.

Parameters

in_path (str) – Location of the input file.
nodes (list) – of nodes to load features for. If empty, load features for all nodes

match(*args, **kwargs)[source]¶: For all connected edges in the graph, apply feature matching

See also

autocnet.graph.edge.Edge.match

minimum_spanning_tree()[source]¶

Calculates the minimum spanning tree of the graph

Returns: boolean mask for edges in the minimum spanning tree
Return type: DataFrame

node_factory¶: alias of autocnet.graph.node.Node

overlap()[source]¶: Compute the percentage and area coverage of two images

See also

autocnet.cg.cg.two_image_overlap

overlap_checks(*args, **kwargs)[source]¶: Apply overlap check to all edges in the graph

plot(ax=None, **kwargs)[source]¶

Plot the graph object

Parameters: ax (object) – A MatPlotLib axes object.
Returns: A MatPlotLib axes object
Return type: object

plot_cluster(ax=None, **kwargs)[source]¶

Plot the graph based on the clusters generated by the markov clustering algorithm

Parameters: ax (object) – A MatPlotLib axes object.
Returns: ax – A MatPlotLib axes object.
Return type: object

ratio_checks(*args, **kwargs)[source]¶: Apply a ratio check to all edges in the graph

See also

autocnet.matcher.cpu_outlier_detector.DistanceRatio.compute

save(filename)[source]¶: Save the graph object to disk. :param filename: The relative or absolute PATH where the network is saved :type filename: str

save_features(out_path)[source]¶

Save the features (keypoints and descriptors) for the specified nodes.

Parameters: out_path (str) – Location of the output file. If the file exists, features are appended. Otherwise, the file is created.

serials()[source]¶

Create a dictionary of ISIS3 compliant serial numbers for each node in the graph.

Returns: serials – with key equal to the node id and value equal to an ISIS3 compliant serial number or None
Return type: dict

size(weight=None)[source]¶

This replaces the built-in size method to properly support Python 3 rounding.

Parameters: weight (string or None, optional (default=None)) – The edge attribute that holds the numerical value used as a weight. If None, then each edge has weight 1.
Returns: nedges – The number of edges or sum of edge weights in the graph.
Return type: int

subgraph_from_matches()[source]¶

Returns a sub-graph where all edges have matches. (i.e. images with no matches are removed)

Returns: A networkX graph object
Return type: Object

subpixel_register(*args, **kwargs)[source]¶: Compute subpixel offsets for all edges using identical parameters

See also

autocnet.graph.edge.Edge.subpixel_register

suppress(*args, **kwargs)[source]¶: Apply a metric of point suppression to the graph

See also

autocnet.matcher.cpu_outlier_detector.SpatialSuppression

symmetry_checks()[source]¶: Apply a symmetry check to all edges in the graph

to_filelist()[source]¶

Generate a file list for the entire graph.

Returns: filelist – A list where each entry is a string containing the full path to an image in the graph.
Return type: list

to_isis(outname, flistpath=None, target='Mars')[source]¶: Write the control network out to the ISIS3 control network format.

property unmatched_edges¶: Returns a list of edges (source, destination) that do not have entries in the matches dataframe.

validate_points()[source]¶: Ensure that all control points currently in the nework are valid. Criteria for validity: * Singularity: A control point can have one and only one measure from any image :returns: :rtype: pd.Series

class autocnet.graph.network.NetworkCandidateGraph(*args, **kwargs)[source]¶

add_from_filelist(filelist, clear_db=False)[source]¶

Parse a filelist to add nodes to the database.

Parameters

filelist (list, str) – If a list, this is a list of paths. If a str, this is a path to a file containing a list of image paths that is newline (“n”) delimited.
clear_db (boolean) – truncates all tables in the active database.

add_from_remote_database(source_db_config, path, query_string='SELECT * FROM public.images LIMIT 10')[source]¶

This is a constructor that takes an existing database containing images and sensors, copies the selected rows into the project specified in the autocnet_config variable, and instantiates a new NetworkCandidateGraph object. This method is similar to the from_database method. The main difference is that this method assumes that the image and sensor rows are prepopulated in an external db and simply copies those entires into the currently speficied project.

Currently, this method does NOT check for duplicate serial numbers during the bulk add. Therefore multiple runs of this method on the same database will fail.

Parameters

source_db_config (dict) –

In the form: {‘username’:’somename’,
’password’:’somepassword’, ‘host’:’somehost’, ‘pgbouncer_port’:6543, ‘name’:’somename’}
path (str) – The PATH to which images in the database specified in the config will be copied to. This method duplicates the data and copies it to a user defined PATH to avoid issues with updating image ephemeris across projects.
query_string (str) – An optional string to select a subset of the images in the database specified in the config.

Example

>>> ncg = NetworkCandidateGraph()
>>> ncg.config_from_dict(new_config)
>>> source_db_config = {'username':'jay',
'password':'abcde',
'host':'autocnet.wr.usgs.gov',
'pgbouncer_port':5432,
'name':'mars'}
>>> geom = 'LINESTRING(145 10, 145 10.25, 145.25 10.25, 145.25 10, 145 10)'
>>> srid = 949900
>>> outpath = '/scratch/jlaura/fromdb'
>>> query = f"SELECT * FROM ctx WHERE ST_INTERSECTS(geom, ST_Polygon(ST_GeomFromText('{geom}'), {srid})) = TRUE"
>>> ncg.add_from_remote_database(source_db_config, outpath, query_string=query)

add_image(img_path)[source]¶

Upload a single image to NetworkCandidateGraph associated DB.

Parameters: img_path (str) – absolute path to image
Returns: node.id – The id of the newly added node.
Return type: int

apply(function, on='edge', args=(), walltime='01:00:00', chunksize=1000, arraychunk=25, filters={}, query_string='', reapply=False, log_dir=None, queue=None, redis_queue='processing_queue', exclude=None, **kwargs)[source]¶

A mirror of the apply function from the standard CandidateGraph object. This implementation dispatches the job to the cluster as an independent operation instead of applying an arbitrary function locally.

This methods returns the number of jobs submitted. The job status is then asynchronously updated as the jobs complete.

Parameters

function (string / obj) – The function to apply. This can be either the full, importable path from this library or an arbitrary function that will be serialized. If the arbitrary function requires imports external to this library, those imports must be made within the function scope.
on (str) – {‘edge’, ‘edges’, ‘e’, 0} for an edge {‘node’, ‘nodes’, ‘n’ 1} for a node {‘measures’, ‘measure’, ‘m’, ‘2’} for measures {‘points’, ‘point’, ‘p’, ‘3’} for points
args (tuple) – Of additional arguments to pass to the apply function
walltime (str) – in the format Hour:Minute:Second, 00:00:00
chunksize (int) – The maximum number of jobs to submit per job array. Defaults to 1000. This number may be have an actualy higher or lower limited based on how the cluster has been configured.
arraychunk (int) – The number of concurrent jobs to run per job array. e.g. chunksize=100 and arraychunk=25 gives the job array 1-100%25
filters (dict) – Of simple filters to apply on database rows where the key is the attribute and the value used to check equivalency (e.g., attribute == value). This is usable only when applying to measures, points, or overlays. Filters can not be used with a query_string. Filters are included as a convenience and are really only usable for simple equivalency checks.
query_string (str) – A SQL query to be applied to the iterable. This is usable only when applying to measures, points, or overlays. The query_string can not be used with a filter and is appropriate for any queries.
reapply (bool) – Flag indicating whether you want to resubmit jobs that are still on the queue after an initial apply due to an slurm launching errors.
log_dir (str) – absolute path of directory used to store the jobs logs, defaults to location indicated in the configuration file.
kwargs (dict) – Of keyword arguments passed to the function being applied
queue (str) – The cluster processing queue to submit jobs to. If None (default), use the cluster processing queue from the config file.
redis_queue (str) – The redis queue to push messages to that are then pulled by the cluster job this call launches. Options are: ‘processing_queue’ (default) or ‘working_queue’

Returns

job_str – The string job that is submitted to the job scheduler

Return type

str

Examples

Apply a function to the overlay table omitting those overlay rows that already have points within them and have an area less than a given threshold.

>>> query_string = 'SELECT overlay.id FROM overlay LEFT JOIN            points ON ST_INTERSECTS(overlay.geom, points.geom) WHERE                points.id IS NULL AND ST_AREA(overlay.geom) >= 0.0001;'
>>> njobs = ncg.apply('spatial.overlap.place_points_in_overlap', on='overlaps', query_string=query_string)

Apply a function to the overlay table and pass keyword arguments (kwargs) to the function.

>>> def ns(x):
        from math import ceil
        return ceil(round(x,1)*8)
>>> def ew(x):
        from math import ceil
        return ceil(round(x,1)*2)
>>> distribute_points_kwargs = {'nspts_func':ns, 'ewpts_func':ew, 'method':'classic'}
>>> njobs = ncg.apply('spatial.overlap.place_points_in_overlap',            on='overlaps', distribute_points_kwargs=distribute_points_kwargs)

clear_db(tables=None)[source]¶

Truncate all of the database tables and reset any autoincrement columns to start with 1.

Parameters: table (str or list of str, optional) – the table name of a list of table names to truncate

clear_queues()[source]¶

Delete all messages from the redis queue. This a convenience method. The redis_queue object is a redis-py StrictRedis object with API documented at: https://redis-py.readthedocs.io/en/latest/#redis.StrictRedis

This also needs to restart any threaded watchers of the queues.

config_from_dict(config_dict, async_watchers=False)[source]¶

A NetworkCandidateGraph uses a database. This method loads a config dict to set up the connection. Additionally, this loads planetary information and settings for other operations the candidate graph can perform.

Parameters

filepath (str) – The path to the config file
async_watchers (bool) – If True the ncg will also spawn redis queue watching threads that manage asynchronous database inserts. This is primarily used for increased write performance.

config_from_file(filepath, async_watchers=False)[source]¶

A NetworkCandidateGraph uses a database. This method parses a config file to set up the connection. Additionally, this loads planetary information and settings for other operations the candidate graph can perform.

Parameters

filepath (str) – The path to the config file
async_watchers (bool) – If True the ncg will also spawn redis queue watching threads that manage asynchronous database inserts. This is primarily used for increased write performance.

copy_images(newdir)[source]¶

Copy images from a given directory into a new directory and update the ‘path’ column in the Images table.

Parameters: newdir (str) – The full output PATH where the images are to be copied to.

distribute_ground_density(threshold=4, distribute_points_kwargs={})[source]¶

Distribute candidate ground points into overlaps with a number of images greater than or equal to the threshold. This function returns a list of 2d nd-arrays where the first element is the longitude and the second element is the latitude.

Parameters

distirbute_points_kwargs (dict) – Of arguments that are passed on the the distribute_points_in_geom argument in autocnet.cg.cg
threshold (int) – Overlaps intersecting threshold images or greater have points placed. Default 4.

Returns

valid – n, 2 array in the form lon, lat

Return type

np.ndarray

Examples

Usage for distribute_ground_density is identical to usage for distribute_ground_uniform.

Previous topic

Next topic

This Page

graph.network — Network File Representation¶

`graph.network` — Network File Representation¶