reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph¶

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

Bases: reoptimization_algorithms.utils.graph.graph.Graph

Undirected Graph data structure class, inheriting Graph class, represented as dictionary with vertices: as key mapped to neighbouring vertices in a symmetric manner

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

Example

import reoptimization_algorithms as ra

graph = ra.UndirectedGraph()
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.UndirectedGraph().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(vertex_1: str, vertex_2: str, weight: float = None) → reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph ¶

Adds an edge in the graph

Parameters

vertex_1 (str) – vertex 1 of the edge
vertex_2 (str) – vertex 2 of the edge
weight (float, optional (default = None)) – Weight of the edge

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(vertex_1: str, vertex_2: str) → reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph ¶

Deletes an edge in the graph

Parameters

vertex_1 (str) – vertex 1 of the edge
vertex_2 (str) – vertex 2 of the edge

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 edges from the graph

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

graph_pretty() → Dict[str, Union[List[Dict[str, Any]], List[dict]]]¶

Returns the graph in the pretty format

Returns: Vertices as list of {‘_Vertex__key’: ‘4’, ‘_weight’: 1, ‘_neighbours’: ..} and edges as list of dictionary {_source, _destination and _weight}

is_edge_exists(vertex_1: str, vertex_2: str) → bool¶

Checks if edge exists in the graph

Parameters

vertex_1 (str) – vertex 1 of the edge
vertex_2 (str) – vertex 2 of the edge

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(vertex_1: str, vertex_2: str, weight: float) → reoptimization_algorithms.utils.graph.undirected_graph.UndirectedGraph ¶

Updates edge weight in the graph

Parameters

vertex_1 (str) – vertex 1 of the edge
vertex_2 (str) – vertex 2 of the edge
weight (float) – Weight to change with

Returns

Self

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

Updates the vertex weight

Parameters

vertex (str) – Vertex key
weight (float) – Vertex weight

Returns

Self