Miscellany

###################
# HW6 - test run  # 
###################

NOTES: 
1) input graph is from the matching packet, plus two singletons and another small graph
2) multiple max matchings may exist

cmerck@G450 /cygdrive/d/code/cs182/HW6-MaxMatch
$ cat infile.dat
18 19
0 6
0 7
0 9
1 7
1 11
2 7
2 8
3 8
3 10
3 11
4 8
4 9
4 10
4 11
5 7
5 10
14 15
14 17
16 15

cmerck@G450 /cygdrive/d/code/cs182/HW6-MaxMatch
$ ./MaxMatch.exe
*** HW6 MaxMatch - Chris Merck ***

* opening i/o files
* parsing infile.dat
* rendering adjacency list
* generating flow network
* graph is bipartite - running matching algorithm:
 19 <- 7 <- 1 <- 0
 19 <- 8 <- 2 <- 0
 19 <- 9 <- 3 <- 0
 19 <- 11 <- 4 <- 0
 19 <- 10 <- 5 <- 0
 19 <- 16 <- 15 <- 0
 19 <- 12 <- 2 <- 8 <- 6 <- 0
 19 <- 18 <- 15 <- 16 <- 17 <- 0
DONE!

cmerck@G450 /cygdrive/d/code/cs182/HW6-MaxMatch
$ cat outfile.dat
***MAXIMUM MATCHING ANALYSIS OF INPUT GRAPH***

Adjacency list is as follows:
0       |  -> 6 -> 7 -> 9
1       |  -> 7 -> 11
2       |  -> 7 -> 8
3       |  -> 8 -> 10 -> 11
4       |  -> 8 -> 9 -> 10 -> 11
5       |  -> 7 -> 10
6       |  -> 0
7       |  -> 0 -> 1 -> 2 -> 5
8       |  -> 2 -> 3 -> 4
9       |  -> 0 -> 4
10      |  -> 3 -> 4 -> 5
11      |  -> 1 -> 3 -> 4
12      |
13      |
14      |  -> 15 -> 17
15      |  -> 14 -> 16
16      |  -> 15
17      |  -> 14

* The input graph is bipartite.

connected component 1 has the following:
 nodes: (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)

connected component 2 has the following:
 nodes: (12)

connected component 3 has the following:
 nodes: (13)

connected component 4 has the following:
 nodes: (14, 15, 16, 17)

Maximum matching:
 (0, 6)
 (5, 7)
 (2, 8)
 (4, 9)
 (3, 10)
 (1, 11)
 (16, 15)
 (14, 17)