// Copyright (C) 1996 DIMACS Center, Rutgers, The State University of New Jersey // Author(s): 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 // /////////////////////////////////////////////////////////////////////////// // LINK: Generic Graph Tool and Class Library // // Function name: Edge // // Synopsis: // Constructors, destructors and methods to support all edges // abstract edge, undirected and directed hyperedges, // undirected and directed binary edges // // Description: // // Creation: 1993 March 31, Patricia K. Fasel, pkf@lanl.gov // // Routines used: // // Related files: // // Test suite: none // // User documentation: none // // Development History: // 93-03-31 pkf added DHyperEdge, DBinEdge // 93-04-05 pkf removed creation of Graphic from constructor // 93-04-28 smm put back creation of Graphics // 93-05-03 smm added savePrint for directed edges // 93-05-07 pkf added MHyperEdge as subclass of DHyperEdge // 93-05-24 pkf removed MHyperEdge, doesn't exist // 93-06-29 ejohnson broke hierarchy between undirected and directed // binary edges and changed constructors to // add vertices to all 3 vertex lists for // UBinEdge and to appropriate lists for DBinEdge // 93-08-13 pkf changed Graph and Edge hierarchies // 94-09-27 mjd added copy constructors // 95-09-05 jwb otherVertices() changed to return Sequence // instead of List (much more efficient) // // Testing History: // // Code Review: // // Bugs and Deficiencies: // ////////////////////////////////////////////////////////////////////////////// #include #include #include #include #include #include #include #include #include ////////////////////////////////////////////////////////////////////////////// // Edge::Edge(const Edge &E, Flag clone) : GraphObject(E,clone) { _vertices = E._vertices->newEmpty(); Bool topLevel = ! GraphObject::_graphBeingConstructed; if ( topLevel ) { //GraphObject::_graphBeingConstructed=GraphObject::_owner; Iterator get_vert(E.vertices()); Vertex *vertex; while (get_vert(vertex)) { _vertices->insert(vertex); } //GraphObject::_graphBeingConstructed=0; // end topLevel } //else we'll be adding our own 'new' vertices (in Graph::Graph) } // constructor and destructor for abstract super class of edges // Edge::Edge(Graph* owner, Collection* passed_vertices) : _vertices(passed_vertices), GraphObject(owner) { } Edge::~Edge() { delete _vertices; } // // return all vertices in this edge which are not the passed vertex // Sequence Edge::otherVertices(Vertex* passed_vertex) { Sequence return_vertices; Iterator get_neighbor(_vertices); Vertex* vertex; while (get_neighbor(vertex)) if (vertex != passed_vertex) return_vertices.insert(vertex); return return_vertices; } // // replace the first vertex pointer with the second, used in subgraphs // void Edge::replace(Vertex* old_v, Vertex* new_v) { if (!old_v || !new_v) error("Edge::replace()"); Sequence bak; Iterator get_vert(_vertices); Vertex *v; while (get_vert(v)) if (*old_v == *v) bak.append(new_v); else bak.append(v); _vertices->clear(); Iterator get_bak(&bak); while (get_bak(v)) _vertices->append(v); } /* Iterator get_vertex(_vertices); Vertex* vertex; while (get_vertex(vertex)) if (vertex == old_v) { _vertices->remove(vertex); return; } } */ Bool Edge::sameSet(const Edge& obj) const { Set e_verts = *_vertices; Set o_verts = *obj.vertices(); if (e_verts == o_verts) return TRUE; return FALSE; } Bool Edge::sameSequence(const Edge& obj) const { Iterator get_next1(_vertices); Iterator get_next2(obj._vertices); Vertex* item1; Vertex* item2; int i; while ( (i=get_next1(item1)) && get_next2(item2)) { if (*item1 != *item2) return(FALSE); } if (i || get_next2(item2)) return(FALSE); return TRUE; } Bool Edge::operator==(const Edge& obj) const { // NOTE: operator== uses a different strategy than the // other Edge comparison operators use. The reason is // twofold: First, we would like edges to appear in // lexicographic order according to their elements. // However, Given a particular edge, we want to be able // to find *exactly* that edge (not another occurrence of // that edge) so that we don't delete one edge when we meant // to delete another. Whereas the inequality comparisons can // look at individual elements (to achieve lexicographic // ordering), the equality comparison *must* ensure that the // two edges are the same object. // // NOTE: Peculiarities of the parser require that we *do* // have to check that all of the vertices of an edges are // the same *in addition to* the name check discussed above. // The reason is this: During the parse of an Edge (e.g. below) // {v1 v2} (name("custom_name")) // the parser first encounters {v1 v2} and *adds* it to the // graph under an auto-generated name. This adding process // also happens to include a removal and re-addition to // accomodate the storing of graphs with collapsed subgraphs. // The removal is a standard Container removal, and uses this // operator== method to compare edges. Here is the trouble: // The auto-generated name for {v1 v2} might already be used. // Consider an earlier edge in the parse: // {u1 u2} (name("e2")) // This edge also got added with an auto-generated name, say "e0." // However, once the name attribute is encountered, the edge // name became "e2." Suppose that our {v1 v2} happened to // receive the auto-generated name "e2." If we do not ensure // in this method that the edge vertices are the same, *{u1 u2}* // will be deleted, and *{v1 v2}* reinserted!! (see the und_edge // nonterminal in parser.y. if (strcmp(name(), obj.name()) != 0) return FALSE; Iterator get_next1(_vertices); Iterator get_next2(obj._vertices); Vertex* item1; Vertex* item2; int i; while ( (i=get_next1(item1)) && get_next2(item2)) { if (*item1 != *item2) return(FALSE); } if (i || get_next2(item2)) return(FALSE); return TRUE; } Bool Edge::operator!=(const Edge& obj) const { return !operator==(obj); } Bool Edge::operator<(const Edge& obj) const { Iterator get_next1(_vertices); Iterator get_next2(obj._vertices); Vertex* item1; Vertex* item2; while (get_next1(item1)) { if (get_next2(item2)) { if (*item1 < *item2) return(TRUE); if (*item1 > *item2) return(FALSE); } else return(FALSE); } if (get_next2(item2)) return(TRUE); if (strcmp(name(), obj.name())<0) return(TRUE); return(FALSE); } Bool Edge::operator>=(const Edge& obj) const { return !operator<(obj); } Bool Edge::operator>(const Edge& obj) const { Iterator get_next1(_vertices); Iterator get_next2(obj._vertices); Vertex* item1; Vertex* item2; while (get_next1(item1)) { if (get_next2(item2)) { if (*item1 > *item2) return(TRUE); if (*item1 < *item2) return(FALSE); } else return(TRUE); } return(FALSE); if (get_next2(item2)) return(FALSE); if (strcmp(name(), obj.name())>0) return(TRUE); return(FALSE); } Bool Edge::operator<=(const Edge& obj) const { return !operator>(obj); } // // output an edge to a stream // ostream& Edge::display(ostream& os) const { os << *vertices(); return os; } //ostream& //operator<<(ostream& os, Edge* passed_edge) //{ // DataType type = passed_edge->type(); // if (type == EDGEDIR) // os << "<"; // else // os << "("; // Iterator get_next(passed_edge->_vertices); // Vertex* vertex; // while (get_next(vertex)) // os << vertex->name() << " "; // if (type == EDGEDIR) // os << ">"; // else // os << ")"; // return os; //} // // save an edge to an ascii file // save to graph always closes every subgraph before continuing so edges // will point to internal supervertices which have been closed // void Edge::saveToFile(ofstream *fout, int indent) { resetAttribute((Graph*) _owner, "x_mark"); //cout << "*************Saving edge: " << *this << endl; char buf[BUFSIZE]; DataType type = this->type(); if (type == EDGEDIR) *fout << "< "; else *fout << "{ "; // process the vertices in the edge, which might be supervertices Iterator get_next(_vertices); Vertex* vertex; while (get_next(vertex)) { Graph* subgraph; int ok = getAttribute((GraphObject*) vertex, "x_subgraph", subgraph); if (ok == LINK_OK && subgraph != 0) { Vertex* real_vertex = subgraph->findVertexWithEdge(this); if (real_vertex) { *fout << vertex->name() << "[" << real_vertex->name() << "] "; setAttribute((GraphObject*) real_vertex, "x_mark", 1); } } else *fout << vertex->name() << " "; } if (type == EDGEDIR) *fout << ">"; else *fout << "}"; GraphObject::saveToFile(fout, indent); } DataType Edge::type() const { if (_vertices->type() == SETCOL) return EDGEUND; else return EDGEDIR; } //String //Edge::getStringRep() const //{ // return _string_rep; //} //String //Edge::setStringRep() const //{ // ostrstream oss; // // _vertices->display(oss); // if (_string_rep != 0) // delete _string_rep; // _string_rep = oss.str(); // return _string_rep; //}