easygraph.classes.multigraph module#

Base class for MultiGraph.

class easygraph.classes.multigraph.MultiGraph(incoming_graph_data=None, multigraph_input=None, **attr)[source]#

Bases: Graph

Attributes:

A: Return the adjacency matrix \(\mathbf{A}\) of the sample graph with torch.sparse_coo_tensor format.
D_v: Return the diagonal matrix of vertex degree \(\mathbf{D}_v\) with torch.sparse_coo_tensor format.
D_v_neg_1_2: Return the normalized diagonal matrix of vertex degree \(\mathbf{D}_v^{-\frac{1}{2}}\) with torch.sparse_coo_tensor format.
L_GCN: Return the GCN Laplacian matrix \(\mathcal{L}_{GCN}\) of the graph with torch.sparse_coo_tensor format.
adj: Return the adjacency matrix
degree: Returns the weighted degree of of each node.
e: Return the edge list, weight list and property list in the graph.
e_both_side: Return the list of edges including both directions.
edges: Return an edge list
index2node: Assign an integer index for each node (start from 0)
name: String identifier of the graph.
ndata
node_index: Assign an integer index for each node (start from 0)
nodes: return [node for node in self._node]

Methods

`add_edge`(u_for_edge, v_for_edge[, key])	Add an edge between u and v.
`add_edges`(edges_for_adding[, edges_attr])	Add a list of edges.
`add_edges_from`(ebunch_to_add, **attr)	Add all the edges in ebunch_to_add.
`add_edges_from_file`(file[, weighted])	Added edges from file For example, txt files,
`add_extra_selfloop`()	Add extra selfloops to the graph.
`add_node`(node_for_adding, **node_attr)	Add one node
`add_nodes`(nodes_for_adding[, nodes_attr])	Add nodes with a list of nodes.
`add_nodes_from`(nodes_for_adding, **attr)	Add multiple nodes.
`add_weighted_edge`(u_of_edge, v_of_edge, weight)	Add a weighted edge
`add_weighted_edges_from`(ebunch_to_add[, weight])	Add weighted edges in ebunch_to_add with specified weight attr
`adjlist_inner_dict_factory`	alias of `dict`
`adjlist_outer_dict_factory`	alias of `dict`
`all_neighbors`(node)	Returns an iterator of a node's neighbors.
`clone`()	Clone the graph.
`copy`()	Returns a copy of the graph.
`edge_attr_dict_factory`	alias of `dict`
`edge_key_dict_factory`	alias of `dict`
`ego_subgraph`(center)	Returns an ego network graph of a node.
`get_edge_data`(u, v[, key, default])	Returns the attribute dictionary associated with edge (u, v).
`gnn_data_dict_factory`	alias of `dict`
`graph_attr_dict_factory`	alias of `dict`
`has_edge`(u, v[, key])	Returns True if the graph has an edge between nodes u and v.
`has_node`(node)	Returns whether a node exists
`is_directed`()	Returns True if graph is directed, False otherwise.
`is_multigraph`()	Returns True if graph is a multigraph, False otherwise.
`nbr_v`(v_idx)	Return a vertex list of the neighbors of the vertex `v_idx`.
`nbunch_iter`([nbunch])	Returns an iterator over nodes contained in nbunch that are also in the graph.
`neighbors`(node)	Returns an iterator of a node's neighbors.
`new_edge_key`(u, v)	Returns an unused key for edges between nodes u and v.
`node_attr_dict_factory`	alias of `dict`
`node_dict_factory`	alias of `dict`
`node_index_dict`	alias of `dict`
`nodes_subgraph`(from_nodes)	Returns a subgraph of some nodes
`number_of_edges`([u, v])	Returns the number of edges between two nodes.
`number_of_nodes`()	Returns the number of nodes.
`order`()	Returns the number of nodes in the graph.
`raw_selfloop_dict`	alias of `dict`
`remove_edge`(u, v[, key])	Remove an edge between u and v.
`remove_edges`(edges_to_remove)	Remove a list of edges from your graph.
`remove_edges_from`(ebunch)	Remove all edges specified in ebunch.
`remove_extra_selfloop`()	Remove extra selfloops from the graph.
`remove_node`(node_to_remove)	Remove one node from your graph.
`remove_nodes`(nodes_to_remove)	Remove nodes from your graph.
`remove_nodes_from`(nodes)	Remove multiple nodes.
`remove_selfloop`()	Remove all selfloops from the graph.
`size`([weight])	Returns the number of edges or total of all edge weights.
`smoothing_with_GCN`(X[, drop_rate])	Return the smoothed feature matrix with GCN Laplacian matrix \(\mathcal{L}_{GCN}\).
`to_directed`()	Returns a directed representation of the graph.
`to_directed_class`()	Returns the class to use for empty directed copies.
`to_index_node_graph`([begin_index])	Returns a deep copy of graph, with each node switched to its index.

N_v
cpp

add_edge(u_for_edge, v_for_edge, key=None, **attr)[source]#

Add an edge between u and v.

The nodes u and v will be automatically added if they are not already in the graph.

Edge attributes can be specified with keywords or by directly accessing the edge’s attribute dictionary. See examples below.

Parameters:

u_for_edge (nodes) – Nodes can be, for example, strings or numbers. Nodes must be hashable (and not None) Python objects.
v_for_edge (nodes) – Nodes can be, for example, strings or numbers. Nodes must be hashable (and not None) Python objects.
key (hashable identifier, optional (default=lowest unused integer)) – Used to distinguish multiedges between a pair of nodes.
attr (keyword arguments, optional) – Edge data (or labels or objects) can be assigned using keyword arguments.

Return type:

The edge key assigned to the edge.

See also

add_edges_from: add a collection of edges

Notes

To replace/update edge data, use the optional key argument to identify a unique edge. Otherwise a new edge will be created.

EasyGraph algorithms designed for weighted graphs cannot use multigraphs directly because it is not clear how to handle multiedge weights. Convert to Graph using edge attribute ‘weight’ to enable weighted graph algorithms.

Default keys are generated using the method new_edge_key(). This method can be overridden by subclassing the base class and providing a custom new_edge_key() method.

Examples

The following all add the edge e=(1, 2) to graph G:

>>> G = eg.MultiGraph()
>>> e = (1, 2)
>>> ekey = G.add_edge(1, 2)  # explicit two-node form
>>> G.add_edge(*e)  # single edge as tuple of two nodes
1
>>> G.add_edges_from([(1, 2)])  # add edges from iterable container
[2]

Associate data to edges using keywords:

>>> ekey = G.add_edge(1, 2, weight=3)
>>> ekey = G.add_edge(1, 2, key=0, weight=4)  # update data for key=0
>>> ekey = G.add_edge(1, 3, weight=7, capacity=15, length=342.7)

For non-string attribute keys, use subscript notation.

>>> ekey = G.add_edge(1, 2)
>>> G[1][2][0].update({0: 5})
>>> G.edges[1, 2, 0].update({0: 5})

add_edges_from(ebunch_to_add, **attr)[source]#

Add all the edges in ebunch_to_add.

Parameters:

ebunch_to_add (container of edges) –
Each edge given in the container will be added to the graph. The edges can be:
- 2-tuples (u, v) or
- 3-tuples (u, v, d) for an edge data dict d, or
- 3-tuples (u, v, k) for not iterable key k, or
- 4-tuples (u, v, k, d) for an edge with data and key k
attr (keyword arguments, optional) – Edge data (or labels or objects) can be assigned using keyword arguments.

Return type:

A list of edge keys assigned to the edges in ebunch.

See also

add_edge: add a single edge
add_weighted_edges_from: convenient way to add weighted edges

Notes

Adding the same edge twice has no effect but any edge data will be updated when each duplicate edge is added.

Edge attributes specified in an ebunch take precedence over attributes specified via keyword arguments.

Default keys are generated using the method new_edge_key(). This method can be overridden by subclassing the base class and providing a custom new_edge_key() method.

Examples

>>> G = eg.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G.add_edges_from([(0, 1), (1, 2)])  # using a list of edge tuples
>>> e = zip(range(0, 3), range(1, 4))
>>> G.add_edges_from(e)  # Add the path graph 0-1-2-3

Associate data to edges

>>> G.add_edges_from([(1, 2), (2, 3)], weight=3)
>>> G.add_edges_from([(3, 4), (1, 4)], label="WN2898")

copy()[source]#

Returns a copy of the graph.

The copy method by default returns an independent shallow copy of the graph and attributes. That is, if an attribute is a container, that container is shared by the original an the copy. Use Python’s copy.deepcopy for new containers.

Notes

All copies reproduce the graph structure, but data attributes may be handled in different ways. There are four types of copies of a graph that people might want.

Deepcopy – A “deepcopy” copies the graph structure as well as all data attributes and any objects they might contain. The entire graph object is new so that changes in the copy do not affect the original object. (see Python’s copy.deepcopy)

Data Reference (Shallow) – For a shallow copy the graph structure is copied but the edge, node and graph attribute dicts are references to those in the original graph. This saves time and memory but could cause confusion if you change an attribute in one graph and it changes the attribute in the other. EasyGraph does not provide this level of shallow copy.

Independent Shallow – This copy creates new independent attribute dicts and then does a shallow copy of the attributes. That is, any attributes that are containers are shared between the new graph and the original. This is exactly what dict.copy() provides. You can obtain this style copy using:

>>> G = eg.path_graph(5)
>>> H = G.copy()
>>> H = eg.Graph(G)
>>> H = G.__class__(G)

Fresh Data – For fresh data, the graph structure is copied while new empty data attribute dicts are created. The resulting graph is independent of the original and it has no edge, node or graph attributes. Fresh copies are not enabled. Instead use:

>>> H = G.__class__()
>>> H.add_nodes_from(G)
>>> H.add_edges_from(G.edges)

See the Python copy module for more information on shallow and deep copies, https://docs.python.org/3/library/copy.html.

Returns:: G – A copy of the graph.
Return type:: Graph

See also

to_directed: return a directed copy of the graph.

Examples

>>> G = eg.path_graph(4)  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> H = G.copy()

property degree#

Returns the weighted degree of of each node.

Parameters:: weight (string, optional (default: 'weight')) – Weight key of the original weighted graph.
Returns:: degree – Each node’s (key) weighted degree (value).
Return type:: dict

Notes

If the graph is not weighted, all the weights will be regarded as 1.

Examples

You can call with no attributes, if ‘weight’ is the weight key:

>>> G.degree()

if you have customized weight key ‘weight_1’.

>>> G.degree(weight='weight_1')

edge_key_dict_factory#: alias of dict

property edges#: Return an edge list

get_edge_data(u, v, key=None, default=None)[source]#

Returns the attribute dictionary associated with edge (u, v).

This is identical to G[u][v][key] except the default is returned instead of an exception is the edge doesn’t exist.

Parameters:

u (nodes) –
v (nodes) –
default (any Python object (default=None)) – Value to return if the edge (u, v) is not found.
key (hashable identifier, optional (default=None)) – Return data only for the edge with specified key.

Returns:

edge_dict – The edge attribute dictionary.

Return type:

dictionary

Examples

>>> G = eg.MultiGraph()  # or MultiDiGraph
>>> key = G.add_edge(0, 1, key="a", weight=7)
>>> G[0][1]["a"]  # key='a'
{'weight': 7}
>>> G.edges[0, 1, "a"]  # key='a'
{'weight': 7}

Warning: we protect the graph data structure by making G.edges and G[1][2] read-only dict-like structures. However, you can assign values to attributes in e.g. G.edges[1, 2, ‘a’] or G[1][2][‘a’] using an additional bracket as shown next. You need to specify all edge info to assign to the edge data associated with an edge.

>>> G[0][1]["a"]["weight"] = 10
>>> G.edges[0, 1, "a"]["weight"] = 10
>>> G[0][1]["a"]["weight"]
10
>>> G.edges[1, 0, "a"]["weight"]
10

>>> G = eg.MultiGraph()  # or MultiDiGraph
>>> G = eg.complete_graph(4, create_using=eg.MultiDiGraph)
>>> G.get_edge_data(0, 1)
{0: {}}
>>> e = (0, 1)
>>> G.get_edge_data(*e)  # tuple form
{0: {}}
>>> G.get_edge_data("a", "b", default=0)  # edge not in graph, return 0
0

has_edge(u, v, key=None)[source]#

Returns True if the graph has an edge between nodes u and v.

This is the same as v in G[u] or key in G[u][v] without KeyError exceptions.

Parameters:

u (nodes) – Nodes can be, for example, strings or numbers.
v (nodes) – Nodes can be, for example, strings or numbers.
key (hashable identifier, optional (default=None)) – If specified return True only if the edge with key is found.

Returns:

edge_ind – True if edge is in the graph, False otherwise.

Return type:

bool

Examples

Can be called either using two nodes u, v, an edge tuple (u, v), or an edge tuple (u, v, key).

>>> G = eg.MultiGraph()  # or MultiDiGraph
>>> G = eg.complete_graph(4, create_using=eg.MultiDiGraph)
>>> G.has_edge(0, 1)  # using two nodes
True
>>> e = (0, 1)
>>> G.has_edge(*e)  #  e is a 2-tuple (u, v)
True
>>> G.add_edge(0, 1, key="a")
'a'
>>> G.has_edge(0, 1, key="a")  # specify key
True
>>> e = (0, 1, "a")
>>> G.has_edge(*e)  # e is a 3-tuple (u, v, 'a')
True

The following syntax are equivalent:

>>> G.has_edge(0, 1)
True
>>> 1 in G[0]  # though this gives :exc:`KeyError` if 0 not in G
True

is_directed()[source]#: Returns True if graph is directed, False otherwise.

is_multigraph()[source]#: Returns True if graph is a multigraph, False otherwise.

new_edge_key(u, v)[source]#

Returns an unused key for edges between nodes u and v.

The nodes u and v do not need to be already in the graph.

Notes

In the standard MultiGraph class the new key is the number of existing edges between u and v (increased if necessary to ensure unused). The first edge will have key 0, then 1, etc. If an edge is removed further new_edge_keys may not be in this order.

Parameters:

u (nodes) –
v (nodes) –

Returns:

key

Return type:

int

number_of_edges(u=None, v=None)[source]#

Returns the number of edges between two nodes.

Parameters:

u (nodes, optional (Gefault=all edges)) – If u and v are specified, return the number of edges between u and v. Otherwise return the total number of all edges.
v (nodes, optional (Gefault=all edges)) – If u and v are specified, return the number of edges between u and v. Otherwise return the total number of all edges.

Returns:

nedges – The number of edges in the graph. If nodes u and v are specified return the number of edges between those nodes. If the graph is directed, this only returns the number of edges from u to v.

Return type:

int

See also

size

Examples

For undirected multigraphs, this method counts the total number of edges in the graph:

>>> G = eg.MultiGraph()
>>> G.add_edges_from([(0, 1), (0, 1), (1, 2)])
[0, 1, 0]
>>> G.number_of_edges()
3

If you specify two nodes, this counts the total number of edges joining the two nodes:

>>> G.number_of_edges(0, 1)
2

For directed multigraphs, this method can count the total number of directed edges from u to v:

>>> G = eg.MultiDiGraph()
>>> G.add_edges_from([(0, 1), (0, 1), (1, 0)])
[0, 1, 0]
>>> G.number_of_edges(0, 1)
2
>>> G.number_of_edges(1, 0)
1

remove_edge(u, v, key=None)[source]#

Remove an edge between u and v.

Parameters:

u (nodes) – Remove an edge between nodes u and v.
v (nodes) – Remove an edge between nodes u and v.
key (hashable identifier, optional (default=None)) – Used to distinguish multiple edges between a pair of nodes. If None remove a single (arbitrary) edge between u and v.

Raises:

EasyGraphError – If there is not an edge between u and v, or if there is no edge with the specified key.

See also

remove_edges_from: remove a collection of edges

Examples

For multiple edges

>>> G = eg.MultiGraph()  # or MultiDiGraph, etc
>>> G.add_edges_from([(1, 2), (1, 2), (1, 2)])  # key_list returned
[0, 1, 2]
>>> G.remove_edge(1, 2)  # remove a single (arbitrary) edge

For edges with keys

>>> G = eg.MultiGraph()  # or MultiDiGraph, etc
>>> G.add_edge(1, 2, key="first")
'first'
>>> G.add_edge(1, 2, key="second")
'second'
>>> G.remove_edge(1, 2, key="second")

remove_edges_from(ebunch)[source]#

Remove all edges specified in ebunch.

Parameters:

ebunch (list or container of edge tuples) –

Each edge given in the list or container will be removed from the graph. The edges can be:

2-tuples (u, v) All edges between u and v are removed.

3-tuples (u, v, key) The edge identified by key is removed.

4-tuples (u, v, key, data) where data is ignored.

See also

remove_edge: remove a single edge

Notes

Will fail silently if an edge in ebunch is not in the graph.

Examples

Removing multiple copies of edges

>>> G = eg.MultiGraph()
>>> keys = G.add_edges_from([(1, 2), (1, 2), (1, 2)])
>>> G.remove_edges_from([(1, 2), (1, 2)])
>>> list(G.edges())
[(1, 2)]
>>> G.remove_edges_from([(1, 2), (1, 2)])  # silently ignore extra copy
>>> list(G.edges)  # now empty graph
[]

to_directed()[source]#

Returns a directed representation of the graph.

Returns:: G – A directed graph with the same name, same nodes, and with each edge (u, v, data) replaced by two directed edges (u, v, data) and (v, u, data).
Return type:: MultiDiGraph

Notes

This returns a “deepcopy” of the edge, node, and graph attributes which attempts to completely copy all of the data and references.

This is in contrast to the similar D=DiGraph(G) which returns a shallow copy of the data.

See the Python copy module for more information on shallow and deep copies, https://docs.python.org/3/library/copy.html.

Warning: If you have subclassed MultiGraph to use dict-like objects in the data structure, those changes do not transfer to the MultiDiGraph created by this method.

Examples

>>> G = eg.Graph()  # or MultiGraph, etc
>>> G.add_edge(0, 1)
>>> H = G.to_directed()
>>> list(H.edges)
[(0, 1), (1, 0)]

If already directed, return a (deep) copy

>>> G = eg.DiGraph()  # or MultiDiGraph, etc
>>> G.add_edge(0, 1)
>>> H = G.to_directed()
>>> list(H.edges)
[(0, 1)]