grakel.Graph¶
-
class
grakel.Graph(initialization_object=None, node_labels=None, edge_labels=None, graph_format='auto', construct_labels=False)[source][source]¶ The general graph class.
A general graph class that supports adjacency, dictionary formats while beeing memory/computationaly sustainable.
- Parameters
- initialization_objectdict, list or array-like, square, default=None
The initialisation object for the graph (valid-graph-format).
If given a dictionary the input can be as follows:
2-level nested dictionaries from edge symbols to weights
Dictionary of symbols to list of symbols (unweighted)
Dictionary of tuples to weights (weighted)
Iterable of tuples of len 2 (unweighted)
Iterable of tuples of len 3 (vertex, vertex, weight)
If given an array the input can be as follows:
array-like lists of lists
np.array
sparse matrix (scipy.sparse)
- node_labelsdict, default=None
A label dictionary corresponding to all vertices of the graph:
for adjacency matrix labels should be given to numbers starting from 0 and ending in N-1, where the matrix has size N by N
for dictionary labels should correspond to all keys
- edge_labelsdict, default=None
A labels dictionary corresponding to all edges of the graph with keys: index/symbol-tuples and value: labels.
- graph_formatstr, valid_values={“dictionary”, “adjacency”, “all”, “auto”}, default=None
Defines the internal representation of the graph object which can be a dictionary as a matrix, or both:
for dictionary: “dictionary”
for adjacency_matrix: “adjacency”
for both: “all”
for the current_format (if existent): “auto”
- Attributes
- nint
The one dimension of the (square) adjacency matrix. Signifies the number of vertices.
- adjacency_matrixnp.array
The adjacency_matrix corresponding to the graph.
- index_node_labelsdict
Label dictionary for indeces, of adjacency matrix. Keys are valid numbers from 0 to n-1.
- index_edge_labelsdict
Label dictionary for edges, of adjacency matrix. Keys are tuple pairs of symbols with valid numbers from 0 to n-1, that have a positive adjacency matrix value.
- verticesset
The set of vertices corresponding to the edge_dictionary representation.
- edge_dictionarydict
A 2-level nested dictionary from edge symbols to weights.
- node_labelsdict
Label dictionary for nodes. Keys are vertex symbols inside vertices.
- edge_labelsdict
Label dictionary for edges. Keys are tuple pairs of symbols inside vertices and edges.
- edsamicdict
Edge-Dictionary-Symbols-Adjacency-Matrix-Index-Correspondance. A dictionary which translates dictionary symbols to adjacency matrix indexes, when storing both formats.
- shortest_path_matnp.array, square
Holds the shortest path matrix.
- label_groupdict
A 2-level nested dict that after the first level of a pair tuple for purpose: “adjacency”, “dictionary” and “vertex”,”edge” specification holds the inverse map of labels.
- laplacian_graphnp.array
Holds the graph laplacian.
- _formatstr, valid_values={“adjacency”, “dictionary”, “all”}
Private attribute that keeps the current format.
Methods
build_graph(self, g[, node_labels, edge_labels])Build a graph structure, given a supported graph representation.
build_shortest_path_matrix(self[, …])Build and return the shortest path matrix between all nodes.
change_format(self, graph_format)Change the format of the graph from an existing to an other.
construct_labels(self[, label_type, purpose])Construct labels (if user does not provide).
convert_labels(self[, target_format, …])Convert labels to a desired format.
desired_format(self, graph_format[, warn])Change the graph format, to include the desired.
get_adjacency_matrix(self)Get the adjacency matrix.
get_edge_dictionary(self)Get the edge dictionary.
get_edges(self[, purpose, with_weights])Create an iterable of edges as tuples.
get_graph_object(self)Return the graph object corresponding to ‘any’.
get_label_group(self[, label_type, purpose])Calculate the inverse dictionary for vertex labels (once).
get_labels(self[, label_type, purpose, …])Get labels corresponding to the purpose.
get_subgraph(self, vertices)Calculate the subgraph of object in the same format as the original.
get_vertices(self[, purpose])Create an iterable of vertices.
label(self, obj[, label_type, purpose])Get the label of a vertex.
laplacian(self[, save])Calculate the laplacian of the given graph.
neighbors(self, vertex[, purpose, with_weights])Find all neighbors of a vertex.
nv(self)Get the number of vertices for any existing format.
produce_neighborhoods(self[, r, purpose, …])Calculate neighborhoods for each node of a Graph, up to a depth.
relabel(self, new_labels[, purpose, label_type])Relabel the graph object, supporting the current format.
__init__ function of the graph object.
- Attributes
- laplacian_graph
- shortest_path_mat
Methods
build_graph(self, g[, node_labels, edge_labels])Build a graph structure, given a supported graph representation.
build_shortest_path_matrix(self[, …])Build and return the shortest path matrix between all nodes.
change_format(self, graph_format)Change the format of the graph from an existing to an other.
construct_labels(self[, label_type, purpose])Construct labels (if user does not provide).
convert_labels(self[, target_format, …])Convert labels to a desired format.
desired_format(self, graph_format[, warn])Change the graph format, to include the desired.
get_adjacency_matrix(self)Get the adjacency matrix.
get_edge_dictionary(self)Get the edge dictionary.
get_edges(self[, purpose, with_weights])Create an iterable of edges as tuples.
get_graph_object(self)Return the graph object corresponding to ‘any’.
get_label_group(self[, label_type, purpose])Calculate the inverse dictionary for vertex labels (once).
get_labels(self[, label_type, purpose, …])Get labels corresponding to the purpose.
get_subgraph(self, vertices)Calculate the subgraph of object in the same format as the original.
get_vertices(self[, purpose])Create an iterable of vertices.
label(self, obj[, label_type, purpose])Get the label of a vertex.
laplacian(self[, save])Calculate the laplacian of the given graph.
neighbors(self, vertex[, purpose, with_weights])Find all neighbors of a vertex.
nv(self)Get the number of vertices for any existing format.
produce_neighborhoods(self[, r, purpose, …])Calculate neighborhoods for each node of a Graph, up to a depth.
relabel(self, new_labels[, purpose, label_type])Relabel the graph object, supporting the current format.
-
__init__(self, initialization_object=None, node_labels=None, edge_labels=None, graph_format='auto', construct_labels=False)[source][source]¶ __init__ function of the graph object.
-
build_graph(self, g, node_labels=None, edge_labels=None)[source][source]¶ Build a graph structure, given a supported graph representation.
- Parameters
- ga valid graph format
Similar to intialization object (of
__init__).- node_labels: dict, default=None
Node labels dictionary relevant to g format.
- edge_labels: dict, default=None
Edge labels dictionary relevant to g format.
- Returns
- None.
-
build_shortest_path_matrix(self, algorithm_type='auto', clean=False, labels='vertex')[source][source]¶ Build and return the shortest path matrix between all nodes.
- Parameters
- algorithm_typestr, valid_values={“auto”, “adjacency”, “dictionary”}, default=”auto”
Defines which shortest-path algorithm will be used for building the shortest path matrix:
“dijkstra” : choses the dijkstra algorithm (Matrix computation complexity: \(O(|V|(|E|+|V|)log(|V|))\)
“floyd_warshall” : choses the floyd-warshall algorithm (Matrix computation complexity: \(O(|V|^3)\)
“auto” : choses the best possible algorithm for the current format
- cleanbool, default=False
Construct the shortest path matrix from scratch or output existing if exists
- labelsstr, valid_values={“vertex”, “edge”, “all”, “none”}, default=”vertex”
Returns labels corresponding for the indexes of the shortest path matrix for vertices, for edge (only for the valid ones on the original graph), for both (“all”) and for no labels (“none”)
- Returns
- shortest_path_matrixnp.array, shape=(\(|V|\), \(|V|\))
The produced shortest path matrix.
- vertex_labelsdict
The vertex labels, outputed only if labels parameter is either “vertex” or “all”.
- edge_labelsdict
The edge labels, outputed only if labels parameter is either “edge” or “all”.
-
change_format(self, graph_format)[source][source]¶ Change the format of the graph from an existing to an other.
- Parameters
- graph_formatstr, valid_values={“dictionary”, “adjacency”, “all”}
Defines the internal representation of the graph object which can be a dictionary as a matrix, or both:
for dictionary: “dictionary”
for adjacency_matrix: “adjacency”
for both: “all”
- Returns
- None.
-
construct_labels(self, label_type='vertex', purpose='adjacency')[source][source]¶ Construct labels (if user does not provide).
- Parameters
- label_typestr, valid_values={“vertex”, “edge”}, default=”vertex”
What kind of labels are going to be constructed
- purposestr, valid_values={“adjacency”, “dictionary”}, default=”adjacency”
Defines if the labels correspond to dictionary or adjacency matrix
- Returns
- None.
-
convert_labels(self, target_format='dictionary', purpose='all', init=False)[source][source]¶ Convert labels to a desired format.
- Parameters
- target_formatstr, valid_values={“adjacency”, “dictionary”}, default=”dictionary”
Defines what the target format for conversion will be.
- purposestr, valid_values={“adjacency”, “dictionary”, “all”}, default=”all”
Defines if the labels will be converted for dictionary, adjacency matrix or both.
- initbool, default=False
An override parameter for format checks, usefull for initialisation.
- Returns
- None.
-
desired_format(self, graph_format, warn=False)[source][source]¶ Change the graph format, to include the desired.
- Parameters
- graph_formatstr, valid_values={“dictionary”, “adjacency”, “all”}
Defines the internal representation of the graph object which can be a dictionary as a matrix, or both:
for dictionary: “dictionary”
for adjacency_matrix: “adjacency”
for both: “all”
- warnbool, default=False
Warn the user if the format of the graph is being changed.
- Returns
- None.
-
get_adjacency_matrix(self)[source][source]¶ Get the adjacency matrix.
Format agnostic method.
- Parameters
- None.
- Returns
- adjacency_matrixnp.array
Returns the adjacency matrix of the current graph.
-
get_edge_dictionary(self)[source][source]¶ Get the edge dictionary.
Format agnostic method.
- Parameters
- None.
- Returns
- edge_dictionarydict
Returns the edge_dictionary of the current graph.
-
get_edges(self, purpose='adjacency', with_weights=False)[source][source]¶ Create an iterable of edges as tuples.
- Parameters
- purposestr, valid_values={“adjacency”, “dictionary”}, default=”adjacency”
Defines if the edges is given for the “dictionary” format of the graph (symbol) to the “adjacency” (index).
- Returns
- verticeslist
Returns a list of tuples for edges.
-
get_graph_object(self)[source][source]¶ Return the graph object corresponding to ‘any’.
Format agnostic method.
- Parameters
- None.
- Returns
- gdict or np.array
The graph Object.
-
get_label_group(self, label_type='vertex', purpose='dictionary')[source][source]¶ Calculate the inverse dictionary for vertex labels (once).
- Parameters
- label_typestr, valid_values={“vertex”, “edge”}, default=”vertex”
Defines if the the labels-group will correspond to vertices or edges.
- purposestr, valid_values={“dictionary”, “adjacency”, “any”},
default=”dictionary”
Defines if the labels-group will correspond to “dictionary” (symbols), to “adjacency” (indexes) or to “any” valid format (if “all” the result is for “adjacency”).
- Returns
- label_groupdict
Returns the inverse label group.
-
get_labels(self, label_type='vertex', purpose='adjacency', return_none=False)[source][source]¶ Get labels corresponding to the purpose.
- Parameters
- label_typestr, valid_values={“vertex”, “edge”}, default=”vertex”
Defines if the the labels will correspond to vertices or edges.
- purposestr, valid_values={“dictionary”, “adjacency”, “any”},
default=”dictionary”
Defines if the labels will correspond to “dictionary” (symbols), to “adjacency” indexes, or to “any” valid format (if “all” the result is for “adjacency”).
- return_nonebool
Defines if get_labels can return None in case of label absence, or raise an error.
- Returns
- labelsdict,
Returns the labels for the given type and purpose.
-
get_subgraph(self, vertices)[source][source]¶ Calculate the subgraph of object in the same format as the original.
- Parameters
- verticesiterable
An iterbale vertices extracted from the original graph.
- Returns
- subgraphgraph
The induced subgraph, from the input vertices.
-
get_vertices(self, purpose='adjacency')[source][source]¶ Create an iterable of vertices.
- Parameters
- purposestr, valid_values={“adjacency”, “dictionary”, “any”},
default=”adjacency”
Defines if the vertices will correspond given for the “dictionary” format of the graph (symbol) to the “adjacency” (index) or to “any” existing format (if “all” the expected type is for “adjacency”).
- Returns
- verticesiterable
Returns an iterable on vertices
-
label(self, obj, label_type='vertex', purpose='dictionary')[source][source]¶ Get the label of a vertex.
- Parameters
- objhashable
The candidate labeled object for the corresponding purpose and label type.
- label_typestr, valid_values={“vertex”, “edge”}, default=”vertex”
Defines if the lookup of the label will be done for vertices or edges.
- purposestr, valid_values={“dictionary”, “adjacency”, “any”}, default=”dictionary”
Defines if the lookup will be done on the existing (“any” - if “all” default is adjacency) to the “dictionary” or to the “adjacency” format of the graph.
- Returns
- labelstr, list, …, valid-label-type
Returns the label of the current object on the defined lookup.
-
laplacian(self, save=True)[source][source]¶ Calculate the laplacian of the given graph.
- Parameters
- savebool, default=True
Optional parameter to store the matrix.
- Returns
- laplacianarray-like
Returns the graph laplacian
-
neighbors(self, vertex, purpose='any', with_weights=False)[source][source]¶ Find all neighbors of a vertex.
- Parameters
- vertexhashable
The vertex, which neighbors we are searching for.
- purposestr, valid_values={“adjacency”, “dictionary”, “any”},
default=”any”
Defines if the vertex is given for the “dictionary” format of the graph (symbol) to the “adjacency” (index) or to “any” existing format (if “all” the expected type is for “adjacency”).
- with_weightsbool, default=False
Defines if the neighbours will be outputed with weights.
- Returns
- neighborslist or dict
- The neighbors of the given vertex.
with_weights=False: list of neighbor vertices
with_weights=True: dictionary between neighbor vertices and edge labels
-
nv(self)[source][source]¶ Get the number of vertices for any existing format.
- Parameters
- None.
- Returns
- num_of_verticesint
Returns the number of vertices.
-
produce_neighborhoods(self, r=3, purpose='adjacency', with_distances=False, d=-1, sort_neighbors=True)[source][source]¶ Calculate neighborhoods for each node of a Graph, up to a depth.
- Parameters
- rint
The neighborhood depth (radius).
- purposestr, valid_values={“adjacency”, “dictionary”},
default=”adjacency”
Defines if the neighborhood symbols will correspond given for the “dictionary” format of the graph (symbol) to the “adjacency” (index).
- with_distancesbool, default=False
Defines if we need to calculate BFS distances for each pair.
- dint, default=-1
Maximum distance considered. If -1 is provided the distance is as max as the radius r.
- Returns
- Ndict
A level, vertex nested dictionary of lists, corresponding to the neighbors of level \(l\) for a certain vertex \(v\).
- Ddict
For each level, set of tuples of nodes connected in that level. Appears only if with_distances is True.
- Dist_pairdict
A dictionary of all pairs and their distances.
-
relabel(self, new_labels, purpose='dictionary', label_type='vertex')[source][source]¶ Relabel the graph object, supporting the current format.
- Parameters
- new_labelsdict
The new labels corresponding to the label type and purpose.
- purposestr, valid_values={“dictionary”, “adjacency”}, default=”dictionary”
Defines if the new labels are given for “adjacency” or “dictionary”.
- label_typestr, valid_values={“vertex”, “edge”}, default=”vertex”
Defines if the new labels are for vertices or edges.
- Returns
- None.
