Aleph::Graph_Attr Struct Reference

General attributes for nodes and arc of graphs. More...

#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:
   • 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.
   • 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.
   • 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

Definition at line 313 of file aleph-graph.H.

Member Function Documentation

reset()

void Aleph::Graph_Attr::reset ( )

inline

Reset all attributes to their default value.

Definition at line 320 of file aleph-graph.H.

References control_bits, cookie, counter, and Aleph::Bit_Fields::reset().

Member Data Documentation

control_bits

Bit_Fields Aleph::Graph_Attr::control_bits

Definition at line 315 of file aleph-graph.H.

Referenced by reset().

cookie

void* Aleph::Graph_Attr::cookie = nullptr

Definition at line 317 of file aleph-graph.H.

Referenced by reset().

counter

long Aleph::Graph_Attr::counter = 0

Definition at line 316 of file aleph-graph.H.

Referenced by reset().

---

The documentation for this struct was generated from the following file:

• aleph-graph.H