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 MULTILEVEL_H
15#define MULTILEVEL_H
16
17#include "SparseMatrix.h"
18
19typedef struct Multilevel_struct *Multilevel;
20
21struct Multilevel_struct {
22 int level;/* 0, 1, ... */
23 int n;
24 SparseMatrix A;/* the weighting matrix */
25 SparseMatrix D;/* the distance matrix. A and D should have same pattern,
26 but different entry values. For spring-electrical method, D = NULL. */
27 SparseMatrix P;
28 SparseMatrix R;
29 real *node_weights;
30 Multilevel next;
31 Multilevel prev;
32 int delete_top_level_A;
33 int coarsen_scheme_used;/* to get from previous level to here */
34};
35
36enum {MAX_IND_VTX_SET_U = -100, MAX_IND_VTX_SET_F = -1, MAX_IND_VTX_SET_C = 0};
37
38enum {MAX_CLUSTER_SIZE = 4};
39
40enum {EDGE_BASED_STA, COARSEN_INDEPENDENT_EDGE_SET, COARSEN_INDEPENDENT_EDGE_SET_HEAVEST_EDGE_PERNODE, COARSEN_INDEPENDENT_EDGE_SET_HEAVEST_EDGE_PERNODE_LEAVES_FIRST, COARSEN_INDEPENDENT_EDGE_SET_HEAVEST_EDGE_PERNODE_SUPERNODES_FIRST, COARSEN_INDEPENDENT_EDGE_SET_HEAVEST_EDGE_PERNODE_DEGREE_SCALED, COARSEN_INDEPENDENT_EDGE_SET_HEAVEST_CLUSTER_PERNODE_LEAVES_FIRST, EDGE_BASED_STO, VERTEX_BASED_STA, COARSEN_INDEPENDENT_VERTEX_SET, COARSEN_INDEPENDENT_VERTEX_SET_RS, VERTEX_BASED_STO, COARSEN_HYBRID};
41
42enum {COARSEN_MODE_GENTLE, COARSEN_MODE_FORCEFUL};
43
44struct Multilevel_control_struct {
45 int minsize;
46 real min_coarsen_factor;
47 int maxlevel;
48 int randomize;
49 int coarsen_scheme;
50 int coarsen_mode;
51};
52
53typedef struct Multilevel_control_struct *Multilevel_control;
54
55Multilevel_control Multilevel_control_new(int scheme, int mode);
56
57void Multilevel_control_delete(Multilevel_control ctrl);
58
59void Multilevel_delete(Multilevel grid);
60
61Multilevel Multilevel_new(SparseMatrix A, SparseMatrix D, real *node_weights, Multilevel_control ctrl);
62
63Multilevel Multilevel_get_coarsest(Multilevel grid);
64
65void print_padding(int n);
66
67#define Multilevel_is_finest(grid) (!((grid)->prev))
68#define Multilevel_is_coarsest(grid) (!((grid)->next))
69
70void Multilevel_coarsen(SparseMatrix A, SparseMatrix *cA, SparseMatrix D, SparseMatrix *cD, real *node_wgt, real **cnode_wgt,
71 SparseMatrix *P, SparseMatrix *R, Multilevel_control ctrl, int *coarsen_scheme_used);
72#endif
73