GeneralGraph¶

GeneralGraph for directed graphs (DiGraph) module

`GeneralGraph`	Class GeneralGraph for directed graphs (DiGraph).
`GeneralGraph.load`	Load input file.
`GeneralGraph.mark`	mark attribute for every node.
`GeneralGraph.area`
`GeneralGraph.perturbation_resistant`
`GeneralGraph.description`	description attribute for every node.
`GeneralGraph.init_status`	init_status attribute for switches.
`GeneralGraph.final_status`	final_status attribute for switches.
`GeneralGraph.mark_status`	mark_status attribute for every node.
`GeneralGraph.status_area`
`GeneralGraph.father_condition`
`GeneralGraph.weight`	weight attribute for every edge.
`GeneralGraph.type`	type attribute for every node.
`GeneralGraph.sources`	list of graph sources.
`GeneralGraph.users`	list of graph users.
`GeneralGraph.switches`	list of graph switches.
`GeneralGraph.initial_service`	initial_service attribute for every node.
`GeneralGraph.service`	Computed service.
`GeneralGraph.shortest_path`	Shortest existing paths between all node pairs.
`GeneralGraph.shortest_path_length`	Shortest path length.
`GeneralGraph.efficiency`	Efficiency of the graph.
`GeneralGraph.nodal_efficiency`	Nodal efficiency of the graph.
`GeneralGraph.local_efficiency`	Local efficiency of the graph.
`GeneralGraph.global_efficiency`	Average global efficiency of the whole graph.
`GeneralGraph.betweenness_centrality`	Betweenness centrality of the graph.
`GeneralGraph.closeness_centrality`	Closeness centrality of the graph.
`GeneralGraph.degree_centrality`	Degree centrality of the graph.
`GeneralGraph.indegree_centrality`	In-degree centrality of the graph.
`GeneralGraph.outdegree_centrality`	Out-degree centrality of the graph.
`GeneralGraph.clear_data`	Delete attributes for all nodes in the graph.
`GeneralGraph.construct_path_kernel`	Reconstruct source-target paths starting from predecessors matrix, and populate the dictionary of shortest paths.
`GeneralGraph.floyd_warshall_initialization`	Initialization of Floyd Warshall APSP algorithm.
`GeneralGraph.floyd_warshall_kernel`	Floyd Warshall’s APSP inner iteration.
`GeneralGraph.floyd_warshall_predecessor_and_distance`	Serial Floyd Warshall’s APSP algorithm.
`GeneralGraph.dijkstra_single_source_shortest_path`	Serial SSSP algorithm based on Dijkstra’s method.
`GeneralGraph.calculate_shortest_path`	Choose the most appropriate way to compute the all-pairs shortest path depending on graph size and density.
`GeneralGraph.efficiency_kernel`	Compute efficiency, starting from path length attribute.
`GeneralGraph.compute_efficiency`	Efficiency calculation.
`GeneralGraph.nodal_efficiency_kernel`	Compute nodal efficiency, starting from efficiency attribute.
`GeneralGraph.compute_nodal_efficiency`	Nodal efficiency calculation.
`GeneralGraph.local_efficiency_kernel`	Compute local efficiency, starting from nodal efficiency attribute.
`GeneralGraph.compute_local_efficiency`	Local efficiency calculation.
`GeneralGraph.shortest_path_list_kernel`	Collect the shortest paths that contain at least two nodes.
`GeneralGraph.betweenness_centrality_kernel`	Compute betweenness centrality, from shortest path list.
`GeneralGraph.compute_betweenness_centrality`	Betweenness_centrality calculation
`GeneralGraph.closeness_centrality_kernel`	Compute betweenness centrality, from shortest path list.
`GeneralGraph.compute_closeness_centrality`	Closeness centrality calculation.
`GeneralGraph.degree_centrality_kernel`	Compute degree centrality.
`GeneralGraph.compute_degree_centrality`	Degree centrality measure of each node calculation.
`GeneralGraph.indegree_centrality_kernel`	Compute in-degree centrality.
`GeneralGraph.compute_indegree_centrality`	In-degree centrality calculation.
`GeneralGraph.outdegree_centrality_kernel`	Compute out-degree centrality.
`GeneralGraph.compute_outdegree_centrality`	Outdegree centrality calculation.
`GeneralGraph.compute_service`	Compute service for every node, together with edge splitting.

class GeneralGraph[source]

Bases: networkx.classes.digraph.DiGraph

Class GeneralGraph for directed graphs (DiGraph).

Constructs a new graph given an input file. A DiGraph stores nodes and edges with optional data or attributes. DiGraphs hold directed edges. Nodes can be arbitrary python objects with optional key/value attributes. Edges are represented as links between nodes with optional key/value attributes.

Initialize a graph with edges, name, or graph attributes.

Parameters

incoming_graph_data (input graph (optional, default: None)) – Data to initialize graph. If None (default) an empty graph is created. The data can be an edge list, or any NetworkX graph object. If the corresponding optional Python packages are installed the data can also be a 2D NumPy array, a SciPy sparse matrix, or a PyGraphviz graph.
attr (keyword arguments, optional (default= no attributes)) – Attributes to add to graph as key=value pairs.

See also

convert

Examples

>>> G = nx.Graph()  # or DiGraph, MultiGraph, MultiDiGraph, etc
>>> G = nx.Graph(name="my graph")
>>> e = [(1, 2), (2, 3), (3, 4)]  # list of edges
>>> G = nx.Graph(e)

Arbitrary graph attribute pairs (key=value) may be assigned

>>> G = nx.Graph(e, day="Friday")
>>> G.graph
{'day': 'Friday'}

property betweenness_centrality

Betweenness centrality of the graph. Returns the betweenness centrality if already stored in the nodes. Otherwise, the attribute is computed.

Returns: betweenness_centrality attribute for every node.
Return type: dict

betweenness_centrality_kernel(nodes, tot_shortest_paths_list)[source]

Compute betweenness centrality, from shortest path list.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
tot_shortest_paths_list (list or multiprocessing.managers.list) – list of shortest paths with at least two nodes.

Returns

between centrality dictionary keyed by node.

Return type

dict

calculate_shortest_path()[source]

Choose the most appropriate way to compute the all-pairs shortest path depending on graph size and density. For a dense graph choose Floyd Warshall algorithm. For a sparse graph choose SSSP algorithm based on Dijkstra’s method.

Note

Edge weights of the graph are taken into account in the computation.

Returns: nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path; nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path length.
Return type: dict, dict

clear_data(attributes_to_remove)[source]

Delete attributes for all nodes in the graph.

Parameters: attributes_to_remove (list) – a list of strings with all the attributes to remove.
Raises: ValueError

property closeness_centrality

Closeness centrality of the graph. Returns the closeness centrality if already stored in the nodes. Otherwise, the attribute is computed.

Returns: closeness_centrality attribute for every node.
Return type: dict

closeness_centrality_kernel(nodes, shortest_path_length, tot_shortest_paths_list, graph_size)[source]

Compute betweenness centrality, from shortest path list.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
shortest_path (dict) – nested dictionary with key. corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path.
tot_shortest_paths_list (list or multiprocessing.managers.list) – list of shortest paths with at least two nodes.
graph_size (int) – graph size.

Returns

closeness centrality dictionary keyed by node.

Return type

dict

Raises

ValueError

compute_betweenness_centrality()[source]

Betweenness_centrality calculation

Note

Betweenness centrality is an index of the relative importance of a node and it is defined by the number of shortest paths that run through it. Nodes with the highest betweenness centrality hold the higher level of control on the information flowing between different nodes in the network, because more information will pass through them.

Returns: betweenness centrality computed for every node.
Return type: dict

compute_closeness_centrality()[source]

Closeness centrality calculation.

Note

Closeness centrality measures the reciprocal of the average shortest path distance from a node to all other reachable nodes in the graph. Thus, the more central a node is, the closer it is to all other nodes. This measure allows to identify good broadcasters, that is key elements in a graph, depicting how closely the nodes are connected with each other.

Returns: closeness centrality computed for every node.
Return type: dict

compute_degree_centrality()[source]

Degree centrality measure of each node calculation.

Note

Degree centrality is a simple centrality measure that counts how many neighbors a node has in an undirected graph. The more neighbors the node has the most important it is, occupying a strategic position that serves as a source or conduit for large volumes of flux transactions with other nodes. A node with high degree centrality is a node with many dependencies.

Returns: degree centrality computed for every node.
Return type: dict

compute_efficiency()[source]

Efficiency calculation.

Note

The efficiency of a path connecting two nodes is defined as the inverse of the path length, if the path has length non-zero, and zero otherwise.

Returns: efficiency attribute computed for every node. The keys correspond to source, while as value a dictionary keyed by target and valued by the source-target efficiency.
Return type: dict

compute_indegree_centrality()[source]

In-degree centrality calculation.

Note

In-degree centrality is measured by the number of edges ending at the node in a directed graph. Nodes with high in-degree centrality are called cascade resulting nodes.

Returns: in-degree centrality computed for every node.
Return type: dict

compute_local_efficiency()[source]

Local efficiency calculation.

Note

The local efficiency shows the efficiency of the connections between the first-order outgoing neighbors of node v when v is removed. Equivalently, local efficiency measures the resilience of the digraph to the perturbation of node removal, i.e. if we remove a node, how efficiently its first-order outgoing neighbors can communicate. It is in the range [0, 1].

Returns: local efficiency computed for every node.
Return type: dict

compute_nodal_efficiency()[source]

Nodal efficiency calculation.

Note

The nodal efficiency of the node is equal to zero for a node without any outgoing path and equal to one if from it we can reach each node of the digraph.

Returns: nodal efficiency computed for every node.
Return type: dict

compute_outdegree_centrality()[source]

Outdegree centrality calculation.

Note

Outdegree centrality is measured by the number of edges starting from a node in a directed graph. Nodes with high outdegree centrality are called cascade inititing nodes.

Returns: out-degree centrality computed for every node.
Return type: dict

compute_service()[source]

Compute service for every node, together with edge splitting.

Returns: computed service computed for every node; splitting computed for every edge.
Return type: dict, dict

construct_path_kernel(nodes, predecessor)[source]

Reconstruct source-target paths starting from predecessors matrix, and populate the dictionary of shortest paths.

Parameters

nodes (list) – list of nodes for which to compute the shortest path between them and all the other nodes.
predecessor (numpy.ndarray) – matrix of predecessors, computed with Floyd Warshall APSP algorithm.

Returns

nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path.

Return type

dict

property degree_centrality

Degree centrality of the graph. Returns the degree centrality if already stored in the nodes. Otherwise, the attribute is computed.

Returns: degree_centrality attribute for every node.
Return type: dict

degree_centrality_kernel(nodes, graph_size)[source]

Compute degree centrality.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
graph_size (int) – graph size.

Returns

degree centrality dictionary keyed by node.

Return type

dict

Raises

ValueError

property description

description attribute for every node. :rtype: dict

Type: return

dijkstra_single_source_shortest_path()[source]

Serial SSSP algorithm based on Dijkstra’s method. The nested dictionaries for shortest-path, length of the paths and efficiency attributes are evaluated.

Note

Edges weight is taken into account. Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

Returns: nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path; nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path length.
Return type: dict, dict

property efficiency

Efficiency of the graph. Returns the efficiency if already stored in the nodes. Otherwise, the attribute is computed.

Returns: efficiency attribute for every node. The keys correspond to source, while as value a dictionary keyed by target and valued by the source-target efficiency.
Return type: dict

efficiency_kernel(nodes, shortest_path_length)[source]

Compute efficiency, starting from path length attribute. Efficiency is a measure of how good is the exchange of commodities flowing from one node to the others.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
shortest_path_length (dict) – nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path length.

Returns

nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target efficiency.

Return type

dict

property final_status

final_status attribute for switches. :rtype: dict

Type: return

floyd_warshall_initialization()[source]

Initialization of Floyd Warshall APSP algorithm. The distancy matrix is mutuated by NetworkX graph adjacency matrix, while the predecessors matrix is initialized with node fathers. The conversion between the labels (ids) in the graph and Numpy matrix indices (and viceversa) is also exploited.

Note

In order for the ids relation to be bijective, ‘mark’ attribute must be unique for each node.

Returns: matrix of distances; matrix of predecessors.
Return type: numpy.ndarray, numpy.ndarray

floyd_warshall_kernel(distance, predecessor, init, stop, barrier=None)[source]

Floyd Warshall’s APSP inner iteration. Distance matrix is intended to take edges weight into account.

Parameters

distance (numpy.ndarray or multiprocessing.sharedctypes.RawArray) – matrix of distances.
predecessor (numpy.ndarray or multiprocessing.sharedctypes.RawArray) – matrix of predecessors.
init (int) – starting column of numpy matrix slice.
stop (int) – ending column of numpy matrix slice.
barrier (multiprocessing.synchronize.Barrier) – multiprocessing barrier to moderate writing on distance and predecessors matrices, default to None.

floyd_warshall_predecessor_and_distance()[source]

Serial Floyd Warshall’s APSP algorithm. The predecessors and distance matrices are evaluated, together with the nested dictionaries for shortest-path, length of the paths and efficiency attributes.

Note

Edges weight is taken into account in the distance matrix. Edge weight attributes must be numerical. Distances are calculated as sums of weighted edges traversed.

Returns: nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path; nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path length.
Return type: dict, dict

property global_efficiency

Average global efficiency of the whole graph.

Note

The average global efficiency of a graph is the average efficiency of all pairs of nodes.

Returns: global_efficiency attribute for every node.
Return type: float
Raises: ValueError

property hubs

list of graph hubs. :rtype: list

Type: return

property indegree_centrality

In-degree centrality of the graph. Returns the in-degree centrality if already stored in the nodes. Otherwise, the attribute is computed.

Returns: indegree_centrality attribute for every node.
Return type: dict

indegree_centrality_kernel(nodes, graph_size)[source]

Compute in-degree centrality.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
graph_size (int) – graph size.

Returns

in-degree centrality dictionary keyed by node.

Return type

dict

Raises

ValueError

property init_status

init_status attribute for switches. :rtype: dict

Type: return

property initial_service

initial_service attribute for every node. :rtype: dict

Type: return

load(filename)[source]

Load input file. Input file must be in CSV format. Each line corresponds to a node/element description, with the relative hierarchy, together with the list of all the node attributes.

Parameters: filename (str) – input file in CSV format.
Returns: DataFrame containing the following attributes: mark, init_status, description; DataFrame containing mark and father_mark attribute.
Return type: pandas.DataFrame, pandas.DataFrame

property local_efficiency

Local efficiency of the graph. Returns the local efficiency if already stored in the nodes. Otherwise, the attribute is computed.

Returns: local_efficiency attribute for every node.
Return type: dict

local_efficiency_kernel(nodes, nodal_efficiency)[source]

Compute local efficiency, starting from nodal efficiency attribute.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
nodal_efficiency (dict) – nodal efficiency dictionary keyed by node.

Returns

local efficiency dictionary keyed by node.

Return type

dict

property mark

mark attribute for every node. :rtype: dict

Type: return

property mark_status

mark_status attribute for every node. :rtype: dict

Type: return

property nodal_efficiency

Nodal efficiency of the graph. Returns the nodal efficiency if already stored in the nodes. Otherwise, the attribute is computed.

Returns: nodal_efficiency attribute for every node.
Return type: dict

nodal_efficiency_kernel(nodes, efficiency, graph_size)[source]

Compute nodal efficiency, starting from efficiency attribute.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
efficiency (dict) – nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target efficiency.
graph_size (int) – graph size.

Returns

nodal efficiency dictionary keyed by node.

Return type

dict

Raises

ValueError

property outdegree_centrality

Out-degree centrality of the graph. Returns the out-degree centrality if already stored in the nodes. Otherwise, the attribute is computed.

Returns: outdegree_centrality attribute for every node.
Return type: dict

outdegree_centrality_kernel(nodes, graph_size)[source]

Compute out-degree centrality.

Parameters

nodes (list) – list of nodes for which to compute the efficiency between them and all the other nodes.
graph_size (int) – graph size.

Returns

out-degree dictionary keyed by node.

Return type

dict

Raises

ValueError

print_graph(radius=None, initial_pos=None, fixed_nodes=None, n_iter=500, thresh=0.0001, size=800, border='black', edge_width=1.0, arrow_size=10, fsize=12, fcolor='k', title='Graph', legend=True, legend_loc='upper right', legend_ncol=1, legend_anchor=None, legend_fsize=12, save_to_file=None, status=None)[source]

Print the graph. Positions of the nodes are generated from a spring layout simulation, if not asked to be fixed during it. Initial positions can be specified for the nodes. Both initial positions and fixed positions can be specified just for a subset of the nodes. The shapes of the nodes characterize their type (SOURCE/HUB/USER/SWITCH). The font size, family and color for labels can be also specified, together with the title for the window figure.

Parameters

radius (float, optional, default to 1/sqrt(n) where n is the number of nodes in the graph) – optimal distance between nodes.
initial_pos (dict, optional) – initial positions for nodes as a dictionary with node as keys and values as a coordinate list or tuple, default to None. If None, then use random initial positions.
fixed_nodes (list, optional) – nodes to keep fixed at initial position, default to None. ValueError raised if fixed_nodes specified and initial_pos not.
n_iter (int, optional) – maximum number of iterations taken in spring layout simulation, default to 500.
thresh (float, optional) – threshold for relative error in node position changes. The iteration stops if the error is below this threshold, default to 0.0001.
size (int, optional) – size of nodes, default to 800.
border (color, optional) – color of node borders, default to ‘black’.
edge_width (float, optional) – width of edges, default to 1.0.
arrow_size (int, optional) – size of the arrow head’s length and width, default to 10.
fsize (int, optional) – font size for text labels, default to 12.
fcolor (string, optional) – font color string for labels, default to ‘k’ (black).
title (string, optional) – title for figure window, default to ‘Graph’.
legend (bool, optional) – show the legend on/off, default to True.
legend_loc (str, optional) – the location of the legend, default to ‘upper right’.
legend_ncol (int, optional) – the number of columns that the legend has, default to 1.
legend_anchor (2-tuple, or 4-tuple of floats, optional) – box that is used to position the legend in conjunction with loc, defaults to axes.bbox (if called as a method to Axes.legend) or figure.bbox (if Figure.legend). This argument allows arbitrary placement of the legend.
legend_fsize (int, optional) – the font size of the legend. The value must be numeric, implying the size the absolute font size in points, default to 12.
save_to_file (string, optional) – name of the file where to save the graph drawing, default to None. The extension is guesses from the filename. Interactive window is rendered in any case.
status (string, optional) – include initial condition of switches in printed graph. To activate it, set it to ‘initial’, default to None.

Returns

a dictionary of positions keyed by node.

Return type

dict

Raises

ValueError

property service

Computed service. Returns the computed service if already stored in the nodes. Otherwise, the attribute is computed.

Returns: service attribute for every node.
Return type: dict

property shortest_path

Shortest existing paths between all node pairs. Returns the shortest path if already stored in the nodes. Otherwise, the attribute is computed.

Returns: shortest_path attribute for every node. The keys correspond to source, while as value a dictionary keyed by target and valued by the source-target shortest path.
Return type: dict

property shortest_path_length

Shortest path length.

Returns: shortest_path_length attribute for every node. The keys correspond to source, while as value a dictionary keyed by target and valued by the source-target shortest path length.
Return type: dict

shortest_path_list_kernel(nodes, shortest_path)[source]

Collect the shortest paths that contain at least two nodes.

Parameters

nodes (list) – list of nodes for which to compute the list of shortest paths.
shortest_path (dict) – nested dictionary with key corresponding to source, while as value a dictionary keyed by target and valued by the source-target shortest path.

Returns

list of shortest paths.

Return type

list

property sources

list of graph sources. :rtype: list

Type: return

property switches

list of graph switches. :rtype: list

Type: return

property type

type attribute for every node. :rtype: dict

Type: return

property users

list of graph users. :rtype: list

Type: return

property weight

weight attribute for every edge. :rtype: dict

Type: return