Personal tools
You are here: Home Projects C++ Cfront releases Release 3.0.3 source libSC Graph_alg cycle.c
Document Actions

cycle.c

by Michael L Powell last modified 2007-01-26 03:24

Click here to get the file

Size 12.2 kB - File type text/plain

File contents

/*ident	"@(#)Graph_alg:cycle.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.
*
******************************************************************************/

//DETECT CYCLES 

/* 
roadmap through cycles

cycle -> intermediate_cycle -> cycle_v -> cycle_e ->cycle0_sub
                                  ^
cycle(v) -> intermediate_cycle_v  |
                                              ^
cycle(e) -> intermediate_cycle_e              |


cycle_list(e) -> intermediate_cycle_list_e -> cycle_sub
                         ^
                         |  <-  <-  <-  <-
                                          ^
cycle_list(v) -> internal_cycle_list_v -> | 

*/

#include "Graph_alg.h"

static Vertex* orig_source;
static Set_of_p<Vertex> stat_v_pset;

//NOTE: cycle0_sub and cycle_sub are similar except that
//cycle_sub builds a list

static tcwbool_ATTLC cycle0_sub(char, const Edge*, int, Vertex**, const Graph&, Vis_v_ticket); 
static tcwbool_ATTLC cycle_sub(char, const Edge*, List_of_p<Edge>&, const Graph&, Vis_v_ticket);
static tcwbool_ATTLC cycle_e(char, const Edge*, int, Vertex**, const Graph&, Vis_v_ticket);
static tcwbool_ATTLC cycle_v(char, const Vertex*, int, Vertex**, const Graph&, Vis_v_ticket);

static int cycle1_test(Edge* e) {  // tests if the current edge's destination
				   // is in the original source
	return(e->dst() == orig_source);
}

static int cycle2_test(Edge* e) {  // tests if current edge's destination
				   // is in the current set being inspected
	return(stat_v_pset.contains(e->dst()) != NULL);
}

static int cycle3_test(Edge* e, Vertex* last_v, Vertex* curr_v) {
	// this is like cycle1_test, except it's for undirected graphs
	if ((last_v != e->src()) && (last_v != e->dst())) {
		Vertex* next_v = (e->src() == curr_v) ? e->dst(): e->src();
		return (next_v == orig_source);  
	}
	else return 0; //this edge has already been traversed
}

static int cycle4_test(Edge* e, Vertex* last_v, Vertex* curr_v) {
	// this is like cycle2_test, except it's for undirected graphs
	if ((last_v != e->src()) && (last_v != e->dst())) {
		Vertex* next_v = (e->src() == curr_v) ? e->dst(): e->src();
		return (stat_v_pset.contains(next_v) != NULL);
	}
	else return 0; //this edge has already been traversed
}

/* cycle() pseudocode:
	if a marked vertex is encountered while in dfs, a 
	cycle exists; the marked vertex is returned
*/


Vertex*
intermediate_cycle_ATTLC(char gtype, const Graph& g) {
	tcwbool_ATTLC found_cycle = FALS;
	Vertex* v;

	Vis_v_ticket vt = Vertex::get_vis_v_ticket();
	Set_of_p<Vertex> spv = g.vertices();
	Set_of_piter<Vertex> vset_iter(spv);
	Vertex* next_v;
	while (next_v = vset_iter.next()) {
		if (!next_v->visited(vt)) {
			next_v->set_visited(vt);
			stat_v_pset.insert(next_v); 
			if (cycle_v(gtype, next_v, 2, &v, g, vt)) {
				found_cycle = TRU;
				break;
			}
			else
				stat_v_pset.remove_all(); //clear for next try
		}
	}
	stat_v_pset.remove_all(); //clear 
	reset_visited(vt, (Set_of_p<Vertex>&)g.vertices());
	Vertex::free_vis_v_ticket(vt);
	return(found_cycle ? v : 0);
}


/* cycle(v) pseudocode:
	if v is encountered twice while in a dfs chain, a cycle exists
*/

int
intermediate_cycle_v_ATTLC(char gtype, const Graph& g, const Vertex* v) {
	tcwbool_ATTLC found_cycle = FALS;
	Vertex* vp;

	if (v) {
		Vis_v_ticket vt = Vertex::get_vis_v_ticket();
		((Vertex*)v)->set_visited(vt);
		stat_v_pset.insert((Vertex*)v);
		found_cycle = cycle_v(gtype, v, 1, &vp, g, vt);
		reset_visited(vt, (Set_of_p<Vertex>&)g.vertices());
		Vertex::free_vis_v_ticket(vt);
		stat_v_pset.remove_all(); //clear
	}
	return(found_cycle);
}


tcwbool_ATTLC
cycle_v(char gtype, const Vertex* v, int test_type, Vertex** vp, const Graph& g, Vis_v_ticket vt) {
	tcwbool_ATTLC found_cycle = FALS;

	if (gtype == 'd') {  /*can't && these 2 expr's together, not implemented*/
		if (v->loop_edges_g(g).size()) { //a loop is a cycle
			*vp = (Vertex*)v;
			found_cycle = TRU;
		}
	}
	Set_of_p<Edge> epset;
	switch (gtype) { /*can't use ternary operator: not implemented for this*/
		case 'd': epset = v->out_edges_g(g);
			  break;
		case 'u': epset = v->edges_g(g);
			  break;
	}
	Set_of_piter<Edge> eset_iter(epset);
	Edge* next_e;  //first in a set is the same as any in a set
	while (next_e = eset_iter.next()) {
		if (cycle_e(gtype, next_e, test_type, vp, g, vt)) {
			found_cycle = TRU;
			break;
		}
	}
	return(found_cycle);
}

/* cycle(e) pseudocode:
	if e is encountered twice while in dfs, a cycle exists.
	This is the same as evaluating whether e's source is visited twice.
*/
int
intermediate_cycle_e_ATTLC(char gtype, const Graph& g, const Edge* e) {
	tcwbool_ATTLC found_cycle = FALS;
	Vertex* v;
	
	if (e) {
		Vis_v_ticket vt = Vertex::get_vis_v_ticket();
		(e->src())->set_visited(vt); //arbitrary for 'u' but consistent
					// with cycle_e
		stat_v_pset.insert(e->src());
		found_cycle = cycle_e(gtype, e, 1, &v, g, vt);
		reset_visited(vt, (Set_of_p<Vertex>&)g.vertices());
		Vertex::free_vis_v_ticket(vt);
		stat_v_pset.remove_all(); //clear
	}
	return(found_cycle);
}


tcwbool_ATTLC
cycle_e(char gtype, const Edge* e, int test_type, Vertex** vp, const Graph& g, Vis_v_ticket vt) {
	tcwbool_ATTLC found_cycle = FALS;
	if (e->src()->visited(vt))  
		orig_source = e->src(); //handles most cases: arbitrary choice 
			//for cycle_u(e) but consistent with it 
	else
		orig_source = e->dst(); //handles a case of cycle_u(v)

	found_cycle = cycle0_sub(gtype, e, test_type, vp, g, vt);
	return(found_cycle);
}

	

/* in this function, test_type == 1 means to look for a cycle that
   contains the node "orig_source", test_type == 2 means to look for
   any old cycle */
tcwbool_ATTLC
cycle0_sub(char gtype, const Edge* e, int test_type, Vertex** vp, const Graph& g, Vis_v_ticket vt) {
	Vertex* v;
	Vertex* last_v;
	Set_of_p<Edge> e_pset;
	int i = e->src()->visited(vt); //better to place these in block below,
	int j = e->dst()->visited(vt); //but get cc warning stmt not reached
	switch (gtype) {
		case 'd':
			v = e->dst();
			e_pset = v->out_edges_g(g);
			break;
		case 'u':
			if (i && j) /*temp ints nec: && not implemented*/
				return(FALS);  
				    //this edge is going back the way it came
			else {
				if (e->src()->visited(vt)) {
					v = e->dst();
					last_v = e->src();
					}
				else {
					v = e->src();
					last_v = e->dst();
					}
				e_pset = v->edges_g(g);
			}
			break;
	}
	Edge* next_e;
	tcwbool_ATTLC found_cycle = FALS;
	v->set_visited(vt);
	stat_v_pset.insert(v);

	Set_of_piter<Edge> e_iter(e_pset);
	if ((test_type == 1) && (gtype == 'd')) {
		while (next_e = e_iter.next()) {
			if (cycle1_test(next_e))
				found_cycle = TRU;
		}
	}
	else if ((test_type == 1) && (gtype == 'u') &&
		(stat_v_pset.size() >= 3)) {
			while (next_e = e_iter.next()) {
			    if (cycle3_test(next_e, last_v, v))
				found_cycle = TRU;
			}
	}
	else if ((test_type == 2) && (gtype == 'd')) {
		while (next_e = e_iter.next()) {
			if (cycle2_test(next_e)) {
				*vp = next_e->dst();
				found_cycle = TRU;
			}
		}
	}
	else if ((test_type == 2) && (gtype == 'u') &&
		(stat_v_pset.size() >= 3)) {
		while (next_e = e_iter.next()) {
			if (cycle4_test(next_e, last_v, v)) {
				*vp = (next_e->src() == v) ? next_e->dst() : next_e->src();
				found_cycle = TRU;
			}
		}
	}

	if (!found_cycle) {      	//keep looking			 
		Set_of_piter<Edge> eset_iter(e_pset);
		Vertex* next_v;
		while (next_e = eset_iter.next()) { 
			if (gtype == 'd')
				next_v = next_e->dst();
			else  //gtype == 'u'
				next_v = (next_e->src() == v) ? next_e->dst() : next_e->src(); 
			if (!next_v->visited(vt)) {
				if (cycle0_sub(gtype, next_e, test_type, vp, g, vt)) {
					found_cycle = TRU;
					break;
				}
			}
		}
	}
	if (!found_cycle) {
		stat_v_pset.remove(v);  //undo insert
	}
	return(found_cycle);
}	

/**************************** CYCLE LISTS ************************************/
/* cycle_list(v) pseudocode:
	if a marked vertex is encountered while in cycle(e), and it is v,
	a cycle exists that includes v; return the cycle.
*/
List_of_p<Edge>
internal_cycle_list_v_ATTLC(const Graph& g, const Vertex* v) {
	List_of_p<Edge> e_list;

	if (v) {
		Set_of_p<Edge> e0_pset = v->loop_edges_g(g);
		if (e0_pset.size() != 0) { 	//loops are cycles
			Set_of_piter<Edge> eset_iter(e0_pset);
			e_list.put(eset_iter.next());
		//	e_list.reset(0);
		}
		else {
			Set_of_p<Edge> spe = v->out_edges_g(g);
			Set_of_piter<Edge> eset2_iter(spe);
			Edge* next_e;  //first in a set is the same as any in a set
			while (next_e = eset2_iter.next()) {
				e_list = intermediate_cycle_list_e_ATTLC('d', g, next_e);
				if (e_list.length())
					break;
			}
		}
	}
	return(e_list);
}

List_of_p<Edge>
internal_u_cycle_list_v_ATTLC(const Graph& g, const Vertex* v) {
	List_of_p<Edge> e_list;

	if (v) {
		Set_of_p<Edge> spe = v->edges_g(g);
		Set_of_piter<Edge> eset_iter(spe);
		Edge* next_e;  //first in a set is the same as any in a set
		while (next_e = eset_iter.next()) {
			e_list = intermediate_cycle_list_e_ATTLC('u', g, next_e);
			if (e_list.length())
				break;
		}
	}
	return(e_list);
}

/* cycle_list(e) pseudocode:
	if the current edge's destination has a back edge to the source 
		then    -- put the back edge on the cycle list and stop
			   (terminating gracefully not forced)
		else 
			-- mark the destination so that don't revisit;
			-- find all edges out of this destination;
			-- try each edge in turn, temporarily putting an
                           edge on the cycle list, calling cycle, and
                           removing the edge later if necessary. 
*/

/* returns list of edges in cycle, including e if other edges in the list*/
List_of_p<Edge>
intermediate_cycle_list_e_ATTLC(char gtype, const Graph& g, const Edge* e) {
	List_of_p<Edge> e_list; 		/*e_list collects the cycle */

	if (e) {
		orig_source = e->src(); //doesn't matter which end we choose for 'u'
		Vis_v_ticket vt = Vertex::get_vis_v_ticket();
		orig_source->set_visited(vt);
		cycle_sub(gtype, e, e_list, g, vt);
		reset_visited(vt, (Set_of_p<Vertex>&)g.vertices());
		Vertex::free_vis_v_ticket(vt);
		if (e_list.length() != 0) {
			// e_list.reset(0);  /*position ptr to head of list for insert */
			// e_list.insert_next(e); //insert start e
			e_list.unget(e);
		}
		// e_list.reset(0);
	}
	return(e_list);
}


tcwbool_ATTLC
cycle_sub(char gtype, const Edge* e, List_of_p<Edge>& e_list, const Graph& g, Vis_v_ticket vt) {
	Vertex* v;
	Vertex* last_v;
	Set_of_p<Edge> e_pset;
	int i = e->src()->visited(vt); //better to place these in block below,
	int j = e->dst()->visited(vt); //but get cc warning stmt not reached
	switch (gtype) {
		case 'd':
			v = e->dst();
			e_pset = v->out_edges_g(g);
			break;
		case 'u':
			if (i && j) /*use of temp ints nec: && not implemented*/
				return(FALS);
				    //this edge is going back the way it came
			else {
				if (e->src()->visited(vt)) {
					v = e->dst();
					last_v = e->src();
				}
				else {
					v = e->src();
					last_v = e->dst();
				}
				e_pset = v->edges_g(g);
			}
			break;
	}
	Edge* next_e;
	tcwbool_ATTLC found_cycle = FALS;
	v->set_visited(vt);

	Set_of_piter<Edge> e_iter(e_pset);
	if ((gtype == 'd')) {
		while (next_e = e_iter.next()) {
			if (cycle1_test(next_e)) {
				e_list.put(next_e);
				found_cycle = TRU;	// cycle was found
			}
		}
	}
	else if ((gtype == 'u') && e_list.length()) {
				//3rd next to see, 1st put on at end
		while (next_e = e_iter.next()) {
			if (cycle3_test(next_e, last_v, v)) {
				e_list.put(next_e);
				found_cycle = TRU;	// cycle was found
			}
		}
	}

	if (!found_cycle) {			//this vertex doesn't have an 
						//edge back to e, keep looking
		Set_of_piter<Edge> eset_iter(e_pset);
		Vertex* next_v;
		while (next_e = eset_iter.next()) { 
			if (gtype == 'd')
				next_v = next_e->dst();
			else  //gtype == 'u'
				next_v = (next_e->src() == v) ? next_e->dst() : next_e->src(); 
			if (!next_v->visited(vt)) {
				e_list.put(next_e);  //temporary put perhaps
				if (cycle_sub(gtype, next_e, e_list, g, vt)) {
					found_cycle = TRU;
					break;
				}
				else
					e_list.unput(next_e);  //edge panned out
			}
		}
	}
	return(found_cycle);
}	

« December 2014 »
Su Mo Tu We Th Fr Sa
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
 

Powered by Plone CMS, the Open Source Content Management System

This site conforms to the following standards: