easygraph.utils package

Submodules

easygraph.utils.alias module

easygraph.utils.alias.alias_draw(J, q)

easygraph.utils.alias.alias_sample(accept, alias)

Parameters:

• accept

• alias

Return type:

sample index

easygraph.utils.alias.alias_setup(probs)

easygraph.utils.alias.create_alias_table(area_ratio)

Parameters:

area_ratio – sum(area_ratio)=1

Returns:

• 1. accept

• 2. alias

easygraph.utils.convert_class module

easygraph.utils.convert_class.convert_graph_class(G, graph_class)

easygraph.utils.convert_to_matrix module

easygraph.utils.convert_to_matrix.from_numpy_array(A, parallel_edges=False, create_using=None)

Returns a graph from a 2D NumPy array.

The 2D NumPy array is interpreted as an adjacency matrix for the graph.

Parameters:

• A (a 2D numpy.ndarray) – An adjacency matrix representation of a graph

• parallel_edges (Boolean) – If this is True, create_using is a multigraph, and A is an integer array, then entry (i, j) in the array is interpreted as the number of parallel edges joining vertices i and j in the graph. If it is False, then the entries in the array are interpreted as the weight of a single edge joining the vertices.

• create_using (EasyGraph graph constructor, optional (default=eg.Graph)) – Graph type to create. If graph instance, then cleared before populated.

Notes

For directed graphs, explicitly mention create_using=eg.DiGraph, and entry i,j of A corresponds to an edge from i to j.

If create_using is easygraph.MultiGraph or easygraph.MultiDiGraph, parallel_edges is True, and the entries of A are of type int, then this function returns a multigraph (of the same type as create_using) with parallel edges.

If create_using indicates an undirected multigraph, then only the edges indicated by the upper triangle of the array A will be added to the graph.

If the NumPy array has a single data type for each array entry it will be converted to an appropriate Python data type.

If the NumPy array has a user-specified compound data type the names of the data fields will be used as attribute keys in the resulting EasyGraph graph.

See also

to_numpy_array

Examples

Simple integer weights on edges:

>>> import numpy as np
>>> A = np.array([[1, 1], [2, 1]])
>>> G = eg.from_numpy_array(A)
>>> G.edges(data=True)
EdgeDataView([(0, 0, {'weight': 1}), (0, 1, {'weight': 2}), (1, 1, {'weight': 1})])

If create_using indicates a multigraph and the array has only integer entries and parallel_edges is False, then the entries will be treated as weights for edges joining the nodes (without creating parallel edges):

>>> A = np.array([[1, 1], [1, 2]])
>>> G = eg.from_numpy_array(A, create_using=eg.MultiGraph)
>>> G[1][1]
AtlasView({0: {'weight': 2}})

If create_using indicates a multigraph and the array has only integer entries and parallel_edges is True, then the entries will be treated as the number of parallel edges joining those two vertices:

>>> A = np.array([[1, 1], [1, 2]])
>>> temp = eg.MultiGraph()
>>> G = eg.from_numpy_array(A, parallel_edges=True, create_using=temp)
>>> G[1][1]
AtlasView({0: {'weight': 1}, 1: {'weight': 1}})

User defined compound data type on edges:

>>> dt = [("weight", float), ("cost", int)]
>>> A = np.array([[(1.0, 2)]], dtype=dt)
>>> G = eg.from_numpy_array(A)
>>> G.edges()
EdgeView([(0, 0)])
>>> G[0][0]["cost"]
2
>>> G[0][0]["weight"]
1.0

easygraph.utils.convert_to_matrix.from_pandas_adjacency(df, create_using=None)

Returns a graph from Pandas DataFrame.

The Pandas DataFrame is interpreted as an adjacency matrix for the graph.

Parameters:

• df (Pandas DataFrame) – An adjacency matrix representation of a graph

• create_using (EasyGraph graph constructor, optional (default=eg.Graph)) – Graph type to create. If graph instance, then cleared before populated.

Notes

For directed graphs, explicitly mention create_using=eg.DiGraph, and entry i,j of df corresponds to an edge from i to j.

If df has a single data type for each entry it will be converted to an appropriate Python data type.

If df has a user-specified compound data type the names of the data fields will be used as attribute keys in the resulting EasyGraph graph.

See also

to_pandas_adjacency

Examples

Simple integer weights on edges:

>>> import pandas as pd
>>> pd.options.display.max_columns = 20
>>> df = pd.DataFrame([[1, 1], [2, 1]])
>>> df
   0  1
0  1  1
1  2  1
>>> G = eg.from_pandas_adjacency(df)
>>> G.name = "Graph from pandas adjacency matrix"

easygraph.utils.convert_to_matrix.from_pandas_edgelist(df, source='source', target='target', edge_attr=None, create_using=None, edge_key=None)

Returns a graph from Pandas DataFrame containing an edge list.

The Pandas DataFrame should contain at least two columns of node names and zero or more columns of edge attributes. Each row will be processed as one edge instance.

Note: This function iterates over DataFrame.values, which is not guaranteed to retain the data type across columns in the row. This is only a problem if your row is entirely numeric and a mix of ints and floats. In that case, all values will be returned as floats. See the DataFrame.iterrows documentation for an example.

Parameters:

• df (Pandas DataFrame) – An edge list representation of a graph

• source (str or int) – A valid column name (string or integer) for the source nodes (for the directed case).

• target (str or int) – A valid column name (string or integer) for the target nodes (for the directed case).

• edge_attr (str or int, iterable, True, or None) – A valid column name (str or int) or iterable of column names that are used to retrieve items and add them to the graph as edge attributes. If True, all of the remaining columns will be added. If None, no edge attributes are added to the graph.

• create_using (EasyGraph graph constructor, optional (default=eg.Graph)) – Graph type to create. If graph instance, then cleared before populated.

• edge_key (str or None, optional (default=None)) – A valid column name for the edge keys (for a MultiGraph). The values in this column are used for the edge keys when adding edges if create_using is a multigraph.

See also

to_pandas_edgelist

Examples

Simple integer weights on edges:

>>> import pandas as pd
>>> pd.options.display.max_columns = 20
>>> import numpy as np
>>> rng = np.random.RandomState(seed=5)
>>> ints = rng.randint(1, 11, size=(3, 2))
>>> a = ["A", "B", "C"]
>>> b = ["D", "A", "E"]
>>> df = pd.DataFrame(ints, columns=["weight", "cost"])
>>> df[0] = a
>>> df["b"] = b
>>> df[["weight", "cost", 0, "b"]]
   weight  cost  0  b
0       4     7  A  D
1       7     1  B  A
2      10     9  C  E
>>> G = eg.from_pandas_edgelist(df, 0, "b", ["weight", "cost"])
>>> G["E"]["C"]["weight"]
10
>>> G["E"]["C"]["cost"]
9
>>> edges = pd.DataFrame(
...     {
...         "source": [0, 1, 2],
...         "target": [2, 2, 3],
...         "weight": [3, 4, 5],
...         "color": ["red", "blue", "blue"],
...     }
... )
>>> G = eg.from_pandas_edgelist(edges, edge_attr=True)
>>> G[0][2]["color"]
'red'

Build multigraph with custom keys:

>>> edges = pd.DataFrame(
...     {
...         "source": [0, 1, 2, 0],
...         "target": [2, 2, 3, 2],
...         "my_edge_key": ["A", "B", "C", "D"],
...         "weight": [3, 4, 5, 6],
...         "color": ["red", "blue", "blue", "blue"],
...     }
... )
>>> G = eg.from_pandas_edgelist(
...     edges,
...     edge_key="my_edge_key",
...     edge_attr=["weight", "color"],
...     create_using=eg.MultiGraph(),
... )
>>> G[0][2]
AtlasView({'A': {'weight': 3, 'color': 'red'}, 'D': {'weight': 6, 'color': 'blue'}})

easygraph.utils.convert_to_matrix.from_scipy_sparse_matrix(A, parallel_edges=False, create_using=None, edge_attribute='weight')

Creates a new graph from an adjacency matrix given as a SciPy sparse matrix.

Parameters:

• A (scipy sparse matrix) – An adjacency matrix representation of a graph

• parallel_edges (Boolean) – If this is True, create_using is a multigraph, and A is an integer matrix, then entry (i, j) in the matrix is interpreted as the number of parallel edges joining vertices i and j in the graph. If it is False, then the entries in the matrix are interpreted as the weight of a single edge joining the vertices.

• create_using (EasyGraph graph constructor, optional (default=eg.Graph)) – Graph type to create. If graph instance, then cleared before populated.

• edge_attribute (string) – Name of edge attribute to store matrix numeric value. The data will have the same type as the matrix entry (int, float, (real,imag)).

Notes

For directed graphs, explicitly mention create_using=eg.DiGraph, and entry i,j of A corresponds to an edge from i to j.

If create_using is easygraph.MultiGraph or easygraph.MultiDiGraph, parallel_edges is True, and the entries of A are of type int, then this function returns a multigraph (constructed from create_using) with parallel edges. In this case, edge_attribute will be ignored.

If create_using indicates an undirected multigraph, then only the edges indicated by the upper triangle of the matrix A will be added to the graph.

Examples

>>> import scipy as sp
>>> import scipy.sparse  # call as sp.sparse
>>> A = sp.sparse.eye(2, 2, 1)
>>> G = eg.from_scipy_sparse_matrix(A)

If create_using indicates a multigraph and the matrix has only integer entries and parallel_edges is Falnxse, then the entries will be treated as weights for edges joining the nodes (without creating parallel edges):

>>> A = sp.sparse.csr_matrix([[1, 1], [1, 2]])
>>> G = eg.from_scipy_sparse_matrix(A, create_using=eg.MultiGraph)
>>> G[1][1]
AtlasView({0: {'weight': 2}})

If create_using indicates a multigraph and the matrix has only integer entries and parallel_edges is True, then the entries will be treated as the number of parallel edges joining those two vertices:

>>> A = sp.sparse.csr_matrix([[1, 1], [1, 2]])
>>> G = eg.from_scipy_sparse_matrix(
...     A, parallel_edges=True, create_using=eg.MultiGraph
... )
>>> G[1][1]
AtlasView({0: {'weight': 1}, 1: {'weight': 1}})

easygraph.utils.convert_to_matrix.to_numpy_array(G, nodelist=None, dtype=None, order=None, multigraph_weight=<built-in function sum>, weight='weight', nonedge=0.0)

Returns the graph adjacency matrix as a NumPy array.

Parameters:

• G (graph) – The EasyGraph graph used to construct the NumPy array.

• nodelist (list, optional) – The rows and columns are ordered according to the nodes in nodelist. If nodelist is None, then the ordering is produced by G.nodes().

• dtype (NumPy data type, optional) – A valid single NumPy data type used to initialize the array. This must be a simple type such as int or numpy.float64 and not a compound data type (see to_numpy_recarray) If None, then the NumPy default is used.

• order ({'C', 'F'}, optional) – Whether to store multidimensional data in C- or Fortran-contiguous (row- or column-wise) order in memory. If None, then the NumPy default is used.

• multigraph_weight ({sum, min, max}, optional) – An operator that determines how weights in multigraphs are handled. The default is to sum the weights of the multiple edges.

• weight (string or None optional (default = 'weight')) – The edge attribute that holds the numerical value used for the edge weight. If an edge does not have that attribute, then the value 1 is used instead.

• nonedge (float (default = 0.0)) – The array values corresponding to nonedges are typically set to zero. However, this could be undesirable if there are array values corresponding to actual edges that also have the value zero. If so, one might prefer nonedges to have some other value, such as nan.

Returns:

A – Graph adjacency matrix

Return type:

NumPy ndarray

See also

from_numpy_array

Notes

For directed graphs, entry i,j corresponds to an edge from i to j.

Entries in the adjacency matrix are assigned to the weight edge attribute. When an edge does not have a weight attribute, the value of the entry is set to the number 1. For multiple (parallel) edges, the values of the entries are determined by the multigraph_weight parameter. The default is to sum the weight attributes for each of the parallel edges.

When nodelist does not contain every node in G, the adjacency matrix is built from the subgraph of G that is induced by the nodes in nodelist.

The convention used for self-loop edges in graphs is to assign the diagonal array entry value to the weight attribute of the edge (or the number 1 if the edge has no weight attribute). If the alternate convention of doubling the edge weight is desired the resulting NumPy array can be modified as follows:

>>> import numpy as np
>>> G = eg.Graph([(1, 1)])
>>> A = eg.to_numpy_array(G)
>>> A
array([[1.]])
>>> A[np.diag_indices_from(A)] *= 2
>>> A
array([[2.]])

Examples

>>> G = eg.MultiDiGraph()
>>> G.add_edge(0, 1, weight=2)
0
>>> G.add_edge(1, 0)
0
>>> G.add_edge(2, 2, weight=3)
0
>>> G.add_edge(2, 2)
1
>>> eg.to_numpy_array(G, nodelist=[0, 1, 2])
array([[0., 2., 0.],
       [1., 0., 0.],
       [0., 0., 4.]])

easygraph.utils.convert_to_matrix.to_numpy_matrix(G, edge_sign=1.0, not_edge_sign=0.0)

Returns the graph adjacency matrix as a NumPy matrix.

Parameters:

• edge_sign (float) – Sign for the position of matrix where there is an edge

• not_edge_sign (float) – Sign for the position of matrix where there is no edge

easygraph.utils.convert_to_matrix.to_scipy_sparse_array(G, nodelist=None, dtype=None, weight='weight', format='csr')

Returns the graph adjacency matrix as a SciPy sparse array.

Parameters:

• G (graph) – The EasyGraph graph used to construct the sparse matrix.

• nodelist (list, optional) – The rows and columns are ordered according to the nodes in nodelist. If nodelist is None, then the ordering is produced by G.nodes().

• dtype (NumPy data-type, optional) – A valid NumPy dtype used to initialize the array. If None, then the NumPy default is used.

• weight (string or None optional (default='weight')) – The edge attribute that holds the numerical value used for the edge weight. If None then all edge weights are 1.

• format (str in {'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'}) – The type of the matrix to be returned (default ‘csr’). For some algorithms different implementations of sparse matrices can perform better. See [1]_ for details.

Returns:

A – Graph adjacency matrix.

Return type:

SciPy sparse array

Notes

For directed graphs, matrix entry i,j corresponds to an edge from i to j.

The matrix entries are populated using the edge attribute held in parameter weight. When an edge does not have that attribute, the value of the entry is 1.

For multiple edges the matrix values are the sums of the edge weights.

When nodelist does not contain every node in G, the adjacency matrix is built from the subgraph of G that is induced by the nodes in nodelist.

The convention used for self-loop edges in graphs is to assign the diagonal matrix entry value to the weight attribute of the edge (or the number 1 if the edge has no weight attribute). If the alternate convention of doubling the edge weight is desired the resulting Scipy sparse matrix can be modified as follows:

>>> G = eg.Graph([(1, 1)])
>>> A = eg.to_scipy_sparse_array(G)
>>> print(A.todense())
[[1]]
>>> A.setdiag(A.diagonal() * 2)
>>> print(A.toarray())
[[2]]

Examples

>>> S = eg.to_scipy_sparse_array(G, nodelist=[0, 1, 2])
>>> print(S.toarray())
[[0 2 0]
 [1 0 0]
 [0 0 4]]

References

[1]

Scipy Dev. References, “Sparse Matrices”, https://docs.scipy.org/doc/scipy/reference/sparse.html

easygraph.utils.convert_to_matrix.to_scipy_sparse_matrix(G, nodelist=None, dtype=None, weight='weight', format='csr')

Returns the graph adjacency matrix as a SciPy sparse matrix.

Parameters:

• G (graph) – The EasyGraph graph used to construct the sparse matrix.

• nodelist (list, optional) – The rows and columns are ordered according to the nodes in nodelist. If nodelist is None, then the ordering is produced by G.nodes().

• dtype (NumPy data-type, optional) – A valid NumPy dtype used to initialize the array. If None, then the NumPy default is used.

• weight (string or None optional (default='weight')) – The edge attribute that holds the numerical value used for the edge weight. If None then all edge weights are 1.

• format (str in {'bsr', 'csr', 'csc', 'coo', 'lil', 'dia', 'dok'}) – The type of the matrix to be returned (default ‘csr’). For some algorithms different implementations of sparse matrices can perform better. See [1]_ for details.

Returns:

A – Graph adjacency matrix.

Return type:

SciPy sparse matrix

Notes

For directed graphs, matrix entry i,j corresponds to an edge from i to j.

The matrix entries are populated using the edge attribute held in parameter weight. When an edge does not have that attribute, the value of the entry is 1.

For multiple edges the matrix values are the sums of the edge weights.

When nodelist does not contain every node in G, the adjacency matrix is built from the subgraph of G that is induced by the nodes in nodelist.

The convention used for self-loop edges in graphs is to assign the diagonal matrix entry value to the weight attribute of the edge (or the number 1 if the edge has no weight attribute). If the alternate convention of doubling the edge weight is desired the resulting Scipy sparse matrix can be modified as follows:

>>> G = eg.Graph([(1, 1)])
>>> A = eg.to_scipy_sparse_matrix(G)
>>> print(A.todense())
[[1]]
>>> A.setdiag(A.diagonal() * 2)
>>> print(A.todense())
[[2]]

Examples

>>> G.add_edge(1, 0)
0
>>> G.add_edge(2, 2, weight=3)
0
>>> G.add_edge(2, 2)
1
>>> S = eg.to_scipy_sparse_matrix(G, nodelist=[0, 1, 2])
>>> print(S.todense())
[[0 2 0]
 [1 0 0]
 [0 0 4]]

References

[1]

Scipy Dev. References, “Sparse Matrices”, https://docs.scipy.org/doc/scipy/reference/sparse.html

easygraph.utils.decorators module

easygraph.utils.decorators.hybrid(cpp_method_name)

easygraph.utils.decorators.nodes_or_number(which_args)

Decorator to allow number of nodes or container of nodes.

With this decorator, the specified argument can be either a number or a container of nodes. If it is a number, the nodes used are range(n). This allows eg.complete_graph(50) in place of eg.complete_graph(list(range(50))). And it also allows eg.complete_graph(any_list_of_nodes).

Parameters:

which_args (string or int or sequence of strings or ints) – If string, the name of the argument to be treated. If int, the index of the argument to be treated. If more than one node argument is allowed, can be a list of locations.

Returns:

_nodes_or_numbers – Function which replaces int args with ranges.

Return type:

function

Examples

Decorate functions like this:

@nodes_or_number("nodes")
def empty_graph(nodes):
    # nodes is converted to a list of nodes

@nodes_or_number(0)
def empty_graph(nodes):
    # nodes is converted to a list of nodes

@nodes_or_number(["m1", "m2"])
def grid_2d_graph(m1, m2, periodic=False):
    # m1 and m2 are each converted to a list of nodes

@nodes_or_number([0, 1])
def grid_2d_graph(m1, m2, periodic=False):
    # m1 and m2 are each converted to a list of nodes

@nodes_or_number(1)
def full_rary_tree(r, n)
    # presumably r is a number. It is not handled by this decorator.
    # n is converted to a list of nodes

easygraph.utils.decorators.not_implemented_for(*graph_types)

Decorator to mark algorithms as not implemented

Parameters:

graph_types (container of strings) – Entries must be one of “directed”, “undirected”, “multigraph”, or “graph”.

Returns:

_require – The decorated function.

Return type:

function

Raises:

• EasyGraphNotImplemented –

• If any of the packages cannot be imported –

Notes

Multiple types are joined logically with “and”. For “or” use multiple @not_implemented_for() lines.

Examples

Decorate functions like this:

@not_implemented_for("directed")
def sp_function(G):
    pass

# rule out MultiDiGraph
@not_implemented_for("directed","multigraph")
def sp_np_function(G):
    pass

# rule out all except DiGraph
@not_implemented_for("undirected")
@not_implemented_for("multigraph")
def sp_np_function(G):
    pass

easygraph.utils.decorators.only_implemented_for_Directed_graph(func)

easygraph.utils.decorators.only_implemented_for_UnDirected_graph(func)

easygraph.utils.decorators.open_file(path_arg, mode='r')

Decorator to ensure clean opening and closing of files.

Parameters:

• path_arg (string or int) – Name or index of the argument that is a path.

• mode (str) – String for opening mode.

Returns:

_open_file – Function which cleanly executes the io.

Return type:

function

Examples

Decorate functions like this:

@open_file(0,"r")
def read_function(pathname):
    pass

@open_file(1,"w")
def write_function(G, pathname):
    pass

@open_file(1,"w")
def write_function(G, pathname="graph.dot"):
    pass

@open_file("pathname","w")
def write_function(G, pathname="graph.dot"):
    pass

@open_file("path", "w+")
def another_function(arg, **kwargs):
    path = kwargs["path"]
    pass

Notes

Note that this decorator solves the problem when a path argument is specified as a string, but it does not handle the situation when the function wants to accept a default of None (and then handle it).

Here is an example of how to handle this case:

@open_file("path")
def some_function(arg1, arg2, path=None):
   if path is None:
       fobj = tempfile.NamedTemporaryFile(delete=False)
   else:
       # `path` could have been a string or file object or something
       # similar. In any event, the decorator has given us a file object
       # and it will close it for us, if it should.
       fobj = path

   try:
       fobj.write("blah")
   finally:
       if path is None:
           fobj.close()

Normally, we’d want to use “with” to ensure that fobj gets closed. However, the decorator will make path a file object for us, and using “with” would undesirably close that file object. Instead, we use a try block, as shown above. When we exit the function, fobj will be closed, if it should be, by the decorator.

easygraph.utils.decorators.retry_method_with_fix(fix_method)

Decorator that executes a fix method before retrying again when the decorated method fails once with any exception.

If the decorated method fails again, the execution fails with that exception.

Notes

This decorator only works on class methods, and the fix function must also be a class method. It would not work on functions.

Parameters:

fix_func (callable) – The fix method to execute. It should not accept any arguments. Its return values are ignored.

easygraph.utils.download module

easygraph.utils.download.check_file(file_path: Path, md5: str)

Check if a file is valid.

Parameters:

• file_path (Path) – The local path of the file.

• md5 (str) – The md5 of the file.

Raises:

FileNotFoundError – Not found the file.

easygraph.utils.download.download_and_check(url: str, file_path: Path, md5: str)

Download a file from a url and check its integrity.

Parameters:

• url (str) – The url of the file.

• file_path (Path) – The path to the file.

• md5 (str) – The md5 of the file.

easygraph.utils.download.download_file(url: str, file_path: Path)

Download a file from a url.

Parameters:

• url (str) – the url of the file

• file_path (str) – the path to the file

easygraph.utils.exception module

Exceptions

Base exceptions and errors for EasyGraph.

exception easygraph.utils.exception.EasyGraphError

Bases: EasyGraphException

Exception for a serious error in EasyGraph

exception easygraph.utils.exception.EasyGraphException

Bases: Exception

Base class for exceptions in EasyGraph.

exception easygraph.utils.exception.EasyGraphNotImplemented

Bases: EasyGraphException

Exception raised by algorithms not implemented for a type of graph.

exception easygraph.utils.exception.EasyGraphPointlessConcept

Bases: EasyGraphException

Raised when a null graph is provided as input to an algorithm that cannot use it.

The null graph is sometimes considered a pointless concept [1]_, thus the name of the exception.

References

[1]

Harary, F. and Read, R. “Is the Null Graph a Pointless Concept?” In Graphs and Combinatorics Conference, George Washington University. New York: Springer-Verlag, 1973.

easygraph.utils.index_of_node module

easygraph.utils.index_of_node.get_relation_of_index_and_node(graph)

easygraph.utils.logging module

easygraph.utils.logging.default_log_formatter() → Formatter

Create a default formatter of log messages for logging.

easygraph.utils.logging.simple_stdout2file(file_path: str | Path) → None

This function simply wraps the sys.stdout stream, and outputs messages to the sys.stdout and a specified file, simultaneously.

Parameters:

file_path (file_path: Union[str, Path]) – The path of the file to output the messages.

easygraph.utils.mapped_queue module

Priority queue class with updatable priorities. Codes from NetworkX - http://networkx.github.io/

class easygraph.utils.mapped_queue.MappedQueue(data=[])

Bases: object

The MappedQueue class implements an efficient minimum heap. The smallest element can be popped in O(1) time, new elements can be pushed in O(log n) time, and any element can be removed or updated in O(log n) time. The queue cannot contain duplicate elements and an attempt to push an element already in the queue will have no effect.

MappedQueue complements the heapq package from the python standard library. While MappedQueue is designed for maximum compatibility with heapq, it has slightly different functionality.

Examples

A MappedQueue can be created empty or optionally given an array of initial elements. Calling push() will add an element and calling pop() will remove and return the smallest element.

>>> q = MappedQueue([916, 50, 4609, 493, 237])
>>> q.push(1310)
True
>>> x = [q.pop() for i in range(len(q.h))]
>>> x
[50, 237, 493, 916, 1310, 4609]

Elements can also be updated or removed from anywhere in the queue.

>>> q = MappedQueue([916, 50, 4609, 493, 237])
>>> q.remove(493)
>>> q.update(237, 1117)
>>> x = [q.pop() for i in range(len(q.h))]
>>> x
[50, 916, 1117, 4609]

References

[1]

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2001). Introduction to algorithms second edition.

[2]

Knuth, D. E. (1997). The art of computer programming (Vol. 3). Pearson Education.

pop()

Remove and return the smallest element in the queue.

push(elt)

Add an element to the queue.

remove(elt)

Remove an element from the queue.

update(elt, new)

Replace an element in the queue with a new one.

easygraph.utils.misc module

easygraph.utils.misc.edges_equal(edges1, edges2, need_data=True)

Check if edges are equal.

Equality here means equal as Python objects. Edge data must match if included. The order of the edges is not relevant.

Parameters:

• edges1 (iterables of with u, v nodes as) – edge tuples (u, v), or edge tuples with data dicts (u, v, d), or edge tuples with keys and data dicts (u, v, k, d)

• edges2 (iterables of with u, v nodes as) – edge tuples (u, v), or edge tuples with data dicts (u, v, d), or edge tuples with keys and data dicts (u, v, k, d)

Returns:

True if edges are equal, False otherwise.

Return type:

bool

easygraph.utils.misc.graphs_equal(graph1, graph2)

Check if graphs are equal.

Equality here means equal as Python objects (not isomorphism). Node, edge and graph data must match.

Parameters:

• graph1 (graph)

• graph2 (graph)

Returns:

True if graphs are equal, False otherwise.

Return type:

bool

easygraph.utils.misc.nodes_equal(nodes1, nodes2)

Check if nodes are equal.

Equality here means equal as Python objects. Node data must match if included. The order of nodes is not relevant.

Parameters:

• nodes1 (iterables of nodes, or (node, datadict) tuples)

• nodes2 (iterables of nodes, or (node, datadict) tuples)

Returns:

True if nodes are equal, False otherwise.

Return type:

bool

easygraph.utils.misc.pairwise(iterable, cyclic=False)

s -> (s0, s1), (s1, s2), (s2, s3), …

easygraph.utils.misc.split(nodes, n)

easygraph.utils.misc.split_len(nodes, step=30000)

easygraph.utils.relabel module

easygraph.utils.relabel.convert_node_labels_to_integers(G, first_label=0, ordering='default', label_attribute=None)

Returns a copy of the graph G with the nodes relabeled using consecutive integers.

Parameters:

• G (graph) – A easygraph graph

• first_label (int, optional (default=0)) – An integer specifying the starting offset in numbering nodes. The new integer labels are numbered first_label, …, n-1+first_label.

• ordering (string) – “default” : inherit node ordering from G.nodes “sorted” : inherit node ordering from sorted(G.nodes) “increasing degree” : nodes are sorted by increasing degree “decreasing degree” : nodes are sorted by decreasing degree

• label_attribute (string, optional (default=None)) – Name of node attribute to store old label. If None no attribute is created.

Notes

Node and edge attribute data are copied to the new (relabeled) graph.

There is no guarantee that the relabeling of nodes to integers will give the same two integers for two (even identical graphs). Use the ordering argument to try to preserve the order.

See also

relabel_nodes

easygraph.utils.relabel.relabel_nodes(G, mapping)

easygraph.utils.sparse module

easygraph.utils.sparse.sparse_dropout(sp_mat: torch.Tensor, p: float, fill_value: float = 0.0) → torch.Tensor

easygraph.utils.type_change module

easygraph.utils.type_change.from_pyGraphviz_agraph(A, create_using=None)

Returns a EasyGraph Graph or DiGraph from a PyGraphviz graph.

Parameters:

• A (PyGraphviz AGraph) – A graph created with PyGraphviz

• create_using (EasyGraph graph constructor, optional (default=None)) – Graph type to create. If graph instance, then cleared before populated. If None, then the appropriate Graph type is inferred from A.

Examples

>>> K5 = eg.complete_graph(5)
>>> A = eg.to_pyGraphviz_agraph(K5)
>>> G = eg.from_pyGraphviz_agraph(A)

Notes

The Graph G will have a dictionary G.graph_attr containing the default graphviz attributes for graphs, nodes and edges.

Default node attributes will be in the dictionary G.node_attr which is keyed by node.

Edge attributes will be returned as edge data in G. With edge_attr=False the edge data will be the Graphviz edge weight attribute or the value 1 if no edge weight attribute is found.

easygraph.utils.type_change.to_pyGraphviz_agraph(N)

Returns a pygraphviz graph from a EasyGraph graph N.

Parameters:

N (EasyGraph graph) – A graph created with EasyGraph

Examples

>>> K5 = eg.complete_graph(5)
>>> A = eg.to_pyGraphviz_agraph(K5)

Notes

If N has an dict N.graph_attr an attempt will be made first to copy properties attached to the graph (see from_agraph) and then updated with the calling arguments if any.

Module contents