// 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 Graph_h
#define Graph_h

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

#include <LINK/graph/GraphObject.h>
#include <LINK/basic/Set.h>
#include <LINK/basic/Sequence.h>
#include <LINK/basic/Array.h>
#include <LINK/basic/general.h>
#include <LINK/basic/Matrix.h>

#define REVERSE 		1
#define CLONE 			1

#define LINK_STATIC 		1
#define LINK_DYNAMIC 		0

#define DEFAULT_WIDTH 		1
#define DEFAULT_SIZE 		10

#define DEFAULT_WEIGHT		((double)1.0)

#define DEFAULT_X               (0.5)
#define DEFAULT_Y               (0.5)

#define DEFAULT_COLOR_VERTEX 	BLUE
#define DEFAULT_COLOR_EDGE 	BLACK
#define DEFAULT_COLOR           BLACK

#define DEFAULT_LABEL           ((char*)"")

#define DEFAULT_MARK            (0)
#define DEFAULT_STARTTIME       (0)
#define DEFAULT_FINISHTIME      (0)
#define DEFAULT_BACK            (0)
#define DEFAULT_LOW             (0)
#define DEFAULT_DISTANCE        ((double)0)

#define DEFAULT_PRED            ((Vertex*)0)

#define DEFAULT_TYPE      0x00

#define TREE_EDGE_TYPE    0x11
#define CROSS_EDGE_TYPE   0x12
#define BACK_EDGE_TYPE    0x13
#define FORWARD_EDGE_TYPE 0x14


class Vertex;
class Edge;
class ostream;
//class DBinGraph;
//class UBinGraph;

class Graph : public GraphObject {

    friend class HyperGraph;		// this to protect the addEdge(Edge*)
					// and addVertex(Vertex*) methods
					// which subgraphs need but shouldn't
					// be available to objects

protected:

    Graph();
    Graph(const Graph &G, Flag clone=CLONE, Flag reverse=0);
    void			addVertex(Vertex* passed_vertex);

    friend class MHyperGraph;

public:

    virtual ~Graph();

				// managing subgraphs
    virtual Graph*		newGraph() = 0;
    virtual Graph*		copyGraph(Flag clone=CLONE, Flag reverse=0) = 0;
            Graph*		transpose(Flag clone=0)
				{ return copyGraph(clone, REVERSE); }
            Graph*		inducedSubgraph(Set<Vertex*>vs,Flag clone)const;
            Graph*		edgeInducedSubgraph(Set<Edge*>vs,
						    Flag clone) const;
            MSet<Edge*>		inducedEdges(Set<Vertex*> vs) const;
    	    Vertex*		addSubgraph(const List<Vertex*>& v);
    	    Vertex*		addSubgraph(const Set<Vertex*>& v);
   	    void 		expandComponents();
   	    void  		collapseComponents(Set<Set<Vertex*> >);
    virtual Set<Vertex*>	dissolveSubgraph(Vertex* super_vertex) = 0;
    virtual void		openSubgraph(Vertex* super_vertex) = 0;
    virtual void		closeSubgraph(Vertex* super_vertex) = 0;
    Bool			open();

				// add vertices
    Vertex*			addVertex(String passed_name);
    void			addVertices(int n);

				// remove from graph without destructor
				// the following 3 should be protected,	
				// but parser.y currently depends on seeing
				// them
    void			removeVertex(Vertex* passed_vertex);
    void			removeEdge(Edge* passed_edge);

   	    AsymMatrix<int>    	adjacencyMatrix() const;

    virtual Edge*        	addEdge(Edge* passed_edge) = 0;

				// add edges to graph and vertices
    virtual Edge*       	addEdge(Collection<Vertex*>&vs, String n=0) = 0;
    virtual Edge*       	addEdge(Sequence<Vertex*> vs, String n=0) = 0;

    virtual MSet<Edge*>       	addEdges(MSet<Set<Vertex*> > es);
    virtual MSet<Edge*>       	addEdges(MSet<Sequence<Vertex*> > es);

    void 			deleteEdges(MSet<Set<Vertex*> > es);
    void 			deleteEdges(MSet<Sequence<Vertex*> > es);

				// destructive remove from graph
    virtual void		deleteVertex(Vertex* passed_vertex) = 0;
    virtual void		deleteVertex(String name) = 0;
    virtual void		deleteEdge(Edge* passed_edge) = 0;
    void 	      		deleteEdge(Collection<Vertex*>&vs);

    				// subgraph add and remove is recursive up
    virtual void		subgraphAddVertex(Vertex* passed_vertex) = 0;
    virtual void		subgraphRemoveVertex(Vertex* passed_vertex) = 0;
    virtual void		subgraphAddEdge(Edge* passed_edge) = 0;
    virtual void		subgraphRemoveEdge(Edge* passed_edge) = 0;
    virtual Bool		internalEdge(Edge* passed_edge) const = 0;

            Bool		isomorphicQ(const Graph*) const;
            Bool		isomorphicQ(const Graph&) const;
            Bool		directedQ() const;
            Bool		binaryQ() const;
            Bool		simpleQ() const;
				// graph relationships
    virtual Bool		adjacentQ(Vertex* v1, Vertex* v2) const = 0;
    virtual MSet<Edge*>		incidentEdges(Vertex* passed_vertex)   const= 0;
    virtual MSet<Edge*>		inIncidentEdges(Vertex* passed_vertex) const= 0;
    virtual MSet<Edge*>		outIncidentEdges(Vertex* passed_vertex)const= 0;

    virtual int			degree(Vertex* passed_vertex) const = 0;
    virtual int			inDegree(Vertex* passed_vertex) const = 0;
    virtual int			outDegree(Vertex* passed_vertex) const = 0;

				// bookkeeping
    const SortedArray<Vertex*>&	vertices() const;	   
    const MSet<Edge*>&		edges()	const	   { return _edges;           }
    Vertex**			vertexStart() const{ return _vertices.start();}
    int				order()       const{ return _vertices.size(); }
    Vertex*			vertex(int i) const{ return _vertices[i];     }
    int				rank(Vertex*v)const
						 { return _vertices.search(v);}
    Edge*			edge(int i) const{ return _edges.ref(i);      }
    int				rank(Edge*e)const
						 { return _edges.rank(e);}
    int				size() const     { return _edges.size();      }
    virtual DataType		type() const	 { return GRAPH;              }
    String			name() const;

    ostream&			display(ostream& os) const;
    void			display(int indent);
    virtual void		saveToFile(ofstream* fout) = 0;
    virtual void		saveToFile(ofstream* fout, int indent) = 0;

    Vertex*			findVertexByName(String name);
    Edge*			findEdgeByName(String name);
    Vertex*			findVertexWithEdge(Edge* edge);
    Edge*			isEdge(Vertex*, Vertex*) const;
    Edge*			isEdge(const Collection<Vertex*>&) const;
    Bool			memberQ(Vertex* v) const;
    Bool			memberQ(Edge* e)   const;

    String			makeVertexName();
    String			makeEdgeName();
    String			makeSubgraphName();

    void			setVertexName(int i)  {_cur_vertex_name = i;  }
    void			setEdgeName(int i)    {_cur_edge_name = i;    }
    void			setSubgraphName(int i){_cur_subgraph_name = i;}
    int 			operator<(const Graph& g) const;
    int 			operator==(const Graph& g) const;
    // uses GraphObject::operator<< now
    //friend ostream& operator<<(ostream& os, const Graph& g)
    //				{ return g.display(os); }

protected:
    virtual Vertex*		addSubgraph(Graph* owner, 	
					    const List<Vertex*>&v)= 0;
    ostream&			displayAllGraphObjects(ostream& os) const;
    SortedArray<Vertex*> 	_vertices;
    MSet<Edge*>			_edges;
    int				_cur_vertex_name;       // naming of vertices
    int				_cur_edge_name;         // naming of edges
    int				_cur_subgraph_name;     // naming of subgraphs

private:
    static int			graph_count;
};


int compareVertexNames(char *str1, char *str2); // definition in Vertex.cc:

Graph *LoadGraph(char*); 		// definition in parseGraph.cc
int    SaveGraph(Graph*, char*); 	// definition in GraphBuild.cc
Graph *LoadDimacsGraph(char*); 		// definition in LoadDimacsGraph.cc
int    SaveDimacsGraph(Graph*, char*);	// definition in SaveDimacsGraph.cc

// definitions in AdjacencyMatrix.cc

class MBinGraph;

AsymMatrix<int> AdjacencyMatrix(const Graph *);
MBinGraph AdjacencyMatrix2Graph(const Matrix<int>&);
MBinGraph AdjacencyMatrix2Digraph(const Matrix<int>&);

// definitions in IncidenceMatrix.cc

AsymMatrix<int> IncidenceMatrix(const Graph* graph, int direction=1);
MHyperGraph       IncidenceMatrix2Graph(const Matrix<int>&);

// definitions in LaplacianMatrix.cc

SymMatrix<int> LaplacianMatrix(Matrix<int>& M);

// definitions in GraphBuild.cc:

Graph* newEmpty(const Graph *);
Graph* multiGraph(const Graph *, Flag c=CLONE, Flag r=0);
Graph* simpleGraph(const Graph *, Flag c=CLONE, Flag r=0);
Graph* directedGraph(const Graph *, Flag c=CLONE, Flag r=0);
Graph* undirectedGraph(const Graph *, Flag c=CLONE, Flag r=0);
Graph* makeGraph(Set<Vertex*> vset, MSet<Edge*> eset);
Graph* makeGraph(MSet<Vertex*> vset, MSet<Set<Vertex*> > eset);
Graph* makeGraph(MSet<Vertex*> vset, MSet<Sequence<Vertex*> > eset);
Graph* makeGraph(MSet<char*> vset, MSet<Set<char*> > eset);
Graph* makeGraph(Set<char*> vseq, MSet<Sequence<char*> > eseq);
Graph* makeGraph(Set<int*> vset, MSet<Set<int*> > eset);
Graph* bipartiteRepresentation(Graph *);
//Graph* makeGraph(Set<int*> vseq, MSet<Sequence<int*> > eseq);

graph *nautyGraph(const Graph *);
graph *canonicalNautyGraph(const Graph *, graph *g, nvector *lab);

#endif