Graph/ZeroKnowledge/sample.cxx File Reference

Driver to show size of complex graphs that are possible. More...

#include <cassert>
#include <iostream>
#include <math.h>
#include "Graph.h"

Functions

void output (Graph const &graph, const char *fileName, const char *header)
 Output graph to a file.
int main (int argc, char **argv)
 Generate the sample large graph.


Detailed Description

Driver to show size of complex graphs that are possible.

In Chapter 10 of the book, a problem is posed regarding zero knowledge proofs. The key to the approach is the ability to construct graphs for which two problems -- GraphIsomorphism and HamiltonianCycle -- are known to be NP-complete (i.e., Extremely hard). While we don't solve these two problems here, we show the construction of the Graph that would be used.

Author:
George Heineman
Date:
6/15/08

Function Documentation

int main ( int  argc,
char **  argv 
)

Generate the sample large graph.

void output ( Graph const &  graph,
const char *  fileName,
const char *  header 
)

Output graph to a file.

File contains:

Header V E v1,v2 v1,v5 ...

Algorithm Development Kit 1.0