Graphviz  2.41.20170921.2350
circuit.c
Go to the documentation of this file.
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 
22 int 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 
41 int 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 }
#define AGSEQ(obj)
Definition: cgraph.h:115
CGRAPH_API Agedge_t * agfstedge(Agraph_t *g, Agnode_t *n)
Definition: edge.c:86
CGRAPH_API Agnode_t * agtail(Agedge_t *e)
Definition: edge.c:525
CGRAPH_API Agnode_t * agnxtnode(Agraph_t *g, Agnode_t *n)
Definition: node.c:45
CGRAPH_API Agnode_t * aghead(Agedge_t *e)
Definition: edge.c:533
#define GD_dist(g)
Definition: types.h:360
void free_array(double **rv)
Definition: stuff.c:63
double ** new_array(int i, int j, double val)
Definition: stuff.c:46
CGRAPH_API Agnode_t * agfstnode(Agraph_t *g)
Definition: node.c:38
CGRAPH_API Agedge_t * agnxtedge(Agraph_t *g, Agedge_t *e, Agnode_t *n)
Definition: edge.c:95
int matinv(double **A, double **Ainv, int n)
Definition: matinv.c:42
EXTERN unsigned char Verbose
Definition: globals.h:64
int circuit_model(graph_t *g, int nG)
Definition: circuit.c:41
int solveCircuit(int nG, double **Gm, double **Gm_inv)
Definition: circuit.c:22
#define ED_dist(e)
Definition: types.h:605