1/* $Id$Revision: */
2/* vim:set shiftwidth=4 ts=8: */
3
4/*************************************************************************
5 * Copyright (c) 2011 AT&T Intellectual Property
6 * All rights reserved. This program and the accompanying materials
7 * are made available under the terms of the Eclipse Public License v1.0
8 * which accompanies this distribution, and is available at
9 * http://www.eclipse.org/legal/epl-v10.html
10 *
11 * Contributors: See CVS logs. Details at http://www.graphviz.org/
12 *************************************************************************/
13
14#ifndef SEARCH_G_H
15#define SEARCH_G_H
16
17#include "structures.h"
18
19typedef struct snode snode;
20typedef struct sedge sedge;
21
22struct snode {
23 int n_val, n_idx;
24 snode* n_dad;
25 sedge* n_edge;
26 short n_adj;
27 short save_n_adj;
28 struct cell* cells[2];
29
30 /* edges incident on this node
31 * -- stored as indices of the edges array in the graph
32 */
33 int* adj_edge_list;
34 int index;
35 boolean isVert; /* true if node corresponds to vertical segment */
36};
37
38struct sedge {
39 double weight; /* weight of edge */
40 int cnt; /* paths using edge */
41 /* end-points of the edge
42 * -- stored as indices of the nodes vector in the graph
43 */
44 int v1, v2;
45};
46
47typedef struct {
48 int nnodes, nedges;
49 int save_nnodes, save_nedges;
50 snode* nodes;
51 sedge* edges;
52} sgraph;
53
54extern void reset(sgraph*);
55extern void gsave(sgraph*);
56extern sgraph* createSGraph(int);
57extern void freeSGraph (sgraph*);
58extern void initSEdges (sgraph* g, int maxdeg);
59extern int shortPath (sgraph* g, snode* from, snode* to);
60extern snode* createSNode (sgraph*);
61extern sedge* createSEdge (sgraph* g, snode* v0, snode* v1, double wt);
62
63#endif
64