Re: Data structures using protocol buffers
Abstractly, a lot of graph algorithms fall into this paradigm:
foreach node in the graph
neighbors = getNeighbors(graph, node);
doSomething(node, neighbors);
end
I am trying to parallelize this operation for large graphs with
millions of nodes. So, one approach would be to partition the graph
nodes and have a mapper operate on each partition. The representation
I'm seeking is one which will allow me to access the neighbors of a
node and read/write to their attributes.
On Oct 23, 4:44 pm, Dave Bailey <[EMAIL PROTECTED]> wrote:
> Sounds like fun. Just curious what is actually supposed to be encoded
> in the protobuf message, if the graph is too big to fit in memory?
> Are you sending just a single node, with its edges? It seems like you
> wouldn't be able to avoid scenarios where some of the edges in your
> message point to nodes that are not also serialized in your message,
> given that you can't actually store the entire graph in memory, let
> alone a protobuf message? What graph operations are you looking to
> parallelize?
>
> -dave
>
> On Oct 23, 12:12 am, GDR <[EMAIL PROTECTED]> wrote:
>
> > Thanks. I am trying to use protocol buffers with a map reduce
> > framework to work on large graphs. The graphs are too big to fit in
> > memory so building auxiliary data structures is difficult. Any ideas?
>
> > On Oct 22, 2:48 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>
> > > Protocol Buffers are a serialization format, rather than general-purpose
> > > data structures. To do computations, you'd probably want to build some
> > > auxiliary data structures, which you populate when you deserialize the
> > > protobuf data. You could have node objects that resemble your original
> > > .proto file, where nodes have references to their neighbors, and you'd
> > > probably need a map from node id to node object reference, which you'd
> > > use during deserialization.
>
> > > --
> > > Jeremy Leader
> > > [EMAIL PROTECTED]
>
> > > GDR wrote:
> > > > my bad. The code snippet should be as follows:
>
> > > > for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
> > > > double sum = 0;
> > > > int count = 0;
> > > > for(UndirectedGraphNodeReference neighbor :
> > > > node.getNeighborsList() ) {
> > > > sum +=
> > > > count++;
> > > > }
> > > > node.setWeight(sum/count);
>
> > > > }
>
> > > > - graph.proto -
>
> > > > package graph;
>
> > > > option java_package = "graph";
> > > > option java_outer_classname = "UndirectedGraphType";
> > > > option optimize_for = CODE_SIZE;
>
> > > > message UndirectedGraphNodeReference {
> > > > required string id = 1;
> > > > }
>
> > > > message UndirectedGraphNode {
> > > > required string id = 1;
> > > > required double weight = 2;
> > > > repeated UndirectedGraphNodeReference neighbors = 2;
> > > > }
>
> > > > message UndirectedGraph {
> > > > repeated UndirectedGraphNode nodes = 1;
> > > > }
>
> > > > On Oct 22, 2:36 pm, GDR <[EMAIL PROTECTED]> wrote:
> > > >> That does solve the duplicate information problem but it makes updates
> > > >> to node attributes (like weight) difficult. Let's say, I want to
> > > >> assign the weight of each node to the average of its neighbors.
>
> > > >> for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
> > > >> double sum = 0;
> > > >> int count = 0;
> > > >> for(UndirectedGraphNodeReference neighbor :
> > > >> node.getNeighborsList() ) {
> > > >> sum +=
> > > >> count++;
> > > >> }
> > > >> node.setWeight(sum/count);
>
> > > >> }
>
> > > >> - graph.proto -
>
> > > >> package graph;
>
> > > >> option java_package = "graph";
> > > >> option java_outer_classname = "UndirectedGraphType";
> > > >> option optimize_for = CODE_SIZE;
>
> > > >> message UndirectedGraphNodeReference {
> > > >> required string id = 1;
> > > >> required double weight = 2;
>
> > > >> }
>
> > > >> message UndirectedGraphNode {
> > > >> required string id = 1;
> > > >> repeated UndirectedGraphNodeReference neighbors = 2;
>
> > > >> }
>
> > > >> message UndirectedGraph {
> > > >> repeated UndirectedGraphNode nodes = 1;
>
> > > >> }
>
> > > >> On Oct 22, 2:14 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>
> > > >>> I was assuming all the properties of a node (weight, label, color,
> > > >>> whatever) would be in UndirectedGraphNode;
> > > >>> UndirectedGraphNodeReference
> > > >>> would only have the id and nothing else.
> > > >>> --
> > > >>> Jeremy Leader
> > > >>> [EMAIL PROTECTED]
> > > >>> GDR wrote:
> > > Thanks Jeremy. That worked!
> > > But we now have information about the same node being replicated. For
> > > instance, let's say we have a field 'weight' attached to each node as
> > > shown below. This setup will replicate the weight information of a
> > > node as many times as its degree. If the weight of a node changes, I
> > > will have update all it's occurrences in the PB. Any way I can avoid
>
Re: Data structures using protocol buffers
Sounds like fun. Just curious what is actually supposed to be encoded
in the protobuf message, if the graph is too big to fit in memory?
Are you sending just a single node, with its edges? It seems like you
wouldn't be able to avoid scenarios where some of the edges in your
message point to nodes that are not also serialized in your message,
given that you can't actually store the entire graph in memory, let
alone a protobuf message? What graph operations are you looking to
parallelize?
-dave
On Oct 23, 12:12 am, GDR <[EMAIL PROTECTED]> wrote:
> Thanks. I am trying to use protocol buffers with a map reduce
> framework to work on large graphs. The graphs are too big to fit in
> memory so building auxiliary data structures is difficult. Any ideas?
>
> On Oct 22, 2:48 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>
> > Protocol Buffers are a serialization format, rather than general-purpose
> > data structures. To do computations, you'd probably want to build some
> > auxiliary data structures, which you populate when you deserialize the
> > protobuf data. You could have node objects that resemble your original
> > .proto file, where nodes have references to their neighbors, and you'd
> > probably need a map from node id to node object reference, which you'd
> > use during deserialization.
>
> > --
> > Jeremy Leader
> > [EMAIL PROTECTED]
>
> > GDR wrote:
> > > my bad. The code snippet should be as follows:
>
> > > for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
> > > double sum = 0;
> > > int count = 0;
> > > for(UndirectedGraphNodeReference neighbor :
> > > node.getNeighborsList() ) {
> > > sum +=
> > > count++;
> > > }
> > > node.setWeight(sum/count);
>
> > > }
>
> > > - graph.proto -
>
> > > package graph;
>
> > > option java_package = "graph";
> > > option java_outer_classname = "UndirectedGraphType";
> > > option optimize_for = CODE_SIZE;
>
> > > message UndirectedGraphNodeReference {
> > > required string id = 1;
> > > }
>
> > > message UndirectedGraphNode {
> > > required string id = 1;
> > > required double weight = 2;
> > > repeated UndirectedGraphNodeReference neighbors = 2;
> > > }
>
> > > message UndirectedGraph {
> > > repeated UndirectedGraphNode nodes = 1;
> > > }
>
> > > On Oct 22, 2:36 pm, GDR <[EMAIL PROTECTED]> wrote:
> > >> That does solve the duplicate information problem but it makes updates
> > >> to node attributes (like weight) difficult. Let's say, I want to
> > >> assign the weight of each node to the average of its neighbors.
>
> > >> for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
> > >> double sum = 0;
> > >> int count = 0;
> > >> for(UndirectedGraphNodeReference neighbor :
> > >> node.getNeighborsList() ) {
> > >> sum +=
> > >> count++;
> > >> }
> > >> node.setWeight(sum/count);
>
> > >> }
>
> > >> - graph.proto -
>
> > >> package graph;
>
> > >> option java_package = "graph";
> > >> option java_outer_classname = "UndirectedGraphType";
> > >> option optimize_for = CODE_SIZE;
>
> > >> message UndirectedGraphNodeReference {
> > >> required string id = 1;
> > >> required double weight = 2;
>
> > >> }
>
> > >> message UndirectedGraphNode {
> > >> required string id = 1;
> > >> repeated UndirectedGraphNodeReference neighbors = 2;
>
> > >> }
>
> > >> message UndirectedGraph {
> > >> repeated UndirectedGraphNode nodes = 1;
>
> > >> }
>
> > >> On Oct 22, 2:14 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>
> > >>> I was assuming all the properties of a node (weight, label, color,
> > >>> whatever) would be in UndirectedGraphNode; UndirectedGraphNodeReference
> > >>> would only have the id and nothing else.
> > >>> --
> > >>> Jeremy Leader
> > >>> [EMAIL PROTECTED]
> > >>> GDR wrote:
> > Thanks Jeremy. That worked!
> > But we now have information about the same node being replicated. For
> > instance, let's say we have a field 'weight' attached to each node as
> > shown below. This setup will replicate the weight information of a
> > node as many times as its degree. If the weight of a node changes, I
> > will have update all it's occurrences in the PB. Any way I can avoid
> > it?
> > package graph;
> > option java_package = "graph";
> > option java_outer_classname = "UndirectedGraphType";
> > option optimize_for = CODE_SIZE;
> > message UndirectedGraphNodeReference {
> > required string id = 1;
> > required double weight = 2;
> > }
> > message UndirectedGraphNode {
> > required string id = 1;
> > repeated UndirectedGraphNodeReference neighbors = 2;
> > }
> > message UndirectedGraph {
> > repeated UndirectedGraphNode nodes = 1;
> > }
> > On Oct 21, 6:37 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> > > Keep in mind that protobufs describe serialized data, and there's no
> > > concept of an object reference
Re: Data structures using protocol buffers
Thanks. I am trying to use protocol buffers with a map reduce
framework to work on large graphs. The graphs are too big to fit in
memory so building auxiliary data structures is difficult. Any ideas?
On Oct 22, 2:48 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> Protocol Buffers are a serialization format, rather than general-purpose
> data structures. To do computations, you'd probably want to build some
> auxiliary data structures, which you populate when you deserialize the
> protobuf data. You could have node objects that resemble your original
> .proto file, where nodes have references to their neighbors, and you'd
> probably need a map from node id to node object reference, which you'd
> use during deserialization.
>
> --
> Jeremy Leader
> [EMAIL PROTECTED]
>
> GDR wrote:
> > my bad. The code snippet should be as follows:
>
> > for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
> > double sum = 0;
> > int count = 0;
> > for(UndirectedGraphNodeReference neighbor :
> > node.getNeighborsList() ) {
> > sum +=
> > count++;
> > }
> > node.setWeight(sum/count);
>
> > }
>
> > - graph.proto -
>
> > package graph;
>
> > option java_package = "graph";
> > option java_outer_classname = "UndirectedGraphType";
> > option optimize_for = CODE_SIZE;
>
> > message UndirectedGraphNodeReference {
> > required string id = 1;
> > }
>
> > message UndirectedGraphNode {
> > required string id = 1;
> > required double weight = 2;
> > repeated UndirectedGraphNodeReference neighbors = 2;
> > }
>
> > message UndirectedGraph {
> > repeated UndirectedGraphNode nodes = 1;
> > }
>
> > On Oct 22, 2:36 pm, GDR <[EMAIL PROTECTED]> wrote:
> >> That does solve the duplicate information problem but it makes updates
> >> to node attributes (like weight) difficult. Let's say, I want to
> >> assign the weight of each node to the average of its neighbors.
>
> >> for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
> >> double sum = 0;
> >> int count = 0;
> >> for(UndirectedGraphNodeReference neighbor :
> >> node.getNeighborsList() ) {
> >> sum +=
> >> count++;
> >> }
> >> node.setWeight(sum/count);
>
> >> }
>
> >> - graph.proto -
>
> >> package graph;
>
> >> option java_package = "graph";
> >> option java_outer_classname = "UndirectedGraphType";
> >> option optimize_for = CODE_SIZE;
>
> >> message UndirectedGraphNodeReference {
> >> required string id = 1;
> >> required double weight = 2;
>
> >> }
>
> >> message UndirectedGraphNode {
> >> required string id = 1;
> >> repeated UndirectedGraphNodeReference neighbors = 2;
>
> >> }
>
> >> message UndirectedGraph {
> >> repeated UndirectedGraphNode nodes = 1;
>
> >> }
>
> >> On Oct 22, 2:14 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>
> >>> I was assuming all the properties of a node (weight, label, color,
> >>> whatever) would be in UndirectedGraphNode; UndirectedGraphNodeReference
> >>> would only have the id and nothing else.
> >>> --
> >>> Jeremy Leader
> >>> [EMAIL PROTECTED]
> >>> GDR wrote:
> Thanks Jeremy. That worked!
> But we now have information about the same node being replicated. For
> instance, let's say we have a field 'weight' attached to each node as
> shown below. This setup will replicate the weight information of a
> node as many times as its degree. If the weight of a node changes, I
> will have update all it's occurrences in the PB. Any way I can avoid
> it?
> package graph;
> option java_package = "graph";
> option java_outer_classname = "UndirectedGraphType";
> option optimize_for = CODE_SIZE;
> message UndirectedGraphNodeReference {
> required string id = 1;
> required double weight = 2;
> }
> message UndirectedGraphNode {
> required string id = 1;
> repeated UndirectedGraphNodeReference neighbors = 2;
> }
> message UndirectedGraph {
> repeated UndirectedGraphNode nodes = 1;
> }
> On Oct 21, 6:37 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> > Keep in mind that protobufs describe serialized data, and there's no
> > concept of an object reference like Java uses. In your example, if A
> > and B are neighbors, then in your proto, the data representing A
> > contains the data representing B, and the data representing B contains
> > the data representing A!
> > One way around this is to implement your own form of references, perhaps
> > using the node ids like this:
> > package graph;
> > option java_package = "graph";
> > option java_outer_classname = "UndirectedGraph";
> > option optimize_for = CODE_SIZE;
> > message UndirectedGraphNodeReference {
> > required string id = 0;
> > }
> > message UndirectedGraphNode {
> > required string id = 0;
> > repeated UndirectedGraphNodeReference neighbors;
> > }
> > message UndirectedGra
Re: Data structures using protocol buffers
Protocol Buffers are a serialization format, rather than general-purpose
data structures. To do computations, you'd probably want to build some
auxiliary data structures, which you populate when you deserialize the
protobuf data. You could have node objects that resemble your original
.proto file, where nodes have references to their neighbors, and you'd
probably need a map from node id to node object reference, which you'd
use during deserialization.
--
Jeremy Leader
[EMAIL PROTECTED]
GDR wrote:
> my bad. The code snippet should be as follows:
>
> for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
>double sum = 0;
>int count = 0;
>for(UndirectedGraphNodeReference neighbor :
> node.getNeighborsList() ) {
> sum +=
> count++;
>}
>node.setWeight(sum/count);
>
> }
>
> - graph.proto -
>
> package graph;
>
> option java_package = "graph";
> option java_outer_classname = "UndirectedGraphType";
> option optimize_for = CODE_SIZE;
>
> message UndirectedGraphNodeReference {
>required string id = 1;
> }
>
> message UndirectedGraphNode {
>required string id = 1;
>required double weight = 2;
>repeated UndirectedGraphNodeReference neighbors = 2;
> }
>
> message UndirectedGraph {
>repeated UndirectedGraphNode nodes = 1;
> }
>
> On Oct 22, 2:36 pm, GDR <[EMAIL PROTECTED]> wrote:
>> That does solve the duplicate information problem but it makes updates
>> to node attributes (like weight) difficult. Let's say, I want to
>> assign the weight of each node to the average of its neighbors.
>>
>> for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
>>double sum = 0;
>>int count = 0;
>>for(UndirectedGraphNodeReference neighbor :
>> node.getNeighborsList() ) {
>> sum +=
>> count++;
>>}
>>node.setWeight(sum/count);
>>
>> }
>>
>> - graph.proto -
>>
>> package graph;
>>
>> option java_package = "graph";
>> option java_outer_classname = "UndirectedGraphType";
>> option optimize_for = CODE_SIZE;
>>
>> message UndirectedGraphNodeReference {
>>required string id = 1;
>>required double weight = 2;
>>
>> }
>>
>> message UndirectedGraphNode {
>>required string id = 1;
>>repeated UndirectedGraphNodeReference neighbors = 2;
>>
>> }
>>
>> message UndirectedGraph {
>>repeated UndirectedGraphNode nodes = 1;
>>
>> }
>>
>> On Oct 22, 2:14 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>>
>>> I was assuming all the properties of a node (weight, label, color,
>>> whatever) would be in UndirectedGraphNode; UndirectedGraphNodeReference
>>> would only have the id and nothing else.
>>> --
>>> Jeremy Leader
>>> [EMAIL PROTECTED]
>>> GDR wrote:
Thanks Jeremy. That worked!
But we now have information about the same node being replicated. For
instance, let's say we have a field 'weight' attached to each node as
shown below. This setup will replicate the weight information of a
node as many times as its degree. If the weight of a node changes, I
will have update all it's occurrences in the PB. Any way I can avoid
it?
package graph;
option java_package = "graph";
option java_outer_classname = "UndirectedGraphType";
option optimize_for = CODE_SIZE;
message UndirectedGraphNodeReference {
required string id = 1;
required double weight = 2;
}
message UndirectedGraphNode {
required string id = 1;
repeated UndirectedGraphNodeReference neighbors = 2;
}
message UndirectedGraph {
repeated UndirectedGraphNode nodes = 1;
}
On Oct 21, 6:37 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> Keep in mind that protobufs describe serialized data, and there's no
> concept of an object reference like Java uses. In your example, if A
> and B are neighbors, then in your proto, the data representing A
> contains the data representing B, and the data representing B contains
> the data representing A!
> One way around this is to implement your own form of references, perhaps
> using the node ids like this:
> package graph;
> option java_package = "graph";
> option java_outer_classname = "UndirectedGraph";
> option optimize_for = CODE_SIZE;
> message UndirectedGraphNodeReference {
>required string id = 0;
> }
> message UndirectedGraphNode {
>required string id = 0;
>repeated UndirectedGraphNodeReference neighbors;
> }
> message UndirectedGraph {
>repeated UndirectedGraphNode nodes;
> }
> --
> Jeremy Leader
> [EMAIL PROTECTED]
> GDR wrote:
>> Hi,
>> I'm wondering how would one go about implementing self-referential
>> data structures? As an exercise, I tried to implement a PB version of
>> the adjacency list representation of a graph. I'm having a hard time
>> getting it work. Any suggestions?
>> Thanks!
>> --- graph.proto ---
>> package graph;
Re: Data structures using protocol buffers
my bad. The code snippet should be as follows:
for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
double sum = 0;
int count = 0;
for(UndirectedGraphNodeReference neighbor :
node.getNeighborsList() ) {
sum +=
count++;
}
node.setWeight(sum/count);
}
- graph.proto -
package graph;
option java_package = "graph";
option java_outer_classname = "UndirectedGraphType";
option optimize_for = CODE_SIZE;
message UndirectedGraphNodeReference {
required string id = 1;
}
message UndirectedGraphNode {
required string id = 1;
required double weight = 2;
repeated UndirectedGraphNodeReference neighbors = 2;
}
message UndirectedGraph {
repeated UndirectedGraphNode nodes = 1;
}
On Oct 22, 2:36 pm, GDR <[EMAIL PROTECTED]> wrote:
> That does solve the duplicate information problem but it makes updates
> to node attributes (like weight) difficult. Let's say, I want to
> assign the weight of each node to the average of its neighbors.
>
> for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
> double sum = 0;
> int count = 0;
> for(UndirectedGraphNodeReference neighbor :
> node.getNeighborsList() ) {
> sum +=
> count++;
> }
> node.setWeight(sum/count);
>
> }
>
> - graph.proto -
>
> package graph;
>
> option java_package = "graph";
> option java_outer_classname = "UndirectedGraphType";
> option optimize_for = CODE_SIZE;
>
> message UndirectedGraphNodeReference {
> required string id = 1;
> required double weight = 2;
>
> }
>
> message UndirectedGraphNode {
> required string id = 1;
> repeated UndirectedGraphNodeReference neighbors = 2;
>
> }
>
> message UndirectedGraph {
> repeated UndirectedGraphNode nodes = 1;
>
> }
>
> On Oct 22, 2:14 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>
> > I was assuming all the properties of a node (weight, label, color,
> > whatever) would be in UndirectedGraphNode; UndirectedGraphNodeReference
> > would only have the id and nothing else.
>
> > --
> > Jeremy Leader
> > [EMAIL PROTECTED]
>
> > GDR wrote:
> > > Thanks Jeremy. That worked!
> > > But we now have information about the same node being replicated. For
> > > instance, let's say we have a field 'weight' attached to each node as
> > > shown below. This setup will replicate the weight information of a
> > > node as many times as its degree. If the weight of a node changes, I
> > > will have update all it's occurrences in the PB. Any way I can avoid
> > > it?
>
> > > package graph;
>
> > > option java_package = "graph";
> > > option java_outer_classname = "UndirectedGraphType";
> > > option optimize_for = CODE_SIZE;
>
> > > message UndirectedGraphNodeReference {
> > > required string id = 1;
> > > required double weight = 2;
> > > }
>
> > > message UndirectedGraphNode {
> > > required string id = 1;
> > > repeated UndirectedGraphNodeReference neighbors = 2;
> > > }
>
> > > message UndirectedGraph {
> > > repeated UndirectedGraphNode nodes = 1;
> > > }
>
> > > On Oct 21, 6:37 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> > >> Keep in mind that protobufs describe serialized data, and there's no
> > >> concept of an object reference like Java uses. In your example, if A
> > >> and B are neighbors, then in your proto, the data representing A
> > >> contains the data representing B, and the data representing B contains
> > >> the data representing A!
>
> > >> One way around this is to implement your own form of references, perhaps
> > >> using the node ids like this:
>
> > >> package graph;
>
> > >> option java_package = "graph";
> > >> option java_outer_classname = "UndirectedGraph";
> > >> option optimize_for = CODE_SIZE;
>
> > >> message UndirectedGraphNodeReference {
> > >> required string id = 0;
>
> > >> }
>
> > >> message UndirectedGraphNode {
> > >> required string id = 0;
> > >> repeated UndirectedGraphNodeReference neighbors;
>
> > >> }
>
> > >> message UndirectedGraph {
> > >> repeated UndirectedGraphNode nodes;
>
> > >> }
>
> > >> --
> > >> Jeremy Leader
> > >> [EMAIL PROTECTED]
>
> > >> GDR wrote:
> > >>> Hi,
> > >>> I'm wondering how would one go about implementing self-referential
> > >>> data structures? As an exercise, I tried to implement a PB version of
> > >>> the adjacency list representation of a graph. I'm having a hard time
> > >>> getting it work. Any suggestions?
> > >>> Thanks!
> > >>> --- graph.proto ---
> > >>> package graph;
> > >>> option java_package = "graph";
> > >>> option java_outer_classname = "UndirectedGraph";
> > >>> option optimize_for = CODE_SIZE;
> > >>> message UndirectedGraphNode {
> > >>> required string id = 0;
> > >>> repeated UndirectedGraphNode neighbors;
> > >>> }
> > >>> message UndirectedGraph {
> > >>> repeated UndirectedGraphNode nodes;
> > >>> }
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Protocol Buffers" group.
To post to this group
Re: Data structures using protocol buffers
That does solve the duplicate information problem but it makes updates
to node attributes (like weight) difficult. Let's say, I want to
assign the weight of each node to the average of its neighbors.
for(UndirectedGraphNode node : UndirectedGraph.getNodesList() ) {
double sum = 0;
int count = 0;
for(UndirectedGraphNodeReference neighbor :
node.getNeighborsList() ) {
sum +=
count++;
}
node.setWeight(sum/count);
}
- graph.proto -
package graph;
option java_package = "graph";
option java_outer_classname = "UndirectedGraphType";
option optimize_for = CODE_SIZE;
message UndirectedGraphNodeReference {
required string id = 1;
required double weight = 2;
}
message UndirectedGraphNode {
required string id = 1;
repeated UndirectedGraphNodeReference neighbors = 2;
}
message UndirectedGraph {
repeated UndirectedGraphNode nodes = 1;
}
On Oct 22, 2:14 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> I was assuming all the properties of a node (weight, label, color,
> whatever) would be in UndirectedGraphNode; UndirectedGraphNodeReference
> would only have the id and nothing else.
>
> --
> Jeremy Leader
> [EMAIL PROTECTED]
>
> GDR wrote:
> > Thanks Jeremy. That worked!
> > But we now have information about the same node being replicated. For
> > instance, let's say we have a field 'weight' attached to each node as
> > shown below. This setup will replicate the weight information of a
> > node as many times as its degree. If the weight of a node changes, I
> > will have update all it's occurrences in the PB. Any way I can avoid
> > it?
>
> > package graph;
>
> > option java_package = "graph";
> > option java_outer_classname = "UndirectedGraphType";
> > option optimize_for = CODE_SIZE;
>
> > message UndirectedGraphNodeReference {
> > required string id = 1;
> > required double weight = 2;
> > }
>
> > message UndirectedGraphNode {
> > required string id = 1;
> > repeated UndirectedGraphNodeReference neighbors = 2;
> > }
>
> > message UndirectedGraph {
> > repeated UndirectedGraphNode nodes = 1;
> > }
>
> > On Oct 21, 6:37 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> >> Keep in mind that protobufs describe serialized data, and there's no
> >> concept of an object reference like Java uses. In your example, if A
> >> and B are neighbors, then in your proto, the data representing A
> >> contains the data representing B, and the data representing B contains
> >> the data representing A!
>
> >> One way around this is to implement your own form of references, perhaps
> >> using the node ids like this:
>
> >> package graph;
>
> >> option java_package = "graph";
> >> option java_outer_classname = "UndirectedGraph";
> >> option optimize_for = CODE_SIZE;
>
> >> message UndirectedGraphNodeReference {
> >> required string id = 0;
>
> >> }
>
> >> message UndirectedGraphNode {
> >> required string id = 0;
> >> repeated UndirectedGraphNodeReference neighbors;
>
> >> }
>
> >> message UndirectedGraph {
> >> repeated UndirectedGraphNode nodes;
>
> >> }
>
> >> --
> >> Jeremy Leader
> >> [EMAIL PROTECTED]
>
> >> GDR wrote:
> >>> Hi,
> >>> I'm wondering how would one go about implementing self-referential
> >>> data structures? As an exercise, I tried to implement a PB version of
> >>> the adjacency list representation of a graph. I'm having a hard time
> >>> getting it work. Any suggestions?
> >>> Thanks!
> >>> --- graph.proto ---
> >>> package graph;
> >>> option java_package = "graph";
> >>> option java_outer_classname = "UndirectedGraph";
> >>> option optimize_for = CODE_SIZE;
> >>> message UndirectedGraphNode {
> >>> required string id = 0;
> >>> repeated UndirectedGraphNode neighbors;
> >>> }
> >>> message UndirectedGraph {
> >>> repeated UndirectedGraphNode nodes;
> >>> }
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Protocol Buffers" group.
To post to this group, send email to protobuf@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/protobuf?hl=en
-~--~~~~--~~--~--~---
Re: Data structures using protocol buffers
I was assuming all the properties of a node (weight, label, color,
whatever) would be in UndirectedGraphNode; UndirectedGraphNodeReference
would only have the id and nothing else.
--
Jeremy Leader
[EMAIL PROTECTED]
GDR wrote:
> Thanks Jeremy. That worked!
> But we now have information about the same node being replicated. For
> instance, let's say we have a field 'weight' attached to each node as
> shown below. This setup will replicate the weight information of a
> node as many times as its degree. If the weight of a node changes, I
> will have update all it's occurrences in the PB. Any way I can avoid
> it?
>
> package graph;
>
> option java_package = "graph";
> option java_outer_classname = "UndirectedGraphType";
> option optimize_for = CODE_SIZE;
>
> message UndirectedGraphNodeReference {
>required string id = 1;
>required double weight = 2;
> }
>
> message UndirectedGraphNode {
>required string id = 1;
>repeated UndirectedGraphNodeReference neighbors = 2;
> }
>
> message UndirectedGraph {
>repeated UndirectedGraphNode nodes = 1;
> }
>
> On Oct 21, 6:37 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
>> Keep in mind that protobufs describe serialized data, and there's no
>> concept of an object reference like Java uses. In your example, if A
>> and B are neighbors, then in your proto, the data representing A
>> contains the data representing B, and the data representing B contains
>> the data representing A!
>>
>> One way around this is to implement your own form of references, perhaps
>> using the node ids like this:
>>
>> package graph;
>>
>> option java_package = "graph";
>> option java_outer_classname = "UndirectedGraph";
>> option optimize_for = CODE_SIZE;
>>
>> message UndirectedGraphNodeReference {
>>required string id = 0;
>>
>> }
>>
>> message UndirectedGraphNode {
>>required string id = 0;
>>repeated UndirectedGraphNodeReference neighbors;
>>
>> }
>>
>> message UndirectedGraph {
>>repeated UndirectedGraphNode nodes;
>>
>> }
>>
>> --
>> Jeremy Leader
>> [EMAIL PROTECTED]
>>
>> GDR wrote:
>>> Hi,
>>> I'm wondering how would one go about implementing self-referential
>>> data structures? As an exercise, I tried to implement a PB version of
>>> the adjacency list representation of a graph. I'm having a hard time
>>> getting it work. Any suggestions?
>>> Thanks!
>>> --- graph.proto ---
>>> package graph;
>>> option java_package = "graph";
>>> option java_outer_classname = "UndirectedGraph";
>>> option optimize_for = CODE_SIZE;
>>> message UndirectedGraphNode {
>>> required string id = 0;
>>> repeated UndirectedGraphNode neighbors;
>>> }
>>> message UndirectedGraph {
>>> repeated UndirectedGraphNode nodes;
>>> }
>
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Protocol Buffers" group.
To post to this group, send email to protobuf@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/protobuf?hl=en
-~--~~~~--~~--~--~---
Re: Data structures using protocol buffers
Thanks Jeremy. That worked!
But we now have information about the same node being replicated. For
instance, let's say we have a field 'weight' attached to each node as
shown below. This setup will replicate the weight information of a
node as many times as its degree. If the weight of a node changes, I
will have update all it's occurrences in the PB. Any way I can avoid
it?
package graph;
option java_package = "graph";
option java_outer_classname = "UndirectedGraphType";
option optimize_for = CODE_SIZE;
message UndirectedGraphNodeReference {
required string id = 1;
required double weight = 2;
}
message UndirectedGraphNode {
required string id = 1;
repeated UndirectedGraphNodeReference neighbors = 2;
}
message UndirectedGraph {
repeated UndirectedGraphNode nodes = 1;
}
On Oct 21, 6:37 pm, Jeremy Leader <[EMAIL PROTECTED]> wrote:
> Keep in mind that protobufs describe serialized data, and there's no
> concept of an object reference like Java uses. In your example, if A
> and B are neighbors, then in your proto, the data representing A
> contains the data representing B, and the data representing B contains
> the data representing A!
>
> One way around this is to implement your own form of references, perhaps
> using the node ids like this:
>
> package graph;
>
> option java_package = "graph";
> option java_outer_classname = "UndirectedGraph";
> option optimize_for = CODE_SIZE;
>
> message UndirectedGraphNodeReference {
> required string id = 0;
>
> }
>
> message UndirectedGraphNode {
> required string id = 0;
> repeated UndirectedGraphNodeReference neighbors;
>
> }
>
> message UndirectedGraph {
> repeated UndirectedGraphNode nodes;
>
> }
>
> --
> Jeremy Leader
> [EMAIL PROTECTED]
>
> GDR wrote:
> > Hi,
>
> > I'm wondering how would one go about implementing self-referential
> > data structures? As an exercise, I tried to implement a PB version of
> > the adjacency list representation of a graph. I'm having a hard time
> > getting it work. Any suggestions?
>
> > Thanks!
>
> > --- graph.proto ---
>
> > package graph;
>
> > option java_package = "graph";
> > option java_outer_classname = "UndirectedGraph";
> > option optimize_for = CODE_SIZE;
>
> > message UndirectedGraphNode {
> > required string id = 0;
> > repeated UndirectedGraphNode neighbors;
> > }
>
> > message UndirectedGraph {
> > repeated UndirectedGraphNode nodes;
> > }
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Protocol Buffers" group.
To post to this group, send email to protobuf@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/protobuf?hl=en
-~--~~~~--~~--~--~---
Re: Data structures using protocol buffers
Keep in mind that protobufs describe serialized data, and there's no
concept of an object reference like Java uses. In your example, if A
and B are neighbors, then in your proto, the data representing A
contains the data representing B, and the data representing B contains
the data representing A!
One way around this is to implement your own form of references, perhaps
using the node ids like this:
package graph;
option java_package = "graph";
option java_outer_classname = "UndirectedGraph";
option optimize_for = CODE_SIZE;
message UndirectedGraphNodeReference {
required string id = 0;
}
message UndirectedGraphNode {
required string id = 0;
repeated UndirectedGraphNodeReference neighbors;
}
message UndirectedGraph {
repeated UndirectedGraphNode nodes;
}
--
Jeremy Leader
[EMAIL PROTECTED]
GDR wrote:
> Hi,
>
> I'm wondering how would one go about implementing self-referential
> data structures? As an exercise, I tried to implement a PB version of
> the adjacency list representation of a graph. I'm having a hard time
> getting it work. Any suggestions?
>
> Thanks!
>
> --- graph.proto ---
>
> package graph;
>
> option java_package = "graph";
> option java_outer_classname = "UndirectedGraph";
> option optimize_for = CODE_SIZE;
>
> message UndirectedGraphNode {
> required string id = 0;
> repeated UndirectedGraphNode neighbors;
> }
>
> message UndirectedGraph {
> repeated UndirectedGraphNode nodes;
> }
>
>
--~--~-~--~~~---~--~~
You received this message because you are subscribed to the Google Groups
"Protocol Buffers" group.
To post to this group, send email to protobuf@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/protobuf?hl=en
-~--~~~~--~~--~--~---
