name: BiGraph <TObject> : private DoubleLinkedList< BiGraphVertex<TObject> >

synopsis:

g++ [flags ...] file ...

#include <BiGraph.h>

BiGraph(const BiGraph<TObject>& copy_graph);
boolean isWeighted() const;
boolean setWeighted(boolean is_weighted = true);

// declare the graph object
//
BiGraph<Char> graph;

// create some data
//
Char* char_a = new Char('a');
Char* char_b = new Char('b');

// create and add the vertices to the graph
//
BiGraphVertex<Char>* vertex_a = graph.insertVertex(char_a);
BiGraphVertex<Char>* vertex_b = graph.insertVertex(char_b);

// draw arcs between the vertices
//
graph.insertArc(graph.getStart(), vertex_a, false, 0.75);
graph.insertArc(vertex_a, vertex_b, false, 0.75);
graph.insertArc(vertex_b, graph.getTerm(), false, 0.75);

// write it in an Sof file
//
String tmp_filename(L"graph");
Sof tmp_file;
tmp_file.open(tmp_filename, File::WRITE_ONLY, File::TEXT);

graph.write(tmp_file, 1);
tmp_file.close();

description:

BiGraph is a generic directed graph template class. Internally, the BiGraph is stored as a list of BiGraphVertices. Each Vertex holds the information of the connection with other vertices.

dependencies:

public constants:

define the class name:

static const String CLASS_NAME = L"BiGraph";

i/o related constants:

static const String DEF_PARAM = L"";

static const String PARAM_VERTICES = L"vertices";

static const String PARAM_ARCS = L"arcs";

static const String PARAM_WEIGHTED = L"weighted";

static const String START_NAME = L"_START_";

static const String TERM_NAME = L"_TERM_";

dummy objects for start and end vertices:

static const TObject START_OBJ;

static const TObject TERM_OBJ;

indeces for start and end vertices:

static const long START_INDEX = -1;

static const long TERM_INDEX = -2;

default values and arguments:

static const boolean DEF_IS_WEIGHTED = true;

error codes:

error code indicating BiGraph class general error:

static const long ERR = 41200;

static const long ERR_EPSCYC = 41201;

static const long ERR_MULPAR = 41202;

protected data:

define typedefs for complex structures:

typedef Triple< Pair, Float, Boolean> TopoTriple;

typedef HashTable< String, BiGraphVertex > ReadHash;

each graph has a dummy start vertex:

BiGraphVertex<TObject>* start_vertex_d;

each graph has a dummy terminal vertex:

BiGraphVertex<TObject>* term_vertex_d;

hash table that associates color with the graph vertices:

ColorHash<TObject>* chash_d;

is the graph weighted:

Boolean is_weighted_d;

the allocation mode:

ALLOCATION alloc_d;

debugging parameters:
```
static Integral::DEBUG debug_level_d;
```
define the memory manager:
```
static MemoryManager mgr_d;
```

required public methods:

static methods: diagnose method is moved outside the class header file and defined in the BiGraphDiagnose.h in order to avoid issues related to preprocessing of the diagnose code
```
static const String& name();
```
```
static boolean diagnose(Integral::DEBUG debug_level);
```

debug methods:

boolean setDebug(Integral::DEBUG debug_level);

boolean debug(const unichar* message) const;

destructor/constructor(s):

~BiGraph();

BiGraph(ALLOCATION alloc = DEF_ALLOCATION);

BiGraph(const BiGraph<TObject>& copy_graph);

assign methods:

boolean assign(const BiGraph<TObject>& copy_graph);

boolean assign(const DiGraph<TObject>& copy_graph);

boolean assign(DoubleLinkedList<TObject>& data, DoubleLinkedList<TopoTriple>& arcs);

operator= methods:

BiGraph<TObject>& operator=(const BiGraph<TObject>& arg);

equality methods:

boolean eq(const BiGraph<TObject>& compare_vertex) const;

i/o methods: refer to the notes section for an explanation of why there are two read and write methods in this class

long sofSize() const;

boolean read(Sof& sof, long tag);

boolean read(Sof& sof, long tag, const String& name);

boolean write(Sof& sof, long tag) const;

boolean write(Sof& sof, long tag, const String& name) const;

boolean readData(Sof& sof, const String& pname = DEF_PARAM, long size = SofParser::FULL_OBJECT, boolean param = true, boolean nested = false);

boolean writeData(Sof& sof, const String& pname = DEF_PARAM) const;

boolean readDataText(Sof& sof, const String& pname = DEF_PARAM, long size = SofParser::FULL_OBJECT, boolean param = true, boolean nested = false);

boolean readDataBinary(Sof& sof);

boolean writeDataText(Sof& sof, const String& pname, DoubleLinkedList& dlist, DoubleLinkedList& alist) const;

boolean writeDataBinary(Sof& sof, const String& pname, DoubleLinkedList& dlist, DoubleLinkedList& alist) const;

memory management methods :

void* operator new(size_t size);

void* operator new[](size_t size);

void operator delete(void* ptr);

void operator delete[](void* ptr);

static boolean setGrowSize(long grow_size);

boolean clear(Integral::CMODE cmode = Integral::DEF_CMODE);

class-specific public methods:

methods that insert and remove graph arcs:

boolean insertArc(long start_index, long end_index, boolean is_epsilon = BiGraphArc<TObject>::DEF_EPSILON, float weight = BiGraphArc::DEF_WEIGHT)

boolean insertArc(BiGraphArc<TObject>* start_vertex, BiGraphArc<TObject>* end_vertex, boolean is_epsilon = BiGraphArc<TObject>::DEF_EPSILON, float weight = BiGraphArc::DEF_WEIGHT)

boolean removeArc(long start_index, long end_index);

boolean removeArc(BiGraphVertex* start_vertex, BiGraphVertex* end_vertex);

method inserts and removes graph vertices:

BiGraphVertex<TObject>* insertVertex(TObject* arg);

boolean removeVertex();

boolean removeVertex(TObject*& arg);

graph find and contains methods:

boolean find(const TObject* obj);

boolean find(BiGraphVertex<TObject>* vertex);

boolean contains(const TObject* obj);

boolean contains(BiGraphVertex<TObject>* vertex);

method to return the start/terminal vertex:

BiGraphVertex<TObject>* getStart() const;

BiGraphVertex<TObject>* getTerm() const;

method to return the graph structure:

boolean get(DoubleLinkedList& data, DoubleLinkedList, Float, Boolean> >& arcs);

method to check if graph is weighted or not:

boolean isWeighted() const;

boolean setWeighted(boolean is_weighted = true);

topological sort methods:

boolean topologicalSort(SingleLinkedList<TObject>& sorted_data, boolean partial = false);

color methods:

Integral::COLOR Graph::getColor(BiGraphVertex* vertex) const;

boolean setColor(Integral::COLOR col);

boolean releaseColorHash();

boolean invertColor();

boolean makeColorHash(Integral::COLOR col = Integral::DEF_COLOR);

boolean setColor(Integral::COLOR col);

boolean isColor(Integral::COLOR col);

boolean replaceColor(Integral::COLOR old_col, Integral::COLOR new_col);

methods to do simple depth first search:

boolean dfsVisit(BiGraphVertex<TObject>& vertex);

allocation mode methods:

ALLOCATION getAllocationMode() const

boolean setAllocationMode(ALLOCATION alloc)

double linked list methods: the BiGraph class derives the DoubleLinkedList bases class which is used as the primary underlying container class. to prevent the user from circumventing the BiGraph's interface and interacting directly with the DoubleLinkedList we use private inheritance. we define here the methods of the DoubleLinkedList interface that the user is permitted access to.

using DoubleLinkedList< BiGraphVertex >::length;

using DoubleLinkedList< BiGraphVertex >::gotoFirst;

using DoubleLinkedList< BiGraphVertex >::gotoNext;

using DoubleLinkedList< BiGraphVertex >::gotoPrev;

using DoubleLinkedList< BiGraphVertex >::getCurr;

using DoubleLinkedList< BiGraphVertex >::getFirst;

using DoubleLinkedList< BiGraphVertex >::getLast;

using DoubleLinkedList< BiGraphVertex >::gotoMark;

using DoubleLinkedList< BiGraphVertex >::setMark;

using DoubleLinkedList< BiGraphVertex >::gotoPosition;

using DoubleLinkedList< BiGraphVertex >::getPosition;

private methods:

methods to split readData:

boolean readVertexDataText(Sof& sof_a, SofParser& parser, HashTable >& hash_table) const;

boolean readArcDataText(Sof& sof_a, SofParser& parser, HashTable >& hash_table) const;

methods to split writeData:

boolean writeVertexDataText(Sof& sof, SingleLinkedList& data) const;

boolean writeArcDataText(Sof& sof, SingleLinkedList, Float, Boolean> >& arcs) const;

methods for topological sort:

boolean dfsVisitTS(SingleLinkedList<TObject>& output, BiGraphVertex<TObject>& vertex);

examples:

This example shows how to create a graph:

// declare the graph object
//
BiGraph<Char> graph(DstrBase::USER);

// perform the required assignments
//
Char* chr_a = new Char(L'a');
BiGraphVertex<Char>* vertex_a = graph.insertVertex(chr_a);
graph.insertArc(graph.getStart(), vertex_a, true);

Char* chr_b = new Char(L'b');
BiGraphVertex<Char>* vertex_b = graph.insertVertex(chr_b);
graph.insertArc(graph.getStart(), vertex_b, true);

Char* chr_c = new Char(L'c');
BiGraphVertex<Char>* vertex_c = graph.insertVertex(chr_c);
graph.insertArc(graph.getStart(), vertex_c, true);

Char* chr_d = new Char(L'd');
BiGraphVertex<Char>* vertex_d = graph.insertVertex(chr_d);
graph.insertArc(graph.getStart(), vertex_d, true);                     
      
// connect two vertices using the insertArc method
//
graph.insertArc(vertex_a,vertex_d, false, (float)0.7);
graph.insertArc(vertex_b, vertex_d, false, (float)0.9);
graph.insertArc(vertex_c, vertex_d, false, (float)3.7);
graph.insertArc(vertex_d, graph.getTerm(), true);

// clean up allocated memory
//
graph.clear(Integral::FREE);

notes:

Unlike other classes, we have two read and write methods in dstr classes. The interface is still the same as that in other classes. The reason behind this is that we can not use "CLASS_NAME" as default argument in the read and write methods here because the data structures build the class name on the fly.