Polaris: UGraphIterator Class Reference
Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Class Members | File Members

UGraphIterator Class Reference

a class for iterating through an undirected graph More...

#include <UGraphIterator.h>

Inheritance diagram for UGraphIterator:

Inheritance graph
[legend]
List of all members.

Public Member Functions

 UGraphIterator ()
 Create an empty iterator.
 UGraphIterator (int number_of_nodes, UGraphtype=UFULL)
 Iterate through a complete graph (UFULL) with given number of nodes.
 UGraphIterator (UGraph &graph)
 Iterate through given graph.
 ~UGraphIterator ()
void add_edge (int node1, int node2)
 Add an edge to the existing graph.
void combine_nodes (int node1, int node2)
 Combine the given nodes in _graph.
void coalesce_nodes (int node1, int node2)
 from all nodes to node1
bool valid ()
 Any more edges left to visit?
UEdge & current ()
 Return the current edge.
void operator++ ()
 Go to the next edge.
void next ()
 Same as operator++.
void reset ()
 Start back at the beginning of the iteration.
bool end ()
 This one is to satisfy Listable.
virtual void print (ostream &o) const
virtual UGraphIterator * clone () const
virtual Listable * listable_clone () const
 Copy and return a pointer to any Listable item (MUST be implemented correctly by subclasses for List copy functions to work).

Protected Attributes

UGraph _graph
 A copy of the UGraph being iterated over.
bool _valid
 Whether any edges remain in the graph to iterate over.
int _node1_pos
 Current position for node1 in iteration loop.
int _node2_pos
 Current position for node2 in iteration loop.
UEdge * _current
 Pointer to current node.

Friends

ostream & operator<< (ostream &o, const UGraphIterator &ad)

Detailed Description

a class for iterating through an undirected graph

Base General utility routines

See also:
UGraphIterator.h

UGraphIterator.cc

UGraphIterator.h

Description

This module contains the structures needed to represent an Iterator through the edges in a given undirected graph.

The class can be used in two ways:

1. to iterate through all possible connections between a set of nodes, or 2. to iterate through all edges in an existing graph

The first way is triggered by using the constructor form UGraphIterator( int nodes ). This simply indicates the number of nodes, and edges are successively returned from all possible edges.

The second way is triggered by using the constructor form UGraphIterator( UGraph graph ). This simply indicates that the existing nodes in the given graph are to be successively returned.

Notice that the first way can be achieved by giving a "complete" graph (also known as a clique) to the constructor implementing the second way.

The philosophy of this iterator, concerning calls to "reset()" is that it will go back to the beginning, finding the first edge in the current graph. It will make no attempt to return to the original graph. That would require making an extra copy of the original graph at every constructor call, and it is not anticipated that this would be a popular feature.

KNOWN/POSSIBLE BUGS/LIMITATIONS

Definition at line 59 of file UGraphIterator.h.

Constructor & Destructor Documentation

UGraphIterator::UGraphIterator (   ) 
 

Create an empty iterator.

Definition at line 12 of file UGraphIterator.cc.

References _current, _node1_pos, _node2_pos, _valid, and register_instance().

Referenced by clone().

UGraphIterator::UGraphIterator (  int  number_of_nodes,
UGraphtype  = UFULL
) 
 

Iterate through a complete graph (UFULL) with given number of nodes.

Definition at line 25 of file UGraphIterator.cc.

References _current, _node1_pos, _node2_pos, _valid, register_instance(), and UEMPTY.

UGraphIterator::UGraphIterator (  UGraph &  graph  ) 
 

Iterate through given graph.

Definition at line 81 of file UGraphIterator.cc.

References register_instance(), and reset().

UGraphIterator::~UGraphIterator (   ) 
 

Definition at line 120 of file UGraphIterator.cc.

References _current, and unregister_instance().

Member Function Documentation

void UGraphIterator::add_edge (  int  node1,
int  node2
) 
 

Add an edge to the existing graph.

Definition at line 94 of file UGraphIterator.cc.

References _graph, UGraph::add_edge(), and reset().

Referenced by main().

void UGraphIterator::combine_nodes (  int  node1,
int  node2
) 
 

Combine the given nodes in _graph.

Compress the graph so that there is no gap. Reset the iterator.

Definition at line 104 of file UGraphIterator.cc.

References _graph, UGraph::combine_nodes(), and reset().

Referenced by main().

void UGraphIterator::coalesce_nodes (  int  node1,
int  node2
) 
 

from all nodes to node1

Reset the iterator.

Definition at line 114 of file UGraphIterator.cc.

References _graph, UGraph::coalesce_nodes(), and reset().

Referenced by main().

bool UGraphIterator::valid (   ) 
 

Any more edges left to visit?

Definition at line 144 of file UGraphIterator.cc.

References _valid.

Referenced by AbstractAccess::coalesce(), main(), and UGraph::print().

UEdge & UGraphIterator::current (   ) 
 

Return the current edge.

Definition at line 131 of file UGraphIterator.cc.

References _current, _graph, _node1_pos, _node2_pos, _valid, and UGraph::delete_edge().

Referenced by AbstractAccess::coalesce(), main(), and UGraph::print().

void UGraphIterator::operator++ (   ) 
 

Go to the next edge.

... Find the next edge to visit

Definition at line 150 of file UGraphIterator.cc.

References UGraph::_connections, _current, _graph, _node1_pos, _node2_pos, _valid, and UGraph::nodes().

void UGraphIterator::next (   ) 
 

Same as operator++.

Definition at line 185 of file UGraphIterator.cc.

void UGraphIterator::reset (  void   ) 
 

Start back at the beginning of the iteration.

... Find the first edge to visit

Definition at line 53 of file UGraphIterator.cc.

References UGraph::_connections, _current, _graph, _node1_pos, _node2_pos, _valid, and UGraph::nodes().

Referenced by add_edge(), coalesce_nodes(), combine_nodes(), and UGraphIterator().

bool UGraphIterator::end (   ) 
 

This one is to satisfy Listable.

Definition at line 191 of file UGraphIterator.cc.

References _valid.

void UGraphIterator::print (  ostream &  o  )  const [virtual]
 

Implements Listable.

Definition at line 197 of file UGraphIterator.cc.

References _node1_pos, _node2_pos, and _valid.

Referenced by operator<<().

UGraphIterator * UGraphIterator::clone (   )  const [virtual]
 

Definition at line 210 of file UGraphIterator.cc.

References UGraphIterator().

Referenced by listable_clone().

Listable * UGraphIterator::listable_clone (   )  const [virtual]
 

Copy and return a pointer to any Listable item (MUST be implemented correctly by subclasses for List copy functions to work).

Implements Listable.

Definition at line 216 of file UGraphIterator.cc.

References clone().

Friends And Related Function Documentation

ostream& operator<< (  ostream &  o,
const UGraphIterator &  ad
)  [friend]
 

Definition at line 222 of file UGraphIterator.cc.

Member Data Documentation

UGraph UGraphIterator::_graph [protected]
 

A copy of the UGraph being iterated over.

Definition at line 62 of file UGraphIterator.h.

Referenced by add_edge(), coalesce_nodes(), combine_nodes(), current(), operator++(), and reset().

bool UGraphIterator::_valid [protected]
 

Whether any edges remain in the graph to iterate over.

Definition at line 63 of file UGraphIterator.h.

Referenced by current(), end(), operator++(), print(), reset(), UGraphIterator(), and valid().

int UGraphIterator::_node1_pos [protected]
 

Current position for node1 in iteration loop.

Definition at line 64 of file UGraphIterator.h.

Referenced by current(), operator++(), print(), reset(), and UGraphIterator().

int UGraphIterator::_node2_pos [protected]
 

Current position for node2 in iteration loop.

Definition at line 65 of file UGraphIterator.h.

Referenced by current(), operator++(), print(), reset(), and UGraphIterator().

UEdge* UGraphIterator::_current [protected]
 

Pointer to current node.

Definition at line 66 of file UGraphIterator.h.

Referenced by current(), operator++(), reset(), UGraphIterator(), and ~UGraphIterator().

The documentation for this class was generated from the following files:
 © 1995-2005 University of Illinois, Urbana-Champaign. All rights reserved.  Fri Mar 25 23:08:37 2005