quick start:g++ [flags ...] file ... #include <DiGraph.h> DiGraph(const DiGraph<TObject>& copy_graph); boolean isWeighted() const; boolean setWeighted(boolean is_weighted = true);
description:// declare the graph object // DiGraph<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 // GraphVertex<Char>* vertex_a = graph.insertVertex(char_a); GraphVertex<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();
static const String CLASS_NAME = L"DiGraph";
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_";
static const TObject START_OBJ;
static const TObject TERM_OBJ;
static const long START_INDEX = -1;
static const long TERM_INDEX = -2;
static const boolean DEF_IS_WEIGHTED = true;error codes:
static const long ERR = 41200;
static const long ERR_EPSCYC = 41201;
static const long ERR_MULPAR = 41202;
typedef Triple< Pair, Float, Boolean> TopoTriple;
typedef HashTable< String, GraphVertex> ReadHash;
GraphVertex<TObject>* start_vertex_d;
GraphVertex<TObject>* term_vertex_d;
ColorHash<TObject>* chash_d;
Boolean is_weighted_d;
ALLOCATION alloc_d;
static Integral::DEBUG debug_level_d;
static MemoryManager mgr_d;
static const String& name();
static boolean diagnose(Integral::DEBUG debug_level);
boolean setDebug(Integral::DEBUG debug_level);
boolean debug(const unichar* message) const;
~DiGraph();
DiGraph(ALLOCATION alloc = DEF_ALLOCATION);
DiGraph(const DiGraph<TObject>& copy_graph);
boolean assign(const DiGraph<TObject>& copy_graph);
boolean assign(SingleLinkedList<TObject>& data, SingleLinkedList<TopoTriple>& arcs);
DiGraph<TObject>& operator=(const DiGraph<TObject>& arg);
boolean eq(const DiGraph<TObject>& compare_vertex) const;
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;
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);
boolean insertArc(long start_index, long end_index, boolean is_epsilon = GraphArc<TObject>::DEF_EPSILON, float weight = GraphArc::DEF_WEIGHT)
boolean insertArc(GraphVertex<TObject>* start_vertex, GraphVertex<TObject>* end_vertex, boolean is_epsilon = GraphArc<TObject>::DEF_EPSILON, float weight = GraphArc::DEF_WEIGHT)
boolean insertArc(GraphVertex<TObject>* start_vertex, GraphVertex<TObject>* end_vertex, GraphArc<TObject>*& new_arc, boolean is_epsilon = GraphArc<TObject>::DEF_EPSILON, float weight = GraphArc::DEF_WEIGHT)
boolean removeArc(long start_index, long end_index);
boolean removeArc(GraphVertex* start_vertex, GraphVertex * end_vertex);
GraphVertex<TObject>* insertVertex(TObject* arg);
boolean removeVertex();
boolean removeVertex(TObject*& arg);
boolean find(const TObject* obj);
boolean find(GraphVertex<TObject>* vertex);
boolean contains(const TObject* obj);
boolean contains(GraphVertex<TObject>* vertex);
GraphVertex<TObject>* getStart() const;
GraphVertex<TObject>* getTerm() const;
GraphVertex<TObject>* getVertex(long index);
boolean get(SingleLinkedList& data, SingleLinkedList , Float, Boolean> >& arcs);
boolean isWeighted() const;
boolean setWeighted(boolean is_weighted = true);
boolean topologicalSort(SingleLinkedList<TObject>& sorted_data, boolean partial = false);
Integral::COLOR Graph::getColor(GraphVertex* 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);
boolean dfsVisit(GraphVertex<TObject>& vertex);
ALLOCATION getAllocationMode() const
boolean setAllocationMode(ALLOCATION alloc)
using DoubleLinkedList< GraphVertex>::length;
using DoubleLinkedList< GraphVertex>::gotoFirst;
using DoubleLinkedList< GraphVertex>::gotoNext;
using DoubleLinkedList< GraphVertex>::gotoPrev;
using DoubleLinkedList< GraphVertex>::getCurr;
using DoubleLinkedList< GraphVertex>::getFirst;
using DoubleLinkedList< GraphVertex>::getLast;
using DoubleLinkedList< GraphVertex>::gotoMark;
using DoubleLinkedList< GraphVertex>::setMark;
using DoubleLinkedList< GraphVertex>::gotoPosition;
using DoubleLinkedList< GraphVertex>::getPosition;
boolean readVertexDataText(Sof& sof_a, SofParser& parser, HashTable>& hash_table) const;
boolean readArcDataText(Sof& sof_a, SofParser& parser, HashTable>& hash_table) const;
boolean writeVertexDataText(Sof& sof, SingleLinkedList& data) const;
boolean writeArcDataText(Sof& sof, SingleLinkedList, Float, Boolean> >& arcs) const;
boolean dfsVisitTS(SingleLinkedList<TObject>& output, GraphVertex<TObject>& vertex);examples:
// declare the graph object // DiGraph<Char> graph(DstrBase::USER); // perform the required assignments // Char* chr_a = new Char(L'a'); GraphVertex<Char>* vertex_a = graph.insertVertex(chr_a); graph.insertArc(graph.getStart(), vertex_a, true); Char* chr_b = new Char(L'b'); GraphVertex<Char>* vertex_b = graph.insertVertex(chr_b); graph.insertArc(graph.getStart(), vertex_b, true); Char* chr_c = new Char(L'c'); GraphVertex<Char>* vertex_c = graph.insertVertex(chr_c); graph.insertArc(graph.getStart(), vertex_c, true); Char* chr_d = new Char(L'd'); GraphVertex<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);
// declare the graph object // DiGraph<Long> index_graph; // first read the graph that defines the connections // if (!index_graph.read(sof_a, graph_tag_a)) { return Error::handle(name(), L"readRecipeGraph", Error::READ, __FILE__, __LINE__, Error::WARNING); } SingleLinkedList<Long> node_indices(DstrBase::USER); SingleLinkedList< Triple< Pair<Long, Long>, Float, Boolean> > topo; index_graph.get(node_indices, topo); // sanity check -- the nodes should be consecutive integers // long count = 0; for (boolean m = node_indices.gotoFirst(); m; m = node_indices.gotoNext()) { if (node_indices.getCurr()->ne(count++)) { return Error::handle(name(), L"readRecipeGraph", ERR, __FILE__, __LINE__); } } // boolean values to represent if the node has parents // boolean no_parents[count]; for (long i = 0; i < count; i++) no_parents[i] = true; // initialization to no parents // iterate over all vertices in the list to test if a node has parents // for (boolean more = topo.gotoFirst(); more; more = topo.gotoNext()) { // retrieve the destination vertex position of the current arc // the node located in second place always has parents // Long dst_pos = topo.getCurr()->first().second(); no_parents[(long)dst_pos] = false; } for (long i = 0; i < count; i++) { if(no_parents[i] == true) printf("node #%ld : (**no** parent)\n", i); else printf("node #%ld : (parents exist)\n", i); }
------------------------------ Input file for above code: @ DiGraph<Long> 0 @ weighted = true; vertices = {0, {0}}, {1, {1}}, {2, {2}}, {3, {3}}, {4, {4}}, {5, {5}}, {6, {6}}, {7, {7}}; arcs = {0, 2, 0}, {1, 3, 0}, {2, 4, 0}, {3, 4, 1}, {4, 5, 0}, {6, 7, 0}, {7, 4, 2}; -------------------------------- This is the output: node #0 : (**no** parent) node #1 : (**no** parent) node #2 : (parents exist) node #3 : (parents exist) node #4 : (parents exist) node #5 : (parents exist) node #6 : (**no** parent) node #7 : (parents exist)