tf_G.graph

tf_G.graph Module

It contains the graph implementations on tf_G module.

Graph

class tf_G.graph.graph.Graph(sess: tensorflow.python.client.session.Session, name: str, writer: tensorflow.python.summary.writer.writer.FileWriter = None, edges_np: numpy.ndarray = None, n: int = None, is_sparse: bool = False) → None[source]

Graph class implemented in the top of TensorFlow.

The class codifies the graph using an square matrix of 2-D shape and provides functionality operating with this matrix.

sess

tf.Session – This attribute represents the session that runs the TensorFlow operations.

name

str – This attribute represents the name of the object in TensorFlow’s op Graph.

writer

tf.summary.FileWriter – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.

_listeners

set – The set of objects that will be notified when an edge modifies it weight.

n

int – Represents the cardinality of the vertex set as Python int.

n_tf

tf.Tensor – Represents the cardinality of the vertex set as 0-D Tensor.

m

int – Represents the cardinality of the edge set as Python int.

A_tf

tf.Tensor – Represents the Adjacency matrix of the graph as 2-D Tensor with shape [n,n].

out_degrees_tf

tf.Tensor – Represents the out-degrees of the vertices of the graph as 2-D Tensor with shape [n, 1]

in_degrees_tf

tf.Tensor – Represents the in-degrees of the vertices of the graph as 2-D Tensor with shape [1, n]

A_tf_vertex(vertex: int) → tensorflow.python.framework.ops.Tensor[source]

Method that returns the adjacency of an individual vertex.

This method extracts the corresponding row referred to the vertex passed as parameter. It constructs a vector that contains the weight of the edge between vertex (obtained as parameter) and the vertex at position i in the vector.

Parameters:vertex (int) – The index of the vertex that wants the degree.
Returns:
A 1-D Tensor with the same length as the cardinality
of the vertex set.
Return type:(tf.Tensor)
L_pseudo_inverse_tf

Method that returns the pseudo inverse of the Laplacian matrix.

This method calculates the pseudo inverse matrix of the Laplacian of the Graph. It generates a matrix of the same shape as the Laplacian matrix, i.e. [n, n] where n is the cardinality of the vertex set.

Returns:
A 2-D square Tensor with the he same length as
cardinality of the vertex set representing the laplacian pseudo inverse.
Return type:(tf.Tensor)
L_tf

This method returns the Laplacian of the graph.

The method generates a 2-D Array containing the laplacian matrix of the graph

Returns:
A 2-D Tensor with [n,n] shape where n is the
cardinality of the vertex set
Return type:(tf.Tensor)
__init__(sess: tensorflow.python.client.session.Session, name: str, writer: tensorflow.python.summary.writer.writer.FileWriter = None, edges_np: numpy.ndarray = None, n: int = None, is_sparse: bool = False) → None[source]

Class Constructor of the Graph

This method is called to construct a Graph object. This block of code initializes all the variables necessaries for this class to properly works.

This class can be initialized using an edge list, that fill the graph at this moment, or can be construct it from the cardinality of vertices set given by n parameter.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • name (str) – This attribute represents the name of the object in TensorFlow’s op Graph.
  • writer (tf.summary.FileWriter, optional) – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.
  • edges_np (np.ndarray, optional) – The edge set of the graph codifies as edges_np[:,0] represents the sources and edges_np[:,1] the destinations of the edges. The default value is None.
  • n (int, optional) – Represents the cardinality of the vertex set. The default value is None.
  • is_sparse (bool, optional) – Use sparse Tensors if it’s set to True. The default value is False` Not implemented yet. Show the Todo for more information.

Todo

  • Implement variables as sparse when it’s possible. Waiting to TensorFlow for it.
append(src: int, dst: int) → None[source]

Append an edge to the graph.

This method process an input edge adding it to the graph updating all the variables necessaries to maintain the graph in correct state.

Parameters:
  • src (int) – The id of the source vertex of the edge.
  • dst (int) – The id of the destination vertex of the edge.
Returns:

This method returns nothing.

edge_list_np

Method that returns the edge set of the graph as list.

This method return all the edges of the graph codified as 2-D matrix in which the first dimension represents each edge and second dimension the source and destination vertices of each edge.

Returns:
A 2-D Array with the he same length as cardinality of
the edge set in the first dimension and 2 in the second.
Return type:(np.ndarray)
edge_list_tf

Method that returns the edge set of the graph as list.

This method return all the edges of the graph codified as 2-D matrix in which the first dimension represents each edge and second dimension the source and destination vertices of each edge.

Returns:
A 2-D Tensor with the he same length as cardinality of
the edge set in the first dimension and 2 in the second.
Return type:(tf.Tensor)
in_degrees_np

This method returns the in-degree of all vertex as vector.

The method generates a 1-D Array containing the in-degree of the vertex i at position i

Returns:
A 1-D Array with the same length as cardinality of the
vertex set.
Return type:(np.ndarray)
in_degrees_tf_vector

The in-degrees of the vertices of the graph

Method that returns the in-degrees of the vertices of the graph as 1-D Tensor with shape [n]

Returns:
A 1-D Tensor with the same length as the cardinality
of the vertex set.
Return type:(tf.Tensor)
is_not_sink_tf

This method returns if a vertex is a sink vertex as vector.

The method generates a 1-D Tensor containing the boolean values that indicates if the vertex at position i is a sink vertex.

Returns:
A 1-D Tensor with the same length as cardinality
of the vertex set.
Return type:(tf.Tensor)
is_not_sink_tf_vertex(vertex: int) → TF_type[source]

This method returns if a vertex is a sink vertex as vector.

The method generates a 1-D Tensor containing the boolean values that indicates if the vertex at position i is a sink vertex.

Parameters:vertex (int) – The index of the vertex that wants to know if is sink.
Returns:
A 0-D Tensor that represents if a vertex is a sink
vertex
Return type:(tf.Tensor)
out_degrees_np

This method returns the degree of all vertex as vector.

The method generates a 1-D Array containing the out-degree of the vertex i at position i

Returns:
A 1-D Array with the same length as cardinality of the
vertex set.
Return type:(np.ndarray)
out_degrees_tf_vector

The out-degrees of the vertices of the graph

Method that returns the out-degrees of the vertices of the graph as 1-D Tensor with shape [n]

Returns:A 1-D Tensor with the same length as the cardinality of the vertex set.
Return type:(tf.Tensor)
out_degrees_tf_vertex(vertex: int) → tensorflow.python.framework.ops.Tensor[source]

This method returns the degree of all vertex as vector.

The method generates a 0-D Array containing the out-degree of the vertex i.

Parameters:vertex (int) – The index of the vertex that wants the degree.
Returns:
A 1-D Array with the same length as cardinality of the
vertex set.
Return type:(np.ndarray)
remove(src: int, dst: int) → None[source]

Remove an edge to the graph.

This method process an input edge deleting it to the graph updating all the variables necessaries to maintain the graph in correct state.

Parameters:
  • src (int) – The id of the source vertex of the edge.
  • dst (int) – The id of the destination vertex of the edge.
Returns:

This method returns nothing.

GraphConstructor

class tf_G.graph.graph_constructor.GraphConstructor[source]

Class that helps to construct a Graph object.

This class contains a set of static methods that helps in the task of graph construction and initialization. It provides the generation of a Graph from an edge list, and allows to generate empty Graphs, sparsifier Graphs an also random Graphs.

static as_naive_sparsifier(sess: tensorflow.python.client.session.Session, graph: tf_G.graph.graph.Graph, p: float, is_sparse: bool = False) → tf_G.graph.graph.Graph[source]

Generates a sparsifier graph of the given graph.

The method picks the edges with probability uniform probability p from edge set of the graph given as parameter. This does not provide any guarantee from the structure of the original graph.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • graph (tf_G.Graph) – The input graph to pick the edges
  • p (float) – The picking probability value. It must be in the [0,1] interval.
  • is_sparse (bool) – Use sparse Tensors if it’s set to True. Not implemented yet.
Returns:

The resulting graph with less edges than the original

graph.

Return type:

(tf_G.Graph)

classmethod as_sparsifier(sess, graph: tf_G.graph.graph.Graph, p: float, is_sparse=False)[source]

Generates a sparsifier graph from the given graph.

The method picks the edges with probability uniform probability p from edge set of the graph given as parameter. The sparsifier uses an heuristic to picks the more edges from the vertices with big out_degree to try to maintain the structure of the graph.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • graph (tf_G.Graph) – The input graph to pick the edges.
  • p (float) – The picking probability value. It must be in the [0,1] interval.
  • is_sparse (bool) – Use sparse Tensors if it’s set to True. Not implemented yet.
Returns:

The resulting graph sparsifier with less edges than

the original graph.

Return type:

(tf_G.Graph)

static empty(sess: tensorflow.python.client.session.Session, name: str, n: int, writer: tensorflow.python.summary.writer.writer.FileWriter = None, sparse: bool = False) → tf_G.graph.graph.Graph[source]

Generates an empty Graph.

This method generates an empty graph with the number of vertex fixed at the construction. The graph allows addition and deletion of edges.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • name (str) – This attribute represents the name of the object in TensorFlow’s op Graph.
  • n (int) – The cardinality of vertex set of the empty graph.
  • writer (tf.summary.FileWriter, optional) – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.
  • is_sparse (bool, optional) – Use sparse Tensors if it’s set to True. Not implemented yet. Show the Todo. The default value is False.
Returns:

A empty graph that allows additions and deletions of

edges from vertex in the interval [0,n].

Return type:

(tf_G.Graph)

static empty_sparsifier(sess: tensorflow.python.client.session.Session, name: str, n: int, p: float, writer: tensorflow.python.summary.writer.writer.FileWriter = None, is_sparse: bool = False) → tf_G.graph.graph_sparsifier.GraphSparsifier[source]

Generates an empty Sparsifier Graph.

This method generates an empty sparsifier graph with the number of vertex fixed at the construction. The graph allows addition and deletion of edges. The sparsifier means that the graph will not add all edges. Only a subset of it to improve the performance of the algorithms.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • name (str) – This attribute represents the name of the object in TensorFlow’s op Graph.
  • n (int) – The cardinality of vertex set of the empty graph.
  • p (float) – The picking probability value. It must be in the [0,1] interval.
  • writer (tf.summary.FileWriter, optional) – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.
  • is_sparse (bool, optional) – Use sparse Tensors if it’s set to True. Not implemented yet. Show the Todo. The default value is False.
Returns:

A empty graph that allows additions and

deletions of edges from vertex in the interval [0,n].

Return type:

(tf_G.GraphSparsifier)

static from_edges(sess: tensorflow.python.client.session.Session, name: str, edges_np: numpy.ndarray, writer: tensorflow.python.summary.writer.writer.FileWriter = None, is_sparse: bool = False) → tf_G.graph.graph.Graph[source]

Generates a graph from a set of edges.

This method acts as interface between the Graph constructor and the rest exterior.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • name (str) – This attribute represents the name of the object in TensorFlow’s op Graph.
  • edges_np (np.ndarray) – The edge set of the graph codifies as edges_np[:,0] represents the sources and edges_np[:,1] the destinations of the edges.
  • writer (tf.summary.FileWriter, optional) – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.
  • is_sparse (bool, optional) – Use sparse Tensors if it’s set to True. Not implemented yet. Show the Todo. The default value is False.
Returns:

A graph containing all the edges passed as input in

edges_np.

Return type:

(tf_G.Graph)

static unweighted_random(sess: tensorflow.python.client.session.Session, name: str, n: int, m: int, writer: tensorflow.python.summary.writer.writer.FileWriter = None, is_sparse: bool = False) → tf_G.graph.graph.Graph[source]

Generates a random unweighted graph.

This method generates a random unweighted graph with n vertex and m edges. The edge set is generated using a uniform distribution.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • name (str) – This attribute represents the name of the object in TensorFlow’s op Graph.
  • n (int) – The cardinality of vertex set of the random graph.
  • m (int) – The cardinality of edge set of the random graph.
  • writer (tf.summary.FileWriter, optional) – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.
  • is_sparse (bool, optional) – Use sparse Tensors if it’s set to True. Not implemented yet. Show the Todo. The default value is False.
Returns:

A empty graph that allows additions and

deletions of edges from vertex in the interval [0,n].

Return type:

(tf_G.GraphSparsifier)

GraphSparsifier

class tf_G.graph.graph_sparsifier.GraphSparsifier(sess: tensorflow.python.client.session.Session, p: float, graph: tf_G.graph.graph.Graph = None, is_sparse: bool = False, name: str = None, n: int = None, writer: tensorflow.python.summary.writer.writer.FileWriter = None) → None[source]

The graph sparsifier class implemented in the top of TensorFlow.

This class inherits the Graph class and modifies it functionality adding a level of randomness on edge additions and deletions, that improves the performance of the results.

sess

tf.Session – This attribute represents the session that runs the TensorFlow operations.

name

str – This attribute represents the name of the object in TensorFlow’s op Graph.

writer

tf.summary.FileWriter – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.

n

int – Represents the cardinality of the vertex set as Python int.

p

float – The default probability to pick an edge and add it to the GraphSparsifier.

n_tf

tf.Tensor – Represents the cardinality of the vertex set as 0-D Tensor.

m

int – Represents the cardinality of the edge set as Python int.

A_tf

tf.Tensor – Represents the Adjacency matrix of the graph as 2-D Tensor with shape [n,n].

out_degrees_tf

tf.Tensor – Represents the out-degrees of the vertices of the graph as 2-D Tensor with shape [n, 1].

in_degrees_tf

tf.Tensor – Represents the in-degrees of the vertices of the graph as 2-D Tensor with shape [1, n].

__init__(sess: tensorflow.python.client.session.Session, p: float, graph: tf_G.graph.graph.Graph = None, is_sparse: bool = False, name: str = None, n: int = None, writer: tensorflow.python.summary.writer.writer.FileWriter = None) → None[source]

Class Constructor of the GraphSparsfiier

This method is called to construct a Graph object. This block of code initializes all the variables necessaries for this class to properly works.

This class can be initialized using an edge list, that fill the graph at this moment, or can be construct it from the cardinality of vertices set given by n parameter.

Parameters:
  • sess (tf.Session) – This attribute represents the session that runs the TensorFlow operations.
  • p (float) – The default probability to pick an edge and add it to the GraphSparsifier.
  • graph (tf_G.Graph, optional) – The input graph to pick the edges. The default value is None.
  • writer (tf.summary.FileWriter, optional) – This attribute represents a TensorFlow’s Writer, that is used to obtain stats. The default value is None.
  • name (str, optional) – This attribute represents the name of the object in TensorFlow’s op Graph.
  • n (int, optional) – Represents the cardinality of the vertex set. The default value is None.
  • is_sparse (bool, optional) – Use sparse Tensors if it’s set to True. The default value is False` Not implemented yet. Show the Todo for more information.

Todo

  • Implement variables as sparse when it’s possible. Waiting to TensorFlow for it.
append(src: int, dst: int)[source]

Append an edge to the graph.

This method overrides it parent’s functionality adding a certain grade of probability.

This method process an input edge adding it to the graph updating all the variables necessaries to maintain the graph in correct state. The additions works with some probability, so there the addition is not guaranteed.

Parameters:
  • src (int) – The id of the source vertex of the edge.
  • dst (int) – The id of the destination vertex of the edge.
Returns:

This method returns nothing.

remove(src: int, dst: int)[source]

Remove an edge to the graph.

This method overrides it parent’s functionality adding a certain grade of probability.

This method process an input edge deleting it to the graph updating all the variables necessaries to maintain the graph in correct state. The deletions works with some probability, so there the deletion is not guaranteed.

Parameters:
  • src (int) – The id of the source vertex of the edge.
  • dst (int) – The id of the destination vertex of the edge.
Returns:

This method returns nothing.