• Main Page
  • Related Pages
  • Modules
  • Data Structures
  • Files
  • File List
  • Globals

/home/pvrabec/project/openscap/openscap-0.7.2/src/common/tsort.h

00001 /*
00002  * Copyright 2010 Red Hat Inc., Durham, North Carolina.
00003  * All Rights Reserved.
00004  *
00005  * This library is free software; you can redistribute it and/or
00006  * modify it under the terms of the GNU Lesser General Public
00007  * License as published by the Free Software Foundation; either
00008  * version 2.1 of the License, or (at your option) any later version.
00009  *
00010  * This library is distributed in the hope that it will be useful, 
00011  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00012  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013  * Lesser General Public License for more details.
00014  *
00015  * You should have received a copy of the GNU Lesser General Public
00016  * License along with this library; if not, write to the Free Software 
00017  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
00018  *
00019  * Authors:
00020  *      Lukas Kuklinek <lkuklinek@redhat.com>
00021  */
00022 
00023 
00024 // topological sort
00025 
00026 #include "list.h"
00027 
00028 #ifndef OSCAP_TSORT_H_
00029 #define OSCAP_TSORT_H_
00030 
00031 OSCAP_HIDDEN_START;
00032 
00033 // returns nodest with an edge from given node
00034 typedef struct oscap_list* (*oscap_tsort_edge_func)(void *node, void *userdata);
00035 
00036 /*
00037  * Topological sort.
00038  *
00039  * Performs a topological sort on a directed graph.
00040  *
00041  * @a edge_func is supposed to return an oscap_list of nodes edges coming from the current node
00042  * (passed to it as an argument) are pointing to. It takes the node as a first argument
00043  * and a pointer passed as @a userdata as a second argument.
00044  *
00045  * The purpose of @a cmp_func is to compare nodes. If it is NULL raw pointer comparison
00046  * is used, which should be good enough in most cases.
00047  *
00048  * Pointer @a output will be set to a list with result. If you want to just check whether
00049  * there is a topological order defined on the graph (i.e. it is an acyclic graph), pass NULL.
00050  * If the function manages to find a topological order of the nodes (returns true),
00051  * it is returned in this variable. Otherwise, it will contain an encountered loop.
00052  * You are responsible to free this list.
00053  *
00054  * @param input set of nodes to sort
00055  * @param output this pointer will be set to the result of the algorithm
00056  * @param edge_func function to return target nodes of outgoing edges from the current one
00057  * @param cmp_func node compasrison function
00058  * @param userdata arbitrary data pointer to be forwarded to the edge_func
00059  * @returns whether the algorithm managed to topologically sort the graph
00060  * @retval true input was sorted, result is in the *output pointer
00061  * @retval false a loop was detected, *output points to the encountered loop
00062  */
00063 bool oscap_tsort(struct oscap_list *input, struct oscap_list **output, oscap_tsort_edge_func edge_func, oscap_cmp_func cmp_func, void *userdata);
00064 
00065 OSCAP_HIDDEN_END;
00066 
00067 #endif // OSCAP_TSORT_H_
00068 

Generated on Wed Apr 20 2011 for Open SCAP Library by  doxygen 1.7.1