-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathBlogGraphOld.html
169 lines (157 loc) · 8.5 KB
/
BlogGraphOld.html
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
<!DOCTYPE html>
<html>
<head>
<!--
- BlogGraph.htm - Code Artist Thoughts
- ver 1.2 - 15 August 2013
- Jim Fawcett, Syracuse University
-->
<meta http-equiv="content-type" content="text/html;charset=UTF-8" />
<meta name="description" content="Software Engineering course notes. Code Samples. Software Links" />
<meta name="keywords" content="Lecture, Notes, Code, Syracuse,University" />
<meta name="Author" content="Jim Fawcett" />
<meta name="Author" content="James Fawcett" />
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<title>Blog.Graph</title>
<script src="js/ScriptsUtilities.js"></script>
<script src="js/ScriptsTemplate.js"></script>
<script src="js/ScriptsKeyboard.js"></script>
<script src="js/ScriptsMenu.js"></script>
<link rel="stylesheet" href="css/StylesTemplate.css" />
<link rel="stylesheet" href="css/StylesDefault.css" />
<link rel="stylesheet" href="css/StylesMenu.css" />
<link rel="stylesheet" href="css/StylesBrownTheme.css" />
<style>
#github header {
margin-left: 0px;
margin-right: 0px;
}
#github #pagetitle {
background-color: #e3dac9;
color: #800020;
border: 1px solid maroon;
}
#github #title {
background-color: #e3dac9;
color: #3f000f;
}
</style>
</head>
<body id="github" onload="initializeMenu()">
<navKeys-Container>
<nav-Key id="sKey" onclick="toggleSwipeEvents()">S</nav-Key>
<nav-Key id="rKey" onclick="location.reload()">R</nav-Key>
<nav-Key id="tKey" onclick="scrollPageTop()">T</nav-Key>
<nav-Key id="bKey" onclick="scrollPageBottom()">B</nav-Key>
<nav-Key id="hKey" onclick="helpWin()">H</nav-Key>
<nav-Key id="pKey" onclick="loadPrev()">P</nav-Key>
<nav-Key id="nKey" onclick="loadNext()">N</nav-Key>
</navKeys-Container>
<nav>
<div id="navbar"></div>
</nav>
<a id="Next" href="BlogFileSystem.html">N</a>
<a id="Prev" href="BlogMTree.html">P</a>
<header>
<hgroup id="pagetitle">
<h1 id="title">Code Artistry - C++ Graph Library</h1>
</hgroup>
</header>
<!-- page content -->
<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 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 style="width:calc(100vw - 9rem);">
<div class="right photo" style="margin:10px; padding:20px; border:1px solid black;">
<img src="Pictures/StdAdjList.png" name="AdjList" width="400" onmouseover="AdjList.width='600'" onmouseout="AdjList.width='400'" />
</div>
</div>
<div style="width:calc(100vw - 9rem);">
<div class="right photo" style="margin:10px; padding:20px; border:1px solid black; clear:both">
<img src="Pictures/graphStruct.png" name="GraphStruct" width="400" onmouseover="GraphStruct.width='800'" onmouseout="GraphStruct.width='400'" />
</div>
</div>
<div style="width:calc(100vw - 9rem);">
<div class="right photo" style="margin:10px; padding:20px; border:1px solid black; clear:both">
<img src="Pictures/graph.png" name="classes" width="400" onmouseover="classes.width='600'" onmouseout="classes.width='400'" />
</div>
</div>
<h3>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>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>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 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>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 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>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>
<info-bar></info-bar>
</body>
</html>