GraphType.h

Go to the documentation of this file.

// Copyright (C) 2005 Alexander Ushakov
// Contents: Definition of the GraphVertex and GraphEdge
//
// Principal Authors: Alexander Ushakov
//
// Revision History:
//


#ifndef _GraphType_H_
#define _GraphType_H_


#include "set"
#include "vector"
#include "iostream"
#include "string"
using namespace std;

#include "GraphConcept.h"
#include "GraphConceptAlgorithms.h"
#include "GraphDrawingAttributes.h"
using namespace Graphs;

#include "RanlibCPP.h"


//---------------------------------------------------------------------------//
//------------------------------- GraphEdge ---------------------------------//
//---------------------------------------------------------------------------//


struct GraphEdge
{
  GraphEdge( int t ) : theTarget(t) { }

  GraphEdge( ) : theTarget(-1) { }


 
  GraphEdge inverse( int origin ) { return GraphEdge( origin ); }


  bool operator < ( const GraphEdge& e ) const { return theTarget< e.theTarget; }


  bool operator ==( const GraphEdge& e ) const { return theTarget==e.theTarget; }


  bool operator!= ( const GraphEdge& e ) const { return theTarget!=e.theTarget; }

  
  int theTarget;
};

ostream& operator << ( ostream& os , const GraphEdge& e );


//---------------------------------------------------------------------------//
//------------------------------- GraphVertex -------------------------------//
//---------------------------------------------------------------------------//


template< class EdgeType >
struct GraphVertex
{
  typedef EdgeType edge_type;
  
  
  GraphVertex( ) { }

  
  set< edge_type > in;

  
  set< edge_type > out;
};


//---------------------------------------------------------------------------//
//----------------------------- IntLabeledEdge ------------------------------//
//---------------------------------------------------------------------------//


struct IntLabeledEdge : virtual public GraphEdge
{
  IntLabeledEdge( int target , int label ) : GraphEdge(target), theLabel( label ) { }

  IntLabeledEdge( ) : GraphEdge(-1), theLabel( 0 ) { }
  
  
  IntLabeledEdge inverse( int origin ) { return IntLabeledEdge( origin , -theLabel ); }
  
  bool operator < ( const IntLabeledEdge& e ) const { 
    if( theLabel!=e.theLabel )
      return theLabel<e.theLabel;
    return theTarget<e.theTarget; 
  }
  
  
  bool operator ==( const IntLabeledEdge& e ) const { return this->GraphEdge::operator==( e ) && theLabel==e.theLabel; }


  bool operator!= ( const IntLabeledEdge& e ) const { return this->GraphEdge::operator!=( e ) || theLabel!=e.theLabel; }


  int theLabel;
};


ostream& operator << ( ostream& os , const IntLabeledEdge& e );


void prepareToFold( const IntLabeledEdge& e1 , const IntLabeledEdge& e2 );


//---------------------------------------------------------------------------//
//----------------------------- PlanarGraphEdge -----------------------------//
//---------------------------------------------------------------------------//


struct PlanarGraphEdge : virtual public GraphEdge
{
  
  PlanarGraphEdge( int target , int cell1=-1 , int cell2=-1 ) : GraphEdge(target), theCell1( cell1 ), theCell2( cell2 ) { }
  
  
  PlanarGraphEdge( ) : GraphEdge(-1), theCell1( -1 ), theCell2( -1 ) { }
  
  
  PlanarGraphEdge inverse( int origin ) { return PlanarGraphEdge( origin , theCell2 , theCell1 ); }
  
  
  bool operator < ( const PlanarGraphEdge& e ) const { 
    if( theCell1!=e.theCell1 )
      return theCell1<e.theCell1;
    if( theCell2!=e.theCell2 )
      return theCell2<e.theCell2;
    return theTarget<e.theTarget;
  }
  
  
  bool operator ==( const PlanarGraphEdge& e ) const { return theTarget==e.theTarget && theCell1==e.theCell1 && theCell2==e.theCell2; }
  
  
  bool operator!= ( const PlanarGraphEdge& e ) const { return theTarget!=e.theTarget || theCell1!=e.theCell1 || theCell2!=e.theCell2; }
  
  
  int theCell1;
  
  
  int theCell2;
};


//---------------------------------------------------------------------------//
//------------------------ PlanarGraphIntLabelledEdge -----------------------//
//---------------------------------------------------------------------------//


struct PlanarGraphIntLabelledEdge : public PlanarGraphEdge, public IntLabeledEdge
{
  
  PlanarGraphIntLabelledEdge( int target , int label , int cell1=-1 , int cell2=-1 ) : PlanarGraphEdge(target,cell1,cell2), IntLabeledEdge(target,label) { }
  
  
  PlanarGraphIntLabelledEdge( ) { }
  
  
  PlanarGraphIntLabelledEdge inverse( int origin ) { return PlanarGraphIntLabelledEdge( origin , -theLabel , theCell2 , theCell1 ); }
  
  
  bool operator < ( const PlanarGraphIntLabelledEdge& e ) const { 
    if( theLabel!=e.theLabel )
      return theLabel<e.theLabel;
    if( theCell1!=e.theCell1 )
      return theCell1<e.theCell1;
    if( theCell2!=e.theCell2 )
      return theCell2<e.theCell2;
    return theTarget<e.theTarget;
  }
  
  
  bool operator ==( const PlanarGraphIntLabelledEdge& e ) const { return theLabel==e.theLabel && theTarget==e.theTarget && theCell1==e.theCell1 && theCell2==e.theCell2; }
  
  
  bool operator!= ( const PlanarGraphIntLabelledEdge& e ) const { return theLabel!=e.theLabel || theTarget!=e.theTarget || theCell1!=e.theCell1 || theCell2!=e.theCell2; }
};


//---------------------------------------------------------------------------//
//----------------------------- IntLabeledEdge ------------------------------//
//---------------------------------------------------------------------------//



typedef GraphConcept< GraphVertex< GraphEdge > , GraphEdge > Graph;



typedef GraphConcept< GraphVertex< IntLabeledEdge > , IntLabeledEdge > IntLabeledGraph;




//---------------------------------------------------------------------------//
//---------------------------- Specific functions ---------------------------//
//---------------------------------------------------------------------------//


template< class ConstIntIterator >
int addRay( IntLabeledGraph& G , int v , ConstIntIterator B , ConstIntIterator E , bool direct=false )
{
  int cur_v = v;
  for( ; B!=E ; ) {
    int l = *(B++);
    int new_v = G.newVertex( IntLabeledGraph::vertex_type( ) );
    G.newEdge( cur_v , IntLabeledGraph::edge_type( new_v ,  l ) );
    if( !direct )
      G.newEdge( new_v , IntLabeledGraph::edge_type( cur_v , -l ) );
    cur_v = new_v;
  }
  return cur_v;
}


template< class ConstIntIterator >
void addLoop( IntLabeledGraph& G , int v , ConstIntIterator B , ConstIntIterator E , bool direct=false )
{
  int cur_v = v;
  for( ; B!=E ; ) {
    int l = *(B++);
    if( B!=E ) {
      int new_v = G.newVertex( IntLabeledGraph::vertex_type( ) );
      G.newEdge( cur_v , IntLabeledGraph::edge_type( new_v ,  l ) );
      if( !direct )
        G.newEdge( new_v , IntLabeledGraph::edge_type( cur_v , -l ) );
      cur_v = new_v;
    } else {
      G.newEdge( cur_v , IntLabeledGraph::edge_type( v ,  l ) );
      if( !direct )
        G.newEdge( v , IntLabeledGraph::edge_type( cur_v , -l ) );
    }
  }
}


Graph randomGraph( int N , float edge_param );


vector< vector< int > > lengthTable( const Graph& G );


vector< vector< int > > innerProductTable( const Graph& G , int origin );


float getHyperbolicityConst( const Graph& G );


string graphviz_format( const Graph& G , const GraphDrawingAttributes& GDA = GraphDrawingAttributes( ) );


string graphviz_format( const IntLabeledGraph& G , const GraphDrawingAttributes& GDA = GraphDrawingAttributes( ) );


#endif