// 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
// 

#ifndef HyperGraph_h
#define HyperGraph_h

#include <LINK/graph/Graph.h>

class Vertex;
class Edge;

//
// mixed hypergraph is the base class (most general)
// edges which are added to this graph may be directed (Sequence<Vertex*>)
// or undirected (Set<Vertex*>) therefore must be represented by Collection
//
class MHyperGraph : public Graph {

protected:

    virtual Edge*	addEdge(Edge* passed_edge);

                        // subgraph add and remove is recursive up
    void                subgraphAddVertex(Vertex* passed_vertex);
    void                subgraphRemoveVertex(Vertex* passed_vertex);
    void                subgraphAddEdge(Edge* passed_edge);
    void                subgraphRemoveEdge(Edge* passed_edge);
    Bool		internalEdge(Edge* passed_edge) const;
    Vertex*		addSubgraph(Graph* owner, const List<Vertex*>& vs);

public:

    MHyperGraph() {}
    MHyperGraph(const Graph &G, Flag clone=CLONE, Flag reverse=0) 
				: Graph(G, clone, reverse) {}

    ~MHyperGraph();

			// managing subgraphs
    Graph*		newGraph() { return (Graph*) new MHyperGraph; }
    Graph*		copyGraph(Flag clone = CLONE, Flag reverse = 0) 
			{ return (Graph*)new MHyperGraph(*this, clone,reverse);}
    void  		collapseComponents(Set<Set<Vertex*> >);
    void  		expandComponents();
    Set<Vertex*>	dissolveSubgraph(Vertex* super_vertex);
    void		openSubgraph(Vertex* super_vertex);
    void		closeSubgraph(Vertex* super_vertex);

    virtual Edge*	addEdge(Collection<Vertex*>&vs, String n=0);
    virtual Edge*	addEdge(Sequence<Vertex*> vs, String n=0);

			// deleting graph objects from graph
    virtual void	deleteVertex(Vertex* passed_vertex);
    virtual void	deleteVertex(String passed_vertex);
    virtual void	deleteEdge(Edge* passed_edge);

			// graph relationships
    Bool		adjacentQ(Vertex* v1, Vertex* v2) const;
    MSet<Edge*>		incidentEdges(Vertex* passed_vertex) const;
    MSet<Edge*>		inIncidentEdges(Vertex* passed_vertex) const;
    MSet<Edge*>		outIncidentEdges(Vertex* passed_vertex) const;

    int			degree(Vertex* passed_vertex) const;
    int			inDegree(Vertex* passed_vertex) const;
    int			outDegree(Vertex* passed_vertex) const;

    DataType		type() const		{ return M_MIXEDHYPERGRAPH; }
    void		saveToFile(ofstream* fout);
    void		saveToFile(ofstream* fout, int indent);
};


class HyperGraph : public MHyperGraph {
public:	
    HyperGraph() {}
    HyperGraph(const Graph &G, Flag clone=CLONE, Flag reverse=0) 
				: MHyperGraph(G, clone, reverse) {}
    Graph*		newGraph() { return (Graph*) new HyperGraph; }
    Graph*		copyGraph(Flag clone = CLONE, Flag reverse = 0) 
			{ return (Graph*) new HyperGraph(*this, clone,reverse);}
    Edge*	addEdge(Collection<Vertex*>&vs, String n=0)
		   { return isEdge(vs)? (Edge*)0: MHyperGraph::addEdge(vs, n); }
    Edge*	addEdge(Sequence<Vertex*> vs, String n=0)
		   { return isEdge(vs)? (Edge*)0: MHyperGraph::addEdge(vs, n); }
    DataType	type() const		{ return MIXEDHYPERGRAPH; }
};

#endif