<p>Reference Routine on a graph</p>

b1b872ce-b062-4465-b58e-b7f516be8ff5 13 4 5 decimal

&[DATE] &[TIME] - &[FILENAME]

Project shout a fly with a Cannon

]]>

W 008000500800050016000500160005002400002400001800025001800025001200050001200050006000250000800050060002500800050080005001200050001200050001600050016000500180002500222 mat :

Overlapping W 00112 black 15 mat 60002500212 black 15 mat 8000500312 black 15 mat 120005000412 black 15 mat 16000500512 black 15 mat 180002500612 black 15 mat 240000712 black 15 mat 81 sys :

B 00112 black 15 mat 60002500212 black 15 mat 8000500312 black 15 mat 120005000412 black 15 mat 16000500512 black 15 mat 180002500612 black 15 mat 240000712 black 15 mat 71 sys :

Overlapping

STEP 0 -Build the Adiacency Matrix of the Graph equivalent to the structure

It is a square matrix (Nodes_Nr x Nodes_Nr) where Nodes_Nr is the number of the nodes(Vertices)

of the graph, built this way:

-Number each node of the graph ( in the Matrix the row/col index match the number used to identify a node)

-Adiac_M(i,j)=1 if there is an arc that link the node i with the node j

-Adiac_M(i,j)=0 if there isn't an arc that link the node i with the node j

]]> <p>Reference Routine on a graph</p>

Evaluates the Degree of each node in  a graph defined through an Adiacency Matrix AdjM# Node_Degree j 1 AdjM# rows range a# j el AdjM# i j el abs i 1 AdjM# cols sum : for a# 21 line :

Evaluates the Starting Node & Ending Node of an Eulerian or Semi-Eulerian graph Nr_Odd_Nodes Odd_Nodes_List# Define_Starting_Node Nr_Odd_Nodes 0 ≡ Eulerian graph Starting_Node 1 : Ending_Node 1 : 31 line Nr_Odd_Nodes 2 ≡ Semi-Eulerian graph k 1 : Starting_Node 0 : 21 line k Nodes_Nr ≤ Odd_Nodes_List# k el 0 ≠ Starting_Node 0 ≡ Starting_Node k : k k 1 + : k Starting_Node trace 31 line Ending_Node k : k Starting_Node Ending_Node trace break 31 line if 11 line k k 1 + : k Starting_Node trace 21 line if 11 line while 31 line Need to add arcs to make the graph Eulerian Starting_Node 0 : 21 line if if Starting_Node Ending_Node 21 mat 21 line :

Used to check if the Path is complete Adj_M# Tot_Adjacency_Matrix Adj_M# sum 11 line :

Look Horizontally for another Node (the 1st found) in the Adjacency Matrix in the row indicated by the index StartNode AdjM# TotNodes StartNode Select_Next_Node Next_Node 0 : k 1 : k TotNodes ≤ AdjM# StartNode k el 0 ≠ Next_Node k : trace(el(AdjM#,StartNode,k),Next_Node) break 31 line k k 1 + : trace(el(AdjM#,StartNode,k),Next_Node) 21 line if 11 line while Next_Node 41 line :

Remove an edge from a Graph and the corresponding Adjacency Matrix knowing its extreme Nodes AdjM# Start_Node End_Node Delete_Edge AdjM# Start_Node End_Node el 0 : AdjM# End_Node Start_Node el 0 : 21 line :

Adjac_M 011000010110001101100011011000110110001101000011077 mat :

Adjac_M Node_Degree 234443271 mat

Nodes_Nr Adjac_M cols :

Nodes_Nr 7

With this information we can check if the structure ( i.e its eqivalent Graph )is : - Eulerian => There is no node of odd degree - Semi-Elerian => There are just 2 nodes of odd degree - not Eulerian => There are 1 or more then 2 nodes of odd degree

Evaluates the type of graph based on the criteria previously detailed V# Graph_Type Nr_Odd_Node 0 : j 1 V# rows range V# j el 2 mod 0 ≠ Nr_Odd_Node Nr_Odd_Node 1 + : Position_Odd_Nodes j el j : 21 line nothing Position_Odd_Nodes j el 0 : 21 line if 11 line for Nr_Odd_Node Position_Odd_Nodes 21 mat 31 line :

In this case it is a:

Adjac_M Node_Degree Graph_Type 1 el 0 ≡ Eulerian Graph white green 1 3 mat Adjac_M Node_Degree Graph_Type 1 el 2 ≡ Semi-Eulerian Graph white red 1 3 mat Non Eulerian Graph white red 1 3 mat if if

Adjac_M Node_Degree Graph_Type 2020006071 mat 21 mat

Adjac_M Node_Degree Graph_Type 2 el 020006071 mat

Based on the type of graph, if it is : - Eulerian => We can draw a path without lifting the pen from the drawing, starting the path from any node - Semi-Elerian => We can draw a path without lifting the pen from the drawing only starting from the 1st odd node and ending to the 2nd one or viceversa - not Eulerian => We can't draw directly a path without lifting the pen from the drawing. It is necessary to turn the graph in an Eulerian one adding further arcs. The Nr of arcs to add is equal to the Nr of nodes of odd degree.

Adjac_M Adjac_M Node_Degree Graph_Type 2 el augment 0110000010110002110110000110110000110110000110160000110078 mat

If the graph is Eulerian we can define it using the Fleury's Algorithm:

Step 1- Start with any node if the Graph is Eulerian or start from one of the 2 odd nodes if is semi-Eulerian

]]>

Starting_Node Adjac_M Node_Degree Graph_Type 1 el Adjac_M Node_Degree Graph_Type 2 el Define_Starting_Node 1 el :

Step 2- Get the next vertex in Euler Path. >> Condition: Don't break the bridge.

i) select the next vertex which has more than one edges.

ii) If next vertex has only one edge,

a) If it is last vertex, We can choose it as next vertex.

b) otherwise dont.

]]>

Various Inizializations

Nodes_Path 1 el Starting_Node :

Nodes_Path 211 mat

Adjac_M Tot_Adjacency_Matrix 22

Adjac_M_Dupl Adjac_M :

Edge_ir Starting_Node :

Edge_ic 0 :

pi 1 :

Adjac_M_Dupl Tot_Adjacency_Matrix 0 > Edge_ic Adjac_M_Dupl Nodes_Nr Starting_Node Select_Next_Node : Adjac_M_Dupl Edge_ic row sum 1 > Adjac_M_Dupl Starting_Node Edge_ic Delete_Edge Starting_Node Edge_ic : pi pi 1 + : Nodes_Path pi el Starting_Node : 41 line Adjac_M_Dupl Tot_Adjacency_Matrix 2 ≡ pi pi 1 + : Nodes_Path pi el Edge_ic : 21 line if if Edge_ic pi Adjac_M_Dupl Tot_Adjacency_Matrix Adjac_M_Dupl Edge_ic row sum trace Adjac_M_Dupl Starting_Node Edge_ic Delete_Edge trace 41 line while

Select next node

and check if has more then 1 edges

if yes remove the edge from Edge_ir to Edge_ic

Select a new Starting Node

Update the path

and if there is just 1 edge ...

check if it is the last node

Adjac_M_Dupl 000000000000000000000000000000000000000000000000077 mat

Nodes_Path transpose 213243546576112 mat

pi 12

Edge_ic 6

Adjac_M_Dupl Edge_ic row sum 0

Adjac_M_Dupl Tot_Adjacency_Matrix 0

The vector Node_Path describes a path - in term of sequence of nodes- we can draw without lifting the pen

from the drawing of the graph equivalent( or associated) to the structure

Next steps:

1-It is necessary to turn each node of the sequence in coordinates and then merge everything in a Matrix

for drawing with the 2d graph method

2-It is necessary to develop the complete Chinese Postman Algorithm , i.e define what to do when the graph

is non Eulerian , so it is necessary to define all the nodes of odd degree , then add a number of edges that turn

the graph in Eulerian using a shortest path technique ( that this time can be managed using a BFS Alghoritm

and not the Dejistra one because all the edges have the same weight ).

3-Working again on a Eulerian graph we can applay again the Fleury Algorithm for its complete traversing.

]]>