-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBlogGraph.html
More file actions
255 lines (244 loc) · 12.7 KB
/
BlogGraph.html
File metadata and controls
255 lines (244 loc) · 12.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
<!DOCTYPE html>
<html>
<!--
BlogGraph.html
-->
<head>
<title>Blog Graph</title>
<meta name="viewport" content="width=device-width, initial-scale=1" />
<!-- <link rel="icon" type="image/x-icon" href="./images/favicon.ico" /> -->
<link rel="stylesheet" href="css/StylesPhoto.css" />
<link rel="stylesheet" href="css/StylesSizerComp.css" />
<!-- PageFrame infrastructure -->
<link rel="stylesheet" href="css/StylesPageFrameDefaults.css" />
<link rel="stylesheet" href="css/StylesPageFrameStructure.css" />
<link rel="stylesheet" href="css/StylesPageFrameMenus.css" />
<link rel="stylesheet" href="css/StylesPageFrameThemePython.css" />
<link rel="stylesheet" href="css/StylesWebComponents.css" />
<script src="js/ScriptsWebComponents.js"></script>
<!--<script src="js/ScriptsPageFrameDefaults.js"></script>-->
<script src="js/ScriptsPageFramePosts.js"></script>
<script src="js/ScriptsPageFramePagesPosts.js"></script>
<script src="js/ScriptsPageFrameKeyboard.js"></script>
<!-- <script src="js/ScriptsSizerComp.js"></script> -->
<!-- No need for Pages script for pages with no next or prev pages -->
<!--<script src="js/ScriptsPageFramePages.js"></script>-->
<!-- <script src="js/ScriptsTemplate.js"></script>
<link rel="stylesheet" href="css/StylesTemplate.css" /> -->
<style>
h3 {
margin-top: 1.5em;
}
#subtitle {
margin-top: 0.4em;
margin-bottom: 0.3em;
}
#github header summary {
border: 1px solid var(--light);
}
#github summary {
padding-right: 2em;
}
/* #github .menuHead {
margin:0em -0.25em 0.0em -0.25em;
padding:0.25em 0.5em;
} */
</style>
<script>
function load() {
initialize();
//loadif();
}
</script>
<style>
#github note {
display: block;
width:max-content;
border:1px solid red;
padding:0.5em 1.0em;
margin:0.5em 0em;
}
#github .bargraph {
border: 1px solid var(--dark);
/* background-color: #bbb; */
padding: 0.1em 0.5em;
font-size:0.9em;
}
#github table {
border:2px solid var(--dark);
}
#github table td {
padding:0.25em 1.0em;
border:none;
}
body {
user-select:none;
}
</style>
<script>
function clickstat() {
// prevent parent click event handling
event.stopImmediatePropagation();
}
</script>
</head>
<body id="github" onload="load()" style="position:relative;">
<a id="Next" href="BlogFileSystem.html">Next</a>
<a id="Prev" href="BlogMTree.html">Prev</a>
<page-frame>
<frame-header>
<nav id="navbar"></nav>
</frame-header>
<main id="main">
<div id="about" onclick="this.style.display = 'none'">about</div>
<div id="page">Blog: Graph</div>
<div id="modified">11/29/2024</div>
<div id="hlp"></div>
<a id="top"></a>
<content style="height:100vh; position:relative;">
<header style="cursor:pointer;" onclick="loadif()">
<!-- <a target="_blank" class="repoLink" href="https://github.com/JimFawcett">github Repositories</a> -->
<hgroup id="pagetitle" style="border: 2px solid var(--dark);">
<h1 id="title">Blog: Graph</h1>
<h3 class="indent" id="subtitle">
directed graph, vector arena
</h3>
</hgroup>
<!-- <img style="width:100%; margin:-0.1em 0em; border:2px solid var(--dark); padding:0.5em; background-color:var(--light);" src="Pictures/officestrip3a.svg" /> -->
<div class="darkItem" onclick="loadif()" style="cursor:pointer; position:relative; padding:0.0em 0em 0.25em 0em; margin-top:-0.50em; border:2px solid var(--dark);">
<a class="repoLinks" target="_blank" href="https://github.com/JimFawcett" style="color:var(--atten); margin-left:1.5em;">About</a>
<div style="font-size:0.9em; position:absolute; top:0.1em; right:1.5em;">click to toggle Site Explorer</div>
<div style="height:0.5em;"></div>
</div>
</header>
<h3>Initial Thoughts:</h3>
<t-b>
A graph, of the kind discussed here, is a collection of vertices connected by edges. We'll be concerned exclusively with directed graphs where each edge
has a direction from its parent vertex to some child vertex in the collection. Directed graphs are particularly useful for describing large sets of relationships.
Here are some example graph models:
</t-b>
<ul class="indent" style="margin-top:0px; padding-top:0px;">
<li>
Build dependency relationships between software packages
</li>
<li>
Calling relationships between functions in a program
</li>
<li>
Relationships between types in a system, e.g., inheritance, composition, aggregation, and using
</li>
<li>
Communication connections, e.g., web hosts and client machines
</li>
</ul>
<t-b>
Frequently graph models are very large, as in
<a target="_blank" href="http://www.caida.org/tools/visualization/walrus/gallery1/">models of the internet developed by "The Cooperative Association for Internet Data Analysis" (CAIDA)</a>.
Therefore, we will be particularly interested in means to persist models to and from disk storage, to make storage parsimonius, and design operations to be as efficient as is reasonably practical.
</t-b>
<div class="right">
<photosizer-block src="Pictures/StdAdjList.png" width="350" class="photoSizerBlock">
<span style="font-family:'Comic Sans MS';">Figure 1. - Graph Adjacency List</span>
</photosizer-block>
</div>
<div class="right clear">
<photosizer-block src="Pictures/graphStruct.png" width="350" class="photoSizerBlock">
<span style="font-family:'Comic Sans MS';">Figure 2. - Graph Structure</span>
</photosizer-block>
</div>
<div class="right clear">
<photosizer-block src="Pictures/graph.png" width="350" class="photoSizerBlock">
<span style="font-family:'Comic Sans MS';">Figure 3. - Graph Classes</span>
</photosizer-block>
</div>
<h3 id="concept">A C++ Template-based Graph Facility</h3>
<t-b>
Frequently graph structures are discussed in terms of adjacency lists like the example in the first diagram. Note that the adjacency list holds redundant nodes to
represent graph vertices, e.g., there are three nodes that represent vertex 4 in the diagram.
</t-b>
<t-b>
We won't want to directly implement this structure, not only because of
the unnecessary storage, but also because that opens up the possiblity of two or more representations of a node having different properties and values. When there are
storage redundancies errors like that are relatively easy to make and often very difficult to find.
</t-b>
<t-b>
The linked structure shown in the next diagram is preferable. It has no redundancies - each vertex holds references to child vertices, where both parent and children
reside in the same collection. These references could be implemented with pointers, but we will choose not to do that, and use indexes into the adjacency collection
to refer to child vertices. That makes creation of copies trivial. In fact, the compiler created member-wise copy constructor and assignment operator will be
correct for that design.
</t-b>
<h3 id="design">Design:</h3>
<t-b>The Graph's logical structure is shown in the third diagram. The graph class is template-based with parameters V, a vertex type, and E, an edge type.</t-b>
<t-b>These could simply be strings that label vertices and edges. In this case a vertex might represent a town on a map with edges that are roads from that town to another.</t-b>
<t-b>
Often, however, we may need a vertex or an edge to hold composite information containing several different values. In this case we simply define
a V class and/or an E class with the appropriate structure to hold that information.
</t-b>
<t-b>
The graph holds a collection of vertices in a std::vector<Vertex<V,E>>, named adj for adjacency list. Each vertex holds an instance of the V type and a collection of edges
in a std::vector<Edge>. An edge is simply a typedef for std::pair<size_t, E>. The size_t argument is an index into the graph's vertex collection, selecting the edge's
target vertex. The E argument is an instance of the E type, so each edge can hold a unique instance.
</t-b>
<t-b>
Simple XmlReader and XmlWriter classes are part of the graphLib archive and are used to create and retrieve graph models from disk storage.
These are not Document Object Model (DOM) based, but
simply implemented with string manipulation and a scope stack. You may find these usesful for other applicatations as well.
</t-b>
<h3 id="code">Source Code:</h3>
<t-b>
This graph implementation is written in C++ using Visual Studio 2013. It should port, with little difficulty, to Gnu gcc to run on Linux, for example.
<div class="indent" style="margin:10px;"><a target="_blank" href="../Research/Code/DirectedGraph">Directed Graph Library</a></div>
This code bears a copyright © that grants all rights to users except the right to publish and requires retention of the copyright notice.
</t-b>
<h3 id="contributions">Contributions</h3>
<t-b>
One of my doctoral advisees, Mehmet Kaya developed strong component and topological softing algorithms for this graph class. He has been using
that to help develop new ways of restructuring C++ source code to improve its structure and maintainability. Here is a Syracuse University
<a target="_blank" href="http://surface.syr.edu/eecs_techreports/73/">Technical Report</a> describing that work. Another advisee, Mubarek Mohammed, is using the
graph class to support research on visualization for large software systems.
</t-b>
<h3 id="conclusions">Conclusions:</h3>
<t-b>
This graph class implementation is reasonably simple, fast, and robust. It supports persisting graph models to XML data files and retrieving back
into graph instances. We have an interest in algorithms, based on this graph facility, that support investigations into the structure and dynamics
of large systems. We will add algorithms we are working with to this package as they mature.
<t-b>
<div style="width:calc(100vw - 9rem);"><img class="photo" src="Pictures/newhouse2.jpg" alt="Newhouse" style="width:100%;" /></div>
</t-b>
<div style="height:1.0em;"></div>
<a id="bottom"></a>
</content>
<page-TOC id="pages" style="display:none;">
</page-TOC>
<page-sections id="sections" style="display:none;">
<menu-elem style="width:0.0em"> </menu-elem>
<menu-elem class="secElem"><a href="#bottom">bottom</a></menu-elem>
<menu-elem class="secElem"><a href="#conclusions">conclusions</a></menu-elem>
<menu-elem class="secElem"><a href="#contributions">contributions</a></menu-elem>
<menu-elem class="secElem"><a href="#code">code</a></menu-elem>
<menu-elem class="secElem"><a href="#design">design</a></menu-elem>
<menu-elem class="secElem"><a href="#concept">concept</a></menu-elem>
<menu-elem class="secElem"><a href="#top">top</a></menu-elem>
<div class='darkItem popupHeader' style="padding:0.25em 2.0em;" onclick="this.parentElement.style.display='none'">Sections</div>
</page-sections>
</main>
<frame-footer>
<menu-item style="width:2.0em;"> </menu-item>
<menu-elem id="nextLink2" onclick="bottomMenu.next()">Next</menu-elem>
<menu-elem id="prevLink2" onclick="bottomMenu.prev()">Prev</menu-elem>
<menu-elem id="pgbtn" onclick="bottomMenu.pages()">Pages</menu-elem>
<menu-elem onclick="bottomMenu.sections()">Sections</menu-elem>
<menu-elem onclick="bottomMenu.about()">About</menu-elem>
<menu-elem id="kysbtn" onclick="storyHlpMenu.keys()">Keys</menu-elem>
<menu-elem style="margin-right:1em">
<span id="loc" style="display:inline-block; font-weight:normal"></span>
</menu-elem>
</frame-footer>
</page-frame>
<script>
let loc = document.getElementById("loc");
let fn = window.location.href.split(/\/|\\/).pop();
loc.innerHTML = fn + ":";
</script>
</body>
</html>