import numpy as np
class G:
def __init__(self,value=None,children=None,color='white'):
self.value = value
self.children=children
self.color=color
def exploration(self,print_call_graph=False):
seen_node_list=[self]
print_call_graph and (print("-->",self.value) )
for node in seen_node_list:
for child in node.children:
if child != None and child not in set(seen_node_list):
print_call_graph and print("-->",child.value)
seen_node_list.append(child)
print_call_graph and print("<--",node.value)
return len(seen_node_list)
def exploration_rec(self,seen_node_list=[],print_call_graph=False,parent=None):
if not self in set(seen_node_list):
print_call_graph and (print("-->",self.value) )
seen_node_list.append(self)
for child in self.children:
if child != None:
child.exploration_rec(seen_node_list,print_call_graph,parent=self)
print_call_graph and parent!=None and print("<--",parent.value)
return len(seen_node_list)
def nbPaths(self,destination):
if self == destination:
return 1
nb_paths = 0
for child in self.children:
if child != None:
nb_paths += child.nbPaths(destination)
return nb_paths
def nbColor_from_node(self,color,seen_node_list=[]):
reachable_color=0
if not self in set(seen_node_list):
seen_node_list.append(self)
if self.color==color:
reachable_color+=1
for child in self.children:
if child != None:
reachable_color+=child.nbColor_from_node(color,seen_node_list)[0]
return reachable_color,len(seen_node_list)
def print_graph(self,depth=0,node_list=[]):
if self in set(node_list):
print("|","---" * depth,">",self.value)
return
else:
print("|","---" * depth,">",self.value)
node_list.append(self)
for child in self.children:
if child != None:
child.print_graph(depth+1,node_list)
To explore the graph in a tree-fashion, we can use two approaches:
Remark: For pure tree-graphs, no child node already met can be met again, so the condition is never enforced
The exploration in tree-form of the whole graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ with vertices (or nodes) $\mathcal{V}$ and edges (or children for each node) $\mathcal{E}$ requires that every vertex $i$ of the $n=|\mathcal{V}|$ vertices identifies its $m_i$ edges (or "children" nodes). In total, calling $m=|\mathcal{E}|=\sum_{i=1}^n$ the number of directed edges in the graph, the total storage cost of the graph information is $$O(n+m).$$
When storing the graph as its adjacency matrix of size $n\times n$, the cost is instead $$O(n^2).$$
It is thus more convenient to use a list of edges representation on sparse graphs (that is, graphs with few edges per vertex).
def exploration(self,print_call_graph=False):
seen_node_list=[self]
print_call_graph and (print("-->",self.value) )
for node in seen_node_list:
for child in node.children:
if child != None and child not in set(seen_node_list):
print_call_graph and print("-->",child.value)
seen_node_list.append(child)
print_call_graph and print("<--",node.value)
return len(seen_node_list)
def exploration_rec(self,seen_node_list=[],print_call_graph=False,parent=None):
if not self in set(seen_node_list):
print_call_graph and (print("-->",self.value) )
seen_node_list.append(self)
for child in self.children:
if child != None:
child.exploration_rec(seen_node_list,print_call_graph,parent=self)
print_call_graph and parent!=None and print("<--",parent.value)
return len(seen_node_list)
### Deterministic tree graph
tree_graph = G('A',[G('B',[G('F',[]),G('G',[])]),G('D',[G('H',[])])])
print("Visual representation of tree_graph:\n")
tree_graph.print_graph(node_list=[])
print("\nIterative exploration of tree_graph:\n")
print("\nNumber of nodes seen from root:\n",tree_graph.exploration(print_call_graph=True),"\n")
print("\nRecursive exploration of tree_graph:\n")
print("\nNumber of nodes seen from root, recursive search:\n",tree_graph.exploration_rec([],print_call_graph=True),"\n")
### Random graph generator
graph_size = 10
list_values = np.random.randint(0,100,graph_size)
# Affinity matrix of the graph with 'p' probability of connection
p = .2
A = np.random.binomial(1,p,(graph_size,graph_size))
A = A-np.diag(np.diag(A))
nodes = []
print("List of values in the graph:",list_values)
for i in range(len(list_values)):
nodes.append(G(value=list_values[i],children=[]))
for i in range(len(nodes)):
for j in range(len(nodes)):
if A[i,j]>0:
nodes[i].children.append(nodes[j])
print("\nAdjacency matrix:\n",A)
node_index = 1
print("\nTree representation of the graph starting from node[",node_index,"]:\n")
nodes[node_index].print_graph(node_list=[])
print("\nNumber of nodes seen from node[",node_index,"]:\n",nodes[node_index].exploration())
print("\nIterative exploration of random graph:\n")
print("\nNumber of nodes seen from node[",node_index,"]:\n",nodes[node_index].exploration(print_call_graph=True),"\n")
print("\nRecursive exploration of random graph:\n")
print("\nNumber of nodes seen from node[",node_index,"]:\n",nodes[node_index].exploration_rec([],print_call_graph=True),"\n")
To evaluate the number of paths from a source node to a destination node, it suffices to accumulate $1$ whenever source == destination and, otherwise, to add the number of paths from each child of the source to the destination. The complexity of the operation is in the worst case similar to previously $O(n+m)$ whenever all children of all nodes need to scanned.
def nbPaths(self,destination):
if self == destination:
return 1
nb_paths = 0
for child in self.children:
if child != None:
nb_paths += child.nbPaths(destination)
return nb_paths
I use here a ugly technique to generate a random DAG: the affinity matrix of DAGs is nilpotent, so that all its eigenvalues are zeros. I generate random affinity matrices until this condition is met. Particular care must be taken to avoid sufficiently many nodes while at the same time ensuring convergence of the search.
graph_size = 25
list_values = np.random.randint(0,200,graph_size)
p = .1
A = np.ones( (graph_size,graph_size) )
while(np.max(np.abs(np.linalg.eig(A)[0])) > 1e-10 ):
A = np.random.binomial(1,p,(graph_size,graph_size))
A = A-np.diag(np.diag(A))
nodes = []
print("List of values in the graph:",list_values)
for i in range(len(list_values)):
nodes.append(G(value=list_values[i],children=[]))
for i in range(len(nodes)):
for j in range(len(nodes)):
if A[i,j]>0:
nodes[i].children.append(nodes[j])
print("\nAdjacency matrix:\n",A)
node_index = 0
print("\nTree representation of the graph starting from node[",node_index,"]:\n")
nodes[node_index].print_graph(node_list=[])
node_s=nodes[0]
node_t=nodes[14]
print("\nNumber of paths from node[",node_s.value,"] to node[",node_t.value,"]:\n",node_s.nbPaths(node_t))
To evaluate the probability of falling on two connected red nodes $N_1$ and $N_2$ in a colored graph, it suffices to observe that this probability equals: $$ \sum_{ \mathcal{C}\in \{ \text{connected components} \} } \mathbb{P} ( N_1,N_2\in\mathcal C ) \cdot \mathbb{P}(N_1,N_2\text{ red}) = \sum_{ \mathcal{C}\in \{ \text{connected components} \} } \frac{|\text{red nodes in $\mathcal C$}|(|\text{red nodes in $\mathcal C$}|-1)}{|\mathcal C|(|\mathcal C|-1)} \frac{|\mathcal C|(|\mathcal C|-1)}{|\mathcal V|(|\mathcal V|-1)} = \sum_{ \mathcal{C}\in \{ \text{connected components} \} } \frac{|\text{red nodes in $\mathcal C$}|(|\text{red nodes in $\mathcal C$}|-1)}{|\mathcal V|(|\mathcal V|-1)}.$$
It thus "suffices" to evaluate the number of red nodes in every connected component of the graph. This can be done by exploration from every node in the graph, keeping in memory the already met nodes.
# At G level:
def nbColor_from_node(self,color,seen_node_list=[]):
reachable_color=0
if not self in set(seen_node_list):
seen_node_list.append(self)
if self.color==color:
reachable_color+=1
for child in self.children:
if child != None:
reachable_color+=child.nbColor_from_node(color,seen_node_list)[0]
return reachable_color,len(seen_node_list)
# Independent function
def probaColor(nodes,color,print_option=False):
probaC = 0
seen_node_list = []
nbTotal_running = 0
for node in nodes:
if node not in set(seen_node_list):
nbColor,nbTotal = node.nbColor_from_node(color,seen_node_list)
probaC += nbColor*(nbColor-1)/(len(nodes)*(len(nodes)-1))
print_option and print("\n New connected component found with",nbColor,"'red' nodes out of",nbTotal-nbTotal_running,"total nodes.")
nbTotal_running = nbTotal
return probaC
### Random symmetric colored graph generator
graph_size = 10
list_values = np.random.randint(0,100,graph_size)
# Affinity matrix of the graph with 'p' probability of connection
p = .2
A = np.random.binomial(1,p,(graph_size,graph_size))
A = A-np.diag(np.diag(A))
A = np.tril(A)+np.tril(A).T
nodes = []
pRed = .5
for i in range(len(list_values)):
if np.random.randint(0,2) == 0:
color='red'
else:
color='white'
nodes.append(G(value=list_values[i],children=[],color=color))
print("List of values in the graph and their colors:\n",list_values,"\n",[1*(node.color=='red') for node in nodes])
for i in range(len(nodes)):
for j in range(len(nodes)):
if A[i,j]>0:
nodes[i].children.append(nodes[j])
print("\nAdjacency matrix:\n",A)
node_index = 0
print("\nTree representation of the graph starting from node[",node_index,"]:\n")
nodes[node_index].print_graph(node_list=[])
print("\nProba 'red'=",probaColor(nodes,'red',print_option=True))
from functools import wraps
def trace(func):
func_name = func.__name__
separator = '| '
trace.recursion_depth = 0
@wraps(func)
def traced_func(*args, **kwargs):
# repeat separator N times (where N is recursion depth)
# `map(str, args)` prepares the iterable with str representation of positional arguments
# `", ".join(map(str, args))` will generate comma-separated list of positional arguments
# `"x"*5` will print `"xxxxx"` - so we can use multiplication operator to repeat separator
print(f'{separator * trace.recursion_depth}|-- {func_name}({", ".join(map(str, args))})')
# we're diving in
trace.recursion_depth += 1
result = func(*args, **kwargs)
# going out of that level of recursion
trace.recursion_depth -= 1
# result is printed on the next level
print(f'{separator * (trace.recursion_depth + 1)}|-- return {result}')
return result
return traced_func