← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/spass/oneiric

« back to all changes in this revision

Viewing changes to SPASS/graph.h

  • Committer: Bazaar Package Importer
  • Author(s): Roland Stigge
  • Date: 2010-06-27 18:59:28 UTC
  • mfrom: (1.1.1 upstream)
  • Revision ID: james.westby@ubuntu.com-20100627185928-kdjuqghv04rxyqmc
Tags: 3.7-1
New upstream release

Show diffs side-by-side

added added

removed removed

Lines of Context:
SPASS/graph.h
 
1
/**************************************************************/
 
2
/* ********************************************************** */
 
3
/* *                                                        * */
 
4
/* *                       GRAPHS                           * */
 
5
/* *                                                        * */
 
6
/* *  $Module:   GRAPH                                      * */ 
 
7
/* *                                                        * */
 
8
/* *  Copyright (C) 1998, 2001 MPI fuer Informatik          * */
 
9
/* *                                                        * */
 
10
/* *  This program is free software; you can redistribute   * */
 
11
/* *  it and/or modify it under the terms of the FreeBSD    * */
 
12
/* *  Licence.                                              * */
 
13
/* *                                                        * */
 
14
/* *  This program is distributed in the hope that it will  * */
 
15
/* *  be useful, but WITHOUT ANY WARRANTY; without even     * */
 
16
/* *  the implied warranty of MERCHANTABILITY or FITNESS    * */
 
17
/* *  FOR A PARTICULAR PURPOSE.  See the LICENCE file       * */ 
 
18
/* *  for more details.                                     * */
 
19
/* *                                                        * */
 
20
/* *                                                        * */
 
21
/* $Revision: 1.2 $                                     * */
 
22
/* $State: Exp $                                            * */
 
23
/* $Date: 2010-02-22 14:09:58 $                             * */
 
24
/* $Author: weidenb $                                         * */
 
25
/* *                                                        * */
 
26
/* *             Contact:                                   * */
 
27
/* *             Christoph Weidenbach                       * */
 
28
/* *             MPI fuer Informatik                        * */
 
29
/* *             Stuhlsatzenhausweg 85                      * */
 
30
/* *             66123 Saarbruecken                         * */
 
31
/* *             Email: spass@mpi-inf.mpg.de                * */
 
32
/* *             Germany                                    * */
 
33
/* *                                                        * */
 
34
/* ********************************************************** */
 
35
/**************************************************************/
 
36
 
 
37
 
 
38
/* $RCSfile: graph.h,v $ */
 
39
 
 
40
#ifndef _GRAPH_
 
41
#define _GRAPH_
 
42
 
 
43
#include "list.h"
 
44
 
 
45
typedef struct {
 
46
  NAT     number;
 
47
  int     dfs_num;
 
48
  int     comp_num;  /* completion number */
 
49
  POINTER info;      /* user defined information */
 
50
  LIST    neighbors;
 
51
} GRAPHNODE_STRUCT, *GRAPHNODE;
 
52
 
 
53
typedef struct {
 
54
  NAT  size;       /* number of nodes */
 
55
  LIST nodes;      /* list of GRAPHNODES */
 
56
  NAT  dfscount;   /* used for DFS */
 
57
  NAT  compcount;  /* used for DFS */
 
58
} GRAPH_STRUCT, *GRAPH;
 
59
 
 
60
static __inline__ NAT graph_NodeNumber(GRAPHNODE Node)
 
61
{
 
62
  return Node->number;
 
63
}
 
64
 
 
65
static __inline__ int graph_NodeDfsNum(GRAPHNODE Node)
 
66
{
 
67
  return Node->dfs_num;
 
68
}
 
69
 
 
70
static __inline__ void graph_NodeSetDfsNum(GRAPHNODE Node, int Number)
 
71
{
 
72
  Node->dfs_num = Number;
 
73
}
 
74
 
 
75
static __inline__ int graph_NodeCompNum(GRAPHNODE Node)
 
76
{
 
77
  return Node->comp_num;
 
78
}
 
79
 
 
80
static __inline__ void graph_NodeSetCompNum(GRAPHNODE Node, int Number)
 
81
{
 
82
  Node->comp_num = Number;
 
83
}
 
84
 
 
85
static __inline__ LIST graph_NodeNeighbors(GRAPHNODE Node)
 
86
{
 
87
  return Node->neighbors;
 
88
}
 
89
 
 
90
static __inline__ POINTER graph_NodeInfo(GRAPHNODE Node)
 
91
{
 
92
  return Node->info;
 
93
}
 
94
 
 
95
static __inline__ void graph_NodeSetInfo(GRAPHNODE Node, POINTER Info)
 
96
{
 
97
  Node->info = Info;
 
98
}
 
99
 
 
100
static __inline__ NAT graph_NodeOutdegree(GRAPHNODE Node)
 
101
{
 
102
  return list_Length(graph_NodeNeighbors(Node));
 
103
}
 
104
 
 
105
static __inline__ BOOL graph_NodeVisited(GRAPHNODE Node)
 
106
{
 
107
  return graph_NodeDfsNum(Node) >= 0;
 
108
}
 
109
 
 
110
static __inline__ BOOL graph_NodeCompleted(GRAPHNODE Node)
 
111
{
 
112
  return graph_NodeCompNum(Node) >= 0;
 
113
}
 
114
 
 
115
static __inline__ NAT graph_Size(GRAPH Graph)
 
116
{
 
117
  return Graph->size;
 
118
}
 
119
 
 
120
static __inline__ LIST graph_Nodes(GRAPH Graph)
 
121
{
 
122
  return Graph->nodes;
 
123
}
 
124
 
 
125
GRAPH     graph_Create(void);
 
126
void      graph_Delete(GRAPH);
 
127
 
 
128
GRAPHNODE graph_GetNode(GRAPH, NAT);
 
129
GRAPHNODE graph_AddNode(GRAPH, NAT);
 
130
 
 
131
void      graph_AddEdge(GRAPHNODE, GRAPHNODE);
 
132
void      graph_DeleteEdge(GRAPHNODE, GRAPHNODE);
 
133
void      graph_DeleteDuplicateEdges(GRAPH);
 
134
 
 
135
void      graph_SortNodes(GRAPH, BOOL (*)(GRAPHNODE, GRAPHNODE));
 
136
NAT       graph_StronglyConnectedComponents(GRAPH);
 
137
 
 
138
void      graph_NodePrint(GRAPHNODE Node);
 
139
void      graph_Print(GRAPH);
 
140
 
 
141
#endif