//#####################################################################
// Copyright 2004-2008, Ronald Fedkiw, Geoffrey Irving, Craig Schroeder, Tamar Shinar, Rachel Weinstein.
// This file is part of PhysBAM whose distribution is governed by the license contained in the accompanying file PHYSBAM_COPYRIGHT.txt.
//#####################################################################
// Class UNDIRECTED_GRAPH
//#####################################################################
#ifndef __UNDIRECTED_GRAPH__
#define __UNDIRECTED_GRAPH__

#include <Core/Arrays/ARRAY.h>
#include <Core/Log/DEBUG_UTILITIES.h>
namespace PhysBAM{

template<class T> class QUEUE;
template<class ID> class DIRECTED_GRAPH;
class DIRECTED_GRAPH_CORE;
class UNDIRECTED_GRAPH_CORE
{
public:

    ARRAY<VECTOR<int,2> > edges; // edges(e) returns (parent,child) of edge e
    ARRAY<ARRAY<int> > adjacent_edges; // adjacent_edges(j) returns list of edges connected to node j

    explicit UNDIRECTED_GRAPH_CORE(const int number_nodes=0,const int number_edges=0);
//##################################################################### 
    template<class RW> void Read(UNTYPED_ISTREAM<RW>& input);
    template<class RW> void Write(UNTYPED_OSTREAM<RW>& output) const;
    void Reset();
    void Add_Edge(const int parent,const int child,const int edge);
    void Remove_Edge(const int edge);
    void Modify_Edge(const int parent,const int child,const int edge);
    void Breadth_First_Directed_Graph(const int root_node,DIRECTED_GRAPH_CORE& directed_graph);
    int Connected_Components(ARRAY<int>& component_id); // returns total number of components
    void Depth_First_Directed_Graph(const int root_node,DIRECTED_GRAPH_CORE& directed_graph);
    bool operator==(const UNDIRECTED_GRAPH_CORE& c) const;
private:
    void Generate_Next_Level_Of_Breadth_First_Directed_Graph(DIRECTED_GRAPH_CORE& directed_graph,ARRAY<bool>& marked_nodes,ARRAY<bool,int>& marked_edges,QUEUE<int>& queue);
    void Generate_Next_Level_Of_Depth_First_Directed_Graph(DIRECTED_GRAPH_CORE& directed_graph,ARRAY<bool>& marked,const int node);
//#####################################################################
};

template<class ID=int,class EID=int>
class UNDIRECTED_GRAPH
{
public:

    UNDIRECTED_GRAPH_CORE core;

    explicit UNDIRECTED_GRAPH(const ID number_nodes=ID(),const EID number_edges=EID())
        :core(Value(number_nodes),Value(number_edges))
    {}

    ID Node_Number() const
    {return core.adjacent_edges.m;}

    EID Edge_Number() const
    {return core.edges.m;}

    ID Last_Node() const
    {return ID(core.adjacent_edges.m);}

    EID Last_Edge() const
    {return EID(core.edges.m);}

    const VECTOR<ID,2> Edges(const EID e) const // edges(e) returns (parent,child) of edge e
    {return VECTOR<ID,2>(core.edges(Value(e)));}

    void Ensure_Number_Nodes(const ID n)
    {if(n>core.adjacent_edges.m) core.adjacent_edges.Resize(n);}

    const ARRAY<EID>& Adjacent_Edges(const ID j) const // adjacent_edges(j) returns list of edges connected to node j
    {return (const ARRAY<EID>&)core.adjacent_edges(j);}

    void Reset()
    {core.Reset();}

    void Add_Edge(const ID parent,const ID child,const EID edge)
    {core.Add_Edge(Value(parent),Value(child),Value(edge));}

    void Remove_Edge(const EID edge)
    {core.Remove_Edge(Value(edge));}

    void Modify_Edge(const ID parent,const ID child,const EID edge)
    {core.Modify_Edge(Value(parent),Value(child),Value(edge));}

    void Breadth_First_Directed_Graph(const ID root_node,DIRECTED_GRAPH<ID>& directed_graph)
    {core.Breadth_First_Directed_Graph(Value(root_node),directed_graph.core);}

    int Connected_Components(ARRAY<int,ID>& component_id) // returns total number of components
    {return core.Connected_Components((ARRAY<int>&)component_id);}

    void Depth_First_Directed_Graph(const ID root_node,DIRECTED_GRAPH<ID>& directed_graph)
    {core.Depth_First_Directed_Graph(Value(root_node),directed_graph.core);}

    template<class RW> void Read(UNTYPED_ISTREAM<RW>& input)
    {Read_Binary(input,core);}

    template<class RW> void Write(UNTYPED_OSTREAM<RW>& output) const
    {Write_Binary(output,core);}

    bool operator==(const UNDIRECTED_GRAPH& c) const
    {return core==c.core;}
//#####################################################################
};
}
#endif
