l2gv2.graphs package

Contents

l2gv2.graphs package#

Submodules#

l2gv2.graphs.graph module#

Graph class.

class l2gv2.graphs.graph.Graph(edge_index, edge_attr=None, x=None, y=None, num_nodes=None, adj_index=None, ensure_sorted=False, undir=None, nodes=None)#

Bases: object

numpy backed graph class with support for memmapped edge_index

adj(node: int)#

list neighbours of node

Parameters:

node – source node

Returns:

neighbours

adj_weighted(node: int)#

list neighbours of node and corresponding edge weight

Parameters:

node – source node

Returns:

neighbours, weights

abstract bfs_order(start=0)#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

Sequence of node indeces

abstract connected_component_ids()#

return connected component ids where ids are sorted in decreasing order by component size

Returns:

Sequence of node indeces

degree: Sequence#
device = 'cpu'#
abstract edges()#

iterator over edges

abstract edges_weighted()#

iterator over weighted edges where each edge is a tuple (source, target, weight)

classmethod from_networkx(nx_graph: Graph, weight=None)#

Create a graph from a networkx graph.

classmethod from_tg(data)#

Create a graph from a torch_geometric data object.

has_node_labels()#

TODO: docstring for has_node_labels.

abstract is_edge(source, target)#

TODO: docstring for is_edge.

lcc(relabel=False)#

TODO: docstring for lcc.

abstract neighbourhood(nodes, hops: int = 1)#

find the neighbourhood of a set of source nodes

note that the neighbourhood includes the source nodes themselves

Parameters:

  • nodes – indices of source nodes

  • hops – number of hops for neighbourhood

Returns:

neighbourhood

property nodes#

docstring for nodes.

Type:

TODO

nodes_in_lcc()#

Iterator over nodes in the largest connected component

property num_edges#

docstring for num_edges.

Type:

TODO

property num_features#

docstring for num_features.

Type:

TODO

abstract partition_graph(partition, self_loops=True)#

TODO: docstring for partition_graph.

abstract sample_negative_edges(num_samples)#

TODO: docstring for sample_negative_edges.

sample_positive_edges(num_samples)#

TODO: docstring for sample_positive_edges.

abstract subgraph(nodes: Iterable, relabel=False, keep_x=True, keep_y=True)#

find induced subgraph for a set of nodes

Parameters:

nodes – node indeces

Returns:

subgraph

to(graph_cls)#

TODO: docstring for to.

to_networkx()#

convert graph to NetworkX format

property weighted#

boolean indicating if graph is weighted

weights: Sequence#

l2gv2.graphs.npgraph module#

TODO: module docstring for network/npgraph.py

class l2gv2.graphs.npgraph.JitGraph(*args, **kwargs)#

Bases: JitGraph

TODO: docstring for JitGraph.

class_type = jitclass.JitGraph#78e0b4c5ead0<edge_index:array(int64, 2d, A),adj_index:array(int64, 1d, A),degree:array(int64, 1d, A),num_nodes:int64>#
class l2gv2.graphs.npgraph.NPGraph(*args, ensure_sorted=False, **kwargs)#

Bases: Graph

numpy backed graph class with support for memmapped edge_index

bfs_order(start=0)#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

tensor of node indeces

connected_component_ids()#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

tensor of node indeces

edges()#

return list of edges where each edge is a tuple (source, target)

edges_weighted()#

return list of edges where each edge is a tuple (source, target, weight)

is_edge(source, target)#

TODO: docstring for is_edge.

classmethod load(folder, mmap_edges=None, mmap_features=None)#

TODO: docstring for load.

neighbourhood(nodes, hops: int = 1)#

find the neighbourhood of a set of source nodes

note that the neighbourhood includes the source nodes themselves

Parameters:

  • nodes – indices of source nodes

  • hops – number of hops for neighbourhood

Returns:

neighbourhood

nodes_in_lcc()#

List all nodes in the largest connected component

partition_graph(partition, self_loops=True)#

TODO: docstring for partition_graph.

sample_negative_edges(num_samples)#

TODO: docstring for sample_negative_edges.

sample_positive_edges(num_samples)#

TODO: docstring for sample_positive_edges.

save(folder)#

TODO: docstring for save.

strength#

tensor of node strength

subgraph(nodes: Tensor, relabel=False, keep_x=True, keep_y=True)#

find induced subgraph for a set of nodes

Parameters:

nodes – node indeces

Returns:

subgraph

l2gv2.graphs.tgraph module#

TODO: module docstring for network/tgraph.py

class l2gv2.graphs.tgraph.TGraph(*args, ensure_sorted=False, **kwargs)#

Bases: Graph

Wrapper class for pytorch-geometric edge_index providing fast adjacency look-up.

bfs_order(start=0)#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

tensor of node indeces

connected_component_ids()#

Find the (weakly)-connected components. Component ids are sorted by size, such that id=0 corresponds to the largest connected component

degree: Sequence#

tensor of node degrees

property device#

device holding graph data

edges()#

return list of edges where each edge is a tuple (source, target)

edges_weighted()#

return list of edges where each edge is a tuple (source, target, weight)

is_edge(source, target)#

TODO: docstring for is_edge.

neighbourhood(nodes: Tensor, hops: int = 1)#

find the neighbourhood of a set of source nodes

note that the neighbourhood includes the source nodes themselves

Parameters:

  • nodes – indices of source nodes

  • hops – number of hops for neighbourhood

Returns:

neighbourhood

nodes_in_lcc()#

List all nodes in the largest connected component

num_nodes#

number of nodes

partition_graph(partition, self_loops=True)#

TODO: docstring for partition_graph.

sample_negative_edges(num_samples)#

TODO: docstring for sample_negative_edges.

sample_positive_edges(num_samples)#

TODO: docstring for sample_positive_edges.

strength#

tensor of node strength

subgraph(nodes: Tensor, relabel=False, keep_x=True, keep_y=True)#

find induced subgraph for a set of nodes

Parameters:

nodes – node indeces

Returns:

subgraph

to(*args, graph_cls=None, **kwargs)#

Convert to different graph type or move to device

Parameters:

  • graph_cls – convert to graph class

  • device – convert to device

Can only specify one argument. If positional, type of move is determined automatically.

to_networkx()#

convert graph to NetworkX format

l2gv2.graphs.utils module#

Graph data handling

class l2gv2.graphs.utils.UnionFind(*args, **kwargs)#

Bases: UnionFind

Union-find data structure.

Each unionFind instance X maintains a family of disjoint sets of hashable objects, supporting the following two methods:

  • X[item] returns a name for the set containing the given item. Each set is named by an arbitrarily-chosen one of its members; as long as the set remains unchanged it will keep the same name. If the item is not yet part of a set in X, a new singleton set is created for it.

  • X.union(item1, item2, …) merges the sets containing each item into a single larger set. If any item is not yet part of a set in X, it is added to X as one of the members of the merged set.

    Union-find data structure. Based on Josiah Carlson’s code, https://code.activestate.com/recipes/215912/ with significant additional changes by D. Eppstein. http://www.ics.uci.edu/~eppstein/PADS/UnionFind.py

class_type = jitclass.UnionFind#78e0b4c68b50<parents:array(int64, 1d, A),weights:array(int64, 1d, A)>#
l2gv2.graphs.utils.conductance(graph: Graph, source, target=None)#

compute conductance between source and target nodes

Parameters:

  • graph – input graph

  • source – set of source nodes

  • target – set of target nodes (if target=None, consider all nodes that are not in source as target)

Returns:

conductance

l2gv2.graphs.utils.induced_subgraph(data: Data, nodes, extend_hops=0)#

Create a subgraph induced by the given nodes.

Parameters:

  • data – input graph

  • nodes – list of nodes to induce the subgraph on

  • extend_hops – number of hops to extend the subgraph

l2gv2.graphs.utils.spanning_tree(graph: TGraph, maximise=False)#

Implements Kruskal’s algorithm for finding minimum or maximum spanning tree.

Parameters:

  • graph – input graph

  • maximise – if True, find maximum spanning tree (default: False)

Returns:

spanning tree

l2gv2.graphs.utils.spanning_tree_mask(graph: Graph, maximise=False)#

Return an edge mask for minimum or maximum spanning tree edges.

Parameters:

  • graph – input graph

  • maximise – if True, find maximum spanning tree (default: False)

Module contents#

TODO: module docstring for network/__init__.py

class l2gv2.graphs.Graph(edge_index, edge_attr=None, x=None, y=None, num_nodes=None, adj_index=None, ensure_sorted=False, undir=None, nodes=None)#

Bases: object

numpy backed graph class with support for memmapped edge_index

adj(node: int)#

list neighbours of node

Parameters:

node – source node

Returns:

neighbours

adj_weighted(node: int)#

list neighbours of node and corresponding edge weight

Parameters:

node – source node

Returns:

neighbours, weights

abstract bfs_order(start=0)#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

Sequence of node indeces

abstract connected_component_ids()#

return connected component ids where ids are sorted in decreasing order by component size

Returns:

Sequence of node indeces

degree: Sequence#
device = 'cpu'#
abstract edges()#

iterator over edges

abstract edges_weighted()#

iterator over weighted edges where each edge is a tuple (source, target, weight)

classmethod from_networkx(nx_graph: Graph, weight=None)#

Create a graph from a networkx graph.

classmethod from_tg(data)#

Create a graph from a torch_geometric data object.

has_node_labels()#

TODO: docstring for has_node_labels.

abstract is_edge(source, target)#

TODO: docstring for is_edge.

lcc(relabel=False)#

TODO: docstring for lcc.

abstract neighbourhood(nodes, hops: int = 1)#

find the neighbourhood of a set of source nodes

note that the neighbourhood includes the source nodes themselves

Parameters:

  • nodes – indices of source nodes

  • hops – number of hops for neighbourhood

Returns:

neighbourhood

property nodes#

docstring for nodes.

Type:

TODO

nodes_in_lcc()#

Iterator over nodes in the largest connected component

property num_edges#

docstring for num_edges.

Type:

TODO

property num_features#

docstring for num_features.

Type:

TODO

abstract partition_graph(partition, self_loops=True)#

TODO: docstring for partition_graph.

abstract sample_negative_edges(num_samples)#

TODO: docstring for sample_negative_edges.

sample_positive_edges(num_samples)#

TODO: docstring for sample_positive_edges.

abstract subgraph(nodes: Iterable, relabel=False, keep_x=True, keep_y=True)#

find induced subgraph for a set of nodes

Parameters:

nodes – node indeces

Returns:

subgraph

to(graph_cls)#

TODO: docstring for to.

to_networkx()#

convert graph to NetworkX format

property weighted#

boolean indicating if graph is weighted

weights: Sequence#
class l2gv2.graphs.JitGraph(*args, **kwargs)#

Bases: JitGraph

TODO: docstring for JitGraph.

class_type = jitclass.JitGraph#78e0b4c5ead0<edge_index:array(int64, 2d, A),adj_index:array(int64, 1d, A),degree:array(int64, 1d, A),num_nodes:int64>#
class l2gv2.graphs.NPGraph(*args, ensure_sorted=False, **kwargs)#

Bases: Graph

numpy backed graph class with support for memmapped edge_index

bfs_order(start=0)#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

tensor of node indeces

connected_component_ids()#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

tensor of node indeces

degree: Sequence#
edges()#

return list of edges where each edge is a tuple (source, target)

edges_weighted()#

return list of edges where each edge is a tuple (source, target, weight)

is_edge(source, target)#

TODO: docstring for is_edge.

classmethod load(folder, mmap_edges=None, mmap_features=None)#

TODO: docstring for load.

neighbourhood(nodes, hops: int = 1)#

find the neighbourhood of a set of source nodes

note that the neighbourhood includes the source nodes themselves

Parameters:

  • nodes – indices of source nodes

  • hops – number of hops for neighbourhood

Returns:

neighbourhood

nodes_in_lcc()#

List all nodes in the largest connected component

partition_graph(partition, self_loops=True)#

TODO: docstring for partition_graph.

sample_negative_edges(num_samples)#

TODO: docstring for sample_negative_edges.

sample_positive_edges(num_samples)#

TODO: docstring for sample_positive_edges.

save(folder)#

TODO: docstring for save.

strength#

tensor of node strength

subgraph(nodes: Tensor, relabel=False, keep_x=True, keep_y=True)#

find induced subgraph for a set of nodes

Parameters:

nodes – node indeces

Returns:

subgraph

weights: Sequence#
class l2gv2.graphs.TGraph(*args, ensure_sorted=False, **kwargs)#

Bases: Graph

Wrapper class for pytorch-geometric edge_index providing fast adjacency look-up.

bfs_order(start=0)#

return nodes in breadth-first-search order

Parameters:

start – index of starting node (default: 0)

Returns:

tensor of node indeces

connected_component_ids()#

Find the (weakly)-connected components. Component ids are sorted by size, such that id=0 corresponds to the largest connected component

degree: Sequence#

tensor of node degrees

property device#

device holding graph data

edges()#

return list of edges where each edge is a tuple (source, target)

edges_weighted()#

return list of edges where each edge is a tuple (source, target, weight)

is_edge(source, target)#

TODO: docstring for is_edge.

neighbourhood(nodes: Tensor, hops: int = 1)#

find the neighbourhood of a set of source nodes

note that the neighbourhood includes the source nodes themselves

Parameters:

  • nodes – indices of source nodes

  • hops – number of hops for neighbourhood

Returns:

neighbourhood

nodes_in_lcc()#

List all nodes in the largest connected component

num_nodes#

number of nodes

partition_graph(partition, self_loops=True)#

TODO: docstring for partition_graph.

sample_negative_edges(num_samples)#

TODO: docstring for sample_negative_edges.

sample_positive_edges(num_samples)#

TODO: docstring for sample_positive_edges.

strength#

tensor of node strength

subgraph(nodes: Tensor, relabel=False, keep_x=True, keep_y=True)#

find induced subgraph for a set of nodes

Parameters:

nodes – node indeces

Returns:

subgraph

to(*args, graph_cls=None, **kwargs)#

Convert to different graph type or move to device

Parameters:

  • graph_cls – convert to graph class

  • device – convert to device

Can only specify one argument. If positional, type of move is determined automatically.

to_networkx()#

convert graph to NetworkX format

weights: Sequence#
l2gv2.graphs.induced_subgraph(data: Data, nodes, extend_hops=0)#

Create a subgraph induced by the given nodes.

Parameters:

  • data – input graph

  • nodes – list of nodes to induce the subgraph on

  • extend_hops – number of hops to extend the subgraph

l2gv2.graphs.spanning_tree(graph: TGraph, maximise=False)#

Implements Kruskal’s algorithm for finding minimum or maximum spanning tree.

Parameters:

  • graph – input graph

  • maximise – if True, find maximum spanning tree (default: False)

Returns:

spanning tree

l2gv2.graphs.spanning_tree_mask(graph: Graph, maximise=False)#

Return an edge mask for minimum or maximum spanning tree edges.

Parameters:

  • graph – input graph

  • maximise – if True, find maximum spanning tree (default: False)

Contents