reoptimization_algorithms.utils.graph.graph.Graph

class Graph(graph: Dict[str, Vertex] = None)

Bases: reoptimization_algorithms.utils.graph.base_graph.BaseGraph, abc.ABC

Graph data structure class, represented as dictionary with vertices as key mapped to neighbouring vertices

T is a type var, bounded to this class, will refer to child class if inherited

Parameters

graph (Dict[str, Vertex]) – Graph definition, if None then empty graph is instantiated

Example

import reoptimization_algorithms as ra

graph = ra.Graph()
graph = graph.add_vertex("4", 14) # Adding vertex
graph.get_vertex("4") # Getting vertex
graph = graph.update_vertex("4", 15) # Update vertex weight
graph = graph.delete_vertex("4") # Deleting vertex
graph = graph.add_edge("4", "5", 11) # Adding Edge
graph.get_edge("4", "5") # Getting Edge
graph = graph.update_edge("4", "5", 10) # Update Edge weight
graph = graph.delete_edge("4", "5") # Deleting Edge

# Add, Update and Deletes can be chained as follows
graph = (ra.Graph().add_vertex("4").add_edge("4", "5").add_edge("40", "50")
         .add_vertex("6").add_edge("4", "8").delete_edge("4", "5").add_vertex("99")
         .delete_vertex("6"))

Attributes

graph

Graph represented as dictionary with vertices as key mapped to neighbouring vertices
add_edge(source: str, destination: str, weight: float = None) → T

Adds edge in the graph, default weight as Edge.DEFAULT_EDGE_WEIGHT

Parameters

  • source (str) – Edge source

  • destination (str) – Edge destination

  • weight (float) – Weight

Returns

Self

add_vertex(vertex: str, weight: float = None) → T

Adds a vertex to the graph, default weight as Vertex.DEFAULT_VERTEX_WEIGHT

Parameters

  • vertex (str) – Vertex key

  • weight (float, optional (default = None)) – Vertex weight

Returns

Self

copy() → T

Return a deep copy of the graph

Returns

Copied Graph

delete_edge(source: str, destination: str) → T

Deletes the edge in the graph

Parameters

  • source (str) – Edge source

  • destination (str) – Edge destination

Returns

Self

delete_isolated_vertices() → T

Deletes isolated vertices in the graph

Returns

Self

delete_vertex(vertex: str) → T

Deletes a vertex

Parameters

vertex (str) – Vertex key

Returns

Self

disjoint_graph_union(attach_graph: T, attach_edges: List[Edge]) → T

Attaches the caller graph with attach graph and attachment edges, make sure the vertices are disjoint

Parameters

  • attach_graph (T) – Graph to attach

  • attach_edges (List[Edge]) – Edges to connect with attach_graph

Raises

InputError – If Vertices of calling graph and attach graph are not disjoint

Returns

Self

get_edge(source: str, destination: str) → reoptimization_algorithms.utils.graph.edge.Edge

Gets edge from the graph

Parameters

  • source (str) – Edge source

  • destination (str) – Edge destination

Returns

Edge

get_edges() → List[Dict]

Gets list of Edges

Returns

List of dictionary having Edge source, destination and weight as keys

get_isolated_vertices() → List[reoptimization_algorithms.utils.graph.vertex.Vertex]

Gets isolated vertices in the graph

Returns

List of vertices

get_vertex(vertex: str) → reoptimization_algorithms.utils.graph.vertex.Vertex

Gets the vertex

Parameters

vertex (str) – Vertex key

Returns

Vertex

get_vertices() → List[str]

Gets the list of vertices in the graph

Returns

List of vertices keys

property graph

Graph represented as dictionary with vertices as key mapped to neighbouring vertices

is_edge_exists(source: str, destination: str) → bool

Checks if the edge exists in the graph

Parameters

  • source (str) – Edge source

  • destination (str) – Edge destination

Returns

Boolean

is_vertex_exists(vertex: str) → bool

Checks if the vertex exists in the graph

Parameters

vertex (str) – Vertex key

Returns

Boolean

update_edge(source: str, destination: str, weight: float) → T

Updates the edge in the graph

Parameters

  • source (str) – Edge source

  • destination (str) – Edge destination

  • weight (float) – Weight

Returns

Self

update_vertex(vertex: str, weight: float) → T

Updates the vertex weight

Parameters

  • vertex (str) – Vertex key

  • weight (float) – Vertex weight

Returns

Self