"""
Python class that demonstrates the essential facts and functionalities of graphs.
This class represents a directed graph using adjacency list representation
It finds biconnected components in a given undirected graph with complexity : O(V + E)
Original version of the code can be found at:
https://www.python-course.eu/graphs_python.php
https://tutorialspoint.dev/data-structure/graph-data-structure/biconnected-components
Modified by A.Goumilevski
"""
from collections import defaultdict
instances:int = 0
[docs]
class Graph(object):
"""Graph class."""
__graph_dict = {}; __weights = {}; __vertices = {}; __inv_vertices = {}
__graph = []
def __init__(self, graph_dict=dict(), m=None, weights=None):
"""Instantiate graph object.
If no dictionary or None is given, an empty dictionary will be used.
"""
global instances
instances += 1
self.__graph_dict = graph_dict
for k in graph_dict:
if bool(graph_dict[k]):
if not weights is None:
w = weights[k]
else:
w = 1
for v in graph_dict[k]:
self.__addEdge(k,v,w)
else:
self.__addEdge(k,k,0) # Self loop
# Nodes dictionary
if not m is None:
self.m = m
self.im = dict((v,k) for k,v in m.items())
# No. of vertices
self.V = len(m) if m else 0
# default dictionary to store graph
self.graph = defaultdict(list)
# default dictionary to store components
self.components = defaultdict(list)
# time is used to find discovery times
self.Time = 0
# Count is number of biconnected components
self.count = 0
[docs]
def vertices(self):
"""Return the vertices of a graph."""
return list(self.__graph_dict.keys())
[docs]
def edges(self):
"""Return the edges of a graph."""
return self.__generate_edges()
[docs]
def add_vertex(self, vertex):
"""Add graph vertex.
If the vertex is not in self.__graph_dict, a key "vertex" with an empty
list as a value is added to the dictionary. Otherwise nothing has to be done.
"""
if vertex not in self.__graph_dict:
self.__graph_dict[vertex] = []
else:
pass
n = len(self.__vertices)
self.__vertices[vertex] = n
self.__inv_vertices[n] = vertex
[docs]
def add_edge(self, edge, w=None):
"""Add an edge.
It is assumed that edge is of type set, tuple or list; between two vertices can be multiple edges!
"""
edge = set(edge)
vertex1 = edge.pop()
if edge:
# not a loop
vertex2 = edge.pop()
else:
# a loop
vertex2 = vertex1
if vertex1 in self.__graph_dict:
self.__graph_dict[vertex1].append(vertex2)
else:
self.__graph_dict[vertex1] = [vertex2]
if not vertex1 in self.__vertices:
i = len(self.__vertices)
self.__vertices[vertex1] = i
self.__inv_vertices[i] = vertex1
else:
i = self.__vertices[vertex1]
if not vertex2 in self.__vertices:
j = len(self.__vertices)
self.__vertices[vertex2] = j
self.__inv_vertices[j] = vertex2
else:
j = self.__vertices[vertex2]
k = str([min(i,j),max(i,j)])
weight = None
if w is None:
if k in self.__weights:
weight = self.__weights[k]
else:
weight = 1
else:
weight = w
self.__addEdge(vertex1,vertex2,weight)
def __addEdge(self,u,v,w=None):
"""Add an edge that connects two vertices to a graph.
Args:
u : str.
Vertex name.
v : str.
Vertex name.
w : int, optional
Edge weight. The default is None.
Returns:
None.
"""
if not u in self.__vertices:
i = len(self.__vertices)
self.__vertices[u] = i
self.__inv_vertices[i] = u
else:
i = self.__vertices[u]
if not v in self.__vertices:
j = len(self.__vertices)
self.__vertices[v] = j
self.__inv_vertices[j] = v
else:
j = self.__vertices[v]
k = str([min(i,j),max(i,j)])
weight = None
if w is None:
if k in self.__weights:
weight = self.__weights[k]
else:
weight = 1
else:
weight = w
self.__weights[k] = weight
self.__graph.append([i,j,weight])
[docs]
def addEdge(self, x, y):
"""Function to add an edge to graph."""
u = self.m[x]
v = self.m[y]
self.graph[u].append(v)
self.graph[v].append(u)
def __generate_edges(self):
"""
Generate the edges of the graph.
Edges are represented as sets with one (a loop back to the vertex)
or two vertices.
"""
edges = []
for vertex in self.__graph_dict:
for neighbour in self.__graph_dict[vertex]:
if {neighbour, vertex} not in edges:
edges.append({vertex, neighbour})
return edges
[docs]
def find_isolated_vertices(self):
"""Return a list of isolated vertices."""
graph = self.__graph_dict
isolated = []
for vertex in graph:
print(isolated, vertex)
if not graph[vertex]:
isolated += [vertex]
return isolated
[docs]
def BCCUtil(self, u, parent, low, disc, st):
"""A recursive function that finds and prints strongly connected components using DFS traversal
u --> The vertex to be visited next
disc[] --> Stores discovery times of visited vertices
low[] -- >> earliest visited vertex (the vertex with minimum
discovery time) that can be reached from subtree
rooted with current vertex
st -- >> To store visited edges
"""
# Count of children in current node
children = 0
# Initialize discovery time and low value
disc[u] = self.Time
low[u] = self.Time
self.Time += 1
# Recur for all the vertices adjacent to this vertex
for v in self.graph[u]:
# If v is not visited yet, then make it a child of u
# in DFS tree and recur for it
if disc[v] == -1 :
parent[v] = u
children += 1
st.append((u, v)) # store the edge in stack
self.BCCUtil(v, parent, low, disc, st)
# Check if the subtree rooted with v has a connection to one of the ancestors of u
# Case 1 -- per Strongly Connected Components Article
low[u] = min(low[u], low[v])
# If u is an articulation point, pop all edges from stack till (u, v)
if parent[u] == -1 and children > 1 or parent[u] != -1 and low[v] >= disc[u]:
w = -1
lst = []
while w != (u, v):
w = st.pop()
lst.append(w)
# print(w)
# print()
self.components[self.count] = lst
self.count += 1 # increment count
elif v != parent[u] and low[u] > disc[v]:
'''Update low value of 'u' only of 'v' is still in stack
(i.e. it's a back edge, not cross edge).
Case 2
-- per Strongly Connected Components Article'''
low[u] = min(low [u], disc[v])
st.append((u, v))
return
[docs]
def BCC(self):
"""Function to do DFS traversal. It uses recursive BCCUtil()."""
# Initialize disc and low, and parent arrays
disc = [-1] * (self.V)
low = [-1] * (self.V)
parent = [-1] * (self.V)
st = []
# Call the recursive helper function to find articulation points
# in DFS tree rooted with vertex 'i'
for i in range(self.V):
if disc[i] == -1:
self.BCCUtil(i, parent, low, disc, st)
# If stack is not empty, pop all edges from stack
if st:
lst = []
while st:
w = st.pop()
lst.append(w)
# print (w)
# print()
self.components[self.count] = lst
self.count = self.count + 1
return
[docs]
def find_path(self, start_vertex, end_vertex, path=[]):
"""Find a path from start_vertex to end_vertex in graph."""
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return path
if start_vertex not in graph:
return None
for vertex in graph[start_vertex]:
if vertex not in path:
extended_path = self.find_path(vertex,end_vertex,path)
if extended_path:
return extended_path
return None
[docs]
def find_all_paths(self, start_vertex, end_vertex, path=[]):
"""Find all paths from start_vertex to end_vertex in graph."""
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return [path]
if start_vertex not in graph:
return []
paths = []
for vertex in graph[start_vertex]:
if vertex not in path:
extended_paths = self.find_all_paths(vertex, end_vertex, path)
for p in extended_paths:
paths.append(p)
return paths
[docs]
def find_shortest_path(self, start_vertex, end_vertex, path=[]):
"""Find shortest path from start_vertex to end_vertex."""
graph = self.__graph_dict
path = path + [start_vertex]
if start_vertex == end_vertex:
return path
if start_vertex not in graph:
return []
shortest = []
for vertex in graph[start_vertex]:
if vertex not in path:
newpath = self.find_shortest_path(vertex, end_vertex, path)
if newpath:
if not shortest or len(newpath) < len(shortest):
shortest = newpath
return shortest
[docs]
def find_distance(self, start_vertex, end_vertex):
"""Find number of edges from start_vertex to end_vertex."""
if start_vertex == end_vertex:
return 0
else:
shortest = self.find_shortest_path(start_vertex, end_vertex)
dist = len(shortest)
return dist-1
[docs]
def get_vertices(self):
"""
Get graph vertices.
Returns:
vertices : list
List of vertices.
"""
vertices = self.__vertices.keys()
return vertices
[docs]
def get_connected_vertices(self, start_vertex, vertices_encountered=None, gdict=None):
"""Determine if graph is connected."""
if gdict is None:
gdict = self.__graph_dict
if vertices_encountered is None:
vertices_encountered=list()
vertices_encountered.append(start_vertex)
vertices = list(gdict.keys())
#vertices = self.get_vertices()
if bool(vertices):
if start_vertex in gdict:
for vertex in gdict[start_vertex]:
if vertex not in vertices_encountered:
self.get_connected_vertices(vertex, vertices_encountered)
return vertices_encountered
[docs]
def get_components(self):
"""Find isolated components of a graph."""
lst = self.__getComponents()
n = len(lst)
components = list()
for i in range(n):
c1 = set(lst[i])
b = True
for j in range(i+1,n):
c2 = set(lst[j])
if len(c1) < len(c2) and c1.issubset(c2):
b = False
break
if b:
components.append(lst[i])
return components
def __getComponents(self):
"""Find isolated vertices."""
# gdict = self.__graph_dict
# vertices = set(gdict.keys())
vertices = set(self.get_vertices())
components = list()
while bool(vertices):
start_vertex = vertices.pop()
comp = self.get_connected_vertices(start_vertex)
components.append(comp)
vertices -= set(comp)
return components
[docs]
def is_connected(self, vertices_encountered = None,start_vertex=None):
"""Determine if graph is connected."""
if vertices_encountered is None:
vertices_encountered = set()
gdict = self.__graph_dict
vertices = list(gdict.keys())
#vertices = self.get_vertices()
if not start_vertex:
# chosse a vertex from graph as a starting point
start_vertex = vertices[0]
vertices_encountered.add(start_vertex)
if len(vertices_encountered) != len(vertices):
for vertex in gdict[start_vertex]:
if vertex not in vertices_encountered:
if self.is_connected(vertices_encountered, vertex):
return True
else:
return True
return False
[docs]
def vertex_degree(self, vertex):
"""Find vertex degree.
The degree of a vertex is the number of edges connecting
it, i.e. the number of adjacent vertices. Loops are counted
double, i.e. every occurence of vertex in the list
of adjacent vertices.
"""
adj_vertices = self.__graph_dict[vertex]
degree = len(adj_vertices) + adj_vertices.count(vertex)
return degree
[docs]
def degree_sequence(self):
"""Calculate the degree sequence."""
seq = []
for vertex in self.__graph_dict:
seq.append(self.vertex_degree(vertex))
seq.sort(reverse=True)
return tuple(seq)
[docs]
@staticmethod
def is_degree_sequence(sequence):
"""Find degree sequence.
Method returns True, if the "sequence" is a
degree sequence, i.e. a non-increasing sequence.
Otherwise returns False.
"""
# check if the sequence sequence is non-increasing:
return all( x>=y for x, y in zip(sequence, sequence[1:]))
[docs]
def delta(self):
"""Get the minimum degree of the vertices."""
minv = 1e10
for vertex in self.__graph_dict:
vertex_degree = self.vertex_degree(vertex)
if vertex_degree < minv:
minv = vertex_degree
return minv
[docs]
def Delta(self):
"""Get the maximum degree of the vertices."""
maxv = 0
for vertex in self.__graph_dict:
vertex_degree = self.vertex_degree(vertex)
if vertex_degree > maxv:
maxv = vertex_degree
return maxv
[docs]
def density(self):
"""Calculate the density of a graph."""
g = self.__graph_dict
V = len(g.keys())
E = len(self.edges())
return 2.0 * E / (V *(V - 1))
[docs]
def diameter(self):
"""Calculate the diameter of the graph."""
v = self.vertices()
pairs = [ (v[i],v[j]) for i in range(len(v)) for j in range(i+1, len(v)-1)]
smallest_paths = []
for (s,e) in pairs:
paths = self.find_all_paths(s,e)
if len(paths) > 0:
smallest = sorted(paths, key=len)[0]
smallest_paths.append(smallest)
smallest_paths.sort(key=len)
# longest path is at the end of list,
# i.e. diameter corresponds to the length of this pathz
diameter = len(smallest_paths[-1]) - 1
return diameter
[docs]
@staticmethod
def erdoes_gallai(dsequence):
"""Check if the condition of the Erdoes-Gallai inequality is fullfilled."""
if sum(dsequence) % 2:
# sum of sequence is odd
return False
if Graph.is_degree_sequence(dsequence):
for k in range(1,len(dsequence) + 1):
left = sum(dsequence[:k])
right = k * (k-1) + sum([min(x,k) for x in dsequence[k:]])
if left > right:
return False
else:
# sequence is increasing
return False
return True
[docs]
def find(self, parent, i):
"""Find a set of an element i.
This algorithm uses path compression technique.
Args:
parent : list
Parent list.
i : int
Element.
Returns:
Set of an element i.
"""
if parent[i] == i:
k = i
else:
k = self.find(parent, parent[i])
return k
[docs]
def union(self, parent, rank, x, y):
"""Return union of two sets of x and y.
This algoritm sorts uses union by rank.
Args:
parent : list
Parent list of vertices.
rank : list
Rank of tree.
x : list
Graph vertices.
y : list
Graph vertices.
Returns:
None.
"""
xroot = self.find(parent, x)
yroot = self.find(parent, y)
# Attach smaller rank tree under root of high rank tree (Union by Rank)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
# If ranks are same, then make one as root and increment its rank by one
else :
parent[yroot] = xroot
rank[xroot] += 1
[docs]
def isCyclic(self):
"""
Check whether a given graph contains a cycle or not.
Returns:
bool
True if graph is cyclic and False otherwise.
"""
# Allocate memory for creating V subsets and
# Initialize all subsets as single element sets
V = len(self.__vertices)
parent = [-1]*V
# Iterate through all edges of graph, find subset of both
# vertices of every edge, if both subsets are same, then
# there is cycle in graph.
g = self.__graph
for k in range(len(g)):
i,j,w = g[k]
x = self.find(parent, i)
y = self.find(parent, j)
if x == y:
return True
self.union(parent,x,y)
[docs]
def getMinimumSpanningTree(self):
"""
Kruskal's algorithm to find Minimum Spanning Tree (MST)of a given connected, undirected and weighted graph.
Time Complexity: O(ElogE) or O(ElogV). Here E is the number of edges and V is the number of vertices.
Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm.
The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time.
The value of E can be atmost O(V2), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV).
https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
Args:
self: Graph object.
Returns:
None.
"""
mst =[] #This will store the resultant MST
# Step 1: Sort all the edges in non-decreasing # order of their # weight.
# If we are not allowed to change the given graph, we can create a copy of graph
self.__graph = sorted(self.__graph,key=lambda item: item[2])
parent = [] ; rank = []
# Create V subsets with single elements
V = len(self.__vertices)
for node in range(V):
parent.append(node)
rank.append(0)
i = 0 # An index variable, used for sorted edges
e = 0 # An index variable, used for result[]
g = self.__graph
#vertices = self.__vertices
inv_vertices = self.__inv_vertices
weights = self.__weights
# Number of edges to be taken is equal to V-1
while e < V and i < len(g):
# Step 2: Pick the smallest edge and increment the index for next iteration
u,v,w = g[i]
#print(i,e,V)
i += 1
x = self.find(parent, u)
y = self.find(parent ,v)
#print(u,v,x,y)
# If including this edge does't cause cycle,
# Include it in result and increment the index of result for next edge
if x != y:
e += 1
k = str([min(u,v),max(u,v)])
v1 = inv_vertices[v]
u1 = inv_vertices[u]
w = weights[k]
mst.append([u1,v1,w])
self.union(parent,rank,x,y)
else:
pass # discard the edge
return mst
[docs]
def connected(self,t):
"""
Return connected vertices of a minimum spanning tree.
Args:
t : list
List of vertices.
Returns:
Connected vertices of a minimum spanning tree.
"""
from utils.util import findVariableLag,findVariableLead
d = {}
for i,x in enumerate(t):
u,v,w = x
if u in d:
d[u] += [i]
else:
d[u] = [i]
if v in d:
d[v] += [i]
else:
d[v] = [i]
ll = LinkedList()
u,v,w = t[0]
self.__connect(ll,d,t,u,v)
current = ll.head
s = ""; i=0
while current is not None:
v = current.value
if "_plus_" in v:
lead = findVariableLead(v)
ind = v.index("_plus")
v = v[:ind] + "(" + str(lead) + ")"
elif "_minus_" in v:
lag = findVariableLag(v)
ind = v.index("_minus_")
v = v[:ind] + "(" + str(lag) + ")"
s += str(v) + "->"
i += 1
if i%10 == 0:
s += "\n"
current = current.next
return s[:-2]
def __connect(self,lli,d,t,u,v):
"""
Build a list of connected nodes.
Args:
lli : LinkedList
List of nodes.
d : dict
Dictionary that has node labels as keys and their edge numbers as values.
t : list
Minimum spanning tree.
u : str
Node label.
v : str
Node label.
Returns:
List of connected nodes.
"""
if u==v:
return
head = lli.head
lst = LinkedList.toList(lli)
if not u in lst:
if not head is None and v == head.value:
lli.push(u)
else:
lli.append(u)
lst = LinkedList.toList(lli)
if not v in lst:
if not head is None and u == head.value:
lli.push(v)
else:
lli.append(v)
lst = LinkedList.toList(lli)
#LinkedList.display(li)
for k in d[u]:
u1,v1,w1 = t[k]
if not u1 in lst or not v1 in lst:
self.__connect(lli,d,t,u1,v1)
lst = LinkedList.toList(lli)
for k in d[v]:
u2,v2,w2 = t[k]
if not u2 in lst or not v2 in lst:
self.__connect(lli,d,t,u2,v2)
lst = LinkedList.toList(lli)
def __str__(self):
"""Represent Graph object as a string."""
# d = self.__graph_dict
res = "\nModel Equations Graph Information:\n----------------------------------"
# res += "\nVertices: "
# for k in d:
# res += str(k) + " "
# res += "\nEdges: "
# edges = self.__generate_edges()
# for edge in edges:
# res += str(edge) + " "
# v = self.__vertices
# res += "\nNumber of vertices: " + str(len(v))
res += "\nDiameter: {}".format(self.diameter())
res += "\nIs cyclic: {}".format(self.isCyclic())
res += "\nMinimum degree: {}".format(self.delta())
res += "\nMaximum degree: {}".format(self.Delta())
res += "\nDensity: {:.2f}".format(self.density())
# components = self.get_components()
# res += "\nNumber of components: {}".format(len(components))
# res += "\nComponents: {}".format(components)
# mst = self.getMinimumSpanningTree()
# print the contents of result[] to display the built MST
# res += "\nFollowing are the edges in the constructed MST:\n"
# for u,v,weight in mst:
# res += "Edge: {0}--{1}, weight: {2}\n".format(u,v,weight)
# res += "\nLinked list of connected vertices of minimum spanning tree:\n"
# res += self.connected(mst)
res += "\n\n"
return res
def __repr__(self):
"""Graph object represntation."""
return self.__str__()
[docs]
def printBiconnectedComponents(self):
print (f"\nThere are {self.count} biconnected components in a graph:")
for i,c in enumerate(self.components):
comp = self.components[c]
x = [self.im[s[0]] + "->" + self.im[s[1]] for s in comp]
print(f"{i+1}: {', '.join(x)}\n")
[docs]
def summary(self):
import numpy as np
#print (f"\nNumber of graph vertices {self.V}")
print (f"There are {self.count} biconnected components in a graph:")
components = self.getBiconnectedComponents()
all_sizes = list()
for comp in components:
sz = len(comp)
all_sizes.append(sz)
sizes = sorted(set(all_sizes))
all_sizes = np.array(all_sizes)
for x in sizes:
n = sum(all_sizes==x)
print(f"{n} component(s) of size {x}")
[docs]
def getBiconnectedComponents(self):
"""Get biconnected components in a graph."""
components = list()
for c in self.components:
comp = self.components[c]
lst = [(self.im[s[0]],self.im[s[1]]) for s in comp]
components.append(lst)
return components
[docs]
class Node(object):
"""Node class."""
value = None
next = None
def __init__(self, value, next=None):
self.value = value
self.next = next
def __str__(self):
"""Representats Graph object as a string."""
res = str(self.value)
return res
def __repr__(self):
"""Graph object represntation."""
return self.__str__()
[docs]
class LinkedList(object):
"""A Simple linked list class."""
def __init__(self, sequence=None):
if sequence is None:
self.head = None
else:
self.head = Node(sequence[0])
current = self.head
for item in sequence[1:]:
current.next = Node(item)
current = current.next
[docs]
def push(self, new_data):
"""Insert a new node at the beginning."""
# 1 & 2: Allocate the Node &
# Put in the data
new_node = Node(new_data)
# 3. Make next of new Node as head
new_node.next = self.head
# 4. Move the head to point to new Node
self.head = new_node
[docs]
def insertAfter(self, prev_node, new_data):
"""Insert a new node after the given prev_node."""
# 1. check if the given prev_node exists
if prev_node is None:
print("The given previous node must exist in the Linked List.")
return
# 2. create new node &
# Put in the data
new_node = Node(new_data)
# 4. Make next of new Node as next of prev_node
new_node.next = prev_node.next
# 5. make next of prev_node as new_node
prev_node.next = new_node
[docs]
def getParentNode(self,v):
"""Get previous node in the linked list."""
n = self.head
while (n):
if n.next == v:
return n
return None
[docs]
def insertBefore(self, node, new_data):
"""Insert a new node before the given node."""
# 1. check if the given prev_node exists
if node is None:
print("The given node must exist in the Linked List.")
return
parentNode = self.getParentNode(node)
if not parentNode is None:
# 2. create new node and put in the data
new_node = Node(new_data)
# 4. Make next of new Node as next of prev_node
parentNode.next = new_node
# 5. make next of prev_node as new_node
new_node.next = node
[docs]
def append(self, new_data):
"""Append a new node at the end."""
# 1. Create a new node
# 2. Put in the data
# 3. Set next as None
new_node = Node(new_data)
# 4. If the Linked List is empty, then make the new node as head
if self.head is None:
self.head = new_node
else:
# 5. Else traverse till the last node
last = self.head
while (last.next):
last = last.next
# 6. Change the next of last node
last.next = new_node
[docs]
def getNode(self,v):
"""Return node of a linked list by value."""
n = self.head
while (n):
if v == n.value:
return n
n = n.next
return None
[docs]
@staticmethod
def toList(self):
"""Convert a linked list to a list."""
temp = self.head
lst = []
while (temp):
lst.append(temp.value)
temp = temp.next
return lst
[docs]
@staticmethod
def display(self):
"""Display the linked list."""
temp = self.head
while (temp):
print(temp.value)
temp = temp.next
def __str__(self):
"""Representats LinkedList object as a string."""
res = ""
temp = self.head
while (temp):
res += str(temp) + "\n"
temp = temp.next
return res
def __repr__(self):
"""Graph object represntation."""
return self.__str__()
if __name__ == '__main__':
""" Test methods of Graph class. """
# Create a graph given in the above diagram
nodes = {'A':0,'B':1,'C':2,'D':3,'E':4,'F':5,'G':6,'H':7,'I':8,'J':9,'K':10,'L':11}
g = Graph(m=nodes)
g.addEdge('A','B')
g.addEdge('B','C')
g.addEdge('B','D')
g.addEdge('C','D')
g.addEdge('C','E')
g.addEdge('D','E')
g.addEdge('B','F')
g.addEdge('A','G')
g.addEdge('F','G')
g.addEdge('F','H')
g.addEdge('F','I')
g.addEdge('H','I')
g.addEdge('I','J')
g.addEdge('K','L')
g.BCC()
g.printBiconnectedComponents()
if False:
g = { "a" : ["d"],
"b" : ["c","e"],
"c" : ["b", "c", "d", "e"],
"d" : ["a", "c","b"],
"e" : ["c"],
"f" : []
}
graph = Graph(graph_dict=g)
print(graph)
print("Veryices degree:")
for node in graph.vertices():
print("{0} - {1}".format(node,graph.vertex_degree(node)))
print("List of isolated vertices:")
print(graph.find_isolated_vertices())
print("""A path from "a" to "e":""")
print(graph.find_path("a", "e"))
print("""A shortest path from "a" to "e":""")
print(graph.find_shortest_path("a", "e"))
print("""All pathes from "a" to "e":""")
print(graph.find_all_paths("a","e"))
print("""Check graph connectivity from "a":""")
print(graph.is_connected(start_vertex="a"))
print(""""Find distance from "a" to "e":""")
print(graph.find_distance("a", "e"))
print(""""Find connected vertices from "a":""")
print(graph.get_connected_vertices("a"))
print(""""Find connected vertices from "f":""")
print(graph.get_connected_vertices("f"))
print("The maximum degree of the graph is:")
print(graph.Delta())
print("The minimum degree of the graph is:")
print(graph.delta())
print("Edges:")
print(graph.edges())
print("Degree Sequence: ")
ds = graph.degree_sequence()
print(ds)
fullfilling = [ [2, 2, 2, 2, 1, 1],
[3, 3, 3, 3, 3, 3],
[3, 3, 2, 1, 1]
]
non_fullfilling = [ [4, 3, 2, 2, 2, 1, 1],
[6, 6, 5, 4, 4, 2, 1],
[3, 3, 3, 1]
]
for sequence in fullfilling + non_fullfilling :
print(sequence, Graph.erdoes_gallai(sequence))
print("Add vertex 'z':")
graph.add_vertex("z")
print(graph)
print("Add edge ('x','y'): ")
graph.add_edge(('x', 'y'))
print(graph)
print("Add edge ('a','d'): ")
graph.add_edge(('a', 'd'))
print(graph)
print("Add edge ('a','x'): ")
graph.add_edge(('a', 'x'))
print(graph)