Aleph-w  1.9
General library for algorithms and data structures
Public Member Functions | Public Attributes | List of all members
Aleph::Graph_Attr Struct Reference
Graphs

#include <aleph-graph.H>

+ Collaboration diagram for Aleph::Graph_Attr:

Public Member Functions

void reset ()
 Reset all attributes to their default value.
 

Public Attributes

Bit_Fields control_bits
 
long counter = 0
 
void * cookie = nullptr
 

Detailed Description

General attributes for nodes and arc of graphs.

Each node and arc of a Aleph-w graph manages three fixed attributes:

  1. control_bits: a field of type Bit_Fields for storing little state.
  2. counter: a long allowing to represent a much more wider state (colors, visit order, etc)
  3. cookie: a cookie is an opaque void pointer. Thes pointer could be used in order to associate to the node or arc state wider or different beyond the possibilities allowed by the bit fields and the counter. The three main uses of this pointer are:
    1. For mapping nodes and/or arcs to other isomorphic subgraphs. By example, you could compute a spanning tree of the graph. Now, in order to know which node or arc of spanning tree corresponds to its counterpart in the original graph, you could use this cookie and to perform an map. This has the great advantage that the map is deterministically $O(1)$, by contrast with the probabilistic $O(1)$ of a hash table or the $O(\lg n)$ of a binary search tree. In addition, this alternative, when required, is less space expensive.
    2. If you need to associate to the node or arc a more sophisticated state, the you could define it with a class (or tuple or whatever else you need), and then allocate it and storing via this cookie pointer. Of course, be careful and be sure of deallocating it when it is not longer needed. Also, consider that you will need to cast the cookie to the type of information that you have defined.
    3. Reverse path tracing. This is a very useful and powerful technique for storing partial and definitive path during graph processing. The general rule is: when in a search you visit a new node, the you saves the parent (the caller) in the cookie. Thus, when you finish the search, the path through the cookies is the revessed path from the the end node to the start node.
See also
Bit_Fields NODE_BITS NODE_COUNTER NODE_COLOR IS_NODE_VISITED NODE_COOKIE ARC_COUNTER ARC_COLOR ARC_BITS IS_ARC_VISITED ARC_COOKIE
The documentation for this struct was generated from the following file:
Leandro Rabindranath León