# HG changeset patch # User alpar # Date 1079368220 0 # Node ID 47cd1716870e73ae320b3915db7ca3f49fc17df9 # Parent 259540358bbfb5db023977c8043201ee8c6210f4 . diff -r 259540358bbf -r 47cd1716870e doc/Doxyfile --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/doc/Doxyfile Mon Mar 15 16:30:20 2004 +0000 @@ -0,0 +1,210 @@ +# Doxyfile 1.3.2 + +#--------------------------------------------------------------------------- +# General configuration options +#--------------------------------------------------------------------------- +PROJECT_NAME = hugo +PROJECT_NUMBER = 0.1 +OUTPUT_DIRECTORY = +OUTPUT_LANGUAGE = English +USE_WINDOWS_ENCODING = NO +EXTRACT_ALL = NO +EXTRACT_PRIVATE = NO +EXTRACT_STATIC = NO +EXTRACT_LOCAL_CLASSES = YES +HIDE_UNDOC_MEMBERS = YES +HIDE_UNDOC_CLASSES = YES +HIDE_FRIEND_COMPOUNDS = NO +HIDE_IN_BODY_DOCS = NO +BRIEF_MEMBER_DESC = YES +REPEAT_BRIEF = NO +ALWAYS_DETAILED_SEC = NO +INLINE_INHERITED_MEMB = NO +FULL_PATH_NAMES = NO +STRIP_FROM_PATH = +INTERNAL_DOCS = NO +CASE_SENSE_NAMES = YES +SHORT_NAMES = NO +HIDE_SCOPE_NAMES = YES +SHOW_INCLUDE_FILES = YES +JAVADOC_AUTOBRIEF = NO +MULTILINE_CPP_IS_BRIEF = NO +DETAILS_AT_TOP = NO +INHERIT_DOCS = NO +INLINE_INFO = YES +SORT_MEMBER_DOCS = NO +DISTRIBUTE_GROUP_DOC = NO +TAB_SIZE = 8 +GENERATE_TODOLIST = YES +GENERATE_TESTLIST = YES +GENERATE_BUGLIST = YES +GENERATE_DEPRECATEDLIST= YES +ALIASES = +ENABLED_SECTIONS = +MAX_INITIALIZER_LINES = 30 +OPTIMIZE_OUTPUT_FOR_C = YES +OPTIMIZE_OUTPUT_JAVA = NO +SHOW_USED_FILES = YES +#--------------------------------------------------------------------------- +# configuration options related to warning and progress messages +#--------------------------------------------------------------------------- +QUIET = NO +WARNINGS = YES +WARN_IF_UNDOCUMENTED = YES +WARN_IF_DOC_ERROR = YES +WARN_FORMAT = "$file:$line: $text" +WARN_LOGFILE = +#--------------------------------------------------------------------------- +# configuration options related to the input files +#--------------------------------------------------------------------------- +INPUT = ../src/demo/alpar/emptygraph.h \ + ../src/doxy/invalid.h \ + ../src/demo/alpar/smart_graph.h \ + ../src/demo/alpar/mapskeleton.h +FILE_PATTERNS = +RECURSIVE = NO +EXCLUDE = +EXCLUDE_SYMLINKS = NO +EXCLUDE_PATTERNS = +EXAMPLE_PATH = examples +EXAMPLE_PATTERNS = +EXAMPLE_RECURSIVE = NO +IMAGE_PATH = +INPUT_FILTER = +FILTER_SOURCE_FILES = NO +#--------------------------------------------------------------------------- +# configuration options related to source browsing +#--------------------------------------------------------------------------- +SOURCE_BROWSER = YES +INLINE_SOURCES = NO +STRIP_CODE_COMMENTS = YES +REFERENCED_BY_RELATION = YES +REFERENCES_RELATION = YES +VERBATIM_HEADERS = YES +#--------------------------------------------------------------------------- +# configuration options related to the alphabetical class index +#--------------------------------------------------------------------------- +ALPHABETICAL_INDEX = YES +COLS_IN_ALPHA_INDEX = 2 +IGNORE_PREFIX = +#--------------------------------------------------------------------------- +# configuration options related to the HTML output +#--------------------------------------------------------------------------- +GENERATE_HTML = YES +HTML_OUTPUT = html +HTML_FILE_EXTENSION = .html +HTML_HEADER = +HTML_FOOTER = +HTML_STYLESHEET = +HTML_ALIGN_MEMBERS = YES +GENERATE_HTMLHELP = NO +CHM_FILE = +HHC_LOCATION = +GENERATE_CHI = NO +BINARY_TOC = NO +TOC_EXPAND = NO +DISABLE_INDEX = NO +ENUM_VALUES_PER_LINE = 4 +GENERATE_TREEVIEW = YES +TREEVIEW_WIDTH = 250 +#--------------------------------------------------------------------------- +# configuration options related to the LaTeX output +#--------------------------------------------------------------------------- +GENERATE_LATEX = YES +LATEX_OUTPUT = latex +LATEX_CMD_NAME = latex +MAKEINDEX_CMD_NAME = makeindex +COMPACT_LATEX = YES +PAPER_TYPE = a4wide +EXTRA_PACKAGES = +LATEX_HEADER = +PDF_HYPERLINKS = YES +USE_PDFLATEX = YES +LATEX_BATCHMODE = NO +LATEX_HIDE_INDICES = NO +#--------------------------------------------------------------------------- +# configuration options related to the RTF output +#--------------------------------------------------------------------------- +GENERATE_RTF = NO +RTF_OUTPUT = rtf +COMPACT_RTF = NO +RTF_HYPERLINKS = NO +RTF_STYLESHEET_FILE = +RTF_EXTENSIONS_FILE = +#--------------------------------------------------------------------------- +# configuration options related to the man page output +#--------------------------------------------------------------------------- +GENERATE_MAN = NO +MAN_OUTPUT = man +MAN_EXTENSION = .3 +MAN_LINKS = NO +#--------------------------------------------------------------------------- +# configuration options related to the XML output +#--------------------------------------------------------------------------- +GENERATE_XML = NO +XML_OUTPUT = xml +XML_SCHEMA = +XML_DTD = +#--------------------------------------------------------------------------- +# configuration options for the AutoGen Definitions output +#--------------------------------------------------------------------------- +GENERATE_AUTOGEN_DEF = NO +#--------------------------------------------------------------------------- +# configuration options related to the Perl module output +#--------------------------------------------------------------------------- +GENERATE_PERLMOD = NO +PERLMOD_LATEX = NO +PERLMOD_PRETTY = YES +PERLMOD_MAKEVAR_PREFIX = +#--------------------------------------------------------------------------- +# Configuration options related to the preprocessor +#--------------------------------------------------------------------------- +ENABLE_PREPROCESSING = YES +MACRO_EXPANSION = NO +EXPAND_ONLY_PREDEF = NO +SEARCH_INCLUDES = YES +INCLUDE_PATH = +INCLUDE_FILE_PATTERNS = +PREDEFINED = DOXYGEN +EXPAND_AS_DEFINED = +SKIP_FUNCTION_MACROS = YES +#--------------------------------------------------------------------------- +# Configuration::addtions related to external references +#--------------------------------------------------------------------------- +TAGFILES = +GENERATE_TAGFILE = +ALLEXTERNALS = NO +EXTERNAL_GROUPS = YES +PERL_PATH = /usr/bin/perl +#--------------------------------------------------------------------------- +# Configuration options related to the dot tool +#--------------------------------------------------------------------------- +CLASS_DIAGRAMS = YES +HIDE_UNDOC_RELATIONS = NO +HAVE_DOT = YES +CLASS_GRAPH = YES +COLLABORATION_GRAPH = YES +UML_LOOK = NO +TEMPLATE_RELATIONS = YES +INCLUDE_GRAPH = YES +INCLUDED_BY_GRAPH = YES +CALL_GRAPH = YES +GRAPHICAL_HIERARCHY = YES +DOT_IMAGE_FORMAT = png +DOT_PATH = +DOTFILE_DIRS = +MAX_DOT_GRAPH_WIDTH = 1024 +MAX_DOT_GRAPH_HEIGHT = 1024 +MAX_DOT_GRAPH_DEPTH = 0 +GENERATE_LEGEND = YES +DOT_CLEANUP = YES +#--------------------------------------------------------------------------- +# Configuration::addtions related to the search engine +#--------------------------------------------------------------------------- +SEARCHENGINE = YES +CGI_NAME = search.cgi +CGI_URL = +DOC_URL = +DOC_ABSPATH = +BIN_ABSPATH = /usr/local/bin/ +EXT_DOC_PATHS = diff -r 259540358bbf -r 47cd1716870e doc/makefile --- a/doc/makefile Sat Mar 13 22:53:07 2004 +0000 +++ b/doc/makefile Mon Mar 15 16:30:20 2004 +0000 @@ -1,2 +1,9 @@ -all: etikol.texi flf-graph.texi - makeinfo etikol.texi&&makeinfo --html etikol.texi&&texi2pdf etikol.texi \ No newline at end of file +doxy: + doxygen Doxyfile + + +texi: etikol.texi flf-graph.texi + makeinfo etikol.texi&&makeinfo --html etikol.texi&&texi2pdf etikol.texi + +texi-html: etikol.texi flf-graph.texi + makeinfo etikol.texi&&makeinfo --html etikol.texi \ No newline at end of file diff -r 259540358bbf -r 47cd1716870e src/work/alpar/emptygraph.h --- a/src/work/alpar/emptygraph.h Sat Mar 13 22:53:07 2004 +0000 +++ b/src/work/alpar/emptygraph.h Mon Mar 15 16:30:20 2004 +0000 @@ -12,8 +12,8 @@ /// An empty graph class. - /// This class provides all the common features of a grapf structure, - /// however completely without implementations or real data structures + /// This class provides all the common features of a graph structure, + /// however completely without implementations and real data structures /// behind the interface. /// All graph algorithms should compile with this class, but it will not /// run properly, of course. @@ -31,7 +31,7 @@ /// The base type of the node iterators. - /// This \c Node is the base type of each node iterators, + /// This is the base type of each node iterators, /// thus each kind of node iterator will convert to this. class Node { public: @@ -58,6 +58,14 @@ }; /// This iterator goes through each node. + + /// This iterator goes through each node. + /// Its usage is quite simple, for example you can count the number + /// of nodes in graph \c G of type \c Graph like this: + /// \code + ///int count=0; + ///for(Graph::NodeIt n(G);G.valid(n);G.next(n)) count++; + /// \endcode class NodeIt : public Node { public: /// @warning The default constructor sets the iterator @@ -91,7 +99,17 @@ bool operator<(Edge n) const { return true; } }; - /// This iterator goes trought the outgoing edges of a certain graph. + /// This iterator goes trought the outgoing edges of a node. + + /// This iterator goes trought the \e outgoing edges of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing edges of a node \c n + /// in graph \c G of type \c Graph as follows. + /// \code + ///int count=0; + ///for(Graph::OutEdgeIt e(G,n);G.valid(e);G.next(e)) count++; + /// \endcode class OutEdgeIt : public Edge { public: @@ -109,6 +127,18 @@ OutEdgeIt(const GraphSkeleton & G, Node n) {} }; + /// This iterator goes trought the incoming edges of a node. + + /// This iterator goes trought the \e incoming edges of a certain node + /// of a graph. + /// Its usage is quite simple, for example you can count the number + /// of outgoing edges of a node \c n + /// in graph \c G of type \c Graph as follows. + /// \code + ///int count=0; + ///for(Graph::InEdgeIt e(G,n);G.valid(e);G.next(e)) count++; + /// \endcode + class InEdgeIt : public Edge { public: /// @warning The default constructor sets the iterator @@ -119,6 +149,16 @@ InEdgeIt(const GraphSkeleton &, Node) {} }; // class SymEdgeIt : public Edge {}; + + /// This iterator goes through each edge. + + /// This iterator goes through each edge of a graph. + /// Its usage is quite simple, for example you can count the number + /// of edges in a graph \c G of type \c Graph as follows: + /// \code + ///int count=0; + ///for(Graph::EdgeIt e(G);G.valid(e);G.next(e)) count++; + /// \endcode class EdgeIt : public Edge { public: /// @warning The default constructor sets the iterator @@ -173,8 +213,14 @@ // Node bNode(SymEdgeIt) const {} /// Checks if a node iterator is valid + + ///\todo Maybe, it would be better if iterator converted to + ///bool directly, as Jacint prefers. bool valid(const Node) const { return true;} /// Checks if an edge iterator is valid + + ///\todo Maybe, it would be better if iterator converted to + ///bool directly, as Jacint prefers. bool valid(const Edge) const { return true;} ///Gives back the \e id of a node. @@ -194,6 +240,7 @@ ///Add a new node to the graph. /// \return the new node. + /// Node addNode() { return INVALID;} ///Add a new edge to the graph. @@ -227,8 +274,10 @@ - ///Read/write map of the nodes to type \c T. + ///Read/write/reference map of the nodes to type \c T. + ///Read/write/reference map of the nodes to type \c T. + /// \sa MemoryMapSkeleton /// \todo We may need copy constructor /// \todo We may need conversion from other nodetype /// \todo We may need operator= @@ -262,10 +311,15 @@ void update(T a) {} //FIXME: Is it necessary }; - ///Read/write map of the edges to type \c T. + ///Read/write/reference map of the edges to type \c T. - ///Read/write map of the edges to type \c T. - ///It behaves exactly the same way as \ref NodeMap. + ///Read/write/reference map of the edges to type \c T. + ///It behaves exactly in the same way as \ref NodeMap. + /// \sa NodeMap + /// \sa MemoryMapSkeleton + /// \todo We may need copy constructor + /// \todo We may need conversion from other edgetype + /// \todo We may need operator= template class EdgeMap { public: diff -r 259540358bbf -r 47cd1716870e src/work/alpar/mapskeleton.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/work/alpar/mapskeleton.h Mon Mar 15 16:30:20 2004 +0000 @@ -0,0 +1,80 @@ +// -*- c++ -*- +#ifndef HUGO_MAPSKELETON_H +#define HUGO_MAPSKELETON_H + +namespace hugo { + + ///Readable map skeleton + template + class ReadMapSkeleton + { + public: + /// Map value type. + typedef T ValueType; + /// Map key type. + typedef K KeyType; + + ///Default constructor. + ReadMapSkeleton() {} + + ///Reads an element of the map. + ValueType get(const KeyType &i) const {return ValueType();} + }; + + + ///Writeable map skeleton + template + class WriteMapSkeleton + { + public: + /// Map value type. + typedef T ValueType; + /// Map key type. + typedef K KeyType; + + ///Default constructor. + WriteMapSkeleton() {} + ///'Fill with' constructor. + WriteMapSkeleton(const ValueType &t) {} + + ///Write an element of a map. + void set(const KeyType &i,const ValueType &t) {} + }; + + ///Read/Write map skeleton. + template + class ReadWriteMapSkeleton : public ReadMapSkeleton, + public WriteMapSkeleton + { + public: + ///Default constructor. + ReadWriteMapSkeleton() : ReadMapSkeleton(), WriteMapSkeleton() {} + ///'Fill with' constructor. + ReadWriteMap(const ValueType &t) :ReadMapSkeleton(), WriteMapSkeleton(t) {} + }; + + + ///Dereferable map skeleton + template + class MemoryMapSkeleton : public ReadWriteMapSkeleton + { + public: + /// Map value type. + typedef T ValueType; + /// Map key type. + typedef K KeyType; + + ///Default constructor. + ReferenceMapSkeleton() : ReadWriteMapSkeleton() {} + ///'Fill with' constructor. + ReferenceMapSkeleton(const ValueType &t) : ReadWriteMapSkeleton(t) {} + + ///Give a reference to the value belonging to a key. + ValueType &operator[](const KeyType &i) {return *(ValueType*)0;} + // const ValueType &operator[](const KeyType &i) const {return *(T*)0;} + }; + + + +} +#endif // HUGO_MAPSKELETON_H diff -r 259540358bbf -r 47cd1716870e src/work/alpar/smart_graph.h --- a/src/work/alpar/smart_graph.h Sat Mar 13 22:53:07 2004 +0000 +++ b/src/work/alpar/smart_graph.h Mon Mar 15 16:30:20 2004 +0000 @@ -12,8 +12,14 @@ class SymSmartGraph; - // template class SymSmartGraph::SymEdgeMap; - + ///A smart graph class. + + ///This is a simple and fast graph implementation. + ///It is also quite memory efficient, but at the price + ///that it does not support node and edge deletion. + ///Apart from this it conforms to the graph interface documented under + ///the description of \ref GraphSkeleton. + ///\sa \ref GraphSkeleton. class SmartGraph { struct NodeT @@ -55,7 +61,7 @@ // protected: // HELPME: - public: + protected: ///\bug It must be public because of SymEdgeMap. /// mutable std::vector * > dyn_node_maps; @@ -99,10 +105,13 @@ int nodeNum() const { return nodes.size(); } //FIXME: What is this? int edgeNum() const { return edges.size(); } //FIXME: What is this? + ///\bug This function does something different than + ///its name would suggests... int maxNodeId() const { return nodes.size(); } //FIXME: What is this? + ///\bug This function does something different than + ///its name would suggests... int maxEdgeId() const { return edges.size(); } //FIXME: What is this? - Node tail(Edge e) const { return edges[e.n].tail; } Node head(Edge e) const { return edges[e.n].head; } @@ -480,15 +489,28 @@ ///The purpose of this graph structure is to handle graphs ///having bidirectional edges. Here the function \c addEdge(u,v) adds a pair - ///of oppositely directed edges. You can define edge maps which - ///stores a common value for the edge pairs. The usual edge maps can be used + ///of oppositely directed edges. + ///There is a new edge map type called + ///\ref SymSmartGraph::SymEdgeMap "SymEdgeMap" + ///that complements this + ///feature by + ///storing shared values for the edge pairs. The usual + ///\ref GraphSkeleton::EdgeMap "EdgeMap" + ///can be used ///as well. /// - ///The oppositely directed edge can also be obtained easily. + ///The oppositely directed edge can also be obtained easily + ///using \ref opposite. + ///\warning It shares the similarity with \ref SmartGraph that + ///it is not possible to delete edges or nodes from the graph. + //\sa \ref SmartGraph. class SymSmartGraph : public SmartGraph { public: + template class SymEdgeMap; + template friend class SymEdgeMap; + SymSmartGraph() : SmartGraph() { } SymSmartGraph(const SmartGraph &_g) : SmartGraph(_g) { } Edge addEdge(Node u, Node v) @@ -498,6 +520,10 @@ return e; } + ///The oppositely directed edge. + + ///Returns the oppositely directed + ///pair of the edge \c e. Edge opposite(Edge e) const { Edge f; @@ -505,6 +531,10 @@ return f; } + ///Common data storage for the edge pairs. + + ///This map makes it possible to store data shared by the oppositely + ///directed pairs of edges. template class SymEdgeMap : public DynMapBase { std::vector container; @@ -513,12 +543,12 @@ typedef T ValueType; typedef Edge KeyType; - SymEdgeMap(const SmartGraph &_G) : + SymEdgeMap(const SymSmartGraph &_G) : DynMapBase(_G), container(_G.maxEdgeId()/2) { - G->dyn_edge_maps.push_back(this); + static_cast(G)->dyn_edge_maps.push_back(this); } - SymEdgeMap(const SmartGraph &_G,const T &t) : + SymEdgeMap(const SymSmartGraph &_G,const T &t) : DynMapBase(_G), container(_G.maxEdgeId()/2,t) { G->dyn_edge_maps.push_back(this); @@ -550,13 +580,14 @@ { if(G) { std::vector* >::iterator i; - for(i=G->dyn_edge_maps.begin(); - i!=G->dyn_edge_maps.end() && *i!=this; ++i) ; + for(i=static_cast(G)->dyn_edge_maps.begin(); + i!=static_cast(G)->dyn_edge_maps.end() + && *i!=this; ++i) ; //if(*i==this) G->dyn_edge_maps.erase(i); //Way too slow... //A better way to do that: (Is this really important?) if(*i==this) { - *i=G->dyn_edge_maps.back(); - G->dyn_edge_maps.pop_back(); + *i=static_cast(G)->dyn_edge_maps.back(); + static_cast(G)->dyn_edge_maps.pop_back(); } } }