1+++
  2title = "Graphs"
  3date = 2017-06-02
  4updated = 2017-06-02
  5[taxonomies]
  6category = ["algos"]
  7tags = ["graphs"]
  8+++
  9
 10<noscript>There are a few things which won't render unless you enable
 11JavaScript. No tracking, I promise!</noscript>
 12
 13> Don't know English? [Read the Spanish version instead](spanish.html).
 14
 15Let's imagine we have 5 bus stations, which we'll denote by ((s_i)):
 16
 17<div class="matrix">
 18      ' s_1 ' s_2 ' s_3 ' s_4 ' s_5 \\
 19s_1   '     '  V  '     '     '     \\
 20s_2   '  V  '     '     '     '  V  \\
 21s_3   '     '     '     '  V  '     \\
 22s_4   '     '  V  '  V  '     '     \\
 23s_5   '  V  '     '     '  V  '
 24</div>
 25
 26This is known as a "table of direct interconnections".
 27The ((V)) represent connected paths. For instance, on the first
 28row starting at ((s_1)), reaching the ((V)),
 29allows us to turn up to get to ((s_2)).
 30
 31We can see the above table represented in a more graphical way:
 32
 33![Table 1 as a Graph](example1.svg)
 34
 35This type of graph is called, well, a graph, and it's a directed
 36graph (or digraph), since the direction on which the arrows go does
 37matter. It's made up of vertices, joined together by edges (also known as
 38lines or directed arcs).
 39
 40One can walk from a node to another through different paths. For
 41example, ((s_4 $rightarrow s_2 $rightarrow s_5)) is an indirect path of order
 42two, because we must use two edges to go from ((s_4)) to
 43((s_5)).
 44
 45Let's now represent its adjacency matrix called A which represents the
 46same table, but uses 1 instead V to represent
 47a connection:
 48
 49<div class="matrix">
 50  0 ' 1 ' 0 ' 0 ' 0 \\
 51  1 ' 0 ' 0 ' 0 ' 1 \\
 52  0 ' 0 ' 0 ' 1 ' 0 \\
 53  0 ' 1 ' 1 ' 0 ' 0 \\
 54  1 ' 0 ' 0 ' 1 ' 0
 55</div>
 56
 57This way we can see how the ((a_{2,1})) element represents the
 58connection ((s_2 $rightarrow s_1)), and the ((a_{5,1})) element the
 59((s_5 $rightarrow s_1)) connection, etc.
 60
 61In general, ((a_{i,j})) represents a connection from
 62  ((s_i $rightarrow s_j))as long as ((a_{i,j}$geq 1)).
 63
 64Working with matrices allows us to have a computable representation of
 65any graph, which is very useful.
 66
 67<hr />
 68
 69Graphs have a lot of interesting properties besides being representable
 70by a computer. What would happen if, for instance, we calculated
 71((A^2))? We obtain the following matrix:
 72
 73<div class="matrix">
 741 ' 0 ' 0 ' 0 ' 1 \\
 751 ' 1 ' 0 ' 1 ' 0 \\
 760 ' 1 ' 1 ' 0 ' 0 \\
 771 ' 0 ' 0 ' 1 ' 1 \\
 780 ' 2 ' 1 ' 0 ' 0
 79</div>
 80
 81We can interpret this as the paths of order two.
 82But what does the element ((a_{5,2}=2)) represent? It indicates
 83the amount of possible ways to go from  ((s_5 $rightarrow s_i $rightarrow s_2)).
 84
 85One can manually multiply the involved row and column to determine which
 86element is the one we need to pass through, this way we have the row
 87(([1 0 0 1 0])) and the column (([1 0 0 1 0])) (on
 88vertical). The elements ((s_i$geq 1)) are ((s_1)) and
 89((s_4)). This is, we can go from ((s_5)) to
 90((s_2)) via ((s_5 $rightarrow s_1 $rightarrow s_2)) or via
 91((s_5 $rightarrow s_4 $rightarrow s_2)):
 92<img src="example2.svg" />
 93
 94It's important to note that graphs to not consider self-connections, this
 95is, ((s_i $rightarrow s_i)) is not allowed; neither we work with multigraphs
 96here (those which allow multiple connections, for instance, an arbitrary
 97number ((n)) of times).
 98
 99<div class="matrix">
1001 ' 1 ' 0          ' 1 ' 0 \\
1011 ' 2 ' \textbf{1} ' 0 ' 1 \\
1021 ' 0 ' 0          ' 1 ' 1 \\
1031 ' 2 ' 1          ' 1 ' 0 \\
1042 ' 0 ' 0          ' 1 ' 2
105</div>
106
107We can see how the first ((1)) just appeared on the element
108  ((a_{2,3})), which means that the shortest path to it is at least
109of order three.
110
111<hr />
112
113A graph is said to be strongly connected as long as there is a
114way to reach all its elements.
115
116We can see all the available paths until now by simply adding up all the
117direct and indirect ways to reach a node, so for now, we can add
118((A+A^2+A^3)) in such a way that:
119
120<div class="matrix">
1212 ' 2 ' 0 ' 1 ' 1 \\
1223 ' 3 ' 1 ' 1 ' 3 \\
1231 ' 1 ' 1 ' 2 ' 1 \\
1242 ' 3 ' 2 ' 2 ' 1 \\
1253 ' 2 ' 1 ' 2 ' 2
126</div>
127
128There isn't a connection between ((s_1)) and ((s_3)) yet.
129If we were to calculate ((A^4)):
130
131<div class="matrix">
1321 ' 2 ' 1 '   '   \\
133  '   '   '   '   \\
134  '   '   '   '   \\
135  '   '   '   '   \\
136  '   '   '   '
137</div>
138
139We don't need to calculate anymore. We now know that the graph is
140strongly connected!
141
142<hr />
143
144Congratulations! You've completed this tiny introduction to graphs.
145Now you can play around with them and design your own connections.
146
147Hold the left mouse button on the above area and drag it down to create
148a new node, or drag a node to this area to delete it.
149
150To create new connections, hold the right mouse button on the node you
151want to start with, and drag it to the node you want it to be connected to.
152
153To delete the connections coming from a specific node, middle click it.
154
155<table><tr><td style="width:100%;">
156  <button onclick="resetConnections()">Reset connections</button>
157  <button onclick="clearNodes()">Clear all the nodes</button>
158  <br />
159  <br />
160  <label for="matrixOrder">Show matrix of order:</label>
161  <input id="matrixOrder" type="number" min="1" max="5"
162                          value="1" oninput="updateOrder()">
163  <br />
164  <label for="matrixAccum">Show accumulated matrix</label>
165  <input id="matrixAccum" type="checkbox" onchange="updateOrder()">
166  <br />
167  <br />
168  <div>
169    <table id="matrixTable"></table>
170  </div>
171</td><td>
172  <canvas id="canvas" width="400" height="400" oncontextmenu="return false;">
173  Looks like your browser won't let you see this fancy example :(
174  </canvas>
175  <br />
176</td></tr></table>
177
178<script src="tinyparser.js"></script>
179<script src="enhancements.js"></script>
180<script src="graphs.js"></script>