MultiSource/Benchmarks/DOE-ProxyApps-C/Pathfinder/searchDiagram.h

/*************************************************************************
 *
 *        PathFinder: finding a series of labeled nodes within a
 *                two-layer directed, cyclic graph.
 *               Copyright (2013) Sandia Corporation
 *
 * Copyright (2013) Sandia Corporation. Under the terms of Contract 
 * DE-AC04-94AL85000 with Sandia Corporation, the U.S. Government 
 * retains certain rights in this software.
 *
 * This file is part of PathFinder.
 * 
 * PathFinder is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Lesser General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * PathFinder 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 PathFinder.  If not, see <http://www.gnu.org/licenses/>.
 *
 * Questions? Contact J. Brian Rigdon (jbrigdo@sandia.gov)
 *
 */

/*
 * searchDiagram.h
 *
 *  Created on: Feb 1, 2013
 *      Author: Brian "Rig" Rigdon, Marcus Smith, Samuel Mulder
 */

#ifndef SEARCHDIAGRAM_H_
#define SEARCHDIAGRAM_H_

#include "node.h"

typedef struct SearchDiagramStruct SearchDiagram;
typedef struct EdgeReferencesStruct EdgeReferences;

struct SearchDiagramStruct
{
    Node *node;  /* a reference to the node */
    EdgeReferences *edgeReferenceArray; /* All the nodes reachable from here */
};

/* We are creating arrays of SearchDiagram - constructor/destructor would be superfluous */


/* The EdgeSearchStruct holds a different representation of
 * the tree through which we're searching. Our search diagram
 * will create an array of these for each node in the graph.
 * Searches will go through the array, looking to match the
 * search criteria. If the search is unsuccessful, it will
 * then search the edges of the node. In this array, the  first
 * element is the SEARCH ELEMENT we're comparing against. In
 * this iteration of the code, we're using the Node pointer
 * as the search key. The second element is the search edges
 * contained by that node. The search edges are referenced
 * directly, no need to go back to the SearchDiagram instance
 * to get to the edges.
 */

struct EdgeReferencesStruct
{
    Node *edgeTarget; /* The address of the node is how we're defining our search */
    EdgeReferences *targetNodeEdges; /* pointer to the "to" node's edge references */
};

/* We are creating arrays of EdgeReferences - constructor/destructor would be superfluous */

/* Scream through the diagram to get the element corresponding to this Node* */
SearchDiagram *SearchDiagram_findNode ( SearchDiagram *diagram, Node *node );

/* The meat of this process - the function that creates the search diagram.
 * It allocates the memory for the array of search diagram elements and
 * populates them with node data and edgeID arrays.
 */
SearchDiagram *SearchDiagram_build ( NodeList *nodeTree, int nodeCount );


/* And, our search methods. The first calls the second, which is recursive */

bool SearchDiagram_findSignatureAlongEdges ( Node *node, EdgeReferences *edges,
                                             char *labels[], NodePtrVec *result, Bitfield *visited );



#endif /* SEARCHDIAGRAM_H_ */