-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathgraph.html
594 lines (531 loc) · 24.7 KB
/
graph.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Smile - Graph Data Structure</title>
<meta name="description" content="Statistical Machine Intelligence and Learning Engine">
<!-- prettify js and CSS -->
<script src="https://cdn.rawgit.com/google/code-prettify/master/loader/run_prettify.js?lang=scala&lang=kotlin&lang=clj"></script>
<style>
.prettyprint ol.linenums > li { list-style-type: decimal; }
</style>
<!-- Bootstrap core CSS -->
<link href="css/cerulean.min.css" rel="stylesheet">
<link href="css/custom.css" rel="stylesheet">
<script src="https://code.jquery.com/jquery.min.js"></script>
<script src="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.6/js/bootstrap.min.js"></script>
<!-- slider -->
<script src="https://cdnjs.cloudflare.com/ajax/libs/owl-carousel/1.3.3/owl.carousel.min.js"></script>
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/owl-carousel/1.3.3/owl.carousel.css" type="text/css" />
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/owl-carousel/1.3.3/owl.transitions.css" type="text/css" />
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/owl-carousel/1.3.3/owl.theme.min.css" type="text/css" />
<!-- table of contents auto generator -->
<script src="js/toc.js" type="text/javascript"></script>
<!-- styles for pager and table of contents -->
<link rel="stylesheet" href="css/pager.css" type="text/css" />
<link rel="stylesheet" href="css/toc.css" type="text/css" />
<!-- Vega-Lite Embed -->
<script src="https://cdn.jsdelivr.net/npm/vega@5"></script>
<script src="https://cdn.jsdelivr.net/npm/vega-lite@5"></script>
<script src="https://cdn.jsdelivr.net/npm/vega-embed@6"></script>
<!-- Google tag (gtag.js) -->
<script async src="https://www.googletagmanager.com/gtag/js?id=G-57GD08QCML"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-57GD08QCML');
</script>
<!-- Sidebar and testimonial-slider -->
<script type="text/javascript">
$(document).ready(function(){
// scroll/follow sidebar
// #sidebar is defined in the content snippet
// This script has to be executed after the snippet loaded.
// $.getScript("js/follow-sidebar.js");
$("#testimonial-slider").owlCarousel({
items: 1,
singleItem: true,
pagination: true,
navigation: false,
loop: true,
autoPlay: 10000,
stopOnHover: true,
transitionStyle: "backSlide",
touchDrag: true
});
});
</script>
</head>
<body>
<div class="container" style="max-width: 1200px;">
<header>
<div class="masthead">
<p class="lead">
<a href="index.html">
<img src="images/smile.jpg" style="height:100px; width:auto; vertical-align: bottom; margin-top: 20px; margin-right: 20px;">
<span class="tagline">Smile — Statistical Machine Intelligence and Learning Engine</span>
</a>
</p>
</div>
<nav class="navbar navbar-default" role="navigation">
<!-- Brand and toggle get grouped for better mobile display -->
<div class="navbar-header">
<button type="button" class="navbar-toggle" data-toggle="collapse" data-target="#navbar-collapse">
<span class="sr-only">Toggle navigation</span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
<span class="icon-bar"></span>
</button>
</div>
<!-- Collect the nav links, forms, and other content for toggling -->
<div class="collapse navbar-collapse" id="navbar-collapse">
<ul class="nav navbar-nav">
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Overview <b class="caret"></b></a>
<ul class="dropdown-menu">
<li><a href="quickstart.html">Quick Start</a></li>
<li><a href="overview.html">What's Machine Learning</a></li>
<li><a href="data.html">Data Processing</a></li>
<li><a href="visualization.html">Data Visualization</a></li>
<li><a href="vegalite.html">Declarative Visualization</a></li>
<li><a href="gallery.html">Gallery</a></li>
<li><a href="faq.html">FAQ</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Supervised Learning <b class="caret"></b></a>
<ul class="dropdown-menu">
<li><a href="classification.html">Classification</a></li>
<li><a href="regression.html">Regression</a></li>
<li><a href="deep-learning.html">Deep Learning</a></li>
<li><a href="feature.html">Feature Engineering</a></li>
<li><a href="validation.html">Model Validation</a></li>
<li><a href="missing-value-imputation.html">Missing Value Imputation</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Unsupervised Learning <b class="caret"></b></a>
<ul class="dropdown-menu">
<li><a href="clustering.html">Clustering</a></li>
<li><a href="vector-quantization.html">Vector Quantization</a></li>
<li><a href="association-rule.html">Association Rule Mining</a></li>
<li><a href="mds.html">Multi-Dimensional Scaling</a></li>
<li><a href="manifold.html">Manifold Learning</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">LLM & NLP <b class="caret"></b></a>
<ul class="dropdown-menu">
<li><a href="llm.html">Large Language Model (LLM)</a></li>
<li><a href="nlp.html">Natural Language Processing (NLP)</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">Math <b class="caret"></b></a>
<ul class="dropdown-menu">
<li><a href="linear-algebra.html">Linear Algebra</a></li>
<li><a href="statistics.html">Statistics</a></li>
<li><a href="wavelet.html">Wavelet</a></li>
<li><a href="interpolation.html">Interpolation</a></li>
<li><a href="graph.html">Graph Data Structure</a></li>
</ul>
</li>
<li class="dropdown">
<a href="#" class="dropdown-toggle" data-toggle="dropdown">API <b class="caret"></b></a>
<ul class="dropdown-menu">
<li><a href="api/java/index.html" target="_blank">Java</a></li>
<li><a href="api/scala/index.html" target="_blank">Scala</a></li>
<li><a href="api/kotlin/index.html" target="_blank">Kotlin</a></li>
<li><a href="api/clojure/index.html" target="_blank">Clojure</a></li>
<li><a href="api/json/index.html" target="_blank">JSON</a></li>
</ul>
</li>
<li><a href="https://mybinder.org/v2/gh/haifengl/smile/notebook?urlpath=lab%2Ftree%2Fshell%2Fsrc%2Funiversal%2Fnotebooks%2Findex.ipynb" target="_blank">Try It Online</a></li>
</ul>
</div>
<!-- /.navbar-collapse -->
</nav>
</header>
<div id="content" class="row">
<div class="col-md-3 col-md-push-9 hidden-xs hidden-sm">
<div id="sidebar">
<div class="sidebar-toc" style="margin-bottom: 20px;">
<p class="toc-header">Contents</p>
<div id="toc"></div>
</div>
<div id="search">
<script>
(function() {
var cx = '010264411143030149390:ajvee_ckdzs';
var gcse = document.createElement('script');
gcse.type = 'text/javascript';
gcse.async = true;
gcse.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') +
'//cse.google.com/cse.js?cx=' + cx;
var s = document.getElementsByTagName('script')[0];
s.parentNode.insertBefore(gcse, s);
})();
</script>
<gcse:searchbox-only></gcse:searchbox-only>
</div>
</div>
</div>
<div class="col-md-9 col-md-pull-3">
<h1 id="graph-top" class="title">Graph Data Structure</h1>
<p>Many machine learning algorithms (e.g. Isomap, UMAP, etc.) employ graph data structures internally.
Graphs are mathematical structures used to model pairwise relations between
objects from a certain collection. A graph is an abstract representation of
a set of objects where some pairs of the objects are connected by links.
The interconnected objects are represented by mathematical abstractions
called vertices (also called nodes or points), and the links that connect
some pairs of vertices are called edges (also called lines).
The edges may be directed (asymmetric) or undirected (symmetric).</p>
<p>There are different ways to store graphs in a computer system. The data
structure used depends on both the graph structure and the algorithm
used for manipulating the graph. Theoretically one can distinguish between
list and matrix structures but in concrete applications the best structure
is often a combination of both. List structures are often preferred for
sparse graphs as they have smaller memory requirements. Matrix structures
on the other hand provide faster access for some applications but can
consume huge amounts of memory. In Smile, we support both adjacency list
(class <code>AdjacencyList</code>) and adjacency matrix
(class <code>AdjacencyMatrix</code>).</p>
<p>In adjacency list, each vertex has a list
of which vertices it is adjacent to. This causes redundancy in an undirected
graph. Adjacency queries are faster, at the cost of extra storage space.</p>
<p>An adjacency matrix is an n by n matrix A, where n is the number
of vertices in the graph. If there is an edge from a vertex x to a vertex y,
then the element A(x,y) is 1 (or in general the number of edges or a weight), otherwise
it is 0. In computing, this matrix makes it easy to find subgraphs, and to
reverse a directed graph.</p>
<p>Both <code>AdjacencyList</code> and <code>AdjacencyMatrix</code> implement
the abstract interface <code>Graph</code>. The method <code>dot()</code>
returns the graphic representation in Graphviz dot format. You may try
<a target="_blank" href="http://viz-js.com/">http://viz-js.com/</a> to visualize the returned string.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_1" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_1">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
import smile.graph.*;
var graph = new AdjacencyList(8);
graph.addEdge(0, 2);
graph.addEdge(1, 7);
graph.addEdge(2, 6);
graph.addEdge(7, 4);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
graph.addEdge(5, 4);
String[] label = {"a", "b", "c", "d"}
graph.dot("SmileGraph", label);
</code></pre>
</div>
</div>
</div>
<p>In this example, we create a DOT graph with name 'SmileGraph' with 4 node labels.
Since we have 8 nodes, the rest of nodes will use their integer ID as label.
</p>
<h2 id="traversal" class="title">Graph Traversal</h2>
<p>The basic operation on graph is traversal, i.e. to visit the vertices in some
systematic order. Typically, we have breadth first search (BFS) and depth first
search (DFS). Both of these construct spanning trees with certain properties
useful in other graph algorithms. The generic methods <code>bfs(VertexVisitor)</code>
and <code>dfs(VertexVisitor)</code> take a user-define <code>VertexVisitor</code>
functor to perform specific operations when visiting a vertex.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_2" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_2">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
graph.dfs(i -> println("Visiting vertex " + i));
</code></pre>
</div>
</div>
</div>
<h2 id="connected_components" class="title">Connected Components</h2>
<p>An application of graph traversal is to compute connected components.
A connected component of an undirected graph is a connected subgraph
that is not part of any larger connected subgraph. The components of
any graph partition its vertices into disjoint sets, and are the
induced subgraphs of those sets. In <code>Graph</code> class, the methods
<code>bfcc()</code> and <code>dfcc()</code> compute the connected
components with BFS and DFS algorithms, respectively. These methods
return a two-dimensional array of which each row is the vertex IDs
in the same connected component.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_3" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_3">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
// compute connected components with BFS
graph.bfcc();
// compute connected components with DFS
graph.dfcc();
</code></pre>
</div>
</div>
</div>
<p>A strongly connected component of a directed graph is a maximal subgraph
where every pair of vertices is mutually reachable. Note that a conventional
DFS method cannot be used to find the strongly connected components. Instead,
one may leverage Kosaraju's algorithm or Tarjan's algorithm to compute strongly
connected components.</p>
<h2 id="topological_sort" class="title">Topological Sort</h2>
<p>With DFS or BFS, we can also obtain the topological ordering of a directed graph, which
is a linear ordering of its vertices such that for every directed edge uv from vertex
u to vertex v, u comes before v in the ordering. For instance, the vertices of the
graph may represent tasks to be performed, and the edges may represent constraints
that one task must be performed before another; in this application, a topological
ordering is just a valid sequence for the tasks. A topological ordering is possible
if and only if the graph has no directed cycles, that is, if it is a directed acyclic
graph (DAG).
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_4" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_4">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
var graph = new AdjacencyList(13, true);
graph.addEdge(8, 7);
graph.addEdge(7, 6);
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(0, 3);
graph.addEdge(0, 5);
graph.addEdge(0, 6);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(3, 5);
graph.addEdge(6, 4);
graph.addEdge(6, 9);
graph.addEdge(4, 9);
graph.addEdge(9, 10);
graph.addEdge(9, 11);
graph.addEdge(9, 12);
graph.addEdge(11, 12);
graph.dfsort(); // topological sort with DFS
graph.bfsort(); // topological sort with BFS
</code></pre>
</div>
</div>
</div>
<h2 id="mst" class="title">Minimum Spanning Tree</h2>
<p>A minimum spanning tree (MST) is a subset of the edges of a connected,
edge-weighted undirected graph that connects all the vertices together,
without any cycles and with the minimum possible total edge weight.
That is, it is a spanning tree whose sum of edge weights is as small as
possible. There are many use cases for minimum spanning trees.
With the method <code>prim</code>, we can calculate an MST by Prim's algorithm.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_5" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_5">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
var graph = new AdjacencyMatrix(6);
graph.addEdge(0, 1, 0.41);
graph.addEdge(1, 2, 0.51);
graph.addEdge(2, 3, 0.50);
graph.addEdge(4, 3, 0.36);
graph.addEdge(3, 5, 0.38);
graph.addEdge(3, 0, 0.45);
graph.addEdge(0, 5, 0.29);
graph.addEdge(5, 4, 0.21);
graph.addEdge(1, 4, 0.32);
graph.addEdge(4, 2, 0.32);
graph.addEdge(5, 1, 0.29);
List<Graph.Edge> mst = new ArrayList<>();
double cost = graph.prim(mst);
mst.forEach(edge -> println(edge))
</code></pre>
</div>
</div>
</div>
<h2 id="Dijkstra" class="title">Shortest Path</h2>
<p>With the method <code>dijkstra()</code>, we can calculate the shortest path
from a source to all other vertices in the graph by Dijkstra algorithm.
If no parameter is provided, Smile will calculate all pairwise shortest
path between all vertecies.
Many manifold algorithms employ the shortest path among the samples as
a similarity measure instead of pairwise distance.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_6" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_6">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
var graph = new AdjacencyMatrix(6, true);
graph.addEdge(0, 1, 0.41);
graph.addEdge(1, 2, 0.51);
graph.addEdge(2, 3, 0.50);
graph.addEdge(4, 3, 0.36);
graph.addEdge(3, 5, 0.38);
graph.addEdge(3, 0, 0.45);
graph.addEdge(0, 5, 0.29);
graph.addEdge(5, 4, 0.21);
graph.addEdge(1, 4, 0.32);
graph.addEdge(4, 2, 0.32);
graph.addEdge(5, 1, 0.29);
double[][] distances = graph.dijkstra();
</code></pre>
</div>
</div>
</div>
<h2 id="TSP" class="title">Travelling Salesman Problem</h2>
<p>The travelling salesman problem (TSP) is another important task in graph
theory, combinatorial optimization, and operations research.
It asks the following question: "Given a list of cities and the distances
between each pair of cities, what is the shortest possible route that visits
each city exactly once and returns to the origin city?" It is an NP-hard problem.
Smile provides the Held-Karp algorithm to compute the optimal solution of TSP.
It is an efficient dynamic programming algorithm, significantly better than
the superexponential performance {\displaystyle \Theta (n!)} of a brute-force algorithm.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_7" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_7">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
var graph = new AdjacencyMatrix(6);
graph.addEdge(0, 1, 0.41);
graph.addEdge(1, 2, 0.51);
graph.addEdge(2, 3, 0.50);
graph.addEdge(4, 3, 0.36);
graph.addEdge(3, 5, 0.38);
graph.addEdge(3, 0, 0.45);
graph.addEdge(0, 5, 0.29);
graph.addEdge(5, 4, 0.21);
graph.addEdge(1, 4, 0.32);
graph.addEdge(4, 2, 0.32);
graph.addEdge(5, 1, 0.29);
int[] tour = graph.heldKarp();
</code></pre>
</div>
</div>
</div>
<p>Although the Held-Karp algorithm is significantly better than a brute-force algorithm,
it is still too slow to apply to large graphs. To process TSPs containing thousands
of cities, Smile provides a branch-and-bound algorithm.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_8" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_8">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
// Branch-and-bound algorithm
int[] tour = graph.tsp();
</code></pre>
</div>
</div>
</div>
<p>For even large TSP problems, Smile provides several heuristic and approximate algorithms,
which quickly yield good solutions. For example, nearest, furthest, and arbitrary insertion
algorithms are implemented. These methods have a quadratic time complexity. Nearest insertion
algorithm yields at most 2 times longer than the optimal solution in the worest case.
Furthest insertion and arbitrary insertion have higher bound in the worest case. We can improve
the result further with the 2-Opt algorithm, which is a simple local search algorithm.
The main idea behind it is to take a route that crosses over itself and reorder it so that
it does not.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_9" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_9">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
// Heuristic algorithm
var tour = graph.nearestInsertion();
// 2-Opt algorithm
double cost = graph.opt2(tour, 3);
</code></pre>
</div>
</div>
</div>
<p>For tigher bound, Smile also implements the Christofides-Serdyukov algorithm yields a solution
that is at most 1.5 times longer than the optimal solution in the worst case. However, it has
a cubic time complexity.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_10" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_10">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
var tour = graph.christofides();
</code></pre>
</div>
</div>
</div>
<h2 id="max_flow" class="title">Maximum Flow Problem</h2>
<p>Another important graph task is the maximum flow problem that involves finding
a feasible flow through a flow network that obtains the maximum possible flow
rate. AdjacencyMatrix implements the push-relabel algorithm that is considered
one of the most efficient maximum flow algorithms. The name "push-relabel" comes
from the two basic operations used in the algorithm. Throughout its execution,
the algorithm maintains a "preflow" and gradually converts it into a maximum
flow by moving flow locally between neighboring nodes using push operations
under the guidance of an admissible network maintained by relabel operations.
</p>
<ul class="nav nav-tabs">
<li class="active"><a href="#java_11" data-toggle="tab">Java</a></li>
</ul>
<div class="tab-content">
<div class="tab-pane active" id="java_11">
<div class="code" style="text-align: left;">
<pre class="prettyprint lang-java"><code>
AdjacencyMatrix graph = new AdjacencyMatrix(6, true);
graph.addEdge(0, 1, 2);
graph.addEdge(0, 2, 9);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 0);
graph.addEdge(1, 4, 0);
graph.addEdge(2, 4, 7);
graph.addEdge(3, 5, 7);
graph.addEdge(4, 5, 4);
double[][] flow = new double[6][6];
double maxFlow = graph.pushRelabel(flow, 0, 5);
</code></pre>
</div>
</div>
</div>
<div id="btnv">
<span class="btn-arrow-left">← </span>
<a class="btn-prev-text" href="interpolation.html" title="Previous Section: Interpolation"><span>Interpolation</span></a>
<a class="btn-next-text" href="nlp.html" title="Next Section: NLP"><span>NLP</span></a>
<span class="btn-arrow-right"> →</span>
</div>
</div>
<script type="text/javascript">
$('#toc').toc({exclude: 'h1, h5, h6', context: '', autoId: true, numerate: false});
</script>
</div>
</div>
<a href=https://github.com/haifengl/smile><img style="position: fixed; top: 0; right: 0; border: 0" src=/images/forkme_right_orange.png alt="Fork me on GitHub"></a>
<!-- Place this tag right after the last button or just before your close body tag. -->
<script async defer id="github-bjs" src="https://buttons.github.io/buttons.js"></script>
</body>
</html>