GA_cycdemo.c
Click here to get the file
Size
1.7 kB
-
File type
text/plain
File contents
/*ident "@(#)Graph_alg:demos/GA_cycdemo.c 3.1" */
/******************************************************************************
*
* C++ Standard Components, Release 3.0.
*
* Copyright (c) 1991, 1992 AT&T and Unix System Laboratories, Inc.
* Copyright (c) 1988, 1989, 1990 AT&T. All Rights Reserved.
*
* THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF AT&T and Unix System
* Laboratories, Inc. The copyright notice above does not evidence
* any actual or intended publication of such source code.
*
******************************************************************************/
/*
This demonstration program determines whether a given Graph is a tree.
*/
#include "GA_demo.h"
#include <stream.h>
// Graphimplement(MyGraph,MyVertex,MyEdge)
Graph_algimplement(MyGraph,MyVertex,MyEdge)
main() {
MyGraph g;
MyVertex gv[15];
/* insertion of Vertices will occur when an Edge pulls it in */
for (int i = 0; i < 7; i++) {
g.insert(new MyEdge(&gv[i], &gv[(2*i)+1]));
g.insert(new MyEdge(&gv[i], &gv[(2*i)+2]));
}
g.insert(new MyEdge(&gv[3], &gv[4]));
for (i = 0; i < 15; i++)
gv[i].id = i;
MyVertex* v = cycle_u(g);
if (v) { //a cycle was found
cout << "a cycle was found: this is not a tree\n" << flush;
List_of_p<MyEdge> elist = cycle_list_u(g, v);
List_of_piter<MyEdge> elisti(elist);
//let's see where the cycle is
Set_of_p<MyVertex> vset;
MyEdge* e;
while (elisti.next(e)) {
vset.insert(e->src());
vset.insert(e->dst());
}
// ... and compare it to where we think it is,
// the solution set
Set_of_p<MyVertex> v2set;
v2set.insert(&gv[1]);
v2set.insert(&gv[3]);
v2set.insert(&gv[4]);
if (vset == v2set)
cout << "cyc: The two Vertex sets are equal\n" << flush;
}
return(0);
}