class node:

def init(self, identity, label, parents, children):
‘’‘
identity: int; its unique id in the graph
label: string;
parents: int->int dict; maps a parent node’s id to its multiplicity
children: int->int dict; maps a child node’s id to its multiplicity
‘’’
self.id = identity
self.label = label
self.parents = parents
self.children = children

def repr (self):
return "id: "+ str(self.id) + ", " + "label: " + str(self.label) + ", " + "parents: " + str(self.parents) + ", " + "children: " + str(self.children)
#ok

def get_id (self):
return self.id

def get_label (self):
return self.label
#ok

def get_parents_ids (self):
return [i for i in self.parents.keys()]
#ok

def get_children_ids (self):
return [i for i in self.children.keys()]
#ok

def get_children(self):
return self.children.values()

def get_parents(self):
return self.parents.values()

def set_id(self, i):
self.id = i
#ok

def set_label(self, i):
self.label = i
#ok

def set_parents_ids(self, i):
self.parents = i
#ok

def set_children_ids(self, i):
self.children = i
#ok

def add_child_id(self, i):
if i in self.get_children_ids():
self.children[i] +=1
else:
self.children[i] = 1
#ok

def add_parent_id(self, i):
if i in self.get_parents_ids():
self.parents[i] +=1
else:
self.parents[i] = 1
#ok

def remove_parent_once(self, id):
try:
if self.parents[id] <= 1:
self.remove_parent_id(id)
return
self.parents[id] = self.parents[id] - 1
except KeyError:
raise “Invalid parent id”
#ok

def remove_child_once(self, id):
try:
if self.children[id] <= 1:
self.remove_child_id(id)
return
self.children[id] = self.children[id] - 1
except KeyError:
raise “Invalid child id”
#ok

def remove_parent_id(self, id):
try:
self.parents.pop(id)
except KeyError:
raise “Invalid parent id”
#ok

def remove_child_id(self, id):
try:
self.children.pop(id)
except KeyError:
raise “Invalid child id”
#ok

def indegree(self):
res = 0
for p in self.parents.values():
res += p
return res

def outdegree(self):
res = 0
for c in self.children.values():
res +=c
return res

def degree(self):
return self.indegree()+self.outdegree()

n = node(2, 0, {1: 2}, {3: 2})
#print(n.indegree())
#print(n.outdegree())
#print(n.degree())


class open_digraph(open_digraph_display_mx, open_digraph_connectivite_mx, open_digraph_tritopo_mx, node): # for open directed graph

def init(self, inputs, outputs, nodes):
‘’‘
inputs: int list; the ids of the input nodes
outputs: int list; the ids of the output nodes
nodes: node list;
‘’’
self.inputs = inputs
self.outputs = outputs
self.nodes = {node.id:node for node in nodes} # self.nodes: <int,node> dict

def str (self):
return "inputs: " + str(self.inputs) + “\n” + "outputs: “+ str(self.outputs) + “\n” + “nodes: " + str(self.nodes)

@classmethod
def empty(cls):
return cls([],[],[])

def copy(self):
newNodes = {}
d = open_digraph.empty()
d.inputs = self.inputs.copy()
d.outputs = self.outputs.copy()
for key in self.nodes.keys():
n0 = node(-1, ‘’, {}, {})
n0.id = self.nodes[key].id
n0.label = self.nodes[key].label
n0.parents = self.nodes[key].parents.copy()
n0.children = self.nodes[key].children.copy()
newNodes[key]=n0
d.nodes = newNodes
return d
#ok

def get_input_ids(self):
return self.inputs
#return [i.get_id() for i in self.inputs]
#ok

def get_output_ids(self):
return self.outputs
#return [i.get_id() for i in self.outputs]
#ok

def get_id_node_map(self):
return self.nodes
#ok

def get_nodes(self):
return [i for i in self.nodes.values()]
#ok

def get_node_ids(self):
return [i for i in self.nodes.keys()]
#ok

def get_node_by_id(self, i):
‘’‘
i : int (id of the node)
‘’’
return self.nodes[i]
#ok

def get_nodes_by_ids(self, t):
‘’‘
t : int iter
‘’’
return [self.nodes[i] for i in t]
#ok

def get_input_nodes(self):
return [self.nodes[node_id] for node_id in self.inputs]

def get_output_nodes(self):
return [node for node in self.nodes.values() if node.outdegree() == 0 and node in self.outputs]

def set_input_ids(self, t):
‘’‘
t : int list
‘’’
self.inputs = t
#ok

def set_output_ids(self, t):
‘’‘
t : int list
‘’’
self.outputs = t
#ok

def add_node(self, label=‘’, parents=None, children=None): #parents et children sont des dictionnaires
‘’‘
adds a NEW (it creates it !) a node
label : string
parents : int:int dict
children : int:int dict
‘’’
if parents is None:
parents = {}
if children is None:
children = {}
new_id = self.new_id()
new_node = node(new_id, label, parents, children)
self.nodes[new_id] = new_node
for parent_id in parents:
self.nodes[parent_id].children[new_id] = parents[parent_id]
for child_id in children:
self.nodes[child_id].parents[new_id] = children[child_id]
return new_id
#ok

def add_input_node (self, id):
nid = self.new_id()
if (id in self.get_input_ids()) or (id in self.get_output_ids()):
raise “invalid connection”
else:
self.nodes[nid] = node(nid, “input”, dict(), {id:1})
self.nodes[id].parents[nid] = 1
self.add_input_id(nid)
#ok

def add_output_node (self, id):
nid = self.new_id()
if (id in self.get_input_ids()) or (id in self.get_output_ids()):
raise “invalid connection”
else:
self.nodes[nid] = node(nid,“output”,{id:1},dict())
self.nodes[id].children[nid] = 1
self.add_output_id(nid)
#ok

def add_input_id(self, t):
‘’‘
makes an existing node an input
t : int (id of the node)
‘’’
if t in self.inputs:
raise “Already an input”
else:
self.inputs += [t]
#ok

def add_output_id(self, t):
‘’‘
makes an existing node an output
t : int (id of the node)
‘’’
if t in self.outputs:
raise ‘Already an output’
else:
self.outputs += [t]
#ok

def add_edge(self, src, tgt):
if src not in self.nodes:
raise ValueError(f"node id source invalide :{src}”) #vérifie si le noeud source (src) existe dans la liste des noeuds (nodes) de ce graph
if tgt not in self.nodes:
raise ValueError(f"node id cible invalide :{tgt}”) #vérifie si le noeud cible (tgt) existe dans la liste des noeuds (nodes)

src_node = self.get_node_by_id(src) # récupere le noeud source a partir de la liste de neouds en utilisant l’identifiant src du noeud source
tgt_node = self.get_node_by_id(tgt) # recupere le noeud cible a partir de la liste des noeuds en utilisant l’id tgt du noeud cible
src_node.add_child_id(tgt)
tgt_node.add_parent_id(src)
#ok

def add_edges(self, edges):
‘’‘
edges : (int, int) iter
‘’’
for src, tgt in edges:
self.add_edge(src, tgt)
#ok
class bool_circ(open_digraph):

def init(self,g):
circuit = {}
nod = g.get_node_ids()
inp = g.get_input_ids()
out = g.get_output_ids()
for n in nod:
if (n not in inp) or (n not in out):
circuit.update(rand.randint(0,3),n) #porte et = 0, porte ou = 1, porte not = 2, porte copie = 3
self.circ = circuit
self.outputs = g.outputs
self.inputs = g.inputs
self.nodes = g.nodes
if not self.is_well_formed():
raise “Invalid circuit”