generic_graph_algorithms.h

//===========================================================================
// GoTools - SINTEF Geometry Tools
//
// GoTools module: Intersections, version 1.0
//
// Copyright (C) 2000-2007 SINTEF ICT, Applied Mathematics, Norway.
//
// This program is free software; you can redistribute it and/or          
// modify it under the terms of the GNU General Public License            
// as published by the Free Software Foundation version 2 of the License. 
//
// This program is distributed in the hope that it will be useful,        
// but WITHOUT ANY WARRANTY; without even the implied warranty of         
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          
// GNU General Public License for more details.                           
//
// You should have received a copy of the GNU General Public License      
// along with this program; if not, write to the Free Software            
// Foundation, Inc.,                                                      
// 59 Temple Place - Suite 330,                                           
// Boston, MA  02111-1307, USA.                                           
//
// Contact information: E-mail: tor.dokken@sintef.no                      
// SINTEF ICT, Department of Applied Mathematics,                         
// P.O. Box 124 Blindern,                                                 
// 0314 Oslo, Norway.                                                     
//
// Other licenses are also available for this software, notably licenses
// for:
// - Building commercial software.                                        
// - Building software whose source code you wish to keep private.        
//===========================================================================
#ifndef _GENERIC_GRAPH_ALGORITHMS_H
#define _GENERIC_GRAPH_ALGORITHMS_H

#include <vector>

//===========================================================================
//Paton's method for finding a fundamental set of cycles of an
//undirected graph.  Connectivity information between nodes is
//expressed by the functor 'connectedTo'.  NB: The outcome will be
//_appended_ to the 'result' sequence, no clear() operator will be
//called.
template<class FunctorConnectedTo > // FunctorConnectedTo(x, y)
                                    // returns 'true' if the node
                                    // indexed 'x' shares an edge with
                                    // the node indexed 'y'.
void get_fundamental_cycle_set(int num_nodes, // number of nodes in
                                              // set, they will be
                                              // indexed from 0
                               FunctorConnectedTo connectedTo, 
                               std::vector<std::vector<int> >& result); 
//===========================================================================

//===========================================================================
//Paton's method for finding a fundamental set of cycles of an
//undirected graph.  Connectivity information between nodes is
//expressed by the 'table' sequence.  Entry 'i' in this table is a
//list of indices of the nodes connected to node 'i'.  The sequence
//'result' is NOT emptied before use!
void get_fundamental_cycle_set(int num_nodes, 
                               const std::vector<std::vector<int> >& table,
                               std::vector<std::vector<int> >& result);
//===========================================================================

//===========================================================================
// Determining whether there is a path between two nodes in a graph
template<class FunctorConnectedTo> // Functor ConnectedTo(x,y) returns
                                   // 'true' if the node indexed 'x'
                                   // shares an edge with the node
                                   // indexed 'y'.
bool is_path_connected(int node1_index, 
                       int node2_index, 
                       int num_nodes, 
                       FunctorConnectedTo connected_to); 
//===========================================================================



//===========================================================================
//Will return all paths between branch-nodes, as well as all
//remaining, closed cycles.  Branch nodes are defined as those nodes
//incident with one, three or more edges.  (Nodes incident with 0
//edges are isolated, nodes incident with two edges lie on an
//"evident" path).  Closed cycles will be stored without duplication
//of the first node at the end.
template<class FunctorConnectedTo>
void get_individual_paths(int num_nodes,
                          FunctorConnectedTo connectedTo,
                          std::vector<std::vector<int> >& paths,
                          std::vector<std::vector<int> >& cycles,
                          std::vector<int>& isolated_nodes);
//===========================================================================



                               
#include "generic_graph_algorithms_implementation.h"
#endif // _GENERIC_GRAPH_ALGORITHMS_H

---