C++

Forum

 
Undirected acyclic graph creation algorithm

awhite1159 (17)
I have been trying to get this most difficult part of my Network Backup Simulator to work for over 2 months and now have a functional network simulator. The part I was tumbling on was how to create an undirected acyclic graph. I read about depth first search, breadth first search, topological sorting, cycle prevention but quite honestly had some difficulty comprehending the algorithms as described. So I designed what I believe is my own way of creating this data structure. It uses vertice locking to prevent backtracking, exchanging of edges between vertices being linked with cost evaluation during recursive dfs search, and dynamic route replace based on cost when creating new edges. I'm not sure if it has ever been done like this. Here is a sample of some of the verbose output when linking 9 vertices together in a row an then linking the two end vertices with a connecting edge:

(Is anyone aware of a similiar approach that is already in use?)

Network Backup Simulator (BkupSim) (c) 2008 AW Systems Inc.
<2>-Rtr registered as router 192.168.2.0
<2> registered as network 192.168.2.0
<3>-Rtr registered as router 192.168.3.0
<3> registered as network 192.168.3.0
<4>-Rtr registered as router 192.168.4.0
<4> registered as network 192.168.4.0
<5>-Rtr registered as router 192.168.5.0
<5> registered as network 192.168.5.0
<6>-Rtr registered as router 192.168.6.0
<6> registered as network 192.168.6.0
<7>-Rtr registered as router 192.168.7.0
<7> registered as network 192.168.7.0
<8>-Rtr registered as router 192.168.8.0
<8> registered as network 192.168.8.0
<9>-Rtr registered as router 192.168.9.0
<9> registered as network 192.168.9.0
<10>-Rtr registered as router 192.168.10.0
<10> registered as network 192.168.10.0
<11>-Rtr registered as router 192.168.11.0
<11> registered as network 192.168.11.0
TestServer2-NIC00 registered as NIC 192.168.5.2
TestServer6-NIC00 registered as NIC 192.168.11.1
<3> linked to <2>
<4> linked to <3>
<5> linked to <4>
<6> linked to <5>
<7> linked to <6>
<8> linked to <7>
<9> linked to <8>
Less costly route for <8>-Rtr to 192.168.3.0 found. Replacing.
Less costly route for <9>-Rtr to 192.168.3.0 found. Replacing.
Less costly route for <9>-Rtr to 192.168.4.0 found. Replacing.
Less costly route for <2>-Rtr to 192.168.7.0 found. Replacing.
Less costly route for <3>-Rtr to 192.168.8.0 found. Replacing.
Less costly route for <2>-Rtr to 192.168.8.0 found. Replacing.
Less costly route for <7>-Rtr to 192.168.2.0 found. Replacing.
Less costly route for <8>-Rtr to 192.168.2.0 found. Replacing.
Less costly route for <9>-Rtr to 192.168.2.0 found. Replacing.
Less costly route for <4>-Rtr to 192.168.9.0 found. Replacing.
Less costly route for <3>-Rtr to 192.168.9.0 found. Replacing.
Less costly route for <2>-Rtr to 192.168.9.0 found. Replacing.
<9> linked to <2>
Name......:<2>-Rtr
Type......:ROUTER
Node ID...:2
Thruput...:16000000
IP/NM/NET.:192.168.002.000| 192.168.002.000| 192.168.002.000 Locked:0
Routes===========================================================================>
192.168.3.0 via <3> (Hop/Cost=>1)
192.168.4.0 via <3> (Hop/Cost=>2)
192.168.5.0 via <3> (Hop/Cost=>3)
192.168.6.0 via <3> (Hop/Cost=>4)
192.168.7.0 via <9> (Hop/Cost=>3)
192.168.8.0 via <9> (Hop/Cost=>2)
192.168.9.0 via <9> (Hop/Cost=>1)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<3>-Rtr
Type......:ROUTER
Node ID...:4
Thruput...:16000000
IP/NM/NET.:192.168.003.000| 192.168.003.000| 192.168.003.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <2> (Hop/Cost=>1)
192.168.4.0 via <4> (Hop/Cost=>1)
192.168.5.0 via <4> (Hop/Cost=>2)
192.168.6.0 via <4> (Hop/Cost=>3)
192.168.7.0 via <4> (Hop/Cost=>4)
192.168.8.0 via <2> (Hop/Cost=>3)
192.168.9.0 via <2> (Hop/Cost=>2)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<4>-Rtr
Type......:ROUTER
Node ID...:6
Thruput...:16000000
IP/NM/NET.:192.168.004.000| 192.168.004.000| 192.168.004.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <3> (Hop/Cost=>2)
192.168.3.0 via <3> (Hop/Cost=>1)
192.168.5.0 via <5> (Hop/Cost=>1)
192.168.6.0 via <5> (Hop/Cost=>2)
192.168.7.0 via <5> (Hop/Cost=>3)
192.168.8.0 via <5> (Hop/Cost=>4)
192.168.9.0 via <3> (Hop/Cost=>3)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<5>-Rtr
Type......:ROUTER
Node ID...:8
Thruput...:16000000
IP/NM/NET.:192.168.005.000| 192.168.005.000| 192.168.005.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <4> (Hop/Cost=>3)
192.168.3.0 via <4> (Hop/Cost=>2)
192.168.4.0 via <4> (Hop/Cost=>1)
192.168.6.0 via <6> (Hop/Cost=>1)
192.168.7.0 via <6> (Hop/Cost=>2)
192.168.8.0 via <6> (Hop/Cost=>3)
192.168.9.0 via <6> (Hop/Cost=>4)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<6>-Rtr
Type......:ROUTER
Node ID...:10
Thruput...:16000000
IP/NM/NET.:192.168.006.000| 192.168.006.000| 192.168.006.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <5> (Hop/Cost=>4)
192.168.3.0 via <5> (Hop/Cost=>3)
192.168.4.0 via <5> (Hop/Cost=>2)
192.168.5.0 via <5> (Hop/Cost=>1)
192.168.7.0 via <7> (Hop/Cost=>1)
192.168.8.0 via <7> (Hop/Cost=>2)
192.168.9.0 via <7> (Hop/Cost=>3)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<7>-Rtr
Type......:ROUTER
Node ID...:12
Thruput...:16000000
IP/NM/NET.:192.168.007.000| 192.168.007.000| 192.168.007.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <8> (Hop/Cost=>3)
192.168.3.0 via <6> (Hop/Cost=>4)
192.168.4.0 via <6> (Hop/Cost=>3)
192.168.5.0 via <6> (Hop/Cost=>2)
192.168.6.0 via <6> (Hop/Cost=>1)
192.168.8.0 via <8> (Hop/Cost=>1)
192.168.9.0 via <8> (Hop/Cost=>2)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<8>-Rtr
Type......:ROUTER
Node ID...:14
Thruput...:16000000
IP/NM/NET.:192.168.008.000| 192.168.008.000| 192.168.008.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <9> (Hop/Cost=>2)
192.168.3.0 via <9> (Hop/Cost=>3)
192.168.4.0 via <7> (Hop/Cost=>4)
192.168.5.0 via <7> (Hop/Cost=>3)
192.168.6.0 via <7> (Hop/Cost=>2)
192.168.7.0 via <7> (Hop/Cost=>1)
192.168.9.0 via <9> (Hop/Cost=>1)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Name......:<9>-Rtr
Type......:ROUTER
Node ID...:16
Thruput...:16000000
IP/NM/NET.:192.168.009.000| 192.168.009.000| 192.168.009.000 Locked:0
Routes===========================================================================>
192.168.2.0 via <2> (Hop/Cost=>1)
192.168.3.0 via <2> (Hop/Cost=>2)
192.168.4.0 via <2> (Hop/Cost=>3)
192.168.5.0 via <8> (Hop/Cost=>4)
192.168.6.0 via <8> (Hop/Cost=>3)
192.168.7.0 via <8> (Hop/Cost=>2)
192.168.8.0 via <8> (Hop/Cost=>1)
End Routes=======================================================================>
MaxTPKB...:16000000
Use Count.:1

Duthomhas (13206)
I'm just a little lost on what exactly you want to know.

If it is how to store a the graph I would suggest a class with the following basic properties:
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
 
#include <deque>
#include <string>
#include <utility>  // std::pair

class t_GraphNode
  {
  public:
    enum t_NodeType {gnRouter, ...};

    std::string  Name;
    t_NodeType   NodeType;
    unsigned int ID;
    ...
    std::deque<t_RouteInfo> Routes;
    ...
  };

class t_GraphEdge: public std::pair<std::size_type, std::size_type> { };

class Graph
  {
  private:
    std::deque<t_GraphNode> f_Nodes;
    std::deque<t_GraphEdge> f_Edges;

  public:
    ...
  };

Hope this helps.
awhite1159 (17)
Duoas,

Thanks for replying. I have already implemented all the required classes to lay down the foundation for my network simulation program. At an abstract level, everything is a DataMover. I have network (vertice) objects, router (edge) objects, NetNodes objects all which derive from the base DataMover. The most difficult part of the system I came across was how to create a functional undirected acyclic graph. I was able to write the code to address this problem but was wondering if anyone has ever done it this way before. I don't believe I would have been able to get this working without all the benefits of C++ vs. C since I make use of polymorphism and the STL. I have been coding in C for a number of years strictly for fun but since January have read a number of books on C++ and object oriented coding. Grasping the concept and making change in my thought processes was difficult in the beginning but I see and am starting to benefit from the power C++ brings to the table.

The way I designed it, the router objects are DataMovers which also have two map members called:

map<Net, h_DM> route_list;
map<Net, int> route_cost;

The key field is the Net object which I use to simulate TCP/IP networking with IPs, and Netmasks. I had to make it two separate maps since the relationship is one to many for the network and the cost.

The route building does not create one central topologically sorted list. It instead uses chaining where the lists are built with recursive calls to the neighbors of each router. Each router views the graph as if it were the root. So when there is a vertice (network) that wants to send a message to another vertice, it consults its edge tables (router) which only knows of an adjacent neighbor that knows about this destination vertice. This continues on until the destination is reached.

I have to admit that after getting this to work after two months of designing and implementing various techniques, I was proud of what I had accomplished and made this post. I can post the code if anyone is interested. What I would really like is for someone to look at it and tell me if it has ever been done this way before. I read a number of technical papers on graph theory and my technique does not seem to be similiar to any technique used before. Maybe it is a combination of all the other techniques? I don't know.

Also, what I would really like to do is make this undirected acyclic graph functionality reusable by making it a template class. What would be the best way to take this code and redesign it as a template class?
Last edited on
Duthomhas (13206)
It seems that you have it under control.

My only concern was that route_list and route_cost might be duplicating Net objects, which would be the t_GraphNode thing in my example...

What it appears that you have done is separate the edge and its cost into two separate structures, instead of having a dedicated edge object (which was my t_GraphEdge, which could easily be written as a struct of the form
1
2
 
  unsigned source, target;  // indices into the list of Net objects
  int cost;

).
I doubt you are the first to do it this way though... (sorry) :-S

The only other concern, which I am pretty sure you handled, is preventing changes to the system from making the graph cyclic. If h_DM really is your edge object, then it should be trivial to check no matter which system you use...

In any case, if it is working and stable, don't waste time and money making it a template class. All things being equal, flexibility is already built into future structures of the same form but different elements --simply because a derived class can be used in place of the parent.

Good job.
awhite1159 (17)
Thanks Duoas. I was considering combining the separate structures into one. I probably will now that I am in a re-evaluation phase of what I have done so far. I have another question. This code as it is now runs as a console program and I wanted to have it run in a windowed gui environment. My past experience with this is with MFC and visual c++. What I did not like and want to avoid is tying myself into proprietary code that will only work on one platform. I have been looking at using Qt3. Does this seem like a good idea?
Duthomhas (13206)
If you can afford the licensing cost then yes, Qt is one of the nicest environments there are.

Otherwise you might want to check out the following pages:

The GUI Toolkit, Framework Page
http://www.free-soft.org/guitool/

Freebyte's Guide to Free Cross-Platform Programming
http://www.freebyte.com/programming/cross_platform/

Boost
http://www.boost.org/

Tcl/Tk
http://wiki.tcl.tk/

And finally, a common option is to make your own intermediate API and selectively compile the correct implementation for the environment.

The kind of stuff you are doing, though (network sniffing and the like) is typically a platform-dependent thing to do (AFAIK), so you'll have to consider whether or not it is worth the effort to support multiple platforms without specific targets in mind.

Hope this helps.
awhite1159 (17)
Working with Qt4 that I aquired from the www.trolltech.com website. They are the developers of the code and offer a commercial version or a GPL (free) version if it is for educational purposes. Works very nicely and is very easy to learn.

Thanks Duoas.
Topic archived. No new replies allowed.