A Java Library of Graph Algorithms and Optimization

Contents
INTRODUCTION ....................................................................................... 1
1. RANDOM GRAPH GENERATION....................................................... 3
1.1 Random Permutation of n Objects ........................................................................................ 3
1.2 Random Graph........................................................................................................................ 4
1.3 Random Bipartite Graph........................................................................................................ 7
1.4 Random Regular Graph ....................................................................................................... 10
1.5 Random Spanning Tree ....................................................................................................... 14
1.6 Random Labeled Tree ......................................................................................................... 16
1.7 Random Unlabeled Rooted Tree......................................................................................... 18
1.8 Random Connected Graph................................................................................................... 21
1.9 Random Hamilton Graph..................................................................................................... 24
1.10 Random Maximum Flow Network .................................................................................... 27
1.11 Random Isomorphic Graphs.............................................................................................. 31
1.12 Random Isomorphic Regular Graphs ............................................................................... 34
2. CONNECTIVITY................................................................................. 37
2.1 Maximum Connectivity ........................................................................................................ 37
2.2 Depth-First Search ................................................................................................................ 39
2.3 Breadth-First Search............................................................................................................. 43
2.4 Connected Graph Testing..................................................................................................... 47
2.5 Connected Components ........................................................................................................ 50
2.6 Cut Nodes............................................................................................................................... 55
2.7 Strongly Connected Components ........................................................................................ 61
2.8 Minimal Equivalent Graph .................................................................................................. 65
2.9 Edge Connectivity ................................................................................................................. 73
2.10 Minimum Spanning Tree.................................................................................................... 75
2.11 All Cliques............................................................................................................................ 81
3. PATHS AND CYCLES ....................................................................... 89
3.1 Fundamental Set of Cycles ................................................................................................... 89
3.2 Shortest Cycle Length........................................................................................................... 93
3.3 One-Pair Shortest Path......................................................................................................... 96
3.4 All Shortest Path Length .................................................................................................... 102
3.5 Shortest Path Tree............................................................................................................... 105
3.6 All Pairs Shortest Paths ...................................................................................................... 109
3.7 k Shortest Paths................................................................................................................... 112
3.8 k Shortest Paths without Repeated Nodes ........................................................................ 123
3.9 Euler Circuit ........................................................................................................................ 142
3.10 Hamilton Cycle .................................................................................................................. 146
3.11 Chinese Postman Tour...................................................................................................... 151
3.12 Traveling Salesman Problem ........................................................................................... 173
4. PLANARITY TESTING..................................................................... 179
5. GRAPH ISOMORPHISM TESTING ................................................. 195
6. COLORING ...................................................................................... 207
6.1 Node Coloring...................................................................................................................... 207
6.2 Chromatic Polynomial ........................................................................................................ 212
7. GRAPH MATCHING ........................................................................ 221
7.1 Maximum Cardinality Matching....................................................................................... 221
7.2 Minimum Sum Perfect Matching ...................................................................................... 225
8. NETWORK FLOW ........................................................................... 243
8.1 Maximum Network Flow.................................................................................................... 243
8.2 Minimum Cost Network Flow............................................................................................ 254
9. PACKING AND COVERING ............................................................ 273
9.1 Assignment Problem ........................................................................................................... 273
9.2 Bottleneck Assignment Problem ........................................................................................ 280
9.3 Quadratic Assignment Problem.......................................................................................... 284
9.4 Multiple Knapsack Problem .............................................................................................. 304
9.5 Set Covering Problem ......................................................................................................... 323
9.6 Set Partitioning Problem .................................................................................................... 325
10. LINEAR PROGRAMMING ............................................................. 329
10.1 Revised Simplex Method .................................................................................................. 329
10.2 Dual Simplex Method ....................................................................................................... 334
11. INTEGER PROGRAMMING........................................................... 341
11.1 Zero-One Integer Programming...................................................................................... 341
11.2 All Integer Programming ................................................................................................ 347
11.3 Mixed Integer Programming........................................................................................... 351
12. QUADRATIC PROGRAMMING ..................................................... 371
APPENDIX A: REFERENCES ............................................................ 377
APPENDIX B: GRAPH-THEORETIC TERMS .................................... 383


Another Graph Theory Books
Another Java Books
Download