// 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 <strstream.h>
#include <stdlib.h>
#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <LINK/basic/SetFuncs.h>
#include <LINK/graph/HyperGraph.h>
#include <LINK/graph/Vertex.h>
#include <LINK/graph/Edge.h>
#include <LINK/graph/Attribute.h>


//
// destructor for a hypergraph opens all subgraphs of the graph first
// then all vertices and edges are at upper level for delete
//
MHyperGraph::~MHyperGraph()
{
    List<Vertex*>* supervertices;
    int ok = 
	getAttribute((GraphObject*) this, "x_supervertices", supervertices);
    if (ok != LINK_OK) return;
   
    Iterator<Vertex*> get_superv(supervertices);
    Vertex* superv;
    while (get_superv(superv))
        openSubgraph(superv);
    get_superv.reset();
    while (get_superv(superv))
	delete superv;
    supervertices->clear();
}


//
// delete a vertex from a graph destructively (vertex is deleted)
//
void
MHyperGraph::deleteVertex(Vertex* passed_vertex)
{
    Set<Edge*> edges_to_delete;

    if (!passed_vertex)
	return;

    // remove from vertex set of every incident edge
    MSet<Edge*> inc_edges = passed_vertex->incidentEdges();
    Iterator<Edge*> get_edge(&inc_edges);
    Edge* edge;
    while (get_edge(edge)) {
        Iterator<Vertex*> get_vertex(edge->vertices());
        Vertex* vertex;
	while (get_vertex(vertex)) {
	    Collection<Vertex*>* vertices = edge->vertices();
	    vertices->remove(passed_vertex);
	    if (vertices->size() == 0)
		edges_to_delete.insert(edge);
	}
    }

    // delete all edges which are now empty
    Iterator<Edge*> get_delete_edge(&edges_to_delete);
    while (get_delete_edge(edge))
	deleteEdge(edge);

    // remove from graph vertex set and delete
    _vertices.remove(passed_vertex);
    delete passed_vertex;
}

void
MHyperGraph::deleteVertex(String v)
{
	Vertex *vert = findVertexByName(v);
	deleteVertex(vert);
}


//
// add an edge to a graph, the edge already contains its sources and sinks
// set up all adjacencies
//
Edge*
MHyperGraph::addEdge(Edge* passed_edge)
{
    //if (passed_edge->owner() != this) {
    //    error("MHyperGraph::addEdge(Edge*): illegal edge");
    //    return 0;
    //}
    if (!passed_edge) return 0;

    _edges.append(passed_edge);
    return passed_edge;
}


ostream& operator<<(ostream&, const Collection<Vertex*>&);
//
// construct a new undirected edge from the set of vertices
// add to the graph
//
Edge*
MHyperGraph::addEdge(Collection<Vertex*>& passed_vertices, String e_name)
{
    Set<Vertex*>* edge_vertices = new Set<Vertex*>;
    Iterator<Vertex*> get_vertex(&passed_vertices);
    Vertex* vertex;
    while (get_vertex(vertex))			//only insert vertices
	if (vertex && (vertex->owner() == this))//belonging to this graph
		edge_vertices->insert(vertex);
	else {
		ostrstream sos;
		sos << "edge " << passed_vertices 
	    	<< "contains vertices not in V(G). Edge not inserted" ;
		char *s = sos.str();
		warning(s);
		delete s;
		delete edge_vertices;
		return (Edge*) 0;
	}

    Edge* edge = new Edge(this, edge_vertices);

    // iterate on all vertices in hyperedge
    Iterator<Vertex*> get_evertex(edge->vertices());
    while (get_evertex(vertex))
        vertex->addEdge(edge);

    _edges.append(edge);

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

    return edge;
}


//
// construct a new directed edge from sequence of vertices
// add to the graph
//
Edge*
MHyperGraph::addEdge(Sequence<Vertex*> passed_vertices, String e_name)
{
    Sequence<Vertex*>* edge_vertices = new Sequence<Vertex*>;
    Iterator<Vertex*> get_vertex(&passed_vertices);
    Vertex* vertex;
    while (get_vertex(vertex))			//only insert vertices
	if (vertex && (vertex->owner() == this))//belonging to this graph
		edge_vertices->append(vertex);
	else {
		ostrstream sos;
		sos << "edge " << passed_vertices 
	    	<< "contains vertices not in V(G). Edge not inserted" ;
		char *s = sos.str();
		warning(s);
		delete s;
		delete edge_vertices;
		return (Edge*) 0;
	}

    Edge* edge = new Edge(this, edge_vertices);

    // iterate on all vertices in hyperedge
    Iterator<Vertex*> get_evertex(edge->vertices());
    while (get_evertex(vertex))
        vertex->addEdge(edge);

    _edges.append(edge);

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

    return edge;
}


//
// delete an edge destructively from a graph (edge is deleted)
//
void
MHyperGraph::deleteEdge(Edge* passed_edge)
{
    if (!passed_edge) 
	return;
    Iterator<Vertex*> get_vertex(passed_edge->vertices());
    Vertex* vertex;
    while (get_vertex(vertex))
        vertex->removeEdge(passed_edge);
    _edges.remove(passed_edge);
    delete passed_edge;
}


//
// subgraph add of a vertex adds recursively up through the graph
//
void
MHyperGraph::subgraphAddVertex(Vertex* passed_vertex)
{
    if (!passed_vertex) return;

    Graph* parent;
    Graph* grandparent;
    int parent_open;

    addVertex(passed_vertex);
    parent = this;
    getAttribute((GraphObject*) parent, "x_parent", grandparent);
    getAttribute((GraphObject*) parent, "x_open", parent_open);

    while (grandparent != parent && parent_open) {
        grandparent->addVertex(passed_vertex);
        parent = grandparent;
        getAttribute((GraphObject*) parent, "x_parent", grandparent);
        getAttribute((GraphObject*) parent, "x_open", parent_open);
    }
}


//
// subgraph remove of a vertex removes recursively up through the graph
//
void
MHyperGraph::subgraphRemoveVertex(Vertex* passed_vertex)
{
    if (!passed_vertex) return;
    Graph* parent;
    Graph* grandparent;
    int parent_open;

    removeVertex(passed_vertex);
    parent = this;
    getAttribute((GraphObject*) parent, "x_parent", grandparent);
    getAttribute((GraphObject*) parent, "x_open", parent_open);

    while (grandparent != parent && parent_open) {
        grandparent->removeVertex(passed_vertex);
        parent = grandparent;
        getAttribute((GraphObject*) parent, "x_parent", grandparent);
        getAttribute((GraphObject*) parent, "x_open", parent_open);
    }
}


//
// subgraph add of an edge adds recursively up through the graph
//
void
MHyperGraph::subgraphAddEdge(Edge* passed_edge)
{
    if (!passed_edge) return;
    Graph* parent;
    Graph* grandparent;
    int parent_open;

    addEdge(passed_edge);
    parent = this;
    getAttribute((GraphObject*) parent, "x_parent", grandparent);
    getAttribute((GraphObject*) parent, "x_open", parent_open);

    while (grandparent != parent && parent_open) {
        grandparent->addEdge(passed_edge);
        parent = grandparent;
        getAttribute((GraphObject*) parent, "x_parent", grandparent);
        getAttribute((GraphObject*) parent, "x_open", parent_open);
    }
}


//
// subgraph remove of an edge removes recursively up through the graph
//
void
MHyperGraph::subgraphRemoveEdge(Edge* passed_edge)
{
    if (!passed_edge) return;
    Graph* parent;
    Graph* grandparent;
    int parent_open;

    removeEdge(passed_edge);
    parent = this;
    getAttribute((GraphObject*) parent, "x_parent", grandparent);
    getAttribute((GraphObject*) parent, "x_open", parent_open);

    while (grandparent != parent && parent_open) {
        grandparent->removeEdge(passed_edge);
        parent = grandparent;
        getAttribute((GraphObject*) parent, "x_parent", grandparent);
        getAttribute((GraphObject*) parent, "x_open", parent_open);
    }
}


//
// add a subgraph to a hypergraph
// parent is the immediate enclosing graph, may be another subgraph
// vertices are both vertices and super_vertices in the new subgraph
// new supervertex created has a x_parent (may not be main) and a x_subgraph
//
Vertex*
MHyperGraph::addSubgraph(Graph* parent, const List<Vertex*>& vertices)
{
    if (!parent) return (Vertex*)0;

    Graph* subgraph = parent->newGraph();

    // create the supervertex, name, add recursively up through the parents
    Vertex* super_vertex = new Vertex(this);
    String sub_name = makeSubgraphName();
    String new_name = strcpy(new char[strlen(sub_name)+1], sub_name);//LEAK
    setAttribute((GraphObject*) subgraph, "graph_name", new_name);
    setAttribute((GraphObject*) super_vertex, "name", new_name);

    parent->subgraphAddVertex(super_vertex);

    setAttribute((GraphObject*) super_vertex, "x_subgraph", subgraph);
    setAttribute((GraphObject*) super_vertex, "x_parent", parent);
    setAttribute((GraphObject*) super_vertex, "x_open", 0);
    setAttribute((GraphObject*) subgraph, "x_parent", parent);
    setAttribute((GraphObject*) subgraph, "x_supervertex", super_vertex);
    setAttribute((GraphObject*) subgraph, "x_open", 0);

    // save the new supervertex in attribute in the main graph
    List<Vertex*>* super_vs;
    getAttribute((GraphObject*) this, "x_supervertices", super_vs);
    super_vs->append(super_vertex);

    // process vertices to be put into the subgraph
    Iterator<Vertex*> get_vertex(&vertices);
    Vertex* vertex;
    while (get_vertex(vertex)) {
	// vertex and any subgraphs it has are all owned by new subgraph
	setAttribute((GraphObject*) vertex, "x_parent", subgraph);
	Graph* subsubgraph;
	getAttribute((GraphObject*) vertex, "x_subgraph", subsubgraph);
	if (subsubgraph)
	    setAttribute((GraphObject*) subsubgraph, "x_parent", subgraph);

	// add vertex to new subgraph, remove from all parents
	subgraph->addVertex(vertex);
	parent->subgraphRemoveVertex(vertex);
    }

    // process each edge attached to vertex deciding on internal or external
    // mark each internal edge so that it is only moved once
    // external edges are not marked because hypergraphs may need to replace
    // more than one vertex with a supervertex in the hyperedge
    get_vertex.reset();
    {
    Attribute<int> mark_attr(this, "s_mark", 0);
    while (get_vertex(vertex)) {
	MSet<Edge*> inc_edges = vertex->incidentEdges();
	Iterator<Edge*> get_inc_edge(&inc_edges);
	Edge* edge;
	while (get_inc_edge(edge)) {
	    int mark;
	    getAttribute((GraphObject*) edge, "s_mark", mark);
	    if (mark == 0) {
	        Bool internal = subgraph->internalEdge(edge);
	        if (internal) {
	            // if edge is internal, move it from parent to subgraph
	            setAttribute((GraphObject*) edge, "x_parent", subgraph);
		    subgraph->addEdge(edge);
		    parent->subgraphRemoveEdge(edge);
		    setAttribute((GraphObject*) edge, "s_mark", 1);
	        } else {
		    // if edge is external, replace vertex with super vertex
		    edge->replace(vertex, super_vertex);
		    super_vertex->addEdge(edge);
		}
	    }
	}
    }
    //printf("about to delete mark_attr:\n");
    }
    return super_vertex;
}


//
// dissolve a subgraph by removing the supervertex
// add all members of the subgraph to the parent graph and main if open
//
Set<Vertex*>
MHyperGraph::dissolveSubgraph(Vertex* super_vertex)
{
    Set<Vertex*> sub_vertices;
    if (!super_vertex)
	return sub_vertices;

    Graph* parent;
    Graph* subgraph;

    getAttribute((GraphObject*) super_vertex, "x_parent", parent);
    getAttribute((GraphObject*) super_vertex, "x_subgraph", subgraph);

    if (!parent || !subgraph) {
	sub_vertices.insert(super_vertex);
	return sub_vertices;
    }

    // remove super vertex from the parent graph
    parent->subgraphRemoveVertex(super_vertex);

    // change parent of members to graph which owned the supervertex
    // add in the subgraph vertices to new parent
    sub_vertices = subgraph->vertices();
    Vertex** sub_vs = subgraph->vertexStart();
    Edge* edge;
    const MSet<Edge*>& sub_edges = subgraph->edges();
    Iterator<Edge*> get_sub_edge(&sub_edges);           
    Attribute<int> internal_mark(this, "internal_mark", 0);
    int mark;

    // No good to test internal edges later when vertices are moving
    // between subgraph and parent graph.  label all internal edges now.
    while (get_sub_edge(edge)) {
	  setAttribute((GraphObject*) edge, "internal_mark", 1);
    }
    get_sub_edge.reset();
   
    int ord = subgraph->order();
    for (int i=0; i < ord; i++) {
	// if vertex is supervertex, also change parent of subgraph
	Graph* sub;
	getAttribute((GraphObject*) sub_vs[i], "x_subgraph", sub);
	if (sub)
	    setAttribute((GraphObject*) sub, "x_parent", parent);
	setAttribute((GraphObject*) sub_vs[i], "x_parent", parent);
	parent->subgraphAddVertex(sub_vs[i]);

	// examine incident edges of the subvertex to see if external
	MSet<Edge*> inc_edges = sub_vs[i]->incidentEdges();
	Iterator<Edge*> get_edge(&inc_edges);
	Edge* edge;
        while (get_edge(edge)) {
            // external edge, replace super vertex with actual vertex
	    getAttribute((GraphObject*) edge, "internal_mark", mark);
            if (!mark) {
                edge->replace(super_vertex, sub_vs[i]);
            }
        }
    }

    // add in the subgraph internal edges
    while (get_sub_edge(edge))
	parent->subgraphAddEdge(edge);

    // remove super vertex from graph attribute of main graph
    List<Vertex*>* super_vs;
    getAttribute((GraphObject*) this, "x_supervertices", super_vs);
    super_vs->remove(super_vertex);
    //delete super_vertex;
    //delete subgraph;	// must reconcile this LEAK!
    return sub_vertices;// and still allow this info to be returned
}


//
// open a subgraph so that its component vertices and edges are available
// at the parent level, vertices must appear in main graph if all above are open
//
void
MHyperGraph::openSubgraph(Vertex* super_vertex)
{
    if (!super_vertex) return;

    Graph* subgraph;
    Graph* parent;
    int open;

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

    if (!parent || !subgraph)
	return;

    if (!open) {

        setAttribute((GraphObject*) subgraph, "x_open", 1);
        setAttribute((GraphObject*) super_vertex, "x_open", 1);

    	// remove super vertex from all parents
	parent->subgraphRemoveVertex(super_vertex);

    	// process vertices and internal edges of subgraph
    	Vertex** sub_vs = subgraph->vertexStart();
        Edge* edge;
        const MSet<Edge*>& sub_edges = subgraph->edges();
        Iterator<Edge*> get_sub_edge(&sub_edges);           

        int ord = subgraph->order();
        for (int i=0; i < ord; i++) {
    	    // add in the subgraph vertices to all parents
	    parent->subgraphAddVertex(sub_vs[i]);

	    // examine incident edges of the subvertex to see if external
	    MSet<Edge*> inc_edges = sub_vs[i]->incidentEdges();
	    Iterator<Edge*> get_edge(&inc_edges);
	    Edge* edge;
	    while (get_edge(edge))
		// external edge replace super vertex with actual vertex
	    	if (!subgraph->internalEdge(edge))
		    edge->replace(super_vertex, sub_vs[i]);
    	}

    	// add in the subgraph internal edges to all parents
        while (get_sub_edge(edge))
	    parent->subgraphAddEdge(edge);
    }
}


//
// close a super vertex, remove vertices from main if parents are all open
//
void
MHyperGraph::closeSubgraph(Vertex* super_vertex)
{
    if (!super_vertex) return;

    Graph* subgraph;
    Graph* parent;
    int open;

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

    if (!parent || !subgraph)
	return;

    if (open) {

        setAttribute((GraphObject*) subgraph, "x_open", 0);
        setAttribute((GraphObject*) super_vertex, "x_open", 0);

	parent->subgraphAddVertex(super_vertex);

    	// incident edges of the super vertex are external edges
    	Vertex** sub_vs = subgraph->vertexStart();
	Edge* edge;
        const MSet<Edge*>& sub_edges = subgraph->edges();
        Iterator<Edge*> get_sub_edge(&sub_edges);           

    	// remove the internal vertices and edges from all parents
        int ord = subgraph->order();
        for (int i=0; i < ord; i++) {
	    parent->subgraphRemoveVertex(sub_vs[i]);
		
	    // examine incident edges of the subvertex to see if external
	    MSet<Edge*> inc_edges = sub_vs[i]->incidentEdges();
	    Iterator<Edge*> get_edge(&inc_edges);
	    Edge* edge;
	    while (get_edge(edge)) {
	    	Bool internal = subgraph->internalEdge(edge);
		// external edge replace super vertex with actual vertex
	    	if (!internal)
		    edge->replace(sub_vs[i], super_vertex);
	    }
	}

    	// add in the subgraph internal edges
	while (get_sub_edge(edge))
	    parent->subgraphRemoveEdge(edge);
    }
}


//
// is the passed edge internal to this subgraph
//
Bool
MHyperGraph::internalEdge(Edge* passed_edge) const
{
    if (!passed_edge) return FALSE;
    Iterator<Vertex*> get_adj_vertex(passed_edge->vertices());
    Vertex* adj_vertex;
    while (get_adj_vertex(adj_vertex)) {
        Bool internal = FALSE;
        int ord = order();
	//*****this is unnecessary - binary search would be better
	for (int i=0; i < ord; i++) {
	    if ( CAST(_vertices,Array<Vertex*>)[i] == adj_vertex)
		internal = TRUE;
	}
	if (internal == FALSE) {
	    return FALSE;
	}
    }
    return TRUE;
}


//
// are the two vertices adjacent to each other
// for undirected hypergraph, are they in the same hyperedge
//
Bool
MHyperGraph::adjacentQ(Vertex* v1, Vertex* v2) const
{
    if (!v1 || !v2) return FALSE;
    MSet<Edge*> inc_edges = v1->incidentEdges();
    Iterator<Edge*> get_edge(&inc_edges);
    Edge* edge;
    while (get_edge(edge)) {
        if (edge->hasVertex(v2))
	    return TRUE;
    }
    return FALSE;
}


//
// save the graph to an ascii file
// all subgraphs are closed (with state saved) to get recursion of subgraphs
// while saveToFile is actually run, supervertices must be opened to allow
// the actual connecting vertex to be listed rather than the supervertex
//
void
MHyperGraph::saveToFile(ofstream *fout)
{
    Attribute<int> mark_attr(this, "x_mark", 0);

    // Iterate over supervertices to save open status, and to close before save
    List<Vertex*>* supervertices;
    int ok = 
      getAttribute((GraphObject*) this, "x_supervertices", supervertices);
    if ( ok == LINK_OK )
    {
      Iterator<Vertex*> get_superv(supervertices);
      Vertex* supervertex;
      while (get_superv(supervertex)) {
    	int x_open;
	getAttribute((GraphObject*) supervertex, "x_open", x_open);
	setAttribute((GraphObject*) supervertex, "open", x_open);
	closeSubgraph(supervertex);
      }

    // Do the actual save to file, all subgraphs are closed to capture structure
      saveToFile(fout, 0);

      // Restore the graph to correct open and closed subgraphs
      get_superv.reset();
      while (get_superv(supervertex)) {
  	int open;
  	getAttribute((GraphObject*) supervertex, "open", open);
	if (open)
	    openSubgraph(supervertex);
      }
    }
    else saveToFile(fout, 0);
}


void
MHyperGraph::saveToFile(ofstream *fout, int indent)
{
    char buf[BUFSIZE];
    sprintf(buf, "%*c", indent, ' ');

    // Save Graph level info
    *fout << buf << "{ Graph ";

    cout << type() << endl;
    switch (type()) {
	case M_MIXEDHYPERGRAPH:
	    *fout << "MHyperGraph "; break;
	case MIXEDHYPERGRAPH:
	    *fout << "HyperGraph "; break;
	case M_UNDHYPERGRAPH:
	    *fout << "MUHyperGraph "; break;
	case UNDHYPERGRAPH:
	    *fout << "UHyperGraph "; break;
	case M_DIRHYPERGRAPH:
	    *fout << "MDHyperGraph "; break;
	case DIRHYPERGRAPH:
	    *fout << "DHyperGraph "; break;
	case M_MIXEDBINARYGRAPH:
	    *fout << "MBinGraph "; break;
	case MIXEDBINARYGRAPH:
	    *fout << "BinGraph "; break;
	case M_UNDBINARYGRAPH:
	    *fout << "MUBinGraph "; break;
	case UNDBINARYGRAPH:
	    *fout << "UBinGraph "; break;
	case M_DIRBINARYGRAPH:
	    *fout << "MDBinGraph "; break;
	case DIRBINARYGRAPH:
	    *fout << "DBinGraph "; break;
    };
    *fout << endl << buf << "(" << endl;

    // Save graph attribute information
    List<AttributeBase*> attrs = attributes();
    Iterator<AttributeBase*> get_attr(&attrs);
    AttributeBase* attribute;
    while (get_attr(attribute)) {
	if (strncmp(attribute->name(), "x_", 2) != 0) {
            *fout << buf << " " << attribute->name() << "(" << *attribute 
		<< ")" << endl;
	}
    }
    *fout << buf << ")" << endl;

    // Save vertex information
    *fout << buf << "Vertices [" << "\n";
    for (int i=0; i < _vertices.size(); i++)
	_vertices[i]->saveToFile(fout, indent);
    *fout << buf << "]" << "\n";

    // Save edge information
    *fout << buf << "Edges {" << endl;
    Edge *edge;
    Iterator<Edge*> get_edge(&_edges);
    while (get_edge(edge))
	edge->saveToFile(fout, indent);
    *fout << buf << "}" << endl;
    *fout << buf << "}" << endl;
}


//
// return the incident edges of a vertex
//
MSet<Edge*> 
MHyperGraph::incidentEdges(Vertex* passed_vertex) const
{
    static MSet<Edge*> d;
    if (!passed_vertex)
	return d;
    return passed_vertex->incidentEdges();
}


MSet<Edge*>
MHyperGraph::inIncidentEdges(Vertex* passed_vertex) const
{
    static MSet<Edge*> d;
    if (!passed_vertex)
	return d;
    MSet<Edge*> return_edges;
    MSet<Edge*> inc_edges = passed_vertex->incidentEdges();
    Iterator<Edge*> get_edge(&inc_edges);
    Edge* edge;
    while (get_edge(edge)) {
        Collection<Vertex*>* verts = edge->vertices();
        if (verts->sortedQ()) // undirected - always include
            return_edges.insert(edge);
        else {
                Vertex* sink = edge->sinkVertex();
                if (sink == passed_vertex)
                        return_edges.insert(edge);
        }
    }
    return return_edges;
}


MSet<Edge*>
MHyperGraph::outIncidentEdges(Vertex* passed_vertex) const
{
    static MSet<Edge*> d;
    if (!passed_vertex)
	return d;
    MSet<Edge*> return_edges;
    MSet<Edge*> inc_edges = passed_vertex->incidentEdges();
    Iterator<Edge*> get_edge(&inc_edges);
    Edge* edge;
    while (get_edge(edge)) {
        Collection<Vertex*>* verts = edge->vertices();
        if (verts->sortedQ())
            return_edges.insert(edge);
        else {
                Vertex* source = edge->sourceVertex();
                if (source == passed_vertex)
                        return_edges.insert(edge);
        }
    }
    return return_edges;
}


int
MHyperGraph::degree(Vertex* passed_vertex) const
{
    if (!passed_vertex)
	return 0;
    return incidentEdges(passed_vertex).size();
}


int
MHyperGraph::inDegree(Vertex* passed_vertex) const
{
    if (!passed_vertex)
	return 0;
    return inIncidentEdges(passed_vertex).size();
}


int
MHyperGraph::outDegree(Vertex* passed_vertex) const
{
    if (!passed_vertex)
	return 0;
    return outIncidentEdges(passed_vertex).size();
}