| /**************************************************************/ | |
| /* ********************************************************** */ | |
| /* * * */ | |
| /* * GRAPHS * */ | |
| /* * * */ | |
| /* * $Module: GRAPH * */ | |
| /* * * */ | |
| /* * Copyright (C) 1998, 2001 MPI fuer Informatik * */ | |
| /* * * */ | |
| /* * 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; either version 2 of the License, * */ | |
| /* * or (at your option) any later version. * */ | |
| /* * * */ | |
| /* * 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 * */ | |
| /* * * */ | |
| /* * * */ | |
| /* $Revision$ * */ | |
| /* $State$ * */ | |
| /* $Date$ * */ | |
| /* $Author$ * */ | |
| /* * * */ | |
| /* * Contact: * */ | |
| /* * Christoph Weidenbach * */ | |
| /* * MPI fuer Informatik * */ | |
| /* * Stuhlsatzenhausweg 85 * */ | |
| /* * 66123 Saarbruecken * */ | |
| /* * Email: weidenb@mpi-sb.mpg.de * */ | |
| /* * Germany * */ | |
| /* * * */ | |
| /* ********************************************************** */ | |
| /**************************************************************/ | |
| /* $RCSfile$ */ | |
| #ifndef _GRAPH_ | |
| #define _GRAPH_ | |
| #include "list.h" | |
| typedef struct { | |
| NAT number; | |
| int dfs_num; | |
| int comp_num; /* completion number */ | |
| POINTER info; /* user defined information */ | |
| LIST neighbors; | |
| } GRAPHNODE_STRUCT, *GRAPHNODE; | |
| typedef struct { | |
| NAT size; /* number of nodes */ | |
| LIST nodes; /* list of GRAPHNODES */ | |
| NAT dfscount; /* used for DFS */ | |
| NAT compcount; /* used for DFS */ | |
| } GRAPH_STRUCT, *GRAPH; | |
| static __inline__ NAT graph_NodeNumber(GRAPHNODE Node) | |
| { | |
| return Node->number; | |
| } | |
| static __inline__ int graph_NodeDfsNum(GRAPHNODE Node) | |
| { | |
| return Node->dfs_num; | |
| } | |
| static __inline__ void graph_NodeSetDfsNum(GRAPHNODE Node, int Number) | |
| { | |
| Node->dfs_num = Number; | |
| } | |
| static __inline__ int graph_NodeCompNum(GRAPHNODE Node) | |
| { | |
| return Node->comp_num; | |
| } | |
| static __inline__ void graph_NodeSetCompNum(GRAPHNODE Node, int Number) | |
| { | |
| Node->comp_num = Number; | |
| } | |
| static __inline__ LIST graph_NodeNeighbors(GRAPHNODE Node) | |
| { | |
| return Node->neighbors; | |
| } | |
| static __inline__ POINTER graph_NodeInfo(GRAPHNODE Node) | |
| { | |
| return Node->info; | |
| } | |
| static __inline__ void graph_NodeSetInfo(GRAPHNODE Node, POINTER Info) | |
| { | |
| Node->info = Info; | |
| } | |
| static __inline__ NAT graph_NodeOutdegree(GRAPHNODE Node) | |
| { | |
| return list_Length(graph_NodeNeighbors(Node)); | |
| } | |
| static __inline__ BOOL graph_NodeVisited(GRAPHNODE Node) | |
| { | |
| return graph_NodeDfsNum(Node) >= 0; | |
| } | |
| static __inline__ BOOL graph_NodeCompleted(GRAPHNODE Node) | |
| { | |
| return graph_NodeCompNum(Node) >= 0; | |
| } | |
| static __inline__ NAT graph_Size(GRAPH Graph) | |
| { | |
| return Graph->size; | |
| } | |
| static __inline__ LIST graph_Nodes(GRAPH Graph) | |
| { | |
| return Graph->nodes; | |
| } | |
| GRAPH graph_Create(void); | |
| void graph_Delete(GRAPH); | |
| GRAPHNODE graph_GetNode(GRAPH, NAT); | |
| GRAPHNODE graph_AddNode(GRAPH, NAT); | |
| void graph_AddEdge(GRAPHNODE, GRAPHNODE); | |
| void graph_DeleteEdge(GRAPHNODE, GRAPHNODE); | |
| void graph_DeleteDuplicateEdges(GRAPH); | |
| void graph_SortNodes(GRAPH, BOOL (*)(GRAPHNODE, GRAPHNODE)); | |
| NAT graph_StronglyConnectedComponents(GRAPH); | |
| void graph_NodePrint(GRAPHNODE Node); | |
| void graph_Print(GRAPH); | |
| #endif |