eolearn.core.graph

The module implements the core graph data structure. It is used, for example, to model dependencies among tasks in the eoworkflow module.

class eolearn.core.graph.DirectedGraph(adjacency_dict=None)

Bases: object

A directed graph using adjacency-list representation.

Constructs a new graph from an adjacency list. If adjacency_dict is None, an empty graph is constructed.

Parameters

adjacency_dict – A dictionary mapping vertices to lists neighbors

get_indegrees()

Returns a dictionary containing in-degrees of vertices of the graph.

Note that if u is not in graph then indegrees[u]=0 due to defaultdict behavior!

get_indegree(vertex)

Returns the in-degree of the vertex.

The in-degree is the number of vertices vertex' such that vertex' -> vertex is an edge of the graph.

Parameters

vertex – Vertex

get_outdegree(vertex)

Returns the out-degree of the vertex.

The out-degree is the number of vertices vertex' such that vertex -> vertex' is an edge of the graph.

Parameters

vertex – Vertex

get_adj_dict()

Returns

adj_dict

get_outdegrees()

Returns

dictionary of out-degrees, see get_outdegree

add_edge(u_vertex, v_vertex)

Adds the edge u_vertex -> v_vertex to the graph if the edge is not already present.

Parameters

• u_vertex – Vertex

• v_vertex – Vertex

Returns

True if a new edge was added. False otherwise.

del_edge(u_vertex, v_vertex)

Removes the edge u_vertex -> v_vertex from the graph if the edge is present.

Parameters

• u_vertex – Vertex

• v_vertex – Vertex

Returns

True if the existing edge was removed. False otherwise.

add_vertex(vertex)

Adds a new vertex to the graph if not present.

Parameters

vertex – Vertex

Returns

True if vertex added and not yet present. False otherwise.

del_vertex(vertex)

Removes the vertex vertex and all incident edges from the graph.

Note that this is an expensive operation that should be avoided!

Running time is O(V+E)

Parameters

vertex – Vertex

Returns

True if vertex was removed from the graph. False otherwise.

is_edge(u_vertex, v_vertex)

True if u_vertex -> v_vertex is an edge of the graph. False otherwise.

Parameters

• u_vertex – Vertex

• v_vertex – Vertex

neighbors(vertex)

Returns the set of successor vertices of vertex.

Parameters

vertex – Vertex

vertices()

Returns the set of vertices of the graph.

static from_edges(edges)

Return DirectedGraph created from edges :param edges: :return: DirectedGraph