MultiSource/Benchmarks/DOE-ProxyApps-C/Pathfinder/graphGen.c

/*************************************************************************
 *
 *        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)
 *
 */

/*
 * graphGen.c
 *
 *  Created on: Aug 2, 2013
 *      Author: jbrigdo
 */

#include <stdbool.h>
#include <stdio.h>
#include "graphGen.h"
#include "vectorUtils.h"


/* getDuplicateNodeForGraph takes a node from another graph and sees if
 * a duplicate has previously been created for this graph. If not, it tries
 * to create and insert a new duplicate. If that fails, we're out of memory.
 * In that circumstance, we have a significant error condition. It is
 * time to delete the graph being built and report that error to the
 * calling method (buildGraphFromPaths).
 */
static Node *getDuplicateNodeForGraph(Graph *graph, Node *from)
{
    Node *newNode = Graph_findNode(graph, from->id, true); /* true == deep search */
    if ( newNode )
        return(newNode);

    /* else */
    newNode = Node_duplicate(from, graph->totalNodes++ ); /* POST increment */
    if ( newNode )
    {
        Graph_addOuterNode(graph,newNode); /* all nodes are exterior in this graph */
        newNode->type = exteriorNode;
        return(newNode);
    }

    /* else */
    Graph_delete(graph); /* Failure is DESTRUCTIVE at this point */
    return NULL;
}


Graph *buildGraphFromPaths(NodeVecVec **pathList, BuildType build)
{
    Graph *newGraph = Graph_new();
    Node *pathNode; /* The node we're looking at in the path */
    Node *currentNode;
    Node *nextNode;
    int i; /* Iterator through the path List array */
    int j; /* Iterator through each path List */
    int k; /* Iterator through each path in the path List */

    if ( !pathList || !newGraph )
        return(NULL);

    for ( i = 0; pathList[i] ; ++i )
    {
        for (j = 0; j < pathList[i]->contentSize; ++j)
        {
            pathNode = pathList[i]->vector[j]->vector[0];
            currentNode = getDuplicateNodeForGraph(newGraph, pathNode);
            if ( !currentNode )
                return(NULL); /* out of memory: crashing! newGraph has already been cleaned up */

            for ( k = 1; k < pathList[i]->vector[j]->contentSize; ++k /*also incremented below*/ )
            {
                if ( build == endNodesOnly )
                {
                    k = pathList[i]->vector[j]->contentSize - 1;
                }
                else if ( build == labeledNodes )
                {
                    while ( pathList[i]->vector[j]->vector[k]->labelIdx < 0 )
                        ++k;
                }
                /* else if ( build == completePath ) no-op */

                pathNode = pathList[i]->vector[j]->vector[k];
                nextNode = getDuplicateNodeForGraph(newGraph, pathNode);
                if ( !nextNode )
                    return(NULL); /* out of memory: crashing! newGraph has already been cleaned up */
                Node_addEdgeToNode(currentNode, nextNode);
                // printf ( "Adding edge: %d ==> %d\n", currentNode->id, nextNode->id );
                currentNode = nextNode;
            }
        }
    }

    return(newGraph);
}


/* Write the given graph to a file */
bool exportGraph(Graph *graph, char *fileName)
{
    FILE *out = NULL;
    NodeList *nodes = NULL;
    EdgeList *edges = NULL;
    int nodeCount = 0;

    if ( !graph || !fileName ) /* A little basic error checking */
        return(false);

    out = fopen(fileName, "w");

    if ( !out ) /* A little more basic error checking */
        return(false);

    /* Write out the header */
    /* ... find out how many functions (outer nodes) the graph holds */
    for ( nodes = graph->outerNodes; nodes != NULL; nodes = nodes->nextNode )
    {
        ++nodeCount;
    }
    fprintf(out, "Functions: %d\n", nodeCount);
    fprintf(out, "Basic blocks: %d\n\n", graph->totalNodes);

    /* First, write out the graph's outer nodes */
    for ( nodes = graph->outerNodes; nodes != NULL; nodes = nodes->nextNode )
    {
        fprintf(out, "%d ", nodes->node->id);
        //printf("Node: %d ", nodes->node->id);
        if ( nodes->node->edges )
        {
            nodeCount = 0;
            /* Wow is this inefficient, but two passes is the easiest way to do it. */
            for ( edges = nodes->node->edges; edges != NULL; edges = edges->nextEdge )
            {
                if ( edges->targetNode->type == exteriorNode )
                    ++nodeCount;
            }
            fprintf(out, "%d ", nodeCount);
            //printf("has %d edges: ", nodeCount);
            for ( edges = nodes->node->edges; edges != NULL; edges = edges->nextEdge )
                {
                    if ( edges->targetNode->type == exteriorNode )
                    {
                        fprintf(out, "%d ", edges->targetNodeId);
                        //printf("%d, ", edges->targetNodeId);
                    }
                }
            fprintf(out, "\n");
            //printf("\n");
        }
        else
        {
            fprintf(out, "0 \n" );
            //printf(" no edges.\n");
        }
    }

    /* then, for each of the outer nodes, write out its interior nodes (if any) */
    /* We are skipping this for the time being. This currently is being called with flat graphs. */

    /* Finally, write out the labels. */
    fprintf(out, "-------------------------------------------- \nSYSTEM CALLS \n\n");

    for ( nodes = graph->outerNodes; nodes != NULL; nodes = nodes->nextNode )
    {
        if ( nodes->node->label != NULL )
            fprintf(out, "%d %s \n", nodes->node->id, nodes->node->label );
        /* If we were worried about interior nodes, we'd need a duplicate loop here. */
    }

    return(true);

}