// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey
// Author(s): Patricia K. Fasel (Los Alamos Nat. Lab.), Jonathan Berry

// This software is copyrighted by the DIMACS Center at Rutgers, The State
// University of New Jersey.  IT IS PROVIDED AS IS, AND THE AUTHORS, DIMACS, AND
// RUTGERS, THE STATE UNIVERSITY OF NEW JERSEY  DISCLAIM
// ALL LIABILITY FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL
// DAMAGES ARISING OUT OF THE USE OF THIS SOFTWARE, ITS DOCUMENTATION, OR ANY
// DERIVATIVES THEREOF, EVEN IF THE AUTHORS HAVE BEEN ADVISED OF THE
// POSSIBILITY OF SUCH DAMAGE.

// THE AUTHORS AND DISTRIBUTORS SPECIFICALLY DISCLAIM ANY WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE, AND NON-INFRINGEMENT.  THIS SOFTWARE
// IS PROVIDED ON AN "AS IS" BASIS, AND THE AUTHORS AND DISTRIBUTORS HAVE
// NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR
// MODIFICATIONS.

// The authors hereby grant permission to use, copy, modify, distribute,
// and license this software and its documentation for any purpose, provided
// that existing copyright notices are retained in all copies and that this
// notice is included verbatim in any distributions. No written agreement,
// license, or royalty fee is required for any of the authorized uses.
// Modifications to this software may be copyrighted by their authors
// and need not follow the licensing terms described here, provided that
// the new terms are clearly indicated on the first page of each file where
// they apply.

// Last File Update: 31-Jul-1996
// 

#include <string.h>
#include <stdio.h>
#include <iostream.h>
#include <strstream.h>
#include <LINK/basic/ElementOps.h>
#include <LINK/graph/Graph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>
#include <LINK/basic/List.h>

#define EXTDEFS			// must define this to prevent multiple 
#include <LINK/graph/nauty.h>	// definitions of some nauty arrays

int	Graph::graph_count = 0;

//
// constructor for an abstract graph
//
Graph::Graph() :
		_cur_vertex_name(0),
		_cur_edge_name(0),
		_cur_subgraph_name(0),
		GraphObject(this)
{
    String new_name = new char[NAMESIZE];
    sprintf(new_name, "Graph%d", graph_count++);
    newAttribute(this, "graph_name", new_name);
    //newAttribute(this, "graph_name", new_name, LINK_DYNAMIC);

    // attributes of graph objects in this graph
    Graph* thisg = this;

    // this is first just to avoid innocuous error on resetAttribute()
    List<Vertex*>* vlist = new List<Vertex*>;
    new Attribute<List<Vertex*>*> (thisg, "x_supervertices", vlist);

    new Attribute<String>(thisg, "name", (char*)"");
    new Attribute<int>(thisg, "direction", (int) Edge::UNDIRECTED);
    new Attribute<int>(thisg, "width", DEFAULT_WIDTH);
    new Attribute<int>(thisg, "size",  DEFAULT_SIZE);
    new Attribute<double>(thisg, "weight", DEFAULT_WEIGHT);
    new Attribute<double>(thisg, "x", DEFAULT_X);
    new Attribute<double>(thisg, "y", DEFAULT_Y);
    new Attribute<String>(thisg, "color", DEFAULT_COLOR);
    new Attribute<String>(thisg, "label", DEFAULT_LABEL);
    new Attribute<int>(thisg, "mark", DEFAULT_MARK);
    new Attribute<int>(thisg, "type", 0);
    new Attribute<int>(thisg, "starttime", DEFAULT_STARTTIME);
    new Attribute<int>(thisg, "finishtime", DEFAULT_FINISHTIME);
    new Attribute<int>(thisg, "back", DEFAULT_BACK);
    new Attribute<int>(thisg, "low", DEFAULT_LOW);
    new Attribute<double>(thisg, "distance", DEFAULT_DISTANCE);
    new Attribute<Vertex*>(thisg, "pred", (Vertex*)0);


    // support for subgraph implementation
    // x_subgraph is used by supervertex to point to its subgraph
    // x_supervertex is used by subgraph to point to its supervertex
    // x_parent is used by supervertex and subgraph to point to graph above
    // x_supervertices is used by main graph to keep track of all subgraphs
    // x_open is used by each subgraph internally to keep state
    // open is used during save and load to indicate how subgraph should be done

    new Attribute<Graph*>(thisg, "x_subgraph", (Graph*) 0);
    new Attribute<Graph*>(thisg, "x_parent", thisg);
    new Attribute<Vertex*>(thisg, "x_supervertex", (Vertex*) 0);
    new Attribute<int>(thisg, "x_open", 1);
    new Attribute<int>(thisg, "open", 1);

}

Graph::Graph(const Graph &G, Flag clone, Flag reverse) 
      : _cur_vertex_name(0),
        _cur_edge_name(0),
        _cur_subgraph_name(0),
        GraphObject(G, clone)
{
    assert( ! GraphObject::_graphBeingConstructed );
    GraphObject::_graphBeingConstructed = this;
    GraphObject::_owner = this;		// And override what was set above

    //
    // Although the GraphObject constructor has already added the source
    // graph's attributes at this point, the job is not finished.  When 
    // Attribute objects are constructed without a Graph reference (as
    // they were just before this routine by the GraphObject constructor),
    // the _graph is not set.  The code below does what Attribute(g,n,v)
    // does.  The reason we can't simply tell GraphObject::GraphObject
    // to pass a Graph reference to the Attribute constructor is that
    // GraphObject must construct Vertices and Edges also. -JWB
    //
    Iterator<AttributeBase*> get_attr(&_attributes);
    AttributeBase *g_attr;
    while (get_attr(g_attr)) {
	char *n = g_attr->name();
	if (strncmp(n, "x_", 2) != 0)
		resetAttribute(this, n);
	g_attr->_graph = this;
    }

    String new_name = new char[NAMESIZE];	 // change the graph's name
    sprintf(new_name, "Graph%d", graph_count++);
    if (clone) 
	//setAttribute((GraphObject*) this, "graph_name",new_name,LINK_DYNAMIC);
	setAttribute((GraphObject*) this, "graph_name", new_name);
    else 
	//newAttribute(this, "graph_name", new_name, LINK_DYNAMIC);
	newAttribute(this, "graph_name", new_name);

    List<Vertex*>* xsvs;
    getAttribute((GraphObject*)&G, "x_supervertices", xsvs);
    if (xsvs && !xsvs->emptyQ()) {
	warning("cannot copy graphs containing collapsed subgraphs");
	return;
    }

    void (Collection<Vertex*>::*pf)(Vertex*);
    if (reverse)
	pf = &Collection<Vertex*>::insert;
    else
	pf = &Collection<Vertex*>::append;

    int i, n = G.order();
    Vertex *v, *old_v;
    Vertex** Gverts = G.vertexStart();
    for (i=0; i<n; i++) {
	v = new Vertex(*Gverts[i], CLONE);
	v->_owner = this;
	addVertex(v);
    }
	
    int vert_index;
    Iterator<Edge*> Gedges(&G._edges);
    Collection<Vertex*> *edge_verts;
    Edge *edge, *old_e;
    String e_name;
    while (Gedges(old_e)) {
	edge = new Edge(*old_e, clone);
	edge->_owner = this;
	edge_verts = old_e->vertices()->newEmpty();
    	Iterator<Vertex*> old_edge_verts(old_e->vertices());
	while (old_edge_verts(v)) {
		vert_index = G._vertices.search(v);
		(edge_verts->*pf)(_vertices[vert_index]);
	}
	edge->_vertices = edge_verts;
	/////////////Edge* edge = new Edge(this, edge_verts, clone);
	Vertex* vertex;
	Iterator<Vertex*> get_evertex(edge_verts);
	while (get_evertex(vertex))
		vertex->addEdge(edge);
	_edges.insert(edge);

	e_name = makeEdgeName();
	//setAttribute((GraphObject*) edge, "name", 
	//	strcpy(new char[strlen(e_name)+1], e_name));
    }

    GraphObject::_graphBeingConstructed = 0;		// stop the stack

}

MSet<Edge*>
Graph::inducedEdges(Set<Vertex*> sub_verts) const 
{
    Vertex *v;
    Iterator<Vertex*> get_vertex(&sub_verts);
    while (get_vertex(v)) {				// can be improved
	MSet<Edge*> incident_edges = v->incidentEdges();
	Iterator<Edge*> get_incident_edge(&incident_edges);
	Edge *e;
	while (get_incident_edge(e))  {
	        double old_weight;
                getAttribute((GraphObject*) e, "weight", old_weight);
		setAttribute((GraphObject*)e, "mark", 0);
                getAttribute((GraphObject*) e, "weight", old_weight);
	}
    }
    MSet<Edge*> result;
    get_vertex.reset();
    while (get_vertex(v)) {				// can be improved
	MSet<Edge*> incident_edges = v->incidentEdges();
	Iterator<Edge*> get_incident_edge(&incident_edges);
	Edge *e;
	while (get_incident_edge(e)) {
		int mark;
	        double old_weight;
		getAttribute((GraphObject*)e, "mark", mark);	
		if (!mark) {
			MSet<Vertex*> intersection=sub_verts ^ *e->vertices();
			if (intersection.size() > 1) {
				result.insert(e);
				setAttribute((GraphObject*)e, "mark", 1);	
			}
		}
	}
    }
    return result;
}

Graph *
Graph::inducedSubgraph(Set<Vertex*> sub_verts, Flag clone=1) const
{
    // This should be the first time.
    //
    Graph *g = newEmpty(this);
    assert( ! GraphObject::_graphBeingConstructed );
    GraphObject::_graphBeingConstructed = g;
    GraphObject::_owner = g;		// And override what was set above

    Vertex *v, *old_v;
    Vertex** verts = vertexStart();
    Iterator<Vertex*> get_sub_vert(&sub_verts);
    while (get_sub_vert(old_v)) {
	v = new Vertex(*old_v, clone);
	v->_owner = g;
	g->addVertex(v);
    }
    int vert_index;
    MSet<Edge*> induced_edges = inducedEdges(sub_verts);
    Iterator<Edge*> edges(&induced_edges);
    Collection<Vertex*> *edge_verts;
    Edge *e, *old_e;
    String e_name;
    while (edges(old_e)) {
	e_name = old_e->name();
	e = new Edge(*old_e, clone);
	e->_owner = g;
	edge_verts = old_e->vertices()->newEmpty();
    	Iterator<Vertex*> old_edge_verts(old_e->vertices());
	while (old_edge_verts(v)) {
	    Vertex *gv;
	    if (v && v->name() && (gv = g->findVertexByName(v->name())))
		edge_verts->append(g->findVertexByName(v->name()));
	}
	e->_vertices = edge_verts;
	Iterator<Vertex*> get_evertex(edge_verts);
	while (get_evertex(v))
		v->addEdge(e);
	g->addEdge(e);
	//setAttribute((GraphObject*) e, "name", 
	//	strcpy(new char[strlen(e_name)+1], e_name), LINK_DYNAMIC);
	setAttribute((GraphObject*) e, "name", 
		strcpy(new char[strlen(e_name)+1], e_name));
    }
    String new_name = new char[NAMESIZE];	 // change the graph's name
    sprintf(new_name, "Graph%d", graph_count++);
    if (clone) 
	//setAttribute((GraphObject*) g, "graph_name", new_name, LINK_DYNAMIC);
	setAttribute((GraphObject*) g, "graph_name", new_name);
    else 
	//newAttribute(g, "graph_name", new_name, LINK_DYNAMIC);
	newAttribute(g, "graph_name", new_name);

    GraphObject::_graphBeingConstructed = 0;
    return g;
}

Graph *
Graph::edgeInducedSubgraph(Set<Edge*> sub_verts, Flag clone=1) const
{
    // This should be the first time.
    //
    Graph *g = newEmpty(this);
    warning("edgeInducedSubgraph(): not implemented yet");
    return g;
}

//
// destructor for an abstract graph
// at this point, the subgraphs have been opened by ~HyperGraph
// and the supervertices have already been removed
//
Graph::~Graph()
{
    // delete the attributes first, ~Attribute will call resetAttribute()
    // to remove all copies of attributes, which requires the vertices and
    // edges to still exist, also x_supervertices must be deleted last

    List<AttributeBase*> attributes = this->attributes();
    Iterator<AttributeBase*> get_attr(&attributes);
    AttributeBase* attribute;
    AttributeBase* x_super_attr;
    while (get_attr(attribute))
    	if (strcmp(attribute->name(), "x_supervertices") == 0)
    	    x_super_attr = attribute;
    	else {
    	    //cout << attribute->name() << endl;
    	    delete attribute;
    	}
    List<Vertex*>* super_vs;
    getAttribute((GraphObject*) this, "x_supervertices", super_vs);
    
    if (x_super_attr)
        delete x_super_attr;

    // Delete all vertices and edges
    for (int i=0; i < _vertices.size(); i++) {
	delete _vertices[i];
    }
    Edge *edge;
    Iterator<Edge*> get_edge(&_edges);
    while (get_edge(edge))
	delete edge;
    _vertices.clear();
    _edges.clear();
}

Bool Graph::isomorphicQ(const Graph *g) const
{
	if (!g)
		return FALSE;
	return isomorphicQ(*g);
}

Bool Graph::isomorphicQ(const Graph &g) const
{
	static Sequence<Vertex*> s;
	int this_order = order(), rflag;
	if ((this_order != g.order()) || (size() != g.size())) {
	   //cout << "violation: " << this_order << " " << g.order() << endl;
	   //cout << "violation: " << size() << " " << g.size() << endl;
		return FALSE;
	}
	int m = (this_order + WORDSIZE - 1) / WORDSIZE;
	graph *g1 = nautyGraph(this);
	graph *g2 = nautyGraph(&g);
	nvector labg1[MAXN], labg2[MAXN];
	graph *canong1 = canonicalNautyGraph(this, g1, labg1);
	graph *canong2 = canonicalNautyGraph(&g,   g2, labg2);
	int sr;
	if (testcanlab(g2, canong1, labg2, &sr, m, this_order)==0) 
		rflag = TRUE;
	else
		rflag = FALSE;
	delete g1;
	delete g2;
	delete canong1;
	delete canong2;
	return rflag;
}

Bool Graph::binaryQ() const
{
	switch (type()) {
		case MIXEDHYPERGRAPH:
		case UNDHYPERGRAPH:
		case DIRHYPERGRAPH:
		case M_MIXEDHYPERGRAPH:
		case M_UNDHYPERGRAPH:
		case M_DIRHYPERGRAPH:
			{ return FALSE; }
	}
	return TRUE;
}

AsymMatrix<int>
Graph::adjacencyMatrix() const
{
	return AdjacencyMatrix(this);
}

Bool Graph::simpleQ() const
{
	switch (type()) {
		case M_MIXEDHYPERGRAPH:
		case M_UNDHYPERGRAPH:
		case M_DIRHYPERGRAPH:
		case M_MIXEDBINARYGRAPH:
		case M_UNDBINARYGRAPH:
		case M_DIRBINARYGRAPH:
			{ return FALSE; }
	}
	return TRUE;
}

Bool Graph::directedQ() const
{
	switch (type()) {
		case M_DIRHYPERGRAPH:
		case M_DIRBINARYGRAPH:
		case DIRHYPERGRAPH:
		case DIRBINARYGRAPH:
			{ return TRUE; }
	}
	return FALSE;
}


void Graph::addVertices(int n)  // 0..n-1 (or j..n+j-1 if j vertices already
{
    int i;
    for(i = 0; i < n; i++){
        addVertex(makeVertexName());
    }
}

void Graph::addVertex(Vertex* passed_vertex)
{
    if (_vertices.search(passed_vertex) == -1) {
    	_vertices.insert(passed_vertex);
    }
    /*else
	warning("Vertex cannot be inserted - already in Graph");*/
}

void Graph::deleteEdge(Collection<Vertex*>&vs)
{
	Edge *e = isEdge(vs);
	deleteEdge(e);
}

MSet<Edge*> 
Graph::addEdges(MSet<Set<Vertex*> > es)
{
	Iterator<Set<Vertex*> > get_edge(&es);
	Set<Vertex*> edge;
	while (get_edge(edge))
		addEdge(edge);
	return _edges;
}

MSet<Edge*> 
Graph::addEdges(MSet<Sequence<Vertex*> > es)
{
	Iterator<Sequence<Vertex*> > get_edge(&es);
	Sequence<Vertex*> edge;
	while (get_edge(edge))
		addEdge(edge);
	return _edges;
}

void
Graph::deleteEdges(MSet<Set<Vertex*> > es)
{
	Iterator<Set<Vertex*> > get_edge(&es);
	Set<Vertex*> edge;
	while (get_edge(edge))
		deleteEdge(edge);
}

void
Graph::deleteEdges(MSet<Sequence<Vertex*> > es)
{
	Iterator<Sequence<Vertex*> > get_edge(&es);
	Sequence<Vertex*> edge;
	while (get_edge(edge))
		deleteEdge(edge);
}

//
// create and add a vertex of the passed name to the graph
//
Vertex*
Graph::addVertex(String name)
{
    Vertex* vertex = new Vertex(this);
    String new_name = strcpy(new char[strlen(name)+1], name);
    //setAttribute((GraphObject*) vertex, "name", new_name, LINK_DYNAMIC);
    setAttribute((GraphObject*) vertex, "name", new_name);
    if (_vertices.search(vertex) == -1)
    	_vertices.insert(vertex);
    /*else 
	warning("Vertex cannot be inserted - already in Graph");*/
    return vertex;
}


//
// remove a vertex or edge from the stored array, don't delete or alter
//
void
Graph::removeVertex(Vertex* passed_vertex)
{
    _vertices.remove(passed_vertex);
}


void
Graph::removeEdge(Edge* passed_edge)
{
    _edges.remove(passed_edge);
}


// 
// locate a vertex of this graph by name, id or location
// must search recursively through the subgraphs of the supervertices
// 
Vertex* 
Graph::findVertexByName(String name)
{
    // search actual vertices of the graph
    int low=0, high=_vertices.size()-1, mid, comp;
    while (low <= high) {
	mid = low + (int) (high-low)/2;
	if ((comp=compareVertexNames(_vertices[mid]->name(), name))==0)
		return _vertices[mid];
	else if (comp < 0)
		low = mid+1;
	else
		high = mid-1;
	Graph* subgraph;
	getAttribute((GraphObject*) _vertices[mid], "x_subgraph", subgraph);
	if (subgraph) {
	    Vertex* return_vertex = subgraph->findVertexByName(name);
	    if (return_vertex)
	        return return_vertex;
	}
    }
    return 0; 
}

Edge* 
Graph::findEdgeByName(String name)
{
    Iterator<Edge*> get_edge(&_edges);
    Edge *e;
    while (get_edge(e)) {
	if (strcmp(e->name(), name)==0)
		return e;
    }
}

//
// locate the vertex which has the given edge as an incident edge
// this is used in the saving of subgraphs to match up edges with superverts
//
Vertex*
Graph::findVertexWithEdge(Edge* passed_edge)
{
    cout << "fvwe: testing edge: " << *passed_edge << endl;
    cout << "in graph: " << *this << endl;
    for (int i = 0; i < _vertices.size(); i++) {
	int mark;
	getAttribute((GraphObject*) _vertices[i], "x_mark", mark);
	cout << "fvwe: testing: " << *_vertices[i] << endl;
	if (mark == 0) {
	    cout << "mark is 0" << endl;
	    Vertex* return_vertex;
	    Graph* subgraph;
	    getAttribute((GraphObject*) _vertices[i], "x_subgraph", subgraph);
	    if (subgraph) {
	    	cout << "it is a supervertex" << endl;
	        return_vertex = subgraph->findVertexWithEdge(passed_edge);
	        if (return_vertex != 0) {
	    	    cout << "found it's v: " << *return_vertex << endl;
	            return return_vertex;
		}
	    } else {
	    	cout << "it is NOT a supervertex" << endl;
	        Set<Edge*> inc_edges = _vertices[i]->incidentEdges();
	        Iterator<Edge*> get_edge(&inc_edges);
	        Edge* edge;
	        while (get_edge(edge)) {
		    cout << "incident edge: " << *edge << endl;
	            if (ElementOps<Edge*>::compareItems(edge, passed_edge)==0) {
		    	cout<<"it matches with this: " << *passed_edge<< endl;
		        return _vertices[i];
		    }
		}
	    }
	}
    }
    return 0;
}

//ostream& operator<<(ostream&, const Container<Vertex*>&);
//ostream& operator<<(ostream&, const Collection<Edge*>&);

ostream&
Graph::display(ostream& os)  const
{
        os << "{" << _vertices << "  ";
        os << _edges << "}";
	//os << _edges << "}" ;
	return os;
}

const SortedArray<Vertex*>&
Graph::vertices() const
{
	return _vertices;
}

// debugging only:
ostream&
Graph::displayAllGraphObjects(ostream& os)  const
{
	Vertex *v;
	Edge *e;
	Iterator<Vertex*> get_vert(&_vertices);
	Iterator<Edge*> get_edge(&_edges);
	os << "graph:" << endl;
	os << this << endl;
	os << "vertices:" << endl;
	while (get_vert(v))
		os << v << ": " << *v << endl;
	os << "edges:" << endl;
	while (get_edge(e))
		os << e << ": " << *e << endl;
		
	return os;
}

int Graph::operator==(const Graph& g) const
{
	if  ((_vertices == g._vertices) && (_edges == g._edges))
		return TRUE;
	return FALSE;
}


int Graph::operator<(const Graph& g) const
{
	if  ((_vertices < g._vertices) && (_edges < g._edges))
		return TRUE;
	return FALSE;
}

void
Graph::display(int indent) 
{
    char buf[BUFSIZE];

    sprintf(buf, "%*c", indent, ' ');
    cout << buf << "Graph: " << name() << endl;
    for (int i=0; i < _vertices.size(); i++) {
	Graph* subgraph;
	getAttribute((GraphObject*) _vertices[i], "x_subgraph", subgraph);
	cout << buf << "Vertex: " << _vertices[i] << endl;
	if (subgraph)
	    subgraph->display(indent+4);
    }
    Edge *edge;
    Iterator<Edge*> get_edge(&_edges);
    while (get_edge(edge)) {
        cout << buf <<  "Edge: ";
	ElementOps<Edge*>::displayItem(cout, edge);
	cout << endl;
    }

    // print all existing subgraphs belonging to this graph
    if (indent == 0) {
	List<Vertex*>* super_vs;
	getAttribute((GraphObject*) this, "x_supervertices", super_vs);
	Vertex* super_vertex;
	Iterator<Vertex*> get_super_v(super_vs);
	while (get_super_v(super_vertex)) {
	    Graph* subgraph;
	    int open;
	    Graph* parent;
 	    Vertex* superv;

	    getAttribute((GraphObject*) super_vertex, "x_subgraph", subgraph);
	    getAttribute((GraphObject*) super_vertex, "x_parent", parent);
	    getAttribute((GraphObject*) subgraph, "x_open", open);
	    getAttribute((GraphObject*) subgraph, "x_supervertex", superv);

	    cout << "Supervertex " << superv->name();
	    if (open)
		cout << " ,Subgraph is OPEN, ";
	    else
		cout << " ,Subgraph is CLOSED, ";
	    cout << "Parent is " << parent->name() << endl;

	    subgraph->display(cout);
	}
    }
}

Edge*
Graph::isEdge(const Collection<Vertex*>& vset) const
{
	if (vset.emptyQ())
		return 0;
	Set<Vertex*> sorted_verts;
	Collection<Vertex*> *cp;
	if (!directedQ()) {
		sorted_verts = vset;
		cp = &sorted_verts;
	} else
		cp = &vset;
		
	Vertex* v1 = cp->first();
        MSet<Edge*> v1_edges = v1->incidentEdges();
        Iterator<Edge*> get_edge(&v1_edges);
        Edge *e;
        while (get_edge(e)) {
		Collection<Vertex*>* everts = e->vertices();
		if (*everts == *cp)
                        return e;
	}
        return 0;
}

Edge*
Graph::isEdge(Vertex* v1, Vertex* v2) const
{
	if (!v1 || !v2)
		return 0;
	Set<Vertex*> s;
	s.insert(v1);
	s.insert(v2);
	return isEdge(s);
}


Bool
Graph::memberQ(Vertex* v) const
{
    for (int i=0; i<_vertices.size(); i++)
	if (ElementOps<Vertex*>::compareItems(_vertices[i],v)==0)
	    return TRUE;
    return FALSE;
}


Bool
Graph::memberQ(Edge* e) const
{
    Edge *edge;
    Iterator<Edge*> get_edge(&_edges);
    while (get_edge(edge))
	if (ElementOps<Edge*>::compareItems(edge, e)==0)
	    return TRUE;
    return FALSE;
}


//
// get the name from the attribute list
//
String
Graph::name() const
{
    Attribute<String>* attr = (Attribute<String>*) getAttr("graph_name");
    String name;
    if (attr)
        name = attr->value();
    else
        name = "";
    return name;
}


//
// is this graph or subgraph open
// need to recurse up the parent attribute, examining the open attribute
//
Bool
Graph::open()
{
    Graph* parent;
    int is_open;
    getAttribute((GraphObject*) this, "x_parent", parent);
    getAttribute((GraphObject*) this, "x_open", is_open);
    if (!is_open || parent == this)
	return is_open;
    else
	return parent->open();
}


//
// generate a new vertex name in the series
//
String
Graph::makeVertexName()
{
    static char name[NAMESIZE];
    sprintf(name, "%d", _cur_vertex_name++);
    return name;
}


String
Graph::makeEdgeName()
{
    static char name[NAMESIZE];
    sprintf(name, "e%d", _cur_edge_name++);
    return name;
}


String
Graph::makeSubgraphName()
{
    static char name[NAMESIZE];
    sprintf(name, "S%d", _cur_subgraph_name++);
    return name;
}

Vertex*
Graph::addSubgraph(const List<Vertex*>& vertices)
{
	return addSubgraph(this, vertices);
}

Vertex*
Graph::addSubgraph(const Set<Vertex*>& vertices)
{
	List<Vertex*> vlist;
	Iterator<Vertex*> get_vert(&vertices);
	Vertex *v;
	while (get_vert(v))
		vlist.append(v);
	return addSubgraph(this, vlist);
}

void Graph::collapseComponents(Set<Set<Vertex*> > vs)
{
	Iterator<Set<Vertex*> > next_piece(&vs);
	Set<Vertex*> piece;
	while (next_piece(piece))
		addSubgraph(piece);
	//cout << *this << endl;
}

void Graph::expandComponents()
{
	Vertex **vertices = vertexStart();
	int i, ord = order();
	for (i=0; i<ord; i++)
		dissolveSubgraph(vertices[i]);
}