Mercurial > hg > camir-aes2014

annotate core/tools/Graph.m @ 0:e9a9cd732c1e tip

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
rev   line source
wolffd@0 1 % GENERAL GRAPH THEORY CLASS
wolffd@0 2 %
wolffd@0 3 % CAVE: Any special application oriented stuff
wolffd@0 4 % should be outside here
wolffd@0 5
wolffd@0 6 classdef Graph < DiGraph
wolffd@0 7
wolffd@0 8 methods
wolffd@0 9
wolffd@0 10 % ---
wolffd@0 11 % Constructor
wolffd@0 12 % ---
wolffd@0 13 function G = Graph(V, E)
wolffd@0 14
wolffd@0 15 if nargin == 1
wolffd@0 16 % ---
wolffd@0 17 % this uses an imput grpaph
wolffd@0 18 % to create a new graph
wolffd@0 19 % ---
wolffd@0 20 G = Graph.copy(V);
wolffd@0 21
wolffd@0 22 elseif nargin == 2
wolffd@0 23
wolffd@0 24 if numel(V) == size(V,2)
wolffd@0 25 G.V = V;
wolffd@0 26 else
wolffd@0 27 G.V = V';
wolffd@0 28 end
wolffd@0 29
wolffd@0 30 G.E = E;
wolffd@0 31 end
wolffd@0 32 end
wolffd@0 33 function w = edge(G, V1, V2)
wolffd@0 34
wolffd@0 35 sm = min([V1, V2]);
wolffd@0 36 bg = max([V1, V2]);
wolffd@0 37
wolffd@0 38 w = G.E(sm, bg);
wolffd@0 39 end
wolffd@0 40
wolffd@0 41 % ---
wolffd@0 42 % add an edge
wolffd@0 43 % the undirected case: G.E is triangular
wolffd@0 44 % ---
wolffd@0 45 function add_edge(G, V1, V2, weight)
wolffd@0 46
wolffd@0 47 G.add_node(V1);
wolffd@0 48 G.add_node(V2);
wolffd@0 49
wolffd@0 50 sm = min([V1, V2]);
wolffd@0 51 bg = max([V1, V2]);
wolffd@0 52
wolffd@0 53 if G.E(sm, bg) == 0
wolffd@0 54
wolffd@0 55 % save weight
wolffd@0 56 G.E(sm, bg) = weight;
wolffd@0 57 else
wolffd@0 58
wolffd@0 59 join_edge(G, V1, V2, weight);
wolffd@0 60 end
wolffd@0 61 end
wolffd@0 62
wolffd@0 63 % remove an edge
wolffd@0 64 function remove_edge(G, V1, V2)
wolffd@0 65
wolffd@0 66 sm = min([V1, V2]);
wolffd@0 67 bg = max([V1, V2]);
wolffd@0 68
wolffd@0 69 G.E(sm,bg) = 0;
wolffd@0 70 end
wolffd@0 71
wolffd@0 72 % ---
wolffd@0 73 % sets the edge without considering earlier weights
wolffd@0 74 % ---
wolffd@0 75 function set_edge(G, V1, V2, weight)
wolffd@0 76
wolffd@0 77 sm = min([V1, V2]);
wolffd@0 78 bg = max([V1, V2]);
wolffd@0 79
wolffd@0 80 G.E(sm, bg) = weight;
wolffd@0 81
wolffd@0 82 end
wolffd@0 83
wolffd@0 84 % ---
wolffd@0 85 % Graph-specific functions
wolffd@0 86 % in the undirected case, these are the same
wolffd@0 87 % ---
wolffd@0 88 function c = children(G, Vid)
wolffd@0 89
wolffd@0 90 c = [find(G.E(Vid,:) > 0) find(G.E(:,Vid) > 0)'];
wolffd@0 91 end
wolffd@0 92
wolffd@0 93 function p = parents(G, Vid)
wolffd@0 94
wolffd@0 95 p = [find(G.E(Vid,:) > 0) find(G.E(:,Vid) > 0)'];
wolffd@0 96 end
wolffd@0 97
wolffd@0 98 % ---
wolffd@0 99 % Vertex Degree
wolffd@0 100 % ---
wolffd@0 101 function out = degree(G, V)
wolffd@0 102
wolffd@0 103 out = sum(G.E(V,:) > 0) + sum(G.E(:,V) > 0);
wolffd@0 104 end
wolffd@0 105
wolffd@0 106 % ---
wolffd@0 107 % Vertex Degree
wolffd@0 108 % ---
wolffd@0 109 function out = degree_in(G, V)
wolffd@0 110
wolffd@0 111 out = sum(G.E(V,:) > 0) + sum(G.E(:,V) > 0);
wolffd@0 112 end
wolffd@0 113
wolffd@0 114 % ---
wolffd@0 115 % Vertex Degree
wolffd@0 116 % ---
wolffd@0 117 function out = degree_out(G, V)
wolffd@0 118
wolffd@0 119 out = sum(G.E(:,V) > 0) + sum(G.E(:,V) > 0);
wolffd@0 120 end
wolffd@0 121
wolffd@0 122 end
wolffd@0 123
wolffd@0 124
wolffd@0 125 methods (Static)
wolffd@0 126 function G = copy(Gin)
wolffd@0 127
wolffd@0 128 if strcmp(class(Gin), 'Graph')
wolffd@0 129
wolffd@0 130 G = Graph(Gin.V, Gin.E);
wolffd@0 131 G.Vlbl = Gin.Vlbl;
wolffd@0 132
wolffd@0 133 else
wolffd@0 134 warning ('cannot copy graph, casting instead')
wolffd@0 135 G = Graph.cast(Gin);
wolffd@0 136 end
wolffd@0 137
wolffd@0 138 end
wolffd@0 139
wolffd@0 140 function G = cast(Gin)
wolffd@0 141
wolffd@0 142 % ---
wolffd@0 143 % this uses an imput grpaph
wolffd@0 144 % to create a new digraph
wolffd@0 145 % ---
wolffd@0 146 G = Graph();
wolffd@0 147
wolffd@0 148 % ---
wolffd@0 149 % Add the input graph to the empty one
wolffd@0 150 % ---
wolffd@0 151 G.add_graph(Gin);
wolffd@0 152 end
wolffd@0 153 end
wolffd@0 154 end