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/*
15 * this implements the resistor circuit current model for
16 * computing node distance, as an alternative to shortest-path.
17 * likely it could be improved by using edge weights, somehow.
18 * Return 1 if successful; 0 otherwise (e.g., graph is disconnected).
19 */
20#include "neato.h"
21
22int solveCircuit(int nG, double **Gm, double **Gm_inv)
23{
24 double sum;
25 int i, j;
26
27 if (Verbose)
28 fprintf(stderr, "Calculating circuit model");
29
30 /* set diagonal entries to sum of conductances but ignore nth node */
31 for (i = 0; i < nG; i++) {
32 sum = 0.0;
33 for (j = 0; j < nG; j++)
34 if (i != j)
35 sum += Gm[i][j];
36 Gm[i][i] = -sum;
37 }
38 return matinv(Gm, Gm_inv, nG - 1);
39}
40
41int circuit_model(graph_t * g, int nG)
42{
43 double **Gm;
44 double **Gm_inv;
45 int rv;
46 long i, j;
47 node_t *v;
48 edge_t *e;
49
50 Gm = new_array(nG, nG, 0.0);
51 Gm_inv = new_array(nG, nG, 0.0);
52
53 /* set non-diagonal entries */
54 for (v = agfstnode(g); v; v = agnxtnode(g, v)) {
55 for (e = agfstedge(g, v); e; e = agnxtedge(g, e, v)) {
56 i = AGSEQ(agtail(e));
57 j = AGSEQ(aghead(e));
58 if (i == j)
59 continue;
60 /* conductance is 1/resistance */
61 Gm[i][j] = Gm[j][i] = -1.0 / ED_dist(e); /* negate */
62 }
63 }
64
65 rv = solveCircuit(nG, Gm, Gm_inv);
66
67 if (rv)
68 for (i = 0; i < nG; i++) {
69 for (j = 0; j < nG; j++) {
70 GD_dist(g)[i][j] =
71 Gm_inv[i][i] + Gm_inv[j][j] - 2.0 * Gm_inv[i][j];
72 }
73 }
74 free_array(Gm);
75 free_array(Gm_inv);
76 return rv;
77}
78